maidsphere

A quantization noise whispers through the net.

楕円曲線暗号の鍵長に512bitがなく521bitがある理由

May 17, 2015 13:34:53 JST

鍵長が512bitとなる鍵も521bitとなる鍵も,実は両方あるというのが答えです. ただし,SSHでは521bitの鍵を使うようにRFC5656で決まっています. RFCで採用されなかったため,SSHでは512bitの鍵が使えない,というわけです.

この制限はSSHのみですので,楕円曲線暗号(より正確にはECDSA)というくくりでは512bitの鍵長の鍵が使えます. ただし一般的ではありません.

521bitの鍵を導くための楕円曲線パラメータはNISTが(最初に)公開したものです. このパラメータは意図的に計算効率を優先して設定されています. 512bitではなく521bitを採用したのもそのためです.


楕円曲線暗号とパラメータ

楕円曲線暗号では暗号で使う「楕円曲線」を事前に定義しておく必要があります. この楕円曲線(と,ベースポイントと呼ばれる座標など)は公開されているものを利用します. 暗号処理系には一般的に使われるパラメータはだいたい実装されています.

楕円曲線暗号で用いられる楕円曲線のパラメータは,様々な機関から様々なものが提案されています.

NIST curve

もっとも頻繁に使われているのは,NISTが1999年に公開したNIST curveと呼ばれているパラメータです. このNIST curveは,鍵長が192bit,224bit,256bit,384bitそして521bitとなるパラメータをもっています.

2000年にアメリカがFIPS 186-2 Digital Signature Standard (DSS)として標準化しました. このNIST curveはANSI X9.62SEC 2の一部としても標準化されています. それぞれの標準化グループにおける呼称のマッピングはRFC4492付録Aに載っています.

Brainpool curve

ほかにも,Brainpool curveと呼ばれるパラメータもあります. これはその名の通り,ドイツのBrainpoolという団体が2005年に公開したものです. INFORMATIONAL扱いですが,RFC5639として標準化もされています. ちなみに,Brainpool curveを使った楕円曲線DSAをECGDSAと呼んでいるドキュメントがあります. 「G」はGermanyの「G」です.

Brainpool curveには,鍵長が160bit,192bit,224bit,256bit,320bit,384bit,そして512bitになるパラメータがあります. つまり,Brainpool curveを使うことで512bitの鍵を利用することができます.

Brainpoolの標準化ドキュメントのTechnical Requirements節には

Most of the previous proposals specify a 521-bit curve instead of a 512-bit curve.

という表記があります. NIST curveにはない鍵長512bitのパラメータを,Brainpoolが提供できていることを意識していることがうかがえます.

しかし,Brainpool curveはNIST curveに比べて,計算効率が非常に悪いことが知られています. これはBrainpool curveの仕様上の制限によるものです. NIST curveはパラメータに計算の効率がよい素数を意図的に選んでいますが,Brainpool curveはそうしていません.

tincというVPNソフトウェアの開発MLには,だいたい2~5倍ほど遅くなっている結果が投稿されています. また,mbed TLSという組み込み向け暗号化ライブラリのナレッジベースにも,同様の情報が公開されています. 後者のドキュメントには,Brainpool curveがNIST curveに対して遅い理由が簡単にまとめられています.

NIST curveで521bitの鍵長が採用されたわけ

パラメータに計算の効率が非常によい素数2521 -1を使いたかったためです. 楕円曲線暗号で使われる特定の計算は,単純に項数が少ないほど高速な計算ができます. そのため,メルセンヌ素数をパラメータとして採用できることはきわめて理想的です. ちなみに256bitの鍵長の場合は,素数2256 -2224 +2192 +296 -1(NIST P-256の場合)を使います.

ある論文には,521bitのほうが半分以下の256bitの時よりも計算速度が速くなっている例(10ページ表4のFast reduction)が示されています. メルセンヌ素数を使うことによる効率化がどれだけ劇的かがよくわかります.

もともとNIST curveの素数パラメータは安全性よりも計算の効率化に焦点を当てて設計されています. そのため,2の冪でない鍵長であったとしても,採用を躊躇する理由にはならなかったようです. このスライドも併せて読むと,よいかもしれません.