楕円曲線デジタル署名アルゴリズム

暗号学において、楕円曲線デジタル署名アルゴリズム（ECDSA ）は、楕円曲線暗号を使用するデジタル署名アルゴリズム（DSA）の変種を提供する。

楕円曲線暗号全般と同様に、ECDSAに必要な秘密鍵のビットサイズは、セキュリティレベルの約2倍（ビット単位）であると考えられています。^{[ 1 ]}例えば、セキュリティレベルが80ビットの場合、攻撃者は最大で約${\displaystyle 2^{80}}$秘密鍵を見つけるための操作— ECDSA の秘密鍵のサイズは 160 ビットになります。一方、署名のサイズは DSA と ECDSA の両方で同じです。約${\displaystyle 4t}$ビット、${\displaystyle t}$は、式中の指数です。${\displaystyle 2^{t}}$つまり、セキュリティレベル80ビットの場合、約320ビットとなり、これは${\displaystyle 2^{80}}$業務。

アリスがボブに署名付きメッセージを送りたいとします。まず、二人は曲線パラメータについて合意する必要があります。${\displaystyle ({\textrm {CURVE}},G,n)}$曲線の場と方程式に加えて、${\displaystyle G}$曲線上の素数位数の基点。${\displaystyle n}$は点の加法的な次数です${\displaystyle G}$。

注文${\displaystyle n}$基点の${\displaystyle G}$は素数でなければならない。実際、環のすべての非零要素は素数であると仮定する。${\displaystyle \mathbb {Z} /n\mathbb {Z} }$は可逆なので、${\displaystyle \mathbb {Z} /n\mathbb {Z} }$フィールドでなければならない。それは、${\displaystyle n}$素数でなければならない（ベズーの恒等式を参照）。

アリスは秘密鍵と整数からなる鍵ペアを作成する。${\displaystyle d_{A}}$区間内でランダムに選択${\displaystyle [1,n-1]}$公開鍵曲線ポイント${\displaystyle Q_{A}=d_{A}\times G}$. 私たちは使用します${\displaystyle \times }$楕円曲線上の点のスカラー倍を表す。

アリスがメッセージに署名するために${\displaystyle m}$彼女は以下の手順に従います。

1. 計算する${\displaystyle e={\textrm {HASH}}(m)}$（ここでいうHASHとは、 SHA-2などの暗号学的ハッシュ関数であり、その出力は整数に変換されます。）
2. させて${\displaystyle z}$になる${\displaystyle L_{n}}$左端のビット${\displaystyle e}$、 どこ${\displaystyle L_{n}}$グループオーダーのビット長${\displaystyle n}$。 （ご了承ください${\displaystyle z}$より大きい可能性がある${\displaystyle n}$しかし、それ以上ではない。^{[ 2 ]}）
3. 暗号的に安全な乱数を選択してください${\displaystyle k}$から${\displaystyle [1,n-1]}$。
4. 曲線の点を計算する${\displaystyle (x_{1},y_{1})=k\times G}$。
5. 計算する${\displaystyle r=x_{1}\,{\bmod {\,}}n}$。 もし${\displaystyle r=0}$ステップ3に戻ってください。
6. 計算する${\displaystyle s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n}$。 もし${\displaystyle s=0}$ステップ3に戻ってください。
7. 署名はペアです${\displaystyle (r,s)}$。 （そして${\displaystyle (r,-s\,{\bmod {\,}}n)}$（これも有効な署名です。）

