楕円曲線暗号についてまとめたいと思います。

この特定の暗号方式を指しているわけではなく、楕円曲線を使用した公開鍵暗号、署名、鍵交換の総称になるようです。

有名どころだとSSLの鍵交換や、ビットコインの楕円曲線を使用したデジタル署名に使われています。

RSAはだいたい鍵の長さが1024とか2048ですが、この楕円曲線暗号250程度の鍵長でRSAと同等の強度を持つと言われています。

今回は、楕円曲線暗号がどういうものでどのような動きをするのかを自分なりにまとめます。
そしてそれをいつか何かに役立てることをここに誓います。

楕円曲線暗号とは

楕円曲線暗号は楕円曲線の演算を有限体上で行います。
有限体はpという素数があるとして0,1,2,3….p-1からなる整数の集合に演算を定義したものです。
有限体の詳しい説明はここでは省きます。

それを踏まえて以下のような公式があるとします。
y② = x③ + ax + b mod(223)　有限体上の楕円曲線
これは y② と x③ + ax + b をそれぞれ223で割ったあまりが等しいということを表しています。

この公式を使って楕円曲線上の点Gに対して2G(2*Gということです)、3G、4G…と演算を繰り返していくと多くの点が現れます。
例えば点Gをx = 47, y = 71, a = 0, b = 7だとします。
この点対して1Gから10Gまで計算すると以下のような結果になります。

1G x = 47 y = 71
2G x = 36 y = 111
3G x = 15 y = 137
4G x = 194 y = 51
5G x = 126 y = 96
6G x = 139 y = 137
7G x = 92 y = 47
8G x = 116 y = 55
9G x = 69 y = 86
10G x = 154 y = 150

点Gをを二倍(2G)するとx=36 y=111になりました。
数学的背景はさておき、具体的にどのような計算をしているのかプログラムを書いて高みの見物してみましょう。

実装

まず有限体の演算をしてくれるクラスを作成します。
言語は見た感じscalaですね。

package ecc
// 多倍長整数を使う
import scala.math._

// 有限体クラス
class FiniteField(var num: BigInt, var prime: BigInt)
{
  // 元の大きさを確認
  if (prime <= num) throw new Exception("Parameter invalid")

  // 加算
  def +(ff: FiniteField): FiniteField = {
    isEqPrime(ff.prime)
    new FiniteField( (this.num + ff.num)%prime, prime )
  }

  // 減算
  def -(ff: FiniteField): FiniteField = {
    isEqPrime(ff.prime)
    new FiniteField( (this.num - ff.num).mod(prime), prime )
  }

  // 乗算　引数:有限体クラス
  def *(ff: FiniteField): FiniteField = {
    isEqPrime(ff.prime)
    new FiniteField( this.num * ff.num % prime, prime )
  }

  // 乗算　引数:Int
  def *(num: Int): FiniteField = {
    new FiniteField( this.num * num % prime, prime )
  }

  // 除算
  def /(ff: FiniteField): FiniteField = {
    isEqPrime(ff.prime)
    val res = num*ff.num.modPow(prime-2,prime)
    new FiniteField( res%prime, prime )
  }

  // 累乗
  def pow(ex: Int): FiniteField = {
    new FiniteField( this.num.modPow(ex, prime), prime )
  }

  //　eq
  def ==(ff: FiniteField): Boolean = num == ff.num && prime == ff.prime
  def ==(num: Int): Boolean = this.num == num

  // not eq
  def !=(ff: FiniteField): Boolean = (num != ff.num) || (prime != ff.prime)
  def !=(num: Int): Boolean = this.num != num

  // ２つのクラスのprimeが等しいか判定
  def isEqPrime(p: BigInt) {
    if (prime != p) {
      throw new Exception("Prime not equal")
    }
  }
}

有限体をある程度理解していれば特に難しいことはないかと思います。

そして楕円曲線上の演算をしてくれるクラスです。

package ecc

import ecc._
// 楕円曲線の演算を行うクラス メンバ変数に有限体クラスを持つ
class ECPoint(var x: FiniteField, var y: FiniteField, var a: FiniteField, var b: FiniteField) {
  // xとyが0じゃなければ値の正当性を確認する
  if (x != 0 && y != 0) {
    if ( y.pow(2) != (x.pow(3) + a*x + b) ) throw new Exception("Parameter Invalid")
  }

  // ２つの点の比較
  def ==(other: ECPoint): Boolean = {
    this.x == other.x &&
    this.y == other.y &&
    this.a == other.a &&
    this.b == other.b
  }

  // ２つの点の比較
  def != (other: ECPoint): Boolean =  {
    !(this == other)
  }

  // 乗算　バイナリ法で加算を繰り返しているようだ
  def *(coef: Int): ECPoint = {
    val zX = new FiniteField(0, this.x.prime)
    val zY = new FiniteField(0, this.x.prime)
    var c = coef
    var current = this
    var result = new ECPoint(zX, zY, a, b)
    while (c > 0){
      if ( (c & 1) == 1 ) {
        result  += current
      }
      current += current
      c = c / 2
    }
    result
  }

  // 加算　点の値によって計算方法が変わる
  def +(other: ECPoint): ECPoint = {
    var zX = new FiniteField(0, this.x.prime)
    var zY = new FiniteField(0, this.x.prime)

    if ( x == 0 ) {
      return other
    }

    if ( other.x == 0 ) {
      return this
    }

    if (this == other && this.y == 0) return new ECPoint(zX,zY,this.a,this.b)

    if (this.a != other.a || this.b != other.b) throw new Exception("Value error")

    // x1 not eq x2
    if ( this.x != other.x ) {
      val s = ( other.y - this.y ) / ( other.x - this.x )
      val x3 = s.pow(2) - this.x - other.x
      val y3 = ( this.x - x3 ) * s - this.y
      return new ECPoint(x3, y3, a, b)
    }

    // x1 eq x2 and y1 eq y2
    if (this == other) {
      val s = ( x.pow(2)*3+this.a )/( this.y*2 )
      val x3 = s.pow(2) - this.x*2
      val y3 = ( this.x - x3 )*s - this.y
      return new ECPoint(x3, y3, a, b)
    }

    new ECPoint(zX, zY, a, b)
  }
}

先ほど例に挙げた演算はこのクラスの+メソッドが行っています。
以下のようにして計算できます。

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 ec = new ECPoint(x,y,a,b)
for (i <- 1 to 10) {
  val res = ec * i
  println(i+"G x = "+res.x.num+" y = "+res.y.num)
}

これを実行すると先ほどと同じ結果が表示されるかと思います。

楕円曲線暗号の離散対数問題

この問題はなにを表しているかというと、
数xと点GがあるとしてこのふたつからxGを得ることは簡単だが、
xGから数xを求めることが難しいということです。

任意の点Gに2G,3G,4G…と繰り返し演算をすることで点が現れます。
先程もかきましたが、点Gをを二倍(2G)するとx=36 y=111になります。
これは数が小さいため数xを求めることはそれほど難しくはありませんが、
さらに巨大な数を使用した場合数xを求めることはとても難しくなります。

これが楕円曲線暗号の安全性の根拠だそうです。