Bitcoin に触れるようになってから、ようやく ECDH の全貌を把握できるようになってきました。ここでいう ECDH というのは、楕円曲線を用いた「安全でない通信経路上で安全に鍵を共有する方法」になります。身近な例では SSL/TLS における暗号化スイートの中の「鍵交換」のプロトコルの1つとして使われたり、Bluetooth のペアリング時にも使われていたと思います。

ECDH の EC というのは、Elliptic Curve、つまり楕円曲線を指します。したがって、ECDH の説明をするのに、楕円曲線の知識は避けられません。

楕円曲線

楕円曲線を簡単に言うと、

$y^{2}=x^{3}+ax+b$

で表現される曲線になります。楕円曲線と言えど、別に楕円になるわけではありません。そして、この楕円曲線上での点 $P(x_{1},y_{1})$ と $Q(x_{2},y_{2})$ には加算を定義することができ、その加算のパターンはwikipedia:楕円曲線に記載がありますが、以下のようになります。

f:id:kiririmode:20190217180142p:plain — 楕円曲線上での加算

もちろん、同じ点 $P$ を加算した結果得られる点 $Q=P+P$ については、乗算として $Q=2P$ のように表現することができるでしょう。同様に、同じ点 $P$ を $n$ 回足した結果の点 $R$ については、 $R=nP$ になります。

上記の楕円曲線は実数体上に定義された楕円曲線ですが、有限体 $F_{p}$ 上でも同様の楕円曲線が定義できます。この場合は、もうドット列としか言えませんが…。

f:id:kiririmode:20190217182457p:plain — 有限体 $F_{17}$ 上の楕円曲線 (Mastering Bitcoin より)

有限体 $F_{17}$ 上の楕円曲線 (Mastering Bitcoin より)

楕円曲線上の離散対数問題

生成元と呼ばれるある点 $S$ を与えられたとき、それを点 $P$ を何回足し合わせて得られるものかを求める問題、つまり、 $n=S/R$ を求める問題を楕円曲線上の離散対数問題と呼びます。これを解くことは非常に難しくて、効率的なアルゴリズムは知られていません。

つまり楕円曲線上の乗算(実際は足し算ですが)は容易ですが、割り算は容易ではない、その非対称性を利用したのが楕円曲線暗号であり、ECDH です。

ECDH

秘密鍵と公開鍵

ECDH においては、鍵を共有する二人(ここでは alice、bob と呼ぶことにします) が、最初にそれぞれ秘密鍵を $d_{a}, d_{b}$ を生成します。この秘密鍵は当然ながら、alice、bob がそれぞれ秘密に管理し、alice の秘密鍵 $d_{a}$ は bob には公開しないし、bob の秘密鍵 $d_{b}$ は alice には公開しません。

一方で、alice、bob はそれぞれの秘密鍵から公開鍵を生成します。公開鍵の生成方法は簡単で、選択した楕円曲線上の生成元たる点 $G$ について、 $Q_{a}=d_{a}G$ が alice の公開鍵、 $Q_{b}=d_{b}G$ が bob の公開鍵です。なお、どういう楕円曲線を使い、その生成元が $G$ であることは、両者に既知であるとします。

鍵の共有

いよいよ鍵の共有です。 alice、bob が秘密とすべき情報 (互いの秘密鍵) を明かさずに、信頼性のない通信路上でどうやって秘密にすべき両者の鍵を共有するか。

alice は bob に対して、alice の公開鍵 $Q_{a}=d_{a}G$ を渡します。bob は alice の公開鍵を元にして $K=d_{b}Q_{a}=d_{a}d_{b}G$ を計算します。
bob は alice に対して、bob の公開鍵 $Q_{b}=d_{b}G$ を渡します。alice は bob の公開鍵を元にして $K=d_{a}Q_{b}=d_{a}d_{b}G$ を計算します。

こうすると、両者はともに $K=d_{a}d_{b}G$ という楕円曲線上の点を得ます。この点の $x$ 座標が、共有すべき鍵になります。一般には、それをそのまま鍵として使うのではなく、さらにそこからハッシュ関数を通した値を通すのが安全とされています。

この鍵の共有プロセスにおいて、それぞれが通信路上に流しているのはあくまで公開鍵でしかないので、これが他者に盗聴されていようと問題はありません。なぜなら、公開鍵 $Q_{a}=d_{a}G$ が漏れたとして、そこから第三者が秘密鍵 $d_{a}$ を求めることは非常に困難だからです。これは、その問題がまさに離散対数問題であるからです。