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

デジタル署名のための暗号化アルゴリズム

暗号化において、楕円曲線デジタル署名アルゴリズム( 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}$

パラメータ
曲線	使用される楕円曲線体と方程式
G	楕円曲線の基点、大きな素数位数nの部分群を生成する曲線上の点
n	Gの整数位は、 （単位元）を意味します。 ${\displaystyle n\times G=O}$ ${\displaystyle O}$
${\displaystyle d_{A}}$	秘密鍵（ランダムに選択）
${\displaystyle Q_{A}}$	公開鍵（楕円曲線で計算） ${\displaystyle d_{A}\times 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 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署名が秘密鍵を漏洩するもう一つの方法は、欠陥のある乱数生成器によって生成された場合です。このような乱数生成の欠陥により、2013年8月にAndroid版ビットコインウォレットのユーザーが資金を失いました。^[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}}}$

効率的な実装では、逆関数の計算は一度だけとなることに注意してください。また、シャミアのトリックを用いると、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）
• GnuTLS
• libgcrypt
• リブレSSL
• mbed TLS
• Microsoft 暗号 API
• オープンSSL
• ウルフクリプト

参照

• エドDSA
• RSA（暗号システム）

参考文献

1. ジョンソン、ドン、メネゼス、アルフレッド (1999). 「楕円曲線デジタル署名アルゴリズム (ECDSA)」. Certicom Research. カナダ. CiteSeerX  10.1.1.38.8014 .
2. 「NIST FIPS 186-4、2013年7月、19ページおよび26ページ」（PDF） 。 2016年12月27日時点のオリジナルよりアーカイブ（PDF） 。 2014年3月17日閲覧。
3. Console Hacking 2010 - PS3 Epic Fail 2014年12月15日アーカイブ、Wayback Machine、123～128ページ
4. “Androidのセキュリティ脆弱性”. 2019年4月7日時点のオリジナルよりアーカイブ。2015年2月24日閲覧。
5. Pornin, T. (2013). RFC 6979 - デジタル署名アルゴリズム（DSA）および楕円曲線デジタル署名アルゴリズム（ECDSA）の決定論的使用法（技術レポート）. doi : 10.17487/RFC6979 . 2015年2月24日閲覧。
6. 「楕円曲線暗号における2基数システム」（PDF） 。 2011年7月26日時点のオリジナルよりアーカイブ（PDF） 。 2014年4月22日閲覧。
7. ダニエル・RL・ブラウンSECG SEC 1: 楕円曲線暗号（バージョン 2.0） https://www.secg.org/sec1-v2.pdf
8. Bendel, Mike (2010年12月29日). 「ハッカーがPS3のセキュリティを大失敗と表現、無制限のアクセスを獲得」Exophase.com. 2019年4月7日時点のオリジナルよりアーカイブ。 2011年1月5日閲覧。
9. “Cryptology ePrint Archive: Report 2011/232”. 2018年12月8日時点のオリジナルよりアーカイブ。2015年2月24日閲覧。
10. 「脆弱性ノート VU#536044 - OpenSSL、リモートタイミング攻撃によりECDSA秘密鍵を漏洩」www.kb.cert.org . 2019年4月7日時点のオリジナルよりアーカイブ。 2011年5月24日閲覧。
11. “ChangeLog”. OpenSSLプロジェクト. 2020年8月9日時点のオリジナルよりアーカイブ。 2014年4月22日閲覧。
12. “AndroidのバグがBitcoinウォレットに打撃を与える”. The Register. 2013年8月12日. 2013年8月15日時点のオリジナルよりアーカイブ。2017年8月27日閲覧。
13. Schneier, Bruce (2013年9月5日). 「NSAはインターネット上のほとんどの暗号化を破っている」. Schneier on Security . 2017年12月15日時点のオリジナルよりアーカイブ。 2018年1月11日閲覧。
14. 「SafeCurves: 楕円曲線暗号のための安全な曲線の選択」 2013年10月25日. 2019年4月7日時点のオリジナルよりアーカイブ。2018年1月11日閲覧。
15. Bernstein, Daniel J.; Lange, Tanja (2013年5月31日). 「NIST曲線のセキュリティ上の危険性」(PDF) . 2019年5月28日時点のオリジナルよりアーカイブ(PDF) . 2018年1月11日閲覧。
16. Schneier, Bruce (2007年11月15日). 「Dual_EC_DRBGの奇妙な物語」. Schneier on Security . 2019年4月23日時点のオリジナルよりアーカイブ。2018年1月11日閲覧。
17. Greenemeier, Larry (2013年9月18日). 「NSAの暗号化技術回避の取り組みが米国の暗号化標準にダメージを与えた」. Scientific American. 2017年12月24日時点のオリジナルよりアーカイブ。 2018年1月11日閲覧。
18. "[email protected]\doc - projects/libssh.git". libssh共有リポジトリ. 2019年3月23日時点のオリジナルよりアーカイブ。 2018年1月11日閲覧。
19. Bernstein, Daniel J. (2014年3月23日). 「楕円曲線署名システムの設計方法」cr.yp.toブログ. 2014年3月23日時点のオリジナルよりアーカイブ。 2018年1月11日閲覧。

さらに読む

• 認定標準委員会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編、『楕円曲線暗号の進歩』、ロンドン数学会講義ノートシリーズ 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に関する詳細なガイドを提供します。ウェイバックリンク

Retrieved from "https://en.wikipedia.org/w/index.php?title=Elliptic_Curve_Digital_Signature_Algorithm&oldid=1301948395"