自堕落な技術者の日記

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ほどは鍵長が長くなる影響を受けない。

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