自堕落な技術者の日記

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

RSA鍵による署名って、フツーはJava JCEでもCryptoAPIでも.NETでもOpenSSLでも、一つのオペレーションになっていて、中でどう処理されているから知る必要もないんですが、やろうと思えばハッシュとRSA鍵による暗号化・復号の暗号プリミティブで実装することはできます。

今回はRSA署名の中身を図説したものって、なかなか良い物が無かったので、ちょっと書いてみて、関連した相互運用上の問題なんかを紹介します。

RSA署名とは何？よ〜し父さん図説しちゃうぞ

RSA署名って、

文書のハッシュ取って秘密鍵で暗号化するんだよね

って簡単に解説しているものがあったりしますが、その説明って、なんか合っているようで合っていないというか、うそ臭いというか、「本当はどうなの？」っていうはなしが抜けているようで、これまでスッキリしませんでした。多分、それはパディングの話が無いからなんじゃないかと思うんです。

RSA署名の方式はPKCS#1 v2.1の中で定められているんですが、一般的な公開鍵証明書やCMS署名なんかは、その中で定められた "RSASSA-PKCS1-v1_5" というアルゴリズムを使っています。

RSASSA-PKCS1_v1_5アルゴリズムにかなり忠実に図説してみたのがコレ：





左から右(→)が「署名の生成」で、右から左(←)が「署名の検証」です。

RSASSA-PKCS1-v1_5 のオペレーションは大きく、

・ハッシュの計算
・パディング処理
・公開鍵暗号

の3つに分かれます。DigestInfoを作るとこも含めてパディング処理と読んだりすることもあり、この図の方が間違っているかもしれませんが、一般的なプログラミング上のパディング処理を知っている方なら、DigestInfoを作った後からをパディング処理と呼んだ方がスッキリするようなが気がします。

DigestInfoと相互運用性

署名では、署名対象データのハッシュ値とハッシュアルゴリズムを格納するためにDigestInfoというASN.1構造を使います。

RSA PKCS#1 v2.1より

DigestInfo ::= SEQUENCE {

  digestAlgorithm DigestAlgorithm,

  digest OCTET STRING

}



DigestAlgorithm ::= AlgorithmIdentifier { {PKCS1-v1-5DigestAlgorithms} }



PKCS1-v1-5DigestAlgorithms ALGORITHM-IDENTIFIER ::= {

  { OID id-md2 PARAMETERS NULL }|

  { OID id-md5 PARAMETERS NULL }|

  { OID id-sha1 PARAMETERS NULL }|

  { OID id-sha256 PARAMETERS NULL }|

  { OID id-sha384 PARAMETERS NULL }|

  { OID id-sha512 PARAMETERS NULL }

}

署名生成時のアルゴリズムパラメータNULL

DigestInfoでハッシュアルゴリズムを指定する際に、アルゴリズムパラメータを指定できるんですが、SHA1、SHA2シリーズの場合にはNULLを指定します。このNULLを入れる入れないで、相互運用上の問題が起きたりします。

この辺りは昔、RSAとNISTの間で紆余曲折あったそうなんですが、解決のためにRSAはv2.1の訂正(PKCS #1 v2.1 Errat)を2005年12月に出しています。結論から言うと

・署名生成時：NULLを含めるものとする(SHALL)
・署名検証時：NULLがあってもなくても検証できるものとする(SHALL)

生成については、これまで自分が触ることができた10ぐらいの署名実装で一つを除き問題なくNULLが含まれていましたし、手当たり次第調べた証明書、CRLなんかも全てNULLが含まれた形になっています。残りの一つについても、パッチが出ているそうなので早く修正されるといいなぁ、、、と思います。(とある製品が国内2つの実サービスで使われているんですが、もう長いことパッチ未適用になってます。残念。)

検証については、目にした殆どの実装がNULLがあっても無くても検証できるようになっているんですが、入手できたうちの20%ぐらいの実装はNULLが無いと検証失敗します。

この辺りは、ハッシュとRSA暗号のプリミティブを使ってNULLの入ってない署名を作ったり、生の署名値、証明書、CMS署名、XML署名などで署名値のDigestInfoにNULLが入っているのかどうかをチェックするツールを作って調べました。

なんか、今回も細かい話ですみませんね。ではでは。

「電子署名及び認証業務に関する法律の施行状況に係る検討会」報告書の公表及び意見募集の結果 （METI/経済産業省）

「電子署名及び認証業務に関する法律の施行状況に係る検討会」報告書の公表及び意見募集の結果

公開されました。

これと関連して、↓も一応

2008.05.23 JIPDEC「特定認証業務の認定に係る調査表」の改訂について
http://www.jipdec.or.jp/esac/new/news20080523.html