楕円曲線暗号Diffie-Hellman鍵交換を検証する

楕円曲線暗号Diffie-Hellman鍵交換を検証する


ビットコインの中核の一つとして鎮座する楕円曲線暗号を使ってDiffie-Hellman鍵交換を実装してみたいと思います。

楕円曲線暗号はDiffie-Helman鍵交換,ElGamal暗号,署名などに用いられていて、RSAよりも短い鍵でRSA並の強度を持っています。


鍵共有のやり取り


ここにアリスとボブがいます。
この二人は以下のような手順で鍵の共有をします。

  1. アリスが有限体Fn上のy²=x³+ax+b (mod n)を満たす点Gを生成し、それをボブに共有する
  2. アリスが乱数a(秘密鍵)を生成し、aG(公開鍵)を求める。
  3. ボブが乱数b(秘密鍵)を生成し、bG(公開鍵)を求める。
  4. アリスがaGをボブに送信し、ボブはbaGを求める。
  5. ボブがbGをアリスに送信し、アリスがabGを求める。
  6. abG(baG)が共有鍵となる。abG=baGのため


楕円曲線暗号の安全性の根拠はGとxGからxを得ることが難しいことです。

今回の場合、GとaG,bGがバレたところでaとbを得ることはできないため共有鍵を第三者が作ることはできません。

検証する


上の記事で楕円曲線上の点を演算するプログラムを作成しました。

それらを使って鍵共有を検証します。


コンパイルして実行すると以下のような結果になります。


確かに共有鍵が同じになりました。

今回小さな素数を使ったので、xGからxを求めることは可能です。
ですが実際にはさらに大きな数を用いて演算を行うため数xを求めることはほぼ不可能になります。

楕円曲線暗号によるDiffie-Hellman鍵交換でした。

コメントする