自堕落な技術者の日記

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