基本は喰ってるか飲んでるかですが、よく趣味でカラオケ・PKI・署名・認証・プログラミング・情報セキュリティをやっています。旅好き。テレビ好きで芸能通
一昨日、Bitcoinの技術解説のスライドをslideshare.netに公開したんですが、
難解な資料にもかかわらず、あまりの反響の多さに少し驚いています。
二日ぐらいで17800を超えるslideshareへのアクセスを頂き、「it is one of the most popular this week on SlideShare」に選んで頂いたり、
たくさんTwitterでつぶやいて頂いたり、Facebookでいいねを頂いたり、
はてなブックマークでもたくさんブックマークやコメントを頂いたり
感謝至極でございます。この場を借りて御礼申し上げます。ありがとうございました。
やっぱり、楕円曲線暗号(Elliptic Curve Cryptography)はRSA暗号に比べて格段になんだかんだ難しいと思うですよ。 自分も勉強中なんですが、なかなか良い説明がなくて悶々としております。 jsrsasignの実装やビットコインを知る必要がある手前仕方なく。そんな状況の中、いろいろ見た中で、 結構オススメなリンクを4つ紹介したいと思います。
| CloudFlare: A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography | |
|---|---|
| http://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography | |
| 長所 | 点の足し算の説明が絵的でわかりやすく最初の導入として良いのでは |
| 短所 | 単に入り口に入ったところ、点の足し算程度で終わってしまう。 |
| Zero to ECC in 30 Minutes (Entrust Inc.) | |
| http://www.entrust.com/wp-content/uploads/2014/03/WP_Entrust_Zero-to-ECC_March2014.pdf | |
| 長所 | 楕円曲線暗号について中学の数学程度でわかるように解説している。絵も多用してわかりやすい。楕円曲線公開鍵暗号はよくわかる。 |
| 短所 | 署名(ECDSA)まで辿り着かない。 |
| Elliptic Curve Cryptography Tutorial | |
| http://www.johannes-bauer.com/compsci/ecc/ | |
| 長所 | 工学系の人に向けてわかりやすく書いてある。ECDSA署名もある。プログラム例もある。結構オススメ。 |
| 短所 | 逆に数学をやった人には物足りない？ |
| 楕円曲線暗号入門「計算機緒論２」配布資料 伊豆哲也さん | |
| http://researchmap.jp/mulzrkzae-42427/#_42427 | |
| 長所 | 何より日本語でわかりやすい。でも大学数学の基礎素養がないと読み辛い。ECDSA解説もある。 |
| 短所 | 使われている記号が一般的なのとちょっと違うようで少し混乱する。 |
前回の記事では、署名生成と署名検証とか、RSAとECDSAとかどっちが速いのかOpenSSLやJava JCEを使って速度の比較をしました。一度作った署名を何回か検証に使うというケースもあるので、検証にかかる時間はとても重要だと思います。今日は、前回の比較をさらに掘り下げてみたいと思います。
・署名検証の速度は(今我々が普通に使う鍵長では)RSAの方が断然速い
・しかしながらECCは鍵長が長くても遅くならないという特徴があるのでいつか逆転するはず
鍵長が長いとRSA不利、ECDSA有利になってくるのでいつか速度の逆転が起きるのだろうと思います。では、それが鍵長としていつなのかを調べたいと思います。
NISTの暗号強度の比較表を再度引用します。
| 共通鍵暗号 相当 | RSA | ECDSA |
|---|---|---|
| 80 | 1024 | 160-223 |
| 112 | 2048 | 224-255 |
| 128 | 3072 | 256-383 |
| 192 | 7680 | 384-511 |
| 256 | 15360 | 512- |
上記のグラフが指数関数的なので今度は秒間署名回数の対数を取ってプロットしてみましょう。
グラフから、暗号強度に対してはほぼリニアに秒間署名速度の対数が推移し、
共通鍵暗号相当の暗号強度の軸であるx座標が212.5423729(bit)の時に、
RSAとECCの署名検証の速度が逆転しています。
それでは、共通鍵暗号の強度で213bitということはRSAやECCではどの程度の鍵長に
相当するのでしょうか。
共通鍵暗号暗号強度と同等のECC、RSAの鍵長は最初のNISTの表から
これも指数関数的なのでRSAの鍵長と、ECCの鍵長の対数を使ってプロットしてみます。
すると、ご覧のように取った対数に対してほぼリニアに推移することがわかります。
共通鍵暗号の暗号強度で213bitとする点はRSAだとy軸が3.965、ECCだと2.612となり、
これらは指数に戻して
RSAとECDSAと同じ暗号強度で署名検証速度が逆転するのはということのようです。この値に近づいてるようならECDSAへの移行を考えた方が よいということなんでしょうね。
・RSAだと9234bit のとき
・ECCだと409bitのとき
今晩はこの辺で
あ、そうそう。これ書いている途中でizuさんのとてもためになる関連記事を発見してしまいました。杜撰な研究者の日記「RSA暗号の強度 (2009.11.19)」。
2013年9月4日に開催されたOpenID Tech Night Vol.10 に参加してて、
大きなプロバイダではRSA署名の検証は結構大変です。 RSAは署名よりも検証の方が計算コストがかかるので...
みたいな話をされ、「んん？逆じゃないの。RSA署名の検証は署名生成よりも圧倒的に計算コスト低いよね。」とか 思ってたわけで「がが〜〜ん」と。 「まぁ、ちょっと調べてみるべぇ。」と手持ちのノートPCで調べてみました。
以下のことを検証してみたいと思います。
言語の偏りがあるのも良くないのでOpenSSLベースのものとJava JCEベースのものと調べます。 いちいちOpenSSLをCで書くのも面倒なので。Rubyを使いました。 処理時間の測定方法については、Ruby+OpenSSL、Java JCEで次のような観点で測定しています。
| 検証環境 | |
|---|---|
| マシン | Lenovo X201s |
| CPU | Intel Core i7 L620 2.00GHz |
| メモリ | 8GB |
| OS | Microsoft Windows 7 Professional 32bit SP1 |
| Java | |
| バージョン | Oracle Java 1.7.0 build 1.7.0-b147 |
| RSA署名JCEプロバイダ | SunRsaSign 1.7 Provider |
| ECDSA署名JCEプロバイダ | SunEC 1.7 Provider |
| Ruby (+ OpenSSL) | |
| バージョン | cygwin C Ruby 1.9.3p194 |
| OpenSSL | OpenSSL 1.0.1c |
Ruby + OpenSSLでRSAやECDSA署名するには、OpenSSLコマンドで普通に PKCS#5の秘密鍵と公開鍵を準備してこんな感じで署名生成、署名検証すればヨロシ。
# ECDSAの署名生成
prvKey = OpenSSL::PKey::EC.new(File.read(PKCS#5秘密鍵PEM))
hashed = OpenSSL::Digest::SHA1.digest(署名対象メッセージ)
sigVal = prvKey.dsa_sign_asn1(hashed)
# ECDSAの署名検証
pubKey = OpenSSL::PKey::EC.new(File.read(PKCS#5公開鍵PEM))
hashed = OpenSSL::Digest::SHA1.digest(data)
isValid = pubKey.dsa_verify_asn1(hashed, sigVal)
# RSAの署名生成
prvKey = OpenSSL::PKey::RSA.new(File.read(PKCS#5秘密鍵PEM))
sigVal = prvKey.sign("sha1", data)
# RSAの署名検証
pubKey = OpenSSL::PKey::RSA.new(File.read(PKCS#5公開鍵PEM))
isValid = pubKey.verify("sha1", sigVal, data)
ECDSAの時はハッシュを自分で計算するのと、
ECDSAの署名値をASN.1構造で表現することに気をつければ問題ないかと思います。
最近、キーストア使って楽してたので普通に鍵ファイルを読みたい場合には、 PKCS#8 DERじゃないといけないんだよなとか探してみると 自分の記事 「OpenSSLで鍵生成した秘密鍵をJavaで使う」が見つかって助かりました。 秘密鍵ファイルはPKCS#8にしといて、公開鍵もPKCS#8にしようとしたら 「読めな〜〜〜い！！」鍵はパラメータの数値(BigInteger)を指定するか 証明書じゃないといけないそうだ。仕方ないから無理やり自己署名証明書を作りました。
ECDSAの署名生成はこんな感じ。
KeySpec keySpec = new PKCS8EncodedKeySpec(PKCS#8秘密鍵DERのデータbyte配列);
KeyFactory kf = KeyFactory.getInstance("EC");
PrivateKey prvKey = kf.generatePrivate(keySpec);
Signature sig = Signature.getInstance("SHA1withECDSA");
sig.initSign(prvKey);
sig.update(署名対象データaaa);
sigVal = sig.sign();
RSAの署名生成はこんな感じ。
KeySpec keySpec = new PKCS8EncodedKeySpec(PKCS#8秘密鍵DERのデータbyte配列);
KeyFactory kf = KeyFactory.getInstance("RSA");
PrivateKey prvKey = kf.generatePrivate(keySpec);
Signature sig = Signature.getInstance("SHA1withRSA");
sig.initSign(prvKey);
sig.update(署名対象データaaa);
sigVal = sig.sign();
RSAやECDSAの署名検証はこんな感じ。
CertificateFactory cf = CertificateFactory.getInstance("X.509");
X509Certificate cer = (X509Certificate)cf.generateCertificate(new FileInputStream(公開鍵証明書));
pubKey = cer.getPublicKey();
Signature sig = Signature.getInstance("SHA1withECDSA"); // RSAならSHA1withRSA
sig.initVerify(pubKey);
sig.update(署名対象データ);
isValid = sig.verify(sigVal);
最初、BouncyCastle使えばいいかとも思ったんですが、 Java SE 7から楕円用のプロバイダSunECが標準提供されるようになったので、 Java SE 7の標準バンドルされたプロバイダを使うことにしました。 サポートしている楕円曲線はどうだっけと思ったら 前に自分で調べてあったのでそれを参考にしました。 ( 祝 Java SE 7 リリース記念「JCEはどうなってんの？」)
一般に、
表を引用しておきましよう。
| 共通鍵暗号 | DSA | RSA | ECDSA |
|---|---|---|---|
| 80 | L=1024,N=160 | 1024 | 160-223 |
| 112 | L=2048,N=256 | 2048 | 224-255 |
| 128 | L=3072,N=256 | 3072 | 256-383 |
| 192 | L=7680,N=384 | 7680 | 384-511 |
| 256 | L=15360,N=512 | 15360 | 512- |
まずはRSA鍵での署名と検証がどれくらい違うのか見てみましょう。
署名と生成では、署名の方が圧倒的に時間がかかることがわかります。 また、鍵長が長くなるほど指数関数的に時間がかかることがわかります。 署名生成に関しては特にJava JCEの遅さが顕著です。
グラフからECDSAではRSAとは逆に署名検証より署名生成の方が わずかながら速いですが、あまり変わらないということがわかります。 また、同じ鍵長のsecp160r1, secp160r2, secp160k1とでは ほとんど処理速度には違いはなく、鍵長が長くなると処理時間は増えますが、 RSAが非常に鍵長の影響を受けるのに対し、ECDSAでは あまり鍵長が長くなっても処理時間が長くはならない事がわかります。
ECC 160bit とRSA 1024bitはほぼ同等の暗号強度です。 ECDSAと比較して、RSAは署名生成はとても遅いが、署名検証は とても速いことがわかります。
鍵長が長いケース、ECC 256bit と同等なRSA 3072bit を比較してみると、 順序関係は変わりませんが、鍵長が長くなった分、 非常にRSA署名の生成時間が長くなっています。 これに対し、ECDSAではRSAほどは鍵長が長くなった影響を受けていません。
簡単にまとめると時間がかかる順に
マイクロソフトのルート証明書の更新プログラムが2010年8月23日にリリースされていました。最近、全く気にしてなかったんですが nahi さんのつぶやきを見ていたら更新されていたことを知りました。
前回から3ヶ月しか経っていないので、大した更新も無いんじゃないかと思っているんですが、今更ながら調べてみました。自分の持っているルートが338→341に増えたので、たった3つだけ増えたってことらしいです。 で、増えたのは以下の3つ。
| 国 | 認証局名 |
|---|---|
| US | Microsoft Root Certificate Authority 2010 |
| US | AffirmTrust Premium ECC |
| LT | Registru Centro Sertifikavimo Centras, VI Registru Centras RCSC (RootCA) |
MSのルートもSHA256withRSA 4096bitのルート証明書を出してきたみたいです。
米国 AffirmTrust の楕円のルート証明書です。曲線はOIDが1.3.132.0.34で 鍵長 384bit の曲線名がSEC 2ではsecp384r1、NISTではP-384と呼ばれているものです。 SEC 2は楕円暗号業界団体 Standards for Efficient Cryptography Group (SECG) が定めた楕円暗号に 関する規格です。署名アルゴリズムは SHA384withECDSA でした。
リトアニア(LT)のルート証明書は適格証明書(QC)のルート証明書になっていて SHA1withRSA 4096bit 鍵の証明書でした。QCステートメントを見てみると以下の値が設定されていました。
これからRSA鍵のルートCAは鍵長4096bitっていうのが多くなってくるんでしょうね。
