ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

ラーメンを完飲してはいけない、旧約聖書にもそう書いてある

雑

はじめに

SSHの鍵を作るときに, 「いまどきRSAだなんて(たとえ4096bitsだとしても)! Ed25519を使うのが常識よ!!」というような文言を耳にするかと思います. 実際僕もGitHubではEd25519を使っています(ykm11).

しかしよく考えてみてください. みなさんはちゃんとEd25519を使うことの意味を理解していますか?「楕円曲線だからRSAよりビット数が少ない上に強度もいい感じ〜」とか「Ed25519を使ってる人は意識高いよね〜」とか, そんな感じで使っていませんか? それでいいと思います.

が, せっかく使うなら「どうして安全なの？」とか「どうして速いの？」とかそういう話にも興味を持ってみると面白いかもしれません. 言い忘れてましたが, Ed25519って高速で動くんですよ. ”楕円曲線だから” ではなくて ”Ed25519だから” ですね. djb氏は神. (一般的に, 楕円曲線はRSAよりもビット数が少なく済み, また速いとされていますが, ここでは楕円曲線を使ったアルゴリズムの中でも特にEd25519が優れているということを強調しました)

今回は実際にopensslのEd25519実装や元となっている論文を読みながらアルゴリズムの紹介をしようと思います. もしかすると間違えている部分があるかもしれないので, 気になる方は論文を読んでみてください.


用語の整理

  • curve25519 (Curve25519)
    GF(2255 - 19)を定義体とする楕円曲線の総称.
    [追記 (2019.09.26)] 総称ではなく, \(y^{2} = x^{3} + Ax^{2} + x\)で表現される楕円曲線. \(A = 486662\). 詳細はRFC7748やこちらを参考に.

  • Ed25519
    twisted Edwards curveを使ったEC"DSA" 署名アルゴリズム. X25519(後述)と混同しないよう注意.

  • X25519
    ECDHE. 鍵共有アルゴリズム. X448とよく一緒に出てくる(はず). TLS1.3ではこれが使われている. (2019.08.24現在)

この記事ではEd25519のみを扱う. (曲線方程式や加算法については余力があれば)(余力がなかったのでいつか更新)


EdDSA key generation and make signature

M: message
H: hash function, H(a, b, c) means H(a|b|c); concatenate
k: private_key (b-bit)
h: H(k) (2b-bit, h[0:2b-1])
A: public key
B: base point of curve25519
ellcard: cardinality of the curve

\( a := 2^{b-2} + \sum_{3 \le i \le b-3} {2^{i}h_{i}} \)
\( r := H(h[b:2b-1], M) \)
\( A := [a]B \)
\( R := [r]B \)
\(S := (r + H(R, A, M)*a) \, mod \,\, ellcard \)

\((R, S) \) が署名となる. Sはscalarとして出てくるが, Rは曲線上の点で, y_coordinateを使う. 通常の楕円曲線はx_coordinateから対応するy_coordinateを取得するが, Ed25519ではy_coordinateからx_coordinateを決定するので逆であることに注意.
余談だが, x_coordinateがあればy_coordinateはすぐに求められるので, \((x, y)\)を送るのは冗長である(x_coodinateとy_coodinateの偶奇の情報だけあればよい).

opensslのcurve25519.cを確認するとED25519_sign()は概ねこの通りに実装されていることがわかる.


Verify signature

検証者は\((R, S) \)を受け取る. \(H(R, A, M)\)を計算し,

\begin{eqnarray} [8S]B = [8]R + [8H(R, A, M)]A \end{eqnarray} を満たすことを確認する.

\( S = (r + H(R, A, M)*a) \, mod \,\, ellcard \) なので,

\begin{eqnarray} [S]B &=& [r]B + [H(R, A, M)*a]B \newline &=& R + [H(R, A, M)]A \end{eqnarray}

\( A := [a]B \), \( R := [r]B \) を使った.

実装としては8倍されていなかったが, 論文では8倍されている. おそらくcofactorの8.


実際のopensslのED25519_verify()は, この方法とは異なるのでこれから示す.

openssl implementation

検証者は\((R, S) \)を受け取り, \(h := H(R, A, M)\)を計算.

\begin{eqnarray} \overline{A} &:=& [-1]A \newline
\overline{R} &:=& [h]\overline{A} + [S]B \newline
&=& [r]B + [h*a]B - [h]A \newline
&=& [r]B + [h]A - [h]A \newline
&=& [r]B \newline
&=& R \end{eqnarray}

\( y(R) = y(\overline{R}) \) を満たしていれば検証成功.

Ed25519では署名アルゴリズムでよくある"乱数生成"が出てこない. 秘密鍵のハッシュを取ると, 暗号学的ハッシュ関数の定義よりハッシュ値から秘密鍵を特定できないのでハッシュ値を推測不可能な乱数とみなせる. 乱数を使わないので署名が決定的になってしまうが, PlayStation3の例もあり乱数を使うことを避けているのだろう. これについても論文内で触れられている.


おわりに

opensslの実装を読むと, scalar倍の計算量を落とすためにmod |E|していたり(落としている関数の実装が面白い), 逆元を求めるのにFermat's Little Threoremを高速で動くように実装していたり. \(\bf{P}^{3}\)の射影座標で実装されていたりするので楽しい.


参考文献