規格に記載されているように、${\displaystyle k}$秘密にしておくことも重要ですが、異なる選択をすることも重要です${\displaystyle k}$異なる署名の場合。そうでない場合は、ステップ 6 の方程式を解くことができます。${\displaystyle d_{A}}$秘密鍵: 2 つの署名が与えられた場合${\displaystyle (r,s)}$そして${\displaystyle (r,s')}$同じ未知のものを使用し${\displaystyle k}$既知のさまざまなメッセージ${\displaystyle m}$そして${\displaystyle m'}$攻撃者は計算できる${\displaystyle z}$そして${\displaystyle z'}$、そして${\displaystyle s-s'=k^{-1}(z-z')}$（この段落のすべての演算はモジュロ演算で行われます）${\displaystyle n}$攻撃者は${\displaystyle k={\frac {z-z'}{s-s'}}}$。 以来${\displaystyle s=k^{-1}(z+rd_{A})}$攻撃者は秘密鍵を計算できるようになる${\displaystyle d_{A}={\frac {sk-z}{r}}}$。

この実装上の欠陥は、例えばPlayStation 3ゲーム機で使用される署名キーを抽出するために利用された。^{[ 3 ]}

ECDSA署名で秘密鍵が漏洩するもう1つの方法は、${\displaystyle k}$これは、欠陥のある乱数生成器によって生成されたものです。このような乱数生成の失敗により、2013年8月にAndroid Bitcoin Walletのユーザーが資金を失いました。^{[ 4 ]}

確実にするために${\displaystyle k}$各メッセージごとに固有であるため、乱数生成を完全に回避し、決定論的な署名を導出することができます。${\displaystyle k}$メッセージと秘密鍵の両方から。^{[ 5 ]}

ボブがアリスの署名を認証するために${\displaystyle r,s}$メッセージについて${\displaystyle m}$彼は彼女の公開鍵曲線ポイントのコピーを持っている必要がある${\displaystyle Q_{A}}$ボブが確認できる${\displaystyle Q_{A}}$有効な曲線点は以下のとおりです。

1. 確認してみてください${\displaystyle Q_{A}}$は単位元Oとは等しくなく、その座標はそれ以外は有効である。
2. 確認してみてください${\displaystyle Q_{A}}$曲線上に位置する。
3. 確認してみてください${\displaystyle n\times Q_{A}=O}$。

その後、ボブは以下の手順に従います。

1. rとsが整数であることを確認してください。${\displaystyle [1,n-1]}$そうでない場合、署名は無効です。
2. 計算する${\displaystyle e={\textrm {HASH}}(m)}$ここで、HASHは署名生成で使用される関数と同じものです。
3. させて${\displaystyle z}$になる${\displaystyle L_{n}}$eの左端のビット。
4. 計算する${\displaystyle u_{1}=zs^{-1}\,{\bmod {\,}}n}$そして${\displaystyle u_{2}=rs^{-1}\,{\bmod {\,}}n}$。
5. 曲線の点を計算する${\displaystyle (x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}}$。 もし${\displaystyle (x_{1},y_{1})=O}$その場合、署名は無効です。
6. 署名が有効であるのは、${\displaystyle r\equiv x_{1}{\pmod {n}}}$それ以外の場合は無効です。

効率的な実装では逆数を計算することに注意してください${\displaystyle s^{-1}\,{\bmod {\,}}n}$一度だけ。また、シャミアのトリックを使用すると、2 つのスカラー乗算の和${\displaystyle u_{1}\times G+u_{2}\times Q_{A}}$2 つのスカラー乗算を個別に行うよりも速く計算できる。^{[ 6 ]}

メッセージmとアリスの署名が与えられた場合${\displaystyle r,s}$そのメッセージから、ボブは（潜在的に）アリスの公開鍵を復元できる。^{[ 7 ]}

1. rとsが整数であることを確認してください。${\displaystyle [1,n-1]}$そうでない場合、署名は無効です。
2. 曲線上の点を計算する${\displaystyle R=(x_{1},y_{1})}$どこ${\displaystyle x_{1}}$は${\displaystyle r}$、${\displaystyle r+n}$、${\displaystyle r+2n}$など（提供）${\displaystyle x_{1}}$曲線の領域に対して大きすぎず、${\displaystyle y_{1}}$は、曲線方程式を満たす値です。これらの条件を満たす曲線上の点は複数存在する可能性があり、Rの値が異なると、それぞれ異なる復元鍵が得られることに注意してください。
3. 計算する${\displaystyle e={\textrm {HASH}}(m)}$ここで、HASHは署名生成で使用される関数と同じものです。
4. zを​${\displaystyle L_{n}}$eの左端のビット。
5. 計算する${\displaystyle u_{1}=-zr^{-1}\,{\bmod {\,}}n}$そして${\displaystyle u_{2}=sr^{-1}\,{\bmod {\,}}n}$。
6. 曲線の点を計算する${\displaystyle Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R}$。
7. 署名が有効であるのは、${\displaystyle Q_{A}}$アリスの公開鍵と一致します。
8. 考えられるすべてのRポイントを試しても、アリスの公開鍵と一致するものが見つからない場合、署名は無効となります。

無効な署名、または別のメッセージの署名を使用した場合、誤った公開鍵が復元されることに注意してください。復元アルゴリズムは、署名者の公開鍵（またはそのハッシュ値）が事前にわかっている場合にのみ、署名の有効性を確認するために使用できます。

2010年12月、 fail0verflowと名乗るグループが、PlayStation 3ゲーム機のソフトウェア署名にソニーが使用していたECDSA秘密鍵の復元を発表した。しかし、この攻撃が成功したのは、ソニーがアルゴリズムを適切に実装していなかったためである。${\displaystyle k}$ランダムではなく静的でした。上記の署名生成アルゴリズムのセクションで指摘したように、これにより${\displaystyle d_{A}}$解決可能であり、アルゴリズム全体が無意味になる。^{[ 8 ]}

2011年3月29日、2人の研究者がIACR論文^{[ 9 ]}を発表し、タイミング攻撃によってバイナリ体上の楕円曲線DSAで認証するOpenSSLを使用するサーバーのTLS秘密鍵を取得できることを示した^{[ 10 ]}。この脆弱性はOpenSSL 1.0.0fで修正された^{[ 11 ]。}

2013年8月、JavaクラスSecureRandomの一部の実装におけるバグにより、衝突が発生することがあることが明らかになった。${\displaystyle k}$価値。これにより、ハッカーは秘密鍵を復元し、正当な鍵の所有者が持っていたのと同じビットコイン取引の制御権を得ることができました。これは、Javaを使用し、取引の認証にECDSAに依存する一部のAndroidアプリ実装でPS3署名鍵を明らかにするために使用されたのと同じエクスプロイトを使用しています。^{[ 12 ]}

この問題は、RFC 6979で説明されているように、kを決定論的に生成することで回避できます。

以下は、ECDSAをサポートする暗号ライブラリの一覧です。

• ボタン
• バウンシーキャッスル
• cryptlib
• クリプト++
• 暗号化API（Linux）
• GnuTLS
• libgcrypt
• LibreSSL
• mbed TLS
• Microsoft CryptoAPI
• OpenSSL
• wolfCrypt

• EdDSA
• RSA（暗号システム）

• 認定標準委員会X9、ASC X9が公開鍵暗号/ECDSAの新標準を発行、2020年10月6日。出典
• 認定標準委員会X9、米国国家規格 X9.62-2005、金融サービス業界向け公開鍵暗号、楕円曲線デジタル署名アルゴリズム (ECDSA)、2005 年 11 月 16 日。
• Certicom Research、「効率的な暗号化のための標準規格、SEC 1：楕円曲線暗号」、バージョン2.0、2009年5月21日。
• López, J. および Dahab, R. 「楕円曲線暗号の概要」、技術報告書 IC-00-10、カンピーナス州立大学、2000 年。
• Daniel J. Bernstein、「Pippengerのべき乗アルゴリズム」、2002年。
• Daniel RL Brown、「汎用グループ、衝突耐性、および ECDSA」、Designs, Codes and Cryptography、35、119–152、2005年 。ePrint版
• Ian F. Blake、Gadiel Seroussi、Nigel Smart編、『Advances in Elliptic Curve Cryptography』、ロンドン数学会講義ノートシリーズ 317、ケンブリッジ大学出版局、2005 年。
• Hankerson, D.; Vanstone, S. ; Menezes, A. (2004).楕円曲線暗号入門. Springer Professional Computing. ニューヨーク: Springer . doi : 10.1007/b97644 . ISBN 0-387-95273-X. S2CID 720546 . 

• デジタル署名規格。ECDSAに関する情報を含む。
• 楕円曲線デジタル署名アルゴリズム（ECDSA）；ECDSAに関する詳細なガイドを提供します。Waybackリンク