楕円曲線DSA

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

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

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

DSAとの比較

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

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

署名生成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2つの異なるメッセージ ${\displaystyle m}$ および ${\displaystyle m'}$ に対して、攻撃者にとっては未知だが同じ1回秘密鍵 ${\displaystyle k}$ から得られた2つの署名がある場合、署名生成のステップ4とステップ5から、この2つの署名の ${\displaystyle r}$ も同じ値になる。攻撃者は多数の署名付きメッセージから ${\displaystyle m}$ は異なるが ${\displaystyle r}$ が同じものを選び出す。これらの署名付きメッセージを ${\displaystyle (m,r,s)}$ および ${\displaystyle (m',r,s')}$ とする。攻撃者は ${\displaystyle z}$ および ${\displaystyle z'}$ を計算することが可能であり、${\displaystyle s-s'=k^{-1}(z-z')}$ であることから、${\displaystyle k={\frac {z-z'}{s-s'}}}$ が得られる。${\displaystyle s=k^{-1}(z+rd_{A})}$ であるから、攻撃者は秘密鍵 ${\displaystyle d_{A}={\frac {sk-z}{r}}}$ を得ることができる。

このように単一の ${\displaystyle k}$ を用いることは不適切な実装であり、PlayStation 3のソフトウェア署名鍵が漏洩したのはこれが原因であった^[4]。

署名検証

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

セキュリティ

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

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

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

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

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

実装ライブラリ

ECDSAをサポートしているライブラリは以下の通りである。

• Botan
• Bouncy Castle（英語版）
• cryptlib（英語版）
• Crypto++（英語版）
• libgcrypt（英語版）
• OpenSSL
• GnuTLS
• wolfCrypt