LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@tnakagawa

EMV®チップ、楕円曲線暗号をサポートするってよ

Posted at

はじめに（Introduction）

この記事は下記URLで発表されたドキュメントの内容を一部抜粋したものです。
https://www.emvco.com/emv-technologies/contact/

EMV®チップってのは、クレジットカードについているICチップの事です。
↓↓↓↓↓の黄色い部分
creditcard_nonumber_black.png

EMVCoというEMVの仕様を管理している団体？からEMV®チップに楕円曲線暗号をサポートするというドキュメントが発表されました。
以下の３つのドキュメントの内容からなぜ楕円曲線が選ばれたのかという理由を見ていきたいと思います。

EMV®チップの仕様に楕円曲線暗号を採用

「EMV® Chip Specifications To Support Elliptic Curve Cryptography」より抜粋します。

In an EMV contact chip payment, the merchant point-of-sale terminal can cryptographically authenticate a card and its data. For this purpose, EMVCo has based its EMV Contact Chip Specifications on RSA (Rivest-Shamir-Adleman) public key cryptography since its inception and intends to continue to support this standard. The addition of ECC into EMV Specifications helps achieve superior cryptographic strength with much smaller key sizes, enabling more efficient transactions in the future.
EMVコンタクトチップによる決済では、加盟店のPOS端末は、カードとそのデータを暗号で認証することができます。この目的のために、EMVCoはEMVコンタクトチップ仕様の策定時からRSA（Rivest-Shamir-Adleman）公開鍵暗号方式を採用しており、今後もこの規格をサポートしていく予定です。今回、EMV仕様にECCを追加することで、より小さな鍵サイズで優れた暗号強度を実現し、将来的にはより効率的な取引を可能にします。

理由としては、**小さな鍵サイズで優れた暗号強度を実現**したい為のようです。

FAQ: EMV®コンタクトチップ仕様 楕円曲線暗号技術に関する一般的な質問

詳しくは、「FAQ: EMV® Contact Chip Specification Elliptic Curve Cryptography – General Questions」を参照との事なのでもう少し詳しく見てみます。

2. What is ECC and why is EMVCo incorporating it into its specifications?
＜中略＞
EMVCo recognises that RSA could continue to be used with longer and therefore ‘stronger’ keys over time; however, the increase in key length increases computing time making transaction times slower. In contrast, ECC is compact and efficient, which makes it an appealing option for use in devices with limited storage and processing capabilities, and where transaction speed is important.
2. ECCとは何か、なぜEMVCoはECCを仕様に組み込むのか？
＜中略＞
EMVCoは、RSAが時間の経過とともにより長い、つまり「より強力な」鍵で使用され続ける可能性があることを認識しています。しかし、鍵の長さが長くなると、計算時間が長くなり、取引時間が遅くなります。対照的に、ECCはコンパクトで効率的であるため、ストレージや処理能力が限られている機器や、取引速度が重要である場合には魅力的な選択肢となります。

ECCはコンパクトで効率的 **取引速度が重要である場合には魅力的な選択肢**という２つの理由がありそうです。

SB nº 243: EMV仕様のためのXDA/ODEの導入

仕様である、「SB nº 243: Introduction of XDA/ODE for EMV Specifications」も見てみます。
楕円曲線暗号はP-256とP-512が採用されていました。
これは、NIST文章の「FIPS 186-4 Digital Signature Standard (DSS)」にも記載されています。
P-256はsecp256r1とも呼ばれます。

セキュリティ強度と鍵サイズ

NIST文章の「SP 800-57 Part 1 Rev.5」から以下の表を抜粋します。

セキュリティ強度 対称鍵
アルゴリズム		 FFC
(DSA, DH, MQV)		 IFC*
(RSA)		 ECC*
(ECDSA, EdDSA,
DH, MQV)
≤ 80 2TDEA L = 1024
N = 160		 k = 1024 f = 160-223
112 3TDEA L = 2048
N = 224		 k = 2048 f = 224-255
128 AES-128 L = 3072
N = 256		 k = 3072 f = 256-383
192 AES-192 L = 7680
N = 384		 k = 7680 f = 384-511
256 AES-256 L = 15360
N = 512		 k = 15360 f = 512+
* 量子コンピューティングが実用化された場合、セキュリティ強度の評価値は大きく影響を受ける。

