楕円曲線DSA

楕円曲線DSA（ECDSA）とは

楕円曲線DSA（Elliptic Curve Digital Signature Algorithm、ECDSA）は、デジタル署名アルゴリズム（DSA）をベースに、楕円曲線暗号（ECC）を用いた暗号技術です。DSAと比較して、より短い鍵長で同等のセキュリティ強度を実現できるため、リソースが限られた環境でも効率的に利用できます。

DSAとの比較

一般的に、楕円曲線暗号は、従来のRSAなどの公開鍵[[暗号]]と比較して、同じセキュリティレベルを達成するのに必要な鍵長が大幅に短くて済むという利点があります。例えば、80ビットのセキュリティ強度を確保する場合、DSAでは1024ビットの公開鍵が必要ですが、ECDSAでは160ビットで十分です。

一方、署名のサイズはDSAとECDSAで同じであり、必要なセキュリティビット数の4倍のビット長が必要です。つまり、80ビットのセキュリティを確保するためには、320ビットの署名サイズが必要です。

署名生成の仕組み

署名生成は、以下のステップで実行されます。

1. パラメータの決定: 楕円曲線 `(E, p, G, n)` のパラメータを決定します。
2. 鍵ペアの生成: アリスは、`[1, n-1]` の範囲からランダムに秘密鍵 `dA` を選択し、公開鍵 `QA = dA G` を生成します。`dA`から`QA`の計算は容易ですが、`QA`から`dA`を計算することは困難です。
3. ハッシュ値の計算: メッセージ `m` のハッシュ値 `e = H(m)` を計算します。`H` はSHA-1などの暗号学的ハッシュ関数です。
4. ハッシュ値の変換: ハッシュ値 `e` の上位 `Ln` ビットを `z` とします。`Ln` は位数 `n` のビット長です。
5. ランダム値の選択: `[1, n-1]` の範囲からランダムに整数 `k` を選択します。
6. 曲線上の点の計算: 曲線上の点 `(x1, y1) = k G` を計算します。
7. 署名値rの計算: `r = x1 mod n` を計算します。`r = 0` の場合は、ステップ5に戻ります。
8. 署名値sの計算: `s = k^-1 (z + r dA) mod n` を計算します。`s = 0` の場合は、ステップ5に戻ります。
9. 署名の完成: `(r, s)` がメッセージ `m` に対する署名となります。

`s` の計算時に使用される `z` は、`n` より大きいことは許容されますが、ビット長が `n` より長くなることは許容されません。

重要な点として、署名ごとに異なる `k` を使用する必要があります。もし、同じ `k` を使用してしまうと、秘密鍵 `dA` が漏洩する危険性があります。これは、PlayStation 3のソフトウェア署名鍵漏洩の原因となった実装ミスとして知られています。

署名検証の仕組み

署名検証は、以下のステップで実行されます。

1. 公開鍵の検証: 検証者はアリスの公開鍵 `QA` が以下の条件を満たしているかを確認します。
`QA` が `O` (無限遠点) でない。
`QA` が楕円曲線上にある。
`n QA = O` が成立する。
2. 署名値の範囲検証: 署名値 `r` および `s` が `[1, n-1]` の範囲にあるかを確認します。この範囲外の場合、署名は不正です。
3. ハッシュ値の計算: メッセージ `m` のハッシュ値 `e = H(m)` を計算します。使用するハッシュ関数は署名生成時と同じである必要があります。
4. ハッシュ値の変換: ハッシュ値 `e` の上位 `Ln` ビットを `z` とします。
5. 逆数の計算: `w = s^-1 mod n` を計算します。
6. パラメータの計算: `u1 = zw mod n` および `u2 = rw mod n` を計算します。
7. 曲線上の点の計算: `(x1, y1) = u1 G + u2 QA` を計算します。
8. 検証: `r ≡ x1 (mod n)` であれば、署名は正当なものとして検証されます。

この検証プロセスでは、Straus's algorithm（Shamir's trick）を用いることで、計算を効率化できます。

アルゴリズムの正当性

署名検証のステップで得られた点 `C` は、以下の計算により、署名生成で使用した `k G` と等しくなることが証明できます。


C = u1 G + u2 QA
C = u1 G + u2 dA G
C = (u1 + u2 dA) G
C = (z s^-1 + r dA s^-1) G
C = (z + r dA) s^-1 G
C = (z + r dA) (z + r dA)^-1 (k^-1)^-1 G
C = k G


この結果から、正当な署名が正しく検証されることがわかります。ただし、この証明はアルゴリズムの正しさを示すものであり、セキュリティ上の脆弱性がないことを示すものではありません。

セキュリティに関する注意点

ランダム値kの取り扱い: 署名ごとに異なるランダム値 `k` を生成する必要があります。固定値を使用すると、秘密鍵が漏洩する危険性があります。
サイドチャネル攻撃: タイミング攻撃などのサイドチャネル攻撃に対する対策が必要です。
SecureRandomの実装: SecureRandomクラスのバグにより、`k` の衝突が発生する可能性があります。決定論的な方法で `k` を生成するRFC 6979などの仕様に従う必要があります。
楕円曲線の選択: NIST標準の楕円曲線を使用する場合、その選定理由やバックドアの可能性について慎重に検討する必要があります。

実装ライブラリ

ECDSAをサポートする主なライブラリには、以下のようなものがあります。

Botan
Bouncy Castle
cryptlib
Crypto++
libgcrypt
OpenSSL
GnuTLS
wolfCrypt

参考文献

Accredited Standards Committee X9, American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), November 16, 2005.
Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography, Version 2.0, May 21, 2009.
López, J. and Dahab, R. An Overview of Elliptic Curve Cryptography, Technical Report IC-00-10, State University of Campinas, 2000.
Daniel J. Bernstein, Pippenger's exponentiation algorithm, 2002.
Daniel R. L. Brown, Generic Groups, Collision Resistance, and ECDSA, Designs, Codes and Cryptography, 35, 119–152, 2005. ePrint version
Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, editors, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
. (2004). doi:10.1007/b97644.

関連項目

楕円曲線暗号
Digital Signature Algorithm

外部リンク

Digital Signature Standard; includes info on ECDSA

もう一度検索