エドワーズ曲線 きょくせん デジタル署名 しょめい アルゴリズム (エドワーズきょくせんデジタルしょめいあるごりずむ、英語 えいご : Edwards-curve Digital Signature Algorithm 、略称 りゃくしょう :EdDSA )は、公開 こうかい 鍵 かぎ 暗号 あんごう において、ツイステッドエドワーズ曲線 きょくせん (英語 えいご 版 ばん ) に基 もと づくシュノア署名 しょめい (英語 えいご 版 ばん ) の一種 いっしゅ を用 もち いたデジタル署名 しょめい の一 ひと つである[ 1] 。他 た のデジタル署名 しょめい において見 み つかっている安全 あんぜん 性 せい に関 かん する問題 もんだい を回避 かいひ した上 うえ で、高 こう 効率 こうりつ で暗号 あんごう 化 か 処理 しょり が行 おこな われるように設計 せっけい されている。エドワーズ曲線 きょくせん 電子 でんし 署名 しょめい アルゴリズムは、ダニエル・バーンスタイン が率 ひき いるチームによって開発 かいはつ された [ 2] 。
EdDSAのアルゴリズムは以下 いか のように表 あらわ すことができる。簡単 かんたん のため、整数 せいすう や曲線 きょくせん 上 じょう の点 てん をどのようにビット列 びっとれつ に符号 ふごう 化 か するかといった詳細 しょうさい は省略 しょうりゃく している。詳細 しょうさい については、引用 いんよう 文献 ぶんけん やRFCを参照 さんしょう のこと[ 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}}
は cofactor と呼 よ ばれる。
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署名 しょめい 方式 ほうしき の全 すべ てのユーザが共通 きょうつう で使 つか うことができる。ベースポイントの選択 せんたく は任意 にんい だが、その他 た のパラメータの選択 せんたく は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}
は、EdDSAの安全 あんぜん 性 せい 解析 かいせき においては通常 つうじょう ランダムオラクル と想定 そうてい される。HashEdDSAという変種 へんしゅ (variant)においては、
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}
座標 ざひょう が正 せい である点 てん 。 ただし、"正 せい "とは、点 てん を符号 ふごう 化 か したビット列 びっとれつ について次 つぎ のように定義 ていぎ される:
"正 せい ":座標 ざひょう が偶数 ぐうすう (最下位 さいかい ビットが0)
"負 ふ ":座標 ざひょう が奇数 きすう (最下位 さいかい ビットが1)
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 (英語 えいご 版 ばん ) プロセッサファミリー向 む けに最適 さいてき 化 か されている。検証 けんしょう は、64個 こ の署名 しょめい を一括 いっかつ で処理 しょり することでよりスループットを向上 こうじょう させることができる。Ed25519 は、128ビット安全 あんぜん 性 せい を持 も つ共通 きょうつう 鍵 かぎ 暗号 あんごう 系 けい と同等 どうとう の攻撃 こうげき 耐 たい 性 せい を提供 ていきょう することを目的 もくてき としている。公開 こうかい 鍵 かぎ は256ビット、署名 しょめい は512ビットである[ 7] 。
安全 あんぜん 性 せい に関 かん しては、Ed25519では、秘密 ひみつ のデータに依存 いぞん した分岐 ぶんき 命令 めいれい と配列 はいれつ 参照 さんしょう が用 もち いられておらず、多 おお くのサイドチャネル攻撃 こうげき に耐 たい 性 せい がある。
他 た の離散 りさん 対数 たいすう 問題 もんだい ベースの署名 しょめい 方式 ほうしき と同様 どうよう に、EdDSAは署名 しょめい 毎 ごと に異 こと なるnonce と呼 よ ばれる秘密 ひみつ 情報 じょうほう が用 もち いられる。DSA とECDSA においては、このnonceは署名 しょめい 生成 せいせい ごとにランダムに生成 せいせい されるのが一般 いっぱん 的 てき である。しかし、もし脆弱 ぜいじゃく な乱数 らんすう 生成 せいせい 方法 ほうほう が用 もち いられてnonceを推測 すいそく 可能 かのう であるときには、署名 しょめい が秘密 ひみつ 鍵 かぎ の情報 じょうほう を漏 も らしてしまう。例 たと えば、ソニーのPlayStation 3 の署名 しょめい 鍵 かぎ が漏洩 ろうえい した事例 じれい がある[ 8] [ 9] [ 10] 。
これに対 たい し、EdDSAでは秘密 ひみつ 鍵 かぎ とメッセージのハッシュ値 ち からnonceを確定 かくてい 的 てき に決 き めるという方法 ほうほう を取 と っている。これにより、秘密 ひみつ 鍵 かぎ をランダムに作成 さくせい すれば、その後 ご の署名 しょめい 生成 せいせい 時 じ には乱数 らんすう を使 つか う必要 ひつよう がなく、脆弱 ぜいじゃく な乱数 らんすう 生成 せいせい 方法 ほうほう を用 もち いることによる秘密 ひみつ 鍵 かぎ の漏洩 ろうえい のリスクが存在 そんざい しない。
EdDSAには2つの標準 ひょうじゅん 化 か が存在 そんざい する。1つはIETF による RFC 8032 であり、もう1つはNIST によるFIPS 186-5 (2019).[ 11] である。これらの標準 ひょうじゅん の間 あいだ の違 ちが いについての解析 かいせき が既 すで に報告 ほうこく されており[ 12] [ 13] 、テストベクタも利用 りよう 可能 かのう である[ 14]
Ed25519の主要 しゅよう な使用 しよう 例 れい には、OpenSSH , GnuPG とさまざまな代替 だいたい ソフトウェア [ 15] 、そして、OpenBSD で提供 ていきょう されているデジタル署名 しょめい ・署名 しょめい 検証 けんしょう ツールsignifyがある [ 16] 。
Ed448 は、エドワーズ曲線 きょくせん デジタル署名 しょめい の実装 じっそう の一 ひと つであり、ハッシュ関数 かんすう としてSHAKE256 を使 つか い、曲線 きょくせん としてCurve448 を用 もち いている。Ed25519と同様 どうよう に、RFC 8032 に定義 ていぎ され、FIPS 186-5の草稿 そうこう において推奨 すいしょう されている[ 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年 ねん 7月 がつ 31日 にち 閲覧 えつらん 。
^ 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年 ねん 11月14日 にち 閲覧 えつらん 。
^ Daniel J. Bernstein; Tanja Lange; Peter Schwabe (1 January 2011). On the correct use of the negation map in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. 2016年 ねん 11月14日 にち 閲覧 えつらん 。
^ Daniel J. Bernstein. “ECDLP Security: Rho ”. 2016年 ねん 11月16日 にち 閲覧 えつらん 。
^ Bernstein, Daniel J. ; Lange, Tanja (2007). Faster addition and doubling on elliptic curves . pp. 29–50. http://eprint.iacr.org/2007/286 .
^ Daniel J. Bernstein (2017年 ねん 1月 がつ 22日 にち ). “Ed25519: high-speed high-security signatures ”. 2019年 ねん 9月 がつ 27日 にち 閲覧 えつらん 。 “This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc.”
^ Johnston, Casey (2010年 ねん 12月30日 にち ). “PS3 hacked through poor cryptography implementation” . Ars Technica . https://arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/ 2016年 ねん 11月15日 にち 閲覧 えつらん 。
^ fail0verflow (29 December 2010). Console Hacking 2010: PS3 Epic Fail (PDF) . Chaos Communication Congress . 2018年 ねん 10月 がつ 26日 にち 時点 じてん のオリジナル (PDF) よりアーカイブ。2016年 ねん 11月15日 にち 閲覧 えつらん 。
^ “27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail ”. 2019年 ねん 8月 がつ 4日 にち 閲覧 えつらん 。
^ a b “FIPS 186-5 (Draft): Digital Signature Standard (DSS) ”. NIST (October 2019). doi :10.6028/NIST.FIPS.186-5-draft . 2022年 ねん 8月 がつ 3日 にち 閲覧 えつらん 。
^ Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko (1 October 2020). Taming the many EdDSAs . Security Standardisation Research Conference (SSR 2020). 2022年 ねん 8月 がつ 3日 にち 閲覧 えつらん 。
^ Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao (3 July 2020). The provable security of ed25519: Theory and practice . IEEE Symposium on Security and Privacy (S&P 2021). 2022年 ねん 8月 がつ 3日 にち 閲覧 えつらん 。
^ “ed25519-speccheck ”. 2022年 ねん 8月 がつ 3日 にち 閲覧 えつらん 。
^ “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年 ねん 11月12日 にち 閲覧 えつらん 。
^ https://www.openssl.org/news/cl111.txt
アルゴリズム 理論 りろん 標準 ひょうじゅん 化 か 関連 かんれん 項目 こうもく
カテゴリ