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

暗号化において、楕円曲線デジタル署名アルゴリズム( ECDSA ) は、楕円曲線暗号化を使用するデジタル署名アルゴリズム(DSA)のバリエーションを提供します。

一般的な楕円曲線暗号と同様に、 ECDSA に必要と考えられる秘密鍵のビットサイズは、セキュリティレベルのサイズ（ ビット単位）の約 2 倍です。^[1]たとえば、セキュリティレベルが 80 ビットの場合（つまり、攻撃者が秘密鍵を見つけるために最大で約 回の操作が必要になる場合）、ECDSA 秘密鍵のサイズは 160 ビットになります。一方、署名のサイズは DSA と ECDSA の両方で同じで、約ビットです（ は式 の指数です）。つまり、セキュリティレベルが 80 ビットの場合は約 320 ビットで、これは 操作に相当します。 ${\displaystyle 2^{80}}$${\displaystyle 4t}$${\displaystyle t}$${\displaystyle 2^{t}}$${\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. を計算します。(ここで、HASH はSHA-2などの暗号ハッシュ関数であり、出力は整数に変換されます。)${\displaystyle e={\textrm {HASH}}(m)}$
2. を の左端のビットとし、を群位数のビット長とします。( は より大きくなることはあっても より長くはならないことに注意してください。[ 2 ^] )${\displaystyle z}$${\displaystyle L_{n}}$${\displaystyle e}$${\displaystyle L_{n}}$${\displaystyle n}$${\displaystyle z}$${\displaystyle n}$
3. から暗号的に安全なランダムな整数を選択します。${\displaystyle k}$${\displaystyle [1,n-1]}$
4. 曲線点を計算します。${\displaystyle (x_{1},y_{1})=k\times G}$
5. を計算します。 の場合は、手順 3 に戻ります。${\displaystyle r=x_{1}\,{\bmod {\,}}n}$${\displaystyle r=0}$
6. を計算します。 の場合は、手順 3 に戻ります。${\displaystyle s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n}$${\displaystyle s=0}$
7. 署名は のペアです。(も有効な署名です。)${\displaystyle (r,s)}$${\displaystyle (r,-s\,{\bmod {\,}}n)}$

標準規格で述べられているように、 が秘密であることが要求されるだけでなく、異なる署名には異なる を選択することも重要です。そうでない場合、ステップ 6 の方程式は、秘密鍵 について解くことができます。2 つの署名 および があり、異なる既知のメッセージおよびに同じ未知数 を使用すると、攻撃者はおよび を計算できます。また、(この段落のすべての演算は を法として行われます) ため、攻撃者は を見つけることができます。 であるため、攻撃者は秘密鍵 を計算できます。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle d_{A}}$${\displaystyle (r,s)}$${\displaystyle (r,s')}$${\displaystyle k}$${\displaystyle m}$${\displaystyle m'}$${\displaystyle z}$${\displaystyle z'}$${\displaystyle ss'=k^{-1}(zz')}$${\displaystyle n}$${\displaystyle k={\frac {zz'}{ss'}}}$${\displaystyle s=k^{-1}(z+rd_{A})}$${\displaystyle d_{A}={\frac {sk-z}{r}}}$

この実装の失敗は、例えば、PlayStation 3ゲーム機に使用される署名キーを抽出するために使用されました。^[3]

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

各メッセージごとに一意であることを保証するには、乱数生成を完全にバイパスし、メッセージと秘密鍵の両方から決定論的な署名を生成することができます。^[5]${\displaystyle k}$${\displaystyle k}$

ボブがメッセージ上のアリスの署名を認証するには、アリスの公開鍵曲線点のコピーが必要です。ボブは次のようにして、有効な曲線点であることを確認できます。 ${\displaystyle r,s}$${\displaystyle m}$${\displaystyle Q_{A}}$${\displaystyle Q_{A}}$

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

その後、ボブは次の手順を実行します。

1. rとsが整数であることを確認します。そうでない場合、署名は無効です。${\displaystyle [1,n-1]}$
2. を計算します。ここで、HASH は署名生成で使用される関数と同じです。${\displaystyle e={\textrm {HASH}}(m)}$
3. eの左端のビットを とします。${\displaystyle z}$${\displaystyle L_{n}}$
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}}}$

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

検証が正しく機能する理由はすぐには分かりません。その理由を理解するために、検証のステップ5で計算された曲線点 をCとします。

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

公開鍵の定義は であり、 ${\displaystyle Q_{A}=d_{A}\times G}$

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

