楕円曲線DSA

楕円曲線DSA（だえんきょくせんDSA、Elliptic Curve Digital Signature Algorithm、Elliptic Curve DSA、楕円DSA、ECDSA）は、楕円曲線暗号における離散対数問題を用いたデジタル署名の一種であり、Digital Signature Algorithm (DSA) の強化版の一つである。

メッセージの送信者は、秘密鍵を決め、これに基づいて決めた公開鍵を、しかるべき権威を持った認証局において、あらかじめ公開しておき、秘密鍵を用いて送信メッセージに添付するデジタル署名を作成する。この際、メッセージの受信者の情報(受信者の公開鍵など)は必要なく、不特定多数の受信者に対して、デジタル署名付きのメッセージを送信可能である。

メッセージの受信者は、認証局から入手する暗号のパラメーターと送信者の公開鍵を用いて、以下で説明するアルゴリズムにより、デジタル署名の正当性を検証できる。検証の際に、受信者は送信者、認証局または第三者から、デジタル署名の正当性に関する追加の情報を得る必要はない(ゼロ知識証明)。

DSAとの比較

ECDSAでは楕円曲線暗号における離散対数問題を用いて、公開鍵から秘密鍵の値が解読されるのを防いでいる。離散対数問題のセキュリティ強度(セキュリティ強度が $l$ (ビット)であるとは、攻撃者が公開鍵から秘密鍵を解読するために必要な単位操作の回数が $2^{l}$ 回程度であることを表している)は、公開鍵のサイズの約1/2である。例えば、80ビットのセキュリティ強度（攻撃者が秘密鍵を取得するために $2^{80}$ 回の計算を必要とする）を得るために、ECDSAでは160ビットの公開鍵が必要である。一方、DSAで同程度のセキュリティ強度を得るには最低でも1024ビットの公開鍵が必要である。なお、ECDSAでは、署名のサイズは、必要とするセキュリティ強度の4倍のビット長を要する（つまり、80ビットのセキュリティ強度を得るためには320ビットの長さの署名が必要である。詳細後述）。

アメリカ国立標準技術研究所(NIST)は、"Digital Signature Standard (DSS)規格書"(FIPS 186-5, February 3, 2023)の中で、理由は明示していないが「従来の DSA は本標準では取り扱わないことになった。ただし、本標準策定以前に行われた署名の検証には利用可能である」と述べており、「RSAデジタル署名」、「楕円曲線デジタル署名」、「エドワーズ曲線デジタル署名」の3種のデジタル署名の標準規格を規定している。

署名生成

アリスが署名したメッセージをボブに送る場合を考える。最初に、使用する楕円曲線のパラメータ $(E,p,G,n)$ を決めておく必要がある。

次に、アリスは $[1,n-1]$ の範囲からランダムに選択された秘密鍵 $d_{A}$ と、公開鍵 $Q_{A}=d_{A}*G$ から成る鍵ペアを生成する。$d_{A}$ と $Q_{A}$ の対応は1対1であり、$d_{A}$ から $Q_{A}$ を計算することは比較的容易だが、 $Q_{A}$ から $d_{A}$ を計算することは実質的に不可能(離散対数問題)である。つまり $d_{A}$ と $Q_{A}$ の対応は一方向性関数になっている。

これらのパラメータと公開鍵 $Q_{A}$ は、しかるべき権威をもった認証局でネット上に公開される(当然、秘密鍵 $d_{A}$ の値は認証局にも知らされない)。

パラメーター	説明
E	$\mathbb {R} ^{2}$ 上で定義される楕円曲線 $y^{2}=x^{3}+ax+b$ (ワイエルシュトラスの標準形)
p	E 上の有理点を還元する素数。E は有限体 $\mathbf {F} _{p}\times \mathbf {F} _{p}$ 上の楕円曲線に写される
G	$\mathbf {F} _{p}\times \mathbf {F} _{p}$ 上のベースポイント
n	G の位数（$n*G=O$ を満たす）
$d_{A}$	秘密鍵：$[1,n-1]$の範囲からランダムに選択され保持される整数
$Q_{A}$	公開鍵：$d_{A}*G$ ($\mathbf {F} _{p}\times \mathbf {F} _{p}$ 上の点)

(注1) $G$、$Q_{A}$ は $\mathbf {F} _{p}\times \mathbf {F} _{p}$ の元であり、$\mathbf {F} _{p}$ の元 $x$ および $y$ の組 $(x,y)$ から成る2次元ベクトル値である。これに対して $p,n,d_{A},m$ は整数であり、以降ベクトル値に対してスカラー値と呼ぶことにする($d_{A}$ は $\mathbf {F} _{n}$ の元でもある)。また、以降、小文字で始まる変数はスカラー値、大文字で始まる変数はベクトル値とする。

(注2)「$*$」はスカラー値とベクトル値の楕円曲線上での掛け算 (scalar multiplication) を意味する。

