前回の記事では、署名生成と署名検証とか、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と同じ暗号強度で署名検証速度が逆転するのはということのようです。この値に近づいてるようならECDSAへの移行を考えた方が よいということなんでしょうね。
・RSAだと9234bit のとき
・ECCだと409bitのとき
今晩はこの辺で
あ、そうそう。これ書いている途中でizuさんのとてもためになる関連記事を発見してしまいました。杜撰な研究者の日記「RSA暗号の強度 (2009.11.19)」。
RSAの速度は、a^b mod n のベキ乗剰余が支配的で、署名生成・検証ともにこの計算時間が全体の99%以上占めます。署名生成の場合、bが鍵長であるのに対して、署名検証は b = 2^16 + 1とするのが慣例で高々17bitなので、とても高速です。他の値は鍵長。よって、結果の通り、鍵長に対して計算時間は指数関数的に増加します。
ECDSAですが、署名生成は、楕円スカラ倍算を１回、署名検証は楕円スカラ倍算を2回(JSF法により軽減可)行います。この楕円スカラ倍算ですが、a x b mod nの剰余乗算が数千回実行され且つ多少重い計算で、全体の80%くらいを占めます。a, b, nともに鍵長です。NISTは、効率良く剰余計算できる素数n (一般化メルセンヌ素数 or メルセンヌ素数)を推奨パラメータとしています。Opensslもこの値を使っています。そして、その効率の良い剰余計算というのが、鍵長とは無関係であるため、一概に鍵長が増えれば計算時間も比例すると言えません。。。最長の鍵長521bitは、一瞬でこの剰余演算ができます。よって、鍵長に対して計算時間はおよそ線形に比例するが、ずれがあるという結果になります。
このあたりは、本当に演算コアの部分を把握している人は案外少ない or 誤った認識を持っている人が多いです。