自堕落な技術者の日記

GoogleのCertificate Transparency (解説 [1] [2] [3]) のログデータベースはパブリックなHTTPSサイトに関する証明書のログデータベースなので、いろんな情報が取得できます。2015年3月27日時点で、6,949,166枚のSSLサーバー証明書に関する情報が格納されており、毎日1万枚以上増え続けています。これだけの枚数ですから、ここ数年有効な全世界のSSLサーバー証明書は網羅されているとして良いのかなと思います。以前紹介したgo.jpドメインのHTTPSサイトの調査もこの公開データをもとに調査しました。

本当は講演資料つくらないとマジでヤバイ感じなんですが、現実逃避して、ちょっと訳あってDSAやECDSA公開鍵のSSLサーバー証明書の利用、発行状況について調べてみたのでご報告を。そもそもはDSA公開鍵のSSLサーバー証明書を使っているDSSの暗号スイートなんて本当に使える公開サイトなんかあんのかって話を知りたかったわけです。

ほとんどの証明書はRSA公開鍵のSSLサーバー証明書であり、SSL Pulseの調査結果を見てもECDSAの証明書など割合からしてちょびっとな状況なわけですが、ログデータベースで見てみるとこんな感じです。(以下、2015年3月27日時点)

証明書	枚数	比率(%)
登録サーバー証明書(ログエントリ)の枚数	6,949,166枚	100%
うちECDSA公開鍵のSSLサーバー証明書の枚数	398,841枚	5.3%
うちDSA公開鍵のSSLサーバー証明書の枚数	100枚	0.0014%

念のため補足しとくと、DSA公開鍵のSSLサーバー証明書とはSubjectPublicKeyInfoフィールドにDSA公開鍵が格納された証明書の事を意味し、これを発行する認証局の鍵のアルゴリズムはRSAでもDSAでもECC(ECDSA)でも何でも構いません。SSLサーバー証明書のSubjectPublicKeyInfoのアルゴリズムにより、SSL/TLSで通信した場合の暗号スイートの認証や鍵交換が決まり、DSA公開鍵の場合にはDSSの暗号スイートが使用されます。ECC(ECDSA)証明書についても同じような感じです。

DSA公開鍵のSSLサーバー証明書

100枚の証明書のうち、さらに実際に接続してみて現在も利用可能なサイトを調べてみました。

証明書	枚数	比率(%)
登録サーバー証明書(ログエントリ)の枚数	6,949,166枚	100%
うちDSA公開鍵のSSLサーバー証明書の枚数	100枚	0.0014%
うち接続可能なDSA公開鍵のSSLサーバー証明書のサイト	11	0.00016%
うちシマンテック以外のDSA公開鍵のSSLサーバー証明書のサイト	3	0.00004%

いや〜、たった11サイトでしたよ。そのうち8サイトはドメイン名から シマンテックさんのテストサイトであることは明らかなので、一般のサイトは たった3つでした。DSA証明書を発行しているブランドは、 シマンテックさん以外は、Thawte、cacert.org、ips CAだけでした。 クライアントもサーバーもDSA公開鍵SSLサーバー証明書を使った DSS暗号スイートを使う可能性は殆ど無いと考えてよいんじゃないですかね。

ちなみに、Firefox 36、Chrome 41 でこのDSA証明書のサイトへアクセスしてみると、以下のように表示され、暗号スイートとしてそもそもサポートしていなかったり、信頼するルートに入っていなかったりで接続できません。OpenSSLのs_clientコマンドで接続するしかないわけです。

ECDSA公開鍵のSSLサーバー証明書

ECDSA証明書については5%とそれなりに数はあるわけですが、 ちょっとドメインのリスト見てみると殆どcloudflaressl.comドメインばっかりなんですよ。

証明書	枚数	比率(%)
ECDSA公開鍵のSSLサーバー証明書の枚数	398,841枚	100%
うちcloudflaressl.comのECDSA公開鍵のSSLサーバー証明書の枚数	398,262枚	99.85%
うちcloudflaressl.com以外のECDSA公開鍵のSSLサーバー証明書の枚数	569枚	0.15%

誰かが、「全世界で数パーセントもECDSA証明書が使われてて純増していて、ECDSA証明書は段々流行りつつあるんですよ」なんて教えてくれた人がいたような気もするんですが、cloudflare以外では全世界でたった569枚しか売れてないんじゃないですか！！！ECDSA証明書はcloudflareさんが支えてたんですねぇ。しみじみ。