アリスがメッセージ $m$ に署名する場合、以下の計算を行う。

1. $e=H(m)$ を計算する。ここで H はSHA-1のような暗号学的ハッシュ関数を指す。
2. $z$ を、$e$ の最上位側の $l_{n}$ ビットとする。ここで $l_{n}$ は位数 $n$ のビット長とする(つまり $l_{n}$ は $\log _{2}n$ 以上の最小の整数である)。
3. $[1,n-1]$ の範囲から整数 $k$ を任意に選択する。$k$ を「1回秘密鍵」と呼ぶことにする。
4. 曲線上の点 $(x_{1},y_{1})=k*G$ を計算する。
5. $r=x_{1}\,{\bmod {\,}}n$ を計算する。$r=0$ となる場合には $k$ の選択に戻る。
6. $s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$ を計算する($k^{-1}$は有限体$\mathbf {F} _{n}$における$k$の逆元である)。$s=0$ となる場合には $k$ の選択に戻る。
7. $(r,s)$ が $m$ に対する署名となる。
   
   

(注3) $s$ を計算する際に、$H(m)$ から得られる $z$ は整数に変換される。$z$ は $n$ より「大きい」ことは許されるが、「長い」ことは許されない。

(注4) $\mathbf {F} _{n}$ の 0 以外の任意の元 $x$ の $\mathbf {F} _{n}$ における逆元 $x^{-1}$ は、フェルマーの小定理から $x^{n-1}\equiv 1\,({\bmod {\,}}n)$ であるから、$x^{-1}=x^{n-2}\,{\bmod {\,}}n$ によって計算できる。

(注5) 上記ステップ4と5において計算され、署名として公表される $r$ の値から $k$ の値を求めることは離散対数問題であり、実質的に不可能である。従って $r$ を公表しても $k$ の値の秘密は保たれるとしてよい。

(注6) 一般に、離散対数問題のセキュリティ強度 $l$ は $n$ のビット長 $l_{n}$ の1/2になる。署名 $r$ と $s$ のビット長は最大で $l_{n}$ と同程度になるので、署名全体のビット長はセキュリティ強度 $l$ の4倍必要になる。

もし、1回秘密鍵 $k$ の値が外部に漏れた場合は、ステップ6において計算され、$r$ と共に署名として公表される $s$ の値から、ステップ6の式によって $d_{A}$ の値を逆算できることになり、アリスの署名の信頼性は壊滅することになる。

$k$ の値が外部に漏れる最もあり得るケースは、異なるメッセージに対して、同一の $k$ を用いて署名を行う場合である。この場合、以下のようにして、ステップ6の式から秘密鍵 $d_{A}$ を得ることが可能となってしまう(これはDSAの場合でも同様である)。

