エドワーズ曲線デジタル署名アルゴリズム
エドワーズ曲線デジタル署名アルゴリズム（EdDSA）は、公開鍵[[暗号]]におけるデジタル署名方式の一つで、ツイステッドエドワーズ曲線に基づいたシュノア署名の一種を使用しています。このアルゴリズムは、他のデジタル署名方式で見られるセキュリティ上の問題を回避しつつ、効率的な暗号化処理を実現するように設計されています。
EdDSAは、特定のパラメータセットを使用します。以下に主なパラメータを説明します。
Fq: 有限体であり、位数は奇素数のべき乗であるqで表されます。
E(Fq): Fq上の楕円曲線です。この曲線の位数は、大きな素数ℓと自然数cを用いて、#E(Fq) = 2^c ℓと表現されます。
B: ベースポイントであり、位数がℓである楕円曲線上の点です。
H: 2bビットの出力を生成するハッシュ関数です。ここで、bは2^(b-1) > qを満たす整数です。このため、Fqと楕円曲線上の点はbビットで表現できます。
これらのパラメータは、EdDSAを使用する全てのユーザーで共有されます。ベースポイントBの選択は任意ですが、他のパラメータの選択はEdDSAの安全性に影響を与えます。特に、ℓは、離散対数問題が現実的に解けないように十分に大きな値（通常は2^200より大きい値）が選択されます。
ℓの選択はqによって制限され、ハッセの定理により、#E(Fq) = 2^c ℓ はq+1から2√q以上離れることができません。ハッシュ関数Hは、セキュリティ解析においてランダムオラクルとして扱われます。HashEdDSAでは、Hに加えて、衝突耐性を持つハッシュ関数H'も必要になります。
以下に、EdDSAの鍵生成、署名生成、および検証の具体的な手順を示します。
署名鍵: 一様ランダムに選択されたbビット列k。
公開鍵: 署名鍵kから計算される値。まず、s = H0,…,b-1(k)を計算し、楕円曲線上の点A = sBを公開鍵とします。
署名: メッセージMに対する署名は、楕円曲線上の点Rと、ℓ未満の正整数Sのペア(R,S)で表されます。署名生成には、kからk' = Hb,…,2b-1(k)を計算し、r = H(k' || M) を計算します。次に、R = rBとS = r + H(R || A || M)s mod ℓ を計算します。
署名検証: 次の式が成り立つことを確認します：2^c SB = 2^c R + 2^c H(R || A || M)A
この検証式は、署名が正しく生成されていれば必ず成立します。
Ed25519は、EdDSAの具体的な実装の一つであり、ハッシュ関数にSHA-512、曲線にCurve25519を使用しています。パラメータは次の通りです。
q = 2^255 - 19
E(Fq): -x^2 + y^2 = 1 - (121665/121666)x^2y^2で表されるツイステッドエドワーズ曲線。
ℓ = 2^252 + 27742317777372353535851937790883648493
c = 3
B: y座標が4/5でx座標が正であるE(Fq)上の点。
* H: SHA-512、b = 256
Curve25519はモンゴメリ型の楕円曲線と双有理同値です。
Ed25519はx86-64プロセッサ向けに最適化されており、複数の署名をまとめて処理することでスループットを向上させることができます。128ビットの安全性を持つ共通鍵[[暗号]]と同等の攻撃耐性を目指して設計されており、公開鍵は256ビット、署名は512ビットです。
Ed25519は、秘密データに依存した分岐命令や配列参照を使用していないため、サイドチャネル攻撃に対する耐性があります。また、署名生成時にnonceを秘密鍵とメッセージのハッシュ値から確定的に生成することで、脆弱な乱数生成による秘密鍵の漏洩リスクを排除しています。
EdDSAには、IETFのRFC 8032とNISTのFIPS 186-5という2つの標準化が存在します。これらの標準間にはいくつかの違いが報告されており、テストベクタも利用可能です。
Ed25519は、OpenSSH、GnuPG、OpenBSDのsignifyなど、多くのソフトウェアで利用されています。リファレンス実装はSUPERCOPで提供され、NaCl、CryptoNote、wolfSSL、OpenSSLなどのライブラリにも実装されています。
Ed448は、ハッシュ関数にSHAKE256、曲線にCurve448を使用したEdDSAの実装です。RFC 8032に定義され、FIPS 186-5の草稿でも推奨されています。
EdDSAの概要
EdDSAは、特定のパラメータセットを使用します。以下に主なパラメータを説明します。
Fq: 有限体であり、位数は奇素数のべき乗であるqで表されます。
E(Fq): Fq上の楕円曲線です。この曲線の位数は、大きな素数ℓと自然数cを用いて、#E(Fq) = 2^c ℓと表現されます。
B: ベースポイントであり、位数がℓである楕円曲線上の点です。
H: 2bビットの出力を生成するハッシュ関数です。ここで、bは2^(b-1) > qを満たす整数です。このため、Fqと楕円曲線上の点はbビットで表現できます。
これらのパラメータは、EdDSAを使用する全てのユーザーで共有されます。ベースポイントBの選択は任意ですが、他のパラメータの選択はEdDSAの安全性に影響を与えます。特に、ℓは、離散対数問題が現実的に解けないように十分に大きな値（通常は2^200より大きい値）が選択されます。
ℓの選択はqによって制限され、ハッセの定理により、#E(Fq) = 2^c ℓ はq+1から2√q以上離れることができません。ハッシュ関数Hは、セキュリティ解析においてランダムオラクルとして扱われます。HashEdDSAでは、Hに加えて、衝突耐性を持つハッシュ関数H'も必要になります。
鍵生成、署名生成、検証
以下に、EdDSAの鍵生成、署名生成、および検証の具体的な手順を示します。
署名鍵: 一様ランダムに選択されたbビット列k。
公開鍵: 署名鍵kから計算される値。まず、s = H0,…,b-1(k)を計算し、楕円曲線上の点A = sBを公開鍵とします。
署名: メッセージMに対する署名は、楕円曲線上の点Rと、ℓ未満の正整数Sのペア(R,S)で表されます。署名生成には、kからk' = Hb,…,2b-1(k)を計算し、r = H(k' || M) を計算します。次に、R = rBとS = r + H(R || A || M)s mod ℓ を計算します。
署名検証: 次の式が成り立つことを確認します：2^c SB = 2^c R + 2^c H(R || A || M)A
この検証式は、署名が正しく生成されていれば必ず成立します。
Ed25519
Ed25519は、EdDSAの具体的な実装の一つであり、ハッシュ関数にSHA-512、曲線にCurve25519を使用しています。パラメータは次の通りです。
q = 2^255 - 19
E(Fq): -x^2 + y^2 = 1 - (121665/121666)x^2y^2で表されるツイステッドエドワーズ曲線。
ℓ = 2^252 + 27742317777372353535851937790883648493
c = 3
B: y座標が4/5でx座標が正であるE(Fq)上の点。
* H: SHA-512、b = 256
Curve25519はモンゴメリ型の楕円曲線と双有理同値です。
Ed25519の性能と安全性
Ed25519はx86-64プロセッサ向けに最適化されており、複数の署名をまとめて処理することでスループットを向上させることができます。128ビットの安全性を持つ共通鍵[[暗号]]と同等の攻撃耐性を目指して設計されており、公開鍵は256ビット、署名は512ビットです。
Ed25519は、秘密データに依存した分岐命令や配列参照を使用していないため、サイドチャネル攻撃に対する耐性があります。また、署名生成時にnonceを秘密鍵とメッセージのハッシュ値から確定的に生成することで、脆弱な乱数生成による秘密鍵の漏洩リスクを排除しています。
標準化と実装の矛盾
EdDSAには、IETFのRFC 8032とNISTのFIPS 186-5という2つの標準化が存在します。これらの標準間にはいくつかの違いが報告されており、テストベクタも利用可能です。
ソフトウェアでの利用
Ed25519は、OpenSSH、GnuPG、OpenBSDのsignifyなど、多くのソフトウェアで利用されています。リファレンス実装はSUPERCOPで提供され、NaCl、CryptoNote、wolfSSL、OpenSSLなどのライブラリにも実装されています。
Ed448
Ed448は、ハッシュ関数にSHAKE256、曲線にCurve448を使用したEdDSAの実装です。RFC 8032に定義され、FIPS 186-5の草稿でも推奨されています。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。