あ、そうそうGoogleでは*.google.comとかECCの公開鍵のSSLサーバー証明書を使っていてSSL/TLSで接続するとECDHE_ECDSAの暗号スイートになるんですが、その証明書の発行する認証局の鍵はRSAでSHA1withRSAで署名してるんですよね。「ChromeでSHA2移行をせかせる割には、お前はSHA1なんかいっっつ！！」みたいな。

おわりに

というわけで、全世界でどれくらいDSA証明書、ECDSA証明書が使われているのかを見てみました。結構興味深い事実もわかって個人的にはよかったかなと思います。オレはまだ本気出してないだけ。明日から講演資料作成頑張りまっすorz Certificate Transparencyについてはいろいろ深く突っ込んで調査しており、どこかで吐き出したいんですが、雑務に追われなかなかチャンスが無いなぁ。

一昨日、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解説もある。
短所	使われている記号が一般的なのとちょっと違うようで少し混乱する。

私は上の順序で読むのがいいのではと思います。誰かこれ全部まとめたやつを日本語で書いてくれると いいんですけどねぇｗ (オマエガヤレ)

コンピューター、IT関係の英語は何とか少しは読めるけど、数学の英語はやっぱり難しいですねぇ。

追記

• 2014.05.29 伊豆さんに最新版のリンクを頂いたので修正いたしました。伊豆さんあざます。
• 2014.10.11 私の書いたスライド「Bitcoinを技術的に理解する(p10-17)」のp10-17で内容8ページで楕円曲線暗号、ECDSAの署名・検証などエンジニア向けにざっくり説明した資料を作りました。我ながら短いページでよくできていると思うのでよかったらご覧ください。
• 2014.10.21 かなりわかりやすい英語の解説ページが出てきました。CoinDesk: The Math Behind Bitcoin これは、現時点では一番オススメ。英語だけど。

JNSA電子署名ワーキンググループのスキルアップタスクフォースの勉強会で 拙作のJavaScript暗号ライブラリjsrsasignとJOSE JWS JWTライブラリ jsjwsのお話をさせて頂く機会を頂きました。スライドを公開しました。 これらのライブラリで日本語版の資料は作ったことがなかったので、 よかったら参考にしてください。

前回の記事では、署名生成と署名検証とか、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-

まずは、同じ暗号強度のECC、RSAの鍵長に対して秒間署名検証回数をプロットしてみましょう。

ご覧の通り共通鍵暗号で200bit相当、RSAなら9000bit、ECCなら200bit程度の所で署名検証の のスピードが逆転しているように見えます。我々が現在利用することの多い2048〜4096bit程度の RSAの鍵ならまだまだ十分高速であることは言えるのではないかと思います。

上記のグラフが指数関数的なので今度は秒間署名回数の対数を取ってプロットしてみましょう。

グラフから、暗号強度に対してはほぼリニアに秒間署名速度の対数が推移し、 共通鍵暗号相当の暗号強度の軸であるx座標が212.5423729(bit)の時に、 RSAとECCの署名検証の速度が逆転しています。

それでは、共通鍵暗号の強度で213bitということはRSAやECCではどの程度の鍵長に 相当するのでしょうか。 共通鍵暗号暗号強度と同等のECC、RSAの鍵長は最初のNISTの表から これも指数関数的なのでRSAの鍵長と、ECCの鍵長の対数を使ってプロットしてみます。

すると、ご覧のように取った対数に対してほぼリニアに推移することがわかります。 共通鍵暗号の暗号強度で213bitとする点はRSAだとy軸が3.965、ECCだと2.612となり、 これらは指数に戻して

RSAとECDSAと同じ暗号強度で署名検証速度が逆転するのは
・RSAだと9234bit のとき
・ECCだと409bitのとき

ということのようです。この値に近づいてるようならECDSAへの移行を考えた方が よいということなんでしょうね。

今晩はこの辺で

あ、そうそう。これ書いている途中でizuさんのとてもためになる関連記事を発見してしまいました。杜撰な研究者の日記「RSA暗号の強度 (2009.11.19)」。

2013年9月4日に開催されたOpenID Tech Night Vol.10 に参加してて、

大きなプロバイダではRSA署名の検証は結構大変です。 RSAは署名よりも検証の方が計算コストがかかるので...

みたいな話をされ、「んん？逆じゃないの。RSA署名の検証は署名生成よりも圧倒的に計算コスト低いよね。」とか 思ってたわけで「がが〜〜ん」と。 「まぁ、ちょっと調べてみるべぇ。」と手持ちのノートPCで調べてみました。

検証内容

以下のことを検証してみたいと思います。