メッセージ $m$ および $m'$ に対して、未知だが同じ1回秘密鍵 $k$ から得られた2つの署名 $(r,s)$ および $(r,s')$ がある場合、攻撃者は $z$ および $z'$ を計算することが可能であり、$s-s'=k^{-1}(z-z')$ であることから、$k={\frac {z-z'}{s-s'}}$ が得られる。$s=k^{-1}(z+rd_{A})$ であるから、攻撃者は秘密鍵 $d_{A}={\frac {sk-z}{r}}$ を得ることができる。このように単一の $k$ を用いることは不適切な実装であり、PlayStation 3のソフトウェア署名鍵が漏洩したのはこれが原因であった。

署名検証

ボブがアリスの署名を検証するためには、アリスの公開鍵 $Q_{A}$ が必要である。公開鍵 $Q_{A}$ が正当なものであるかの検証は以下のとおりである。

1. $Q_{A}$ が $O$ でないことを確認する。
2. $Q_{A}$ が曲線上にあることを確認する。
3. $n*Q_{A}=O$ であることを確認する。

メッセージ $m$ と署名 $(r,s)$ の検証は以下のように行われる。

1. $r$ および $s$ がいずれも $[1,n-1]$ の範囲にある整数であることを確認する。これを満たさない場合には署名は不正なものである。
2. $e=H(m)$ を計算する。ここで H は署名生成に用いられたハッシュ関数と同一のものである。
3. $z$ を、$e$ の最上位側の $l_{n}$ ビットとする。
4. $s^{-1}$ を計算する。
5. $u_{1}=zs^{-1}\,{\bmod {\,}}n$ および $u_{2}=rs^{-1}\,{\bmod {\,}}n$ を計算する。
6. 曲線上の点 $(x_{1},y_{1})=u_{1}*G+u_{2}*Q_{A}$ を計算する。
7. $r\equiv x_{1}{\pmod {n}}$ であれば署名は正当なものである。

Straus's algorithm（Shamir's trickとも）を用いることで、2つの楕円曲線上での掛け算の和 $u_{1}*G+u_{2}*Q_{A}$ を、2つの楕円曲線上での掛け算よりも速く計算することができる。

署名検証アルゴリズムの説明

メッセージ $m$ に対する署名 $(r,s)$ が、秘密鍵 $d_{A}$ の値を知っている者によって正しく生成されたものと仮定する。

$C$ を署名検証のステップ6で得られた点$(x_{1},y_{1})$とする。つまり、

$C=u_{1}*G+u_{2}*Q_{A}$

公開鍵が $Q_{A}=d_{A}*G$ と定義されているので

$C=u_{1}*G+u_{2}d_{A}*G$

楕円曲線上での掛け算より

$C=(u_{1}+u_{2}d_{A})*G$

署名検証のステップ5から

$C=(zs^{-1}+rd_{A}s^{-1})*G$

$s^{-1}$ を外に出して

$C=(z+rd_{A})s^{-1}*G$

$s^{-1}=(k^{-1}(z+rd_{A}))^{-1}=k(z+rd_{A})^{-1}\,{\bmod {\,}}n$

$C=(z+rd_{A})(z+rd_{A})^{-1}k*G$

$(z+rd_{A})^{-1}$は有限体$\mathbf {F} _{n}$ における $(z+rd_{A})$ の逆元であるから $(z+rd_{A})(z+rd_{A})^{-1}=1\,{\bmod {\,}}n$ である。これから

$C=(x_{1},y_{1})=k*G$

署名の作成者は、1回秘密鍵 $k$ の値を自分で決めて、署名生成のステップ4とステップ5によって $r$ の値を求めるまでのことは秘密鍵 $d_{A}$ の値を知らなくても可能であるが、$d_{A}$ の値を知らない場合は、署名生成のステップ6の $s$ の値を正しく決めることはできない。

署名検証のステップ7、つまり $r\equiv x_{1}{\pmod {n}}$ が成立するということは、上記の最後の式が成立しているということであり、これは署名の作成者は、$s$ の値を正しく決めていたことを意味する。このためには署名の作成者は $d_{A}$ の値を知っている必要があり、最初の仮定「署名の作成者は秘密鍵 $d_{A}$ の値を知っている」が肯定されることになる。

なお、以上は秘密鍵 $d_{A}$ の値を知っている者が、正しく署名したメッセージは、正しく検証されるということを示しているが、秘密鍵 $d_{A}$ の値を知っている者が、本当にアリスであるかは別問題である。例えば前述のように、異なるメッセージに対して、同一の1回秘密鍵 $k$ を用いて署名した場合、 $k$ の値を解読されて、さらにこれから $d_{A}$ の値も解読されることになる。

セキュリティ

2010年12月、fail0verflowと名乗るグループが、ソニーがPlayStation 3のソフトウェア署名に用いていたECDSA秘密鍵の回復に成功したと発表した。しかし、これは $k$ をランダムではなく固定値としていたソニーの不適切な実装によるものであり、アルゴリズム自体の脆弱性ではない。署名生成のセクションで述べたように、$k$ を固定値で用いることは秘密鍵 $d_{A}$ を計算可能とし、アルゴリズムを破綻させるものである。

2011年3月29日、2人の研究者による論文がIACRに発表された。この論文では、サイドチャネル攻撃の一つであるタイミング攻撃によって、ECDSAを認証に利用し、OpenSSLを用いたサーバのTLS秘密鍵を入手可能であることが示された。この脆弱性はOpenSSL 1.0.0eで修正された。

2013年8月、Java class SecureRandomのいくつかの実装において、$k$ のコリジョンが発生することがあるバグが明らかとなった。前述のように、これにより秘密鍵を得ることが可能であり、Javaを利用しECDSAを認証に用いていたAndroidアプリからBitcoinが盗まれる危険性があった。この問題は独立提出のRFC 6979にあるように、秘密鍵とメッセージハッシュから決定論的に $k$ を導くことで回避できる。

2015年1月、Bitcoinのウォレットが完全にオフラインであっても、ECDSAを利用したトランザクションのデジタル署名を通して秘密鍵が漏洩される可能性があることを示す研究論文がarXivにて発表された。この論文では、利用ユーザー側がECDSAおよびビットコインの実装を完全に検証できない限り信頼できないことから、ソースコードの検証からコンパイルといったユーザー側の敷居が高くなるため、プライベートキー漏洩の攻撃を防ぐための実質的な解決策が現段階でないと結論付けている。

このアルゴリズムは楕円曲線をパラメータとして必要とするが、多くの場合NISTによって定められた楕円曲線（P-256、P-384、P-521など）が用いられる。これらの曲線は特定のシード値からSHA-1を基盤としたアルゴリズムを用いて算出されているが、シード値の根拠が不明であること、また同じく固定の楕円曲線を用いたアルゴリズムであるDual_EC_DRBGにNSAがバックドアを仕込んだ上でRSAセキュリティ社のセキュリティ製品に採用させたと報道されたことから、疑いの目で見られることがある。

実装ライブラリ

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