ECDH完全理解した。

参考

ECDHを紹介するyoutube 楕円曲線暗号をビリヤードに例えている例

ECDHの説明

かなり面白いね。ECDH。 まず、楕円曲線上で足し算というものを定義する。 これは、ビリヤードである。二点を決めて、その直線を引くと新たに楕円曲線と交わる点が生じる。それをx軸に対象に折り曲げた点、これを足し算の結果とする。

a + b = c

ここで、p + p = 2pというものを定義可能である。pというのは、接線となる。 で、ここで不思議なのが、以下の結合法則が成り立つこと。

p + 2p = 3p
3p + p = 4p

2p + 2p = 4p

先に

p + 2p = 3p
3p + p = 4p

を計算して出した4pも

2p + 2p = 4p

で出した４pも同じ点になる。これは面白い。

でだ、 こんな感じで最初の点Gを決めて、k倍した点Q

Q = kP

を求めることは簡単である。（例えば、k = 128の時は、2p+2p, 4P+4p,,,, 64p+64pで計算関数は少なく済む。） しかし、QとPからkを求めることは困難である。前から順番にやっていくしかないのである。 ということで、Qという値をサーバとクライアントで生成するんだよね。それぞれ、Q1,Q2.

Q1 = K1P
Q2 = k2P

そして、Q1とQ2を交換します。opensslではRSAなどで署名が施されて交換されるので、真正性も担保される。 で、プリマスターシークレットを、

Q = K1K2P

として、鍵交換が完了。これを元に共通鍵を生成して暗号通信がスタートする、という感じだ。 素晴らしい。

楕円曲線暗号のイメージは、以下のように説明されています。

2ポイントあって、最初のポイント同士でn回「dot」すると、最後のポイントに到達しますが、最初のポイントと最後のポイントだけがわかっている状態で「n」が何を指すのか判断することは困難です。この不思議なビリヤードの例を続けて、ある人が一人で部屋のなかでこのゲームを任意の時間行うとします。彼が上記のルールに従って、何度も玉を突くことは簡単です。誰かが後で部屋に入り、玉が最後に到達した場所を見たとき、ゲームの全ルールと玉をつき始めた場所が分かったとしても、玉が同じポイントに到達するまで再びゲーム全体をリプレイすることなく、玉が最終地点に到達するために打った回数が何回だったかを割り出すことはできません。簡単にできるが、元に戻すのは難しい。これがとても優れたトラップドア関数の基盤になるのです。

回数がわかったら、最終地点が簡単にわかる、というのは、もちろん結合法則が使えるから簡単にわかるという話です。

どんなに大きい数字kでも、2^nすればすぐに辿り着けるんです。これがすごく大事なんですねー。 kがわからない人は最初から全てをリプレイする必要がある。しかし、kを知っている人は、例えばk=129だとすると、

129 = 128 + 1 = (64+64)+1

みたいな感じにして、一瞬で求められる形にするんですね。