エドワーズ曲線 きょくせん 署名 しょめい （エドワーズきょくせんデジタルしょめいあるごりずむ、英語 えいご Edwards-curve Digital Signature Algorithm 、略称 りゃくしょう EdDSA ）は、公開 こうかい 鍵 かぎ 暗号 あんごう ツイステッドエドワーズ曲線 きょくせん （英語 えいご 版 ばん 基 もと シュノア署名 しょめい （英語 えいご 版 ばん 一種 いっしゅ 用 もち デジタル署名 しょめい の一 ひと [ 1] 他 た 署名 しょめい 見 み 安全 あんぜん 性 せい 関 かん 問題 もんだい 回避 かいひ 上 うえ 高 こう 効率 こうりつ 暗号 あんごう 化 か 処理 しょり 行 おこな 設計 せっけい 曲線 きょくせん 電子 でんし 署名 しょめい ダニエル・バーンスタイン が率 ひき 開発 かいはつ [ 2]
EdDSAのアルゴリズムは以下 いか 表 あらわ 簡単 かんたん 整数 せいすう 曲線 きょくせん 上 じょう 点 てん ビット列 びっとれつ 符号 ふごう 化 か 詳細 しょうさい 省略 しょうりゃく 詳細 しょうさい 引用 いんよう 文献 ぶんけん 参照 さんしょう [ 3] [ 2] [ 1]
EdDSA 方式 ほうしき 次 つぎ 用 もち
F
q
{\displaystyle \mathbb {F} _{q}}
奇 き 素数 そすう
q
{\displaystyle q}
位 い 数 すう 持 も 有限 ゆうげん 体 たい
E
(
F
q
)
{\displaystyle E(\mathbb {F} _{q})}
F
q
{\displaystyle \mathbb {F} _{q}}
上 うえ 楕円 だえん 曲線 きょくせん 位 い 数 すう 大 おお 素数 そすう
ℓ
{\displaystyle \ell }
適当 てきとう 自然 しぜん 数 すう
c
{\displaystyle c}
#
E
(
F
q
)
=
2
c
ℓ
{\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }
表 あらわ 必要 ひつよう
2
c
{\displaystyle 2^{c}}
呼 よ
B
∈
E
(
F
q
)
{\displaystyle B\in E(\mathbb {F} _{q})}
位 い 数 すう
ℓ
{\displaystyle \ell }
楕円 だえん 曲線 きょくせん 上 じょう 点 てん
H
{\displaystyle H}
出力 しゅつりょく
2
b
{\displaystyle 2b}
ハッシュ関数 かんすう 。ただし、
b
{\displaystyle b}
2
b
−
1
>
q
{\displaystyle 2^{b-1}>q}
満 み 整数 せいすう
F
q
{\displaystyle \mathbb {F} _{q}}
楕円 だえん 曲線 きょくせん
E
(
F
q
)
{\displaystyle E(\mathbb {F} _{q})}
上 うえ 点 てん
b
{\displaystyle b}
表 あらわ これらのパラメータは、EdDSA署名 しょめい 方式 ほうしき 全 すべ 共通 きょうつう 使 つか 選択 せんたく 任意 にんい 他 た 選択 せんたく 署名 しょめい 方式 ほうしき 安全 あんぜん 性 せい 大 おお 影響 えいきょう 与 あた 例 たと ポラード・ロー離散 りさん 対数 たいすう を用 もち 離散 りさん 対数 たいすう 計算 けいさん 必要 ひつよう 楕円 だえん 加算 かさん 回数 かいすう
ℓ
π ぱい
/
4
{\displaystyle {\sqrt {\ell \pi /4}}}
回 かい [ 4] 離散 りさん 対数 たいすう 解 と 事実 じじつ 上 じょう
ℓ
{\displaystyle \ell }
十分 じゅうぶん 大 おお 典型 てんけい 的 てき
ℓ
{\displaystyle \ell }
2
200
{\displaystyle 2^{200}}
大 おお 値 ね 用 もち [ 5]
ℓ
{\displaystyle \ell }
選択 せんたく
q
{\displaystyle q}
選択 せんたく 制限 せいげん 受 う Hasseの定理 ていり により、位 い 数 すう
#
E
(
F
q
)
=
2
c
ℓ
{\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }
q
+
1
{\displaystyle q+1}
2
q
{\displaystyle 2{\sqrt {q}}}
以上 いじょう 離 はな 関数 かんすう
H
{\displaystyle H}
安全 あんぜん 性 せい 解析 かいせき 通常 つうじょう ランダムオラクル と想定 そうてい 変種 へんしゅ
H
{\displaystyle H}
加 くわ 衝突 しょうとつ 耐 たい 性 せい （英語 えいご 版 ばん 持 も 関数 かんすう
H
′
{\displaystyle H'}
必要 ひつよう
鍵 かぎ 生成 せいせい 署名 しょめい 生成 せいせい 署名 しょめい 検証 けんしょう 方法 ほうほう 以下 いか 通 とお
∥
{\displaystyle \parallel }
ビット列 びっとれつ 連結 れんけつ 表 あらわ
署名 しょめい 鍵 かぎ 一様 いちよう 選 えら
b
{\displaystyle b}
ビット列 びっとれつ
k
{\displaystyle k}
公開 こうかい 鍵 かぎ 署名 しょめい 鍵 かぎ
k
{\displaystyle k}
s
=
H
0
,
…
,
b
−
1
(
k
)
{\displaystyle s=H_{0,\dots ,b-1}(k)}
値 ち 下位 かい
b
{\displaystyle b}
計算 けいさん 楕円 だえん 曲線 きょくせん 上 じょう 点 てん
A
=
s
B
∈
E
(
F
q
)
{\displaystyle A=sB\in E(\mathbb {F} _{q})}
公開 こうかい 鍵 かぎ
b
{\displaystyle b}
ビット列 びっとれつ 表 あらわ 署名 しょめい メッセージ
M
{\displaystyle M}
対 たい 署名 しょめい 楕円 だえん 曲線 きょくせん 上 じょう 点 てん
R
{\displaystyle R}
ℓ
{\displaystyle \ell }
未 み 満 まん 正 せい 整数 せいすう
S
{\displaystyle S}
(
R
,
S
)
{\displaystyle (R,S)}
表 あらわ 共 とも
b
{\displaystyle b}
表 あらわ 署名 しょめい 長 ちょう
2
b
{\displaystyle 2b}
得 え 署名 しょめい 鍵 かぎ
k
{\displaystyle k}
k
′
=
H
b
,
…
,
2
b
−
1
(
k
)
{\displaystyle k'=H_{b,\dots ,2b-1}(k)}
値 ち 上位 じょうい
b
{\displaystyle b}
計算 けいさん
r
=
H
(
k
′
∥
M
)
{\displaystyle r=H(k'\parallel M)}
計算 けいさん 用 もち 以下 いか 計算 けいさん
R
=
r
B
{\displaystyle R=rB}
S
=
r
+
H
(
R
∥
A
∥
M
)
s
mod
ℓ
{\displaystyle S=r+H(R\parallel A\parallel M)s{\bmod {\ell }}}
署名 しょめい 検証 けんしょう 次 つぎ 式 しき 成 な 立 た 確認 かくにん
2
c
S
B
=
2
c
R
+
2
c
H
(
R
∥
A
∥
M
)
A
{\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A}
署名 しょめい 生成 せいせい 方法 ほうほう 位 い 数 すう
ℓ
2
c
{\displaystyle \ell 2^{c}}
正 まさ 作 つく 署名 しょめい 必 かなら 検証 けんしょう 通 とお
2
c
S
B
=
2
c
(
r
+
H
(
R
∥
A
∥
M
)
s
)
B
=
2
c
r
B
+
2
c
H
(
R
∥
A
∥
M
)
s
B
=
2
c
R
+
2
c
H
(
R
∥
A
∥
M
)
A
.
{\displaystyle {\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}}
Ed25519 は、エドワーズ曲線 きょくせん 署名 しょめい 実装 じっそう 一 ひと 関数 かんすう SHA-512（SHA-2） を使 つか 曲線 きょくせん Curve25519 を用 もち 各 かく 以下 いか 通 とお
−
x
2
+
y
2
=
1
−
121665
121666
x
2
y
2
,
{\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}
ℓ
=
2
252
+
27742317777372353535851937790883648493
{\displaystyle \ell =2^{252}+27742317777372353535851937790883648493}
c
=
3
{\displaystyle c=3}
B
{\displaystyle B}
E
(
F
q
)
{\displaystyle E(\mathbb {F} _{q})}
上 うえ 点 てん
y
{\displaystyle y}
座標 ざひょう
4
/
5
{\displaystyle 4/5}
x
{\displaystyle x}
座標 ざひょう 正 せい 点 てん 正 せい 点 てん 符号 ふごう 化 か ビット列 びっとれつ 次 つぎ 定義 ていぎ "正 せい 座標 ざひょう 偶数 ぐうすう 最下位 さいかい
"負 ふ 座標 ざひょう 奇数 きすう 最下位 さいかい
H
{\displaystyle H}
SHA-512 。したがって
b
=
256
{\displaystyle b=256}
曲線 きょくせん
E
(
F
q
)
{\displaystyle E(\mathbb {F} _{q})}
Curve25519 として知 し モンゴメリ型 がた 楕円 だえん 曲線 きょくせん （英語 えいご 版 ばん 双 そう 有理 ゆうり 同値 どうち 具体 ぐたい 的 てき 同値 どうち
x
=
−
486664
u
/
v
,
y
=
(
u
−
1
)
/
(
u
+
1
)
{\displaystyle x={\sqrt {-486664}}u/v,\quad y=(u-1)/(u+1)}
与 あた [ 2] [ 6]
Ed25519は、x86-64 Nehalem /Westmere （英語 えいご 版 ばん 向 む 最適 さいてき 化 か 検証 けんしょう 個 こ 署名 しょめい 一括 いっかつ 処理 しょり 向上 こうじょう 安全 あんぜん 性 せい 持 も 共通 きょうつう 鍵 かぎ 暗号 あんごう 系 けい 同等 どうとう 攻撃 こうげき 耐 たい 性 せい 提供 ていきょう 目的 もくてき 公開 こうかい 鍵 かぎ 署名 しょめい [ 7]
安全 あんぜん 性 せい 関 かん 秘密 ひみつ 依存 いぞん 分岐 ぶんき 命令 めいれい 配列 はいれつ 参照 さんしょう 用 もち 多 おお サイドチャネル攻撃 こうげき に耐 たい 性 せい
他 た 離散 りさん 対数 たいすう 問題 もんだい 署名 しょめい 方式 ほうしき 同様 どうよう 署名 しょめい 毎 ごと 異 こと nonce と呼 よ 秘密 ひみつ 情報 じょうほう 用 もち DSA とECDSA においては、このnonceは署名 しょめい 生成 せいせい 生成 せいせい 一般 いっぱん 的 てき 脆弱 ぜいじゃく 乱数 らんすう 生成 せいせい 方法 ほうほう 用 もち 推測 すいそく 可能 かのう 署名 しょめい 秘密 ひみつ 鍵 かぎ 情報 じょうほう 漏 も 例 たと PlayStation 3 の署名 しょめい 鍵 かぎ 漏洩 ろうえい 事例 じれい [ 8] [ 9] [ 10]
これに対 たい 秘密 ひみつ 鍵 かぎ 値 ち 確定 かくてい 的 てき 決 き 方法 ほうほう 取 と 秘密 ひみつ 鍵 かぎ 作成 さくせい 後 ご 署名 しょめい 生成 せいせい 時 じ 乱数 らんすう 使 つか 必要 ひつよう 脆弱 ぜいじゃく 乱数 らんすう 生成 せいせい 方法 ほうほう 用 もち 秘密 ひみつ 鍵 かぎ 漏洩 ろうえい 存在 そんざい
EdDSAには2つの標準 ひょうじゅん 化 か 存在 そんざい IETF による RFC 8032 であり、もう1つはNIST によるFIPS 186-5 (2019).[ 11] 標準 ひょうじゅん 間 あいだ 違 ちが 解析 かいせき 既 すで 報告 ほうこく [ 12] [ 13] 利用 りよう 可能 かのう [ 14]
Ed25519の主要 しゅよう 使用 しよう 例 れい OpenSSH , GnuPG とさまざまな代替 だいたい [ 15] OpenBSD で提供 ていきょう 署名 しょめい 署名 しょめい 検証 けんしょう [ 16]
Ed448 は、エドワーズ曲線 きょくせん 署名 しょめい 実装 じっそう 一 ひと 関数 かんすう SHAKE256 を使 つか 曲線 きょくせん Curve448 を用 もち 同様 どうよう RFC 8032 に定義 ていぎ 草稿 そうこう 推奨 すいしょう [ 11]
^ a b Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA) 英語 えいご Internet Engineering Task Force . doi :10.17487/RFC8032 ISSN 2070-1721 . RFC 8032 . 2017年 ねん 月 がつ 日 にち 閲覧 えつらん 。
^ a b c Bernstein, Daniel J. ; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang (2011-09-26) (PDF). High-speed high-security signatures . http://ed25519.cr.yp.to/ed25519-20110926.pdf .
^ Daniel J. Bernstein; Simon Josefsson; Tanja Lange; Peter Schwabe; Bo-Yin Yang (4 July 2015). EdDSA for more curves (PDF) (Technical report). 2016年 ねん 日 にち 閲覧 えつらん 。 ^ Daniel J. Bernstein; Tanja Lange; Peter Schwabe (1 January 2011). On the correct use of the negation map in the Pollard rho method . 2016年 ねん 日 にち 閲覧 えつらん 。 ^ Daniel J. Bernstein. “ECDLP Security: Rho ”. 2016年 ねん 日 にち 閲覧 えつらん ^ Bernstein, Daniel J. ; Lange, Tanja (2007). Faster addition and doubling on elliptic curves . http://eprint.iacr.org/2007/286 . ^ Daniel J. Bernstein (2017年 ねん 月 がつ 日 にち Ed25519: high-speed high-security signatures ”. 2019年 ねん 月 がつ 日 にち 閲覧 えつらん ^ Johnston, Casey (2010年 ねん 日 にち “PS3 hacked through poor cryptography implementation” . Ars Technica . https://arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/ 2016年 ねん 日 にち 閲覧 えつらん ^ fail0verflow (29 December 2010). Console Hacking 2010: PS3 Epic Fail (PDF) . Chaos Communication Congress . 2018年 ねん 月 がつ 日 にち 時点 じてん オリジナル (PDF) よりアーカイブ。2016年 ねん 日 にち 閲覧 えつらん 。 ^ “27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail ”. 2019年 ねん 月 がつ 日 にち 閲覧 えつらん ^ a b “FIPS 186-5 (Draft): Digital Signature Standard (DSS) ”. NIST (October 2019). doi :10.6028/NIST.FIPS.186-5-draft . 2022年 ねん 月 がつ 日 にち 閲覧 えつらん
^ Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko (1 October 2020). Taming the many EdDSAs . 2022年 ねん 月 がつ 日 にち 閲覧 えつらん 。 ^ Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao (3 July 2020). The provable security of ed25519: Theory and practice . 2022年 ねん 月 がつ 日 にち 閲覧 えつらん 。 ^ “ed25519-speccheck ”. 2022年 ねん 月 がつ 日 にち 閲覧 えつらん ^ “Things that use Ed25519 ”. 6 January 2015 閲覧 えつらん ^ “マイナビニュース：OpenBSD、デジタル署名 しょめい 付 つ ”. 2 February 2015 閲覧 えつらん ^ “Alternate implementations ”. 17 November 2014 閲覧 えつらん ^ “wolfSSL Embedded SSL/TLS Library | wolfSSL Products” (日本語 にほんご wolfSSL . https://www.wolfssl.jp/products/wolfssl/ 2018年 ねん 日 にち 閲覧 えつらん ^ https://www.openssl.org/news/cl111.txt
アルゴリズム 理論 りろん 標準 ひょうじゅん 化 か 関連 かんれん 項目 こうもく
カテゴリ
カテゴリ