ビットコインの中核の一つとして鎮座する楕円曲線暗号を使って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を得ることはできないため共有鍵を第三者が作ることはできません。

検証する

楕円曲線暗号をプログラムしたらこうなった

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

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

import ecc._
import scala.util.Random
object test {
  def main(args: Array[String]) {
    // 鍵共有のやりとりの1
    val a = new FiniteField(0,223)
    val b = new FiniteField(7,223)
    val x = new FiniteField(47,223)
    val y = new FiniteField(71,223)
    var p = new ECPoint(x,y,a,b)

    val r = new Random()
    // 鍵共有のやりとりの2
    val priA = r.nextInt(500)
    val pubA = p*priA
    println("private A "+priA)
    println("public A x:"+pubA.x.num+" y:"+pubA.y.num)

    // 鍵共有のやりとりの3
    val priB = r.nextInt(500)
    val pubB = p*priB
    println("private B "+priB)
    println("public B x:"+pubB.x.num+" y:"+pubB.y.num)

    // 鍵共有のやりとりの4,5,6
    val shareKeyA = pubA*priB
    val shareKeyB = pubB*priA
    println("share key A x:"+shareKeyA.x.num+" y:"+shareKeyA.y.num)
    println("share key B x:"+shareKeyB.x.num+" y:"+shareKeyB.y.num)

  }
}

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

private A 405
public A x:139 y:137
private B 135
public B x:69 y:86
share key A x:69 y:137
share key B x:69 y:137

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

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

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