暗号に楕円曲線を使う
楕円曲線暗号(ECC)は、RSA よりはるかに小さい鍵で同等の安全性を提供します。点の演算と鍵交換を学びましょう。
- 1
有限体上の楕円曲線 y^2 = x^3 + ax + b は、点の加法のもとで群をなします。楕円曲線上の「離散対数問題」(P と kP が与えられて k を求める)は、素因数分解や Z_p 上の DLP より難しいです。そのため ECC は、同等のセキュリティにより小さな鍵を使います。P-256(256 ビット)≈ RSA 3072 ビット。Curve25519 は ECDH で人気があります。
- 2 剰余べき乗計算ツール →
ECC は点のスカラー倍(べき乗ではない)を使いますが、その根底にある体の演算は剰余算を使います。このツールは、ECC の体演算で使われる剰余算を示します。点のスカラー倍は点の加法の繰り返しで、べき乗が乗算の繰り返しであるのと類似しています。
- 3 素数判定ツール →
楕円曲線の体の素数の法を確認します。標準曲線(P-256、Curve25519)は慎重に選ばれた素数を使います。安全であるためには、素数が十分大きく(256 ビット以上)、曲線が大きな素数位数の部分群を持たなければなりません。
よくある質問
- ECC の鍵はなぜ RSA より小さいのですか?
- 楕円曲線離散対数問題(ECDLP)に対する既知の最良アルゴリズムは O(sqrt(n))(群の位数の平方根)です。RSA に対する最良アルゴリズム(GNFS)は劣指数的です。そのため、鍵サイズに対して ECDLP はより難しいです。256 ビット ECC ≈ 3072 ビット RSA、384 ビット ECC ≈ 7680 ビット RSA。
- どの曲線を使うべきですか?
- ECDH には Curve25519(Daniel J. Bernstein)。高速、一定時間、悪いパラメーターなし。互換性には P-256(NIST)。TLS と標準で広くサポートされています。Bitcoin/Ethereum には secp256k1。理由の説明のないパラメーターを持つ曲線は避けてください(NSA のバックドアの可能性)。標準化され、十分に解析された曲線を使ってください。