楕円曲線のスカラー乗算は加算に対して分配されるので、

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

検証ステップ4からの定義を拡張し、 ${\displaystyle u_{1}}$${\displaystyle u_{2}}$

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

共通用語を収集し、 ${\displaystyle s^{-1}}$

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

署名ステップ6から sの定義を拡張すると、

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

逆元の逆元は元の元であり、元の逆元と元の積は単位元なので、

${\displaystyle C=k\times G}$

rの定義から、これは検証ステップ 6 です。

これは、正しく署名されたメッセージが正しく検証されることを示しているだけです。安全な署名アルゴリズムには、誤って署名されたメッセージが正しく検証されないことや、暗号解読攻撃に対する耐性などの他の特性が必要です。

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

1. rとsが整数であることを確認します。そうでない場合、署名は無効です。${\displaystyle [1,n-1]}$
2. が、、などのいずれかであり（が曲線のフィールドに対して大きすぎない場合）、 が曲線方程式が満たされるような値である曲線点を計算します。これらの条件を満たす曲線点が複数ある場合があり、異なるR値ごとに異なる回復キーが生成されることに注意してください。${\displaystyle R=(x_{1},y_{1})}$${\displaystyle x_{1}}$${\displaystyle r}$${\displaystyle r+n}$${\displaystyle r+2n}$${\displaystyle x_{1}}$${\displaystyle y_{1}}$
3. を計算します。ここで、HASH は署名生成で使用される関数と同じです。${\displaystyle e={\textrm {HASH}}(m)}$
4. z をeの左端のビットとします。${\displaystyle L_{n}}$
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ポイントをすべて試しても、どれも Alice の公開鍵と一致しない場合、署名は無効になります。

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

回復ステップ6の定義から始めます。 ${\displaystyle Q_{A}}$

${\displaystyle Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R}$

署名ステップ4の 定義から、${\displaystyle R=(x_{1},y_{1})=k\times G}$

${\displaystyle Q_{A}=u_{1}\times G+u_{2}k\times G}$

楕円曲線のスカラー乗算は加算に対して分配されるので、

${\displaystyle Q_{A}=(u_{1}+u_{2}k)\times G}$

回復ステップ5 の定義を拡張し、${\displaystyle u_{1}}$${\displaystyle u_{2}}$

${\displaystyle Q_{A}=(-zr^{-1}+skr^{-1})\times G}$

署名ステップ6から sの定義を拡張すると、

${\displaystyle Q_{A}=(-zr^{-1}+k^{-1}(z+rd_{A})kr^{-1})\times G}$

元の逆元と元の積は単位元なので、

${\displaystyle Q_{A}=(-zr^{-1}+(zr^{-1}+d_{A}))\times G}$

第一項と第二項は互いに打ち消し合い、

${\displaystyle Q_{A}=d_{A}\times G}$

の定義から、これはアリスの公開鍵です。 ${\displaystyle Q_{A}=d_{A}\times G}$

これは、署名値rから曲線点を一意に計算するための追加情報が共有されていれば、正しく署名されたメッセージによって正しい公開鍵が復元されることを示しています。 ${\displaystyle R=(x_{1},y_{1})}$

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

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

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

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

ECDSA に関して表明された懸念事項:

1. 政治的な懸念：NSAがソフトウェア、ハードウェアコンポーネント、公開された標準にバックドアを意図的に挿入していることが明らかになった後、 NISTが作成した曲線の信頼性が疑問視されています。著名な暗号学者^[13]はNIST曲線の設計方法について疑問を表明しており^{[14] [15]}、意図的な汚染は過去にすでに証明されています。^{[16] [17]}（libssh curve25519の紹介も参照してください。^[18]）しかし、名前の付いたNIST曲線がまれな弱点を悪用しているという証明はまだありません。
2. 技術的な懸念：標準を適切に実装することの難しさ、その遅さ、防御が不十分な実装でセキュリティを低下させる設計上の欠陥。^[19]

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

• ぼたん
• バウンシーキャッスル
• クリプトライブラリ
• 暗号++
• 暗号 API (Linux)
• TLS の
• libgcrypt
• リブレSSL
• mbed TLS
• Microsoft 暗号化 API
• オープンSSL
• ウルフクリプト

• エドDSA
• 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 年。
• ダニエル RL ブラウン、「ジェネリック グループ、衝突耐性、ECDSA」、デザイン、コード、暗号化、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 に関する詳細なガイドを提供します。ウェイバック リンク