セキュリティ強度が同じ部分を比較します。
セキュリティ強度128あたりで、RSAの鍵サイズは3072ビット、ECCの鍵サイズは256～383ビット程度であることがわかります。
また、セキュリティ強度256あたりで、RSAの鍵サイズは15360ビット、ECCの鍵サイズは512ビット程度であることがわかります。
約10倍～15倍程度の差があることがわかります。

計算速度

実際にJavaの標準ライブラリを利用して計測してみます。
RSAは3072ビット、ECDSAはP-256を利用します。
ランダムなデータ10,000に対し、署名（Sign）⇒検証（Verify）の順に処理を行い時間を計測してみます。

ソースコード
package sample;

import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.SecureRandom;
import java.security.Signature;
import java.security.spec.ECGenParameterSpec;
import java.util.ArrayList;
import java.util.List;

public class SampleSign {

  public static void main(String[] args) {
    init();
    long t0 = System.currentTimeMillis();
    PublicKey ecPub = signEC();
    long t1 = System.currentTimeMillis();
    verifyEC(ecPub);
    long t2 = System.currentTimeMillis();
    PublicKey rsaPub = RSA();
    long t3 = System.currentTimeMillis();
    verifyRSA(rsaPub);
    long t4 = System.currentTimeMillis();
    System.out.println(String.format("EC  Sign   : %8d ms", t1 - t0));
    System.out.println(String.format("EC  Verify : %8d ms", t2 - t1));
    System.out.println(String.format("EC  Total  : %8d ms", t2 - t0));
    System.out.println(String.format("RSA Sign   : %8d ms", t3 - t2));
    System.out.println(String.format("RSA Verify : %8d ms", t4 - t3));
    System.out.println(String.format("RSA Total  : %8d ms", t4 - t2));
    float r0 = (float) (t3 - t2) / (float) (t1 - t0);
    float r1 = (float) (t4 - t3) / (float) (t2 - t1);
    float r2 = (float) (t4 - t2) / (float) (t2 - t0);
    System.out.println(String.format("Sign   RSA/EC : %10f,  EC/RSA : %10f", r0, 1 / r0));
    System.out.println(String.format("Verify RSA/EC : %10f,  EC/RSA : %10f", r1, 1 / r1));
    System.out.println(String.format("Total  RSA/EC : %10f,  EC/RSA : %10f", r2, 1 / r2));
  }

  private static final int COUNT = 10000;

  private static List<byte[]> data = new ArrayList<byte[]>();

  private static List<byte[]> ecSigs = new ArrayList<byte[]>();

  private static List<byte[]> rsaSigs = new ArrayList<byte[]>();

  private static void init() {
    data.clear();
    SecureRandom random = new SecureRandom();
    for (int i = 0; i < COUNT; i++) {
      byte[] bs = new byte[32];
      random.nextBytes(bs);
      data.add(bs);
    }
  }

  private static PublicKey signEC() {
    PublicKey pub = null;
    try {
      ecSigs.clear();
      KeyPairGenerator generator = KeyPairGenerator.getInstance("EC");
      generator.initialize(new ECGenParameterSpec("secp256r1"), new SecureRandom());
      KeyPair pair = generator.generateKeyPair();
      PrivateKey pri = pair.getPrivate();
      pub = pair.getPublic();
      System.out.println(pub.toString());

      Signature ecdsa = Signature.getInstance("SHA256withECDSA");
      for (int i = 0; i < data.size(); i++) {
        byte[] bs = data.get(i);
        ecdsa.initSign(pri);
        ecdsa.update(bs);
        byte[] sig = ecdsa.sign();
        ecSigs.add(sig);
      }
    } catch (Exception e) {
      e.printStackTrace();
    }
    return pub;
  }

  private static void verifyEC(PublicKey pub) {
    try {
      Signature ecdsa = Signature.getInstance("SHA256withECDSA");
      for (int i = 0; i < data.size(); i++) {
        byte[] bs = data.get(i);
        ecdsa.initVerify(pub);
        ecdsa.update(bs);
        byte[] sig = ecSigs.get(i);
        boolean ret = ecdsa.verify(sig);
        if (!ret) {
          throw new Exception("Fail verify!");
        }
      }
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  private static PublicKey RSA() {
    PublicKey pub = null;
    try {
      rsaSigs.clear();
      KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA");
      generator.initialize(3072);

      KeyPair pair = generator.generateKeyPair();
      PrivateKey pri = pair.getPrivate();
      pub = pair.getPublic();
      System.out.println(pub.toString());

      Signature rsa = Signature.getInstance("SHA256withRSA");
      for (int i = 0; i < data.size(); i++) {
        byte[] bs = data.get(i);
        rsa.initSign(pri);
        rsa.update(bs);
        byte[] sig = rsa.sign();
        rsaSigs.add(sig);
      }
    } catch (Exception e) {
      e.printStackTrace();
    }
    return pub;
  }

  private static void verifyRSA(PublicKey pub) {
    try {
      Signature rsa = Signature.getInstance("SHA256withRSA");
      for (int i = 0; i < data.size(); i++) {
        byte[] bs = data.get(i);
        rsa.initVerify(pub);
        rsa.update(bs);
        byte[] sig = rsaSigs.get(i);
        boolean ret = rsa.verify(sig);
        if (!ret) {
          throw new Exception("Fail verify!");
        }
      }
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

}

以下が結果となります。

Sun EC public key, 256 bits
  public x coord: 66752532227157286693786882731141038087059042588900596468118306910368813461224
  public y coord: 90035358848596344539113708118509218591691557153703761207978026402835267755999
  parameters: secp256r1 [NIST P-256, X9.62 prime256v1] (1.2.840.10045.3.1.7)
Sun RSA public key, 3072 bits
  params: null
  modulus: 3140780148557968801630685470001818419517187149928419452928294725787352246389314736411751263272593210474608348265145551931949906383943172558611826922686768055661561793509426777565264519700692657284666422365784624603234230140775377367564234867330810159822873911336475080564238056420696889156160400525075053597725260639768119892205271453416088744362133170823536810369227910860934957784873042608775975912854595845397590585803818406965015667936701390081601441154835233410690346939909818421769045350247209987778573815782529557616313474559339849516920984285182614199766362551379821079506019938200160110858605356075062950444624390119338911476417548364991682545889779158100557438049081798167636508771515760008076247193229699183002840333201003215468784247819142750491365236181003785328452450642739020875303386547307965491961957969659701639195303408943033262311369683702137199288087089496100183083298163751998782419423454959034316499389
  public exponent: 65537
EC  Sign   :     5826 ms
EC  Verify :    26730 ms
EC  Total  :    32556 ms
RSA Sign   :    77828 ms
RSA Verify :     1462 ms
RSA Total  :    79290 ms
Sign   RSA/EC :  13.358737,  EC/RSA :   0.074857
Verify RSA/EC :   0.054695,  EC/RSA :  18.283175
Total  RSA/EC :   2.435496,  EC/RSA :   0.410594

署名（Sign）に関しては、ECの方がRSAよりも約13倍速い事がわかります。
一方、検証（Verify）に関しては、RSAの方がECよりも約18倍速い事がわかります。
ただし、そもそもの計算時間は署名（Sign）＞検証（Verify）である為
トータルで判断すると、ECの方がRSAよりも約2倍速い事がわかります。

ランダムなデータなので毎回異なる値が出ます。

まとめ（Conclustion）

楕円曲線（EC）を利用することで、鍵サイズがコンパクトになります。
処理時間に関しては、署名（Sign）は楕円曲線の方が速いですが、検証（Verify）はRSAの方が速いという結果になりました。
実際には、署名（Sign）と検証（Verify）がセットとなるので楕円曲線の方が有利なように思えます。

EMV®チップからは鍵サイズがコンパクトになる事の方が重要だと思います。
ただ、署名（Sign）と検証（Verify）のどちらをメインの処理としているかによって選択する必要があると思いました。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?