• 署名の生成と検証ではどちらが速いのか。RSAとECC(ECDSA)では違いがあるのか。
• 同程度の暗号強度のRSA署名とECDSA署名ではどれくらい速度差があるのか。
• RSA署名では鍵長が変わったとき、どれくらい速度差があるのか。
• ECDSA署名では楕円曲線や鍵長が変わったとき、どれくらい速度差があるのか。
• Ruby+OpenSSLとJava JCEではどれくらい速度差があるのか。

なんか、楕円「マンセー」みたいな人もおられますが、 「楕円は鍵長が短いから圧倒的に速い」みたいな事を言い出す人もいて 「ホンマかいな？」と調べてみたかったわけです。 楕円って期待するほどそんなに速くないですよね？ むしろ遅いですよね。

検証方法・検証環境

言語の偏りがあるのも良くないのでOpenSSLベースのものとJava JCEベースのものと調べます。 いちいちOpenSSLをCで書くのも面倒なので。Rubyを使いました。 処理時間の測定方法については、Ruby+OpenSSL、Java JCEで次のような観点で測定しています。

共通

• 鍵や証明書のロードの時間は処理時間に含めない。
• 測定条件統一のためハッシュ計算の時間は処理時間に含める。
• 同一のマシンで測定する。
• 再利用しない同一の鍵で2000回の署名生成、署名検証の時間を計測。
• 公開鍵暗号のパフォーマンスを知りたいだけなので署名対象は"aaa"の短い文字列。
• SHA1withRSAもしくはSHA1withECDSAで比較する。

Ruby+OpenSSL

• Ruby標準の'benchmark'モジュールを用い、リハーサルも行う。benchmarkのrealの時間を用いる。

Java JCE

• イテレーションループの前後でのSystem.currentTimeMillis()の値の差を処理時間とする。

細かい検証環境情報は以下の通りとなります。

検証環境
マシン	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で署名

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構造で表現することに気をつければ問題ないかと思います。

Java JCEで署名

最近、キーストア使って楽してたので普通に鍵ファイルを読みたい場合には、 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はどうなってんの？」)

RSAとECCの暗号強度対応

一般に、

• ECC 160bit は RSA 1024bitに相当する、とか
• ECC 256bit は RSA 3072bitに相当する、とか

言われていますが、調べて見ると、 NIST SP800-57 Recommendation for Key Management - Part1: Generalの 5.6.1節 Comparable Algorithm Strengthで対象暗号、RSA、DSA、ECC(ECDSA)の鍵長と 暗号強度の対応の表があり、 RFC 5656 Elliptic Curve Algorithm Integration in the Secure Shell Transport Layerでも引用してます。(こっちの方が見やすい)

表を引用しておきましよう。

共通鍵暗号	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-

(結果1)RSAの署名生成と署名検証はどっちが速いか

まずはRSA鍵での署名と検証がどれくらい違うのか見てみましょう。

署名と生成では、署名の方が圧倒的に時間がかかることがわかります。 また、鍵長が長くなるほど指数関数的に時間がかかることがわかります。 署名生成に関しては特にJava JCEの遅さが顕著です。

(結果2)ECDSAの署名生成と署名検証はどっちが速いか

グラフからECDSAではRSAとは逆に署名検証より署名生成の方が わずかながら速いですが、あまり変わらないということがわかります。 また、同じ鍵長のsecp160r1, secp160r2, secp160k1とでは ほとんど処理速度には違いはなく、鍵長が長くなると処理時間は増えますが、 RSAが非常に鍵長の影響を受けるのに対し、ECDSAでは あまり鍵長が長くなっても処理時間が長くはならない事がわかります。

(結果3)同じ暗号強度ではRSAとECDSAとどちらが速いか

ECC 160bit とRSA 1024bitはほぼ同等の暗号強度です。 ECDSAと比較して、RSAは署名生成はとても遅いが、署名検証は とても速いことがわかります。

鍵長が長いケース、ECC 256bit と同等なRSA 3072bit を比較してみると、 順序関係は変わりませんが、鍵長が長くなった分、 非常にRSA署名の生成時間が長くなっています。 これに対し、ECDSAではRSAほどは鍵長が長くなった影響を受けていません。

まとめ

簡単にまとめると時間がかかる順に

• RSA署名の生成には非常に時間がかかる
• ECDSAの署名検証は署名生成よりほんの少し長く時間がかかる
• ECDSAの署名生成は普通に時間がかかる
• RSA署名の検証は非常に短時間であるECDSAの署名生成は普通に時間がかかる
• RSAでは鍵長が長くなるほどその傾向が顕著になる。
• ECDSAはRSAほどは鍵長が長くなる影響を受けない。

といった感じでしょうか。認識してたとおりで良かったなぁと思いました。今日はこの辺で。