「ED25519」が爆速な理由とその仕組み

25519とはなんぞ

大きな素数である $p = 2^{255} - 19$ から取られている。

この素数のおかげで計算が高速になる。

楕円曲線とはなんぞ

$$y^2 \equiv x^3 + ax + b \pmod{p}$$

$p$ が大きな素数。
$y^2$ と $x^3 + ax + b$ それぞれ $p$ で割った余りが同じになるような $x$ と $y$ の点を集めたら曲線になった

どうやって暗号化してるの？

「点 $P$ と点 $Q$ を結ぶ直線が曲線と交わるもう一つの点の、 $x$ 軸に対する対称点」を点 $P$ と点 $Q$の加算の結果と定義する
図^[1]で簡単に説明すると $P$ と $Q$ の足した結果が $R$ になるような計算を加算と定義するということ。

$k$ を秘密鍵として、ある点 $P$ を $k$ 回加算した結果 点 $G$ と点 $P$ を公開情報とする。
その場合高速に $k$ 回加算する計算をする必要がある。(点 $G$ と点 $P$ から $k$ を導くのは時間がかかる非対称性がある）

このとき何度も大きな素数 $p$ で割った余りを求める計算をするので、そこが高速だと非常にいい。
これが今回の肝である。

割った余りを高速に確認できる

たとえば $2^{255}$ を $p = 2^{255} - 19$ で割ったとすると余りは $19$ になる。
つまり

$$2^{255} \equiv 19 \pmod{p}$$

これは $p$ で割った余りに関しては $2^{255}$ と $19$ を同様に扱って良いことを意味する！

割られる数を $N$ 倍したら余りも $N$ 倍になるので

$$N * 2^{255} \equiv N * 19 \pmod{p}$$

この法則を使って $550$ bitの大きい数字 $S$ を $p$ で割った余りを求める方法について考える。
$S$ については $S = [1001...1010...]_{550}$ このように表してみる。

$S$ を前半 $255$ bitと後半 $255$ bitに分けてみる。
$[1001...]_{255}$ 、$[1010...]_{255}$
これを使って $S$ を

$$S = [1001...]_{255} * 2^{255} + [1010...]_{255}$$

と表すことができる。
先程の法則を使って

$$S \equiv [1011...]_{255} * 19 + [1010...]_{255} \pmod{p}$$

これは $S$ を $p$ で割った余りは $[1011...]_{255} * 19 + [1010...]_{255}$ で求められることを表す。（ $p$ より小さくなるまで繰り返す）

別に $550$ bitでなくてもこの処理を繰り返すことで、
非常に高速に素数 $p$ で割った余りを求めることができる。

必要な処理は255のビットシフトと19との乗算と2つの値の加算なのでコンピューター的に非常に高速に処理ができてうれしい。

なんで255なの？

現在推奨されている「128ビットセキュリティレベル」を満たすため

• 128ビットセキュリティレベルとは？
  「暗号を解読するには、約 $2^{128}$ 回の計算が必要になる強度」を意味する。

楕円曲線暗号の安全性の強度は、一般的に、素数 $p$ のビット長の約半分になる。
$255$ ビットあれば十分に「128ビットセキュリティレベル」をほぼ満たすことができる。
$256$ ビットだと桁溢れの心配があり、一つ小さい $255$ ビットが選ばれている。

なんで19なの？

$2^{255} - n$ が素数になるような正の整数 $n$ の中で $19$ が最も小さいから

おわりに

私も今回ED25519の理由がわからなくて調べてみたら、思っていたより処理が高速である理由、仕組み、原理について触れている記事が少なかったので自分が理解できた範囲で記事を書きました。
今後も、わからなかったらわかるまで調べ、それを共有する姿勢を大事にしていきたいです。
処理が高速になる理由についてできるだけ短い時間で理解できることを意識して記事を書きました。もし定義や言い回し、理解が間違えているところがありましたらご指摘ください。
また、この記事でわからない部分などがありましたらコメント💬お願いします！

脚注

1. 図はsh-miyoshiさんのこちらの記事が非常にわかりやすかったので使わせていただきました。ありがとうございます。 ↩︎