鍵交換と楕円曲線暗号

盗聴されている通信路でも共通の鍵を作れる Diffie-Hellman 鍵交換を、小さな数で 1 手ずつ計算します。有限体の上の楕円曲線の点の足し算と、楕円曲線版の鍵交換（ECDH）・署名（ECDSA）、小さな鍵が総当たりで破られる様子も確かめられます。

素数 p（g はいちばん小さい原始根）

アリス

秘密の数 a =

A = g^a mod p = 5⁶ mod 23 = 8

A をボブに送る

鍵 = B^a mod p = 2

公開の通信路（イブが盗聴）

p = 23
g = 5
A = 8 （アリス → ボブ）
B = 19 （ボブ → アリス）

イブに見えるのはこの 4 つだけ。a か b がわからないと鍵を計算できません。

ボブ

秘密の数 b =

B = g^b mod p = 5¹⁵ mod 23 = 19

B をアリスに送る

鍵 = A^b mod p = 2

2 人の鍵はどちらも 2。B^a = (g^b)^a = g^ab = (g^a)^b = A^b なので、秘密の数を送らずに同じ値になります。

イブの攻撃: A から a を求める（離散対数問題）

x = 1〜22 の g^x mod p。値は規則なく散らばり、x を 1 増やすと次の値がどこに飛ぶか見当がつきません（青い丸がアリスの a）。

p の大きさ	総当たり	Baby-step giant-step
32 ビット	一瞬	一瞬
64 ビット	10^3 年	一瞬
128 ビット	10^22 年	10^3 年
2048 ビット	10^600 年	10^292 年

1 秒に 10 億回試せるとしたときの目安（宇宙の年齢は約 10^10 年）。実際には mod p の離散対数にはもっと速い方法（数体ふるい法）があるので、Diffie-Hellman は 2048 ビット以上を使います。楕円曲線には同じような近道が知られていないので、256 ビットで同じくらいの強さになります。

使い方

Diffie-Hellman: 素数 p を選び、アリスとボブの秘密の数を変えてみましょう。通信路に流れる値から、盗聴者のイブが秘密の数を探す手間も比べられます。
楕円曲線の足し算: 実数の曲線では 2 点を通る直線で足し算の意味を、有限体の曲線では点を押して同じ式の計算を確かめます。スカラー倍 k·G の点の飛び方も見られます。
ECDH と署名: 楕円曲線での鍵交換と、ECDSA の署名・検証です。届いたメッセージを書き換えると検証に失敗します。同じ k で 2 通に署名すると、秘密鍵が計算できてしまう様子も確かめられます。
数はすべて学習用の小さなものです。実際の暗号は 256 ビット（約 78 桁）以上の数を使います。

鍵交換とは

暗号で通信するには、送る側と受ける側が同じ鍵を持つ必要があります。しかし初めて通信する相手と、鍵そのものを盗聴されるかもしれない通信路で送るわけにはいきません。Diffie-Hellman 鍵交換（1976 年）は、それぞれが秘密の数を持ち、そこから計算した値だけを交換して、2 人だけが同じ鍵にたどり着く方法です。g^a mod p は計算しやすいのに、結果から a を求める（離散対数問題）のはとても難しい、という性質を使っています。HTTPS（TLS）では、接続のたびにこの方法で鍵を作ります。

楕円曲線暗号

楕円曲線 y² = x³ + ax + b の点には、2 点を通る直線を使った「足し算」が決められます。同じ点を k 回足した k·G は計算しやすいのに、k·G から k を求めるのは、mod p の離散対数よりさらに難しいことが知られています。そのため 256 ビットの楕円曲線で 3072 ビットの RSA や Diffie-Hellman と同じくらいの強さになり、鍵も計算も小さく済みます。ビットコインは y² = x³ + 7 の形の曲線（secp256k1）を、多くの Web サイトは P-256（a = −3）や Curve25519 を使っています。