楕円曲線Elgamal暗号

楕円曲線Elgamal暗号は楕円曲線上での離散対数問題の困難性を安全性の根拠とした暗号スキームである。Elgamal暗号の離散対数問題の困難性を楕円曲線上での離散対数問題の難しさに置き換えている。一般の離散対数問題より非常に困難な問題であることが知られている。

実装について

実装はScalaを用いて、主に参考文献の「暗号技術のすべて」を参考に作成した。

有限体クラス

package EncUtils                                                                                                                                             
object math{
    import scala.util.Random
    import scala.math.{sqrt,floor}

    def power(x:Int,p:Int):Int = if(p==0) 1 else x * power(x,p-1)
    def mod(x:Int,modulo:Int):Int =  ( x % modulo + modulo ) % modulo
    def modInv(a:Int,modulo:Int):Int = {
        def extEuclid(a:Int,b:Int):(Int,Int) = if (b==0) (1,0) else ((t:(Int,Int)) => (t._2,t._1 - a/b * t._2))(extEuclid(b,a%b))
        mod(extEuclid(mod(a,modulo),modulo)._1,modulo)
    }

    case class GField(num:Int,modulo:Int){
        def  +(other:Int):GField = GField(mod(num + other,modulo),modulo)
        def  +(gf:GField):GField = GField(mod(num + gf.num,modulo),modulo)
        def  -(other:Int):GField = GField(mod(num - other,modulo),modulo)
        def  -(gf:GField):GField = GField(mod(num - gf.num,modulo),modulo)
        def  *(other:Int):GField = GField(mod(num * other,modulo),modulo)
        def  *(gf:GField):GField = GField(mod(num * gf.num,modulo),modulo)
        def  /(other:Int):GField = GField(mod(num * modInv(other,modulo),modulo),modulo)
        def  /(gf:GField):GField = GField(mod(num * modInv(gf.num,modulo),modulo),modulo)
        def **(p:Int):GField = GField(mod(power(num,p),modulo),modulo)
        def <(other:Int):Boolean =  this.num < other
    }
}

楕円曲線Elgamal暗号で数値を扱う場合、演算は全てZp（整数上の素数pによる剰余類）上での演算となるため、単純化するために有限体（ガロア体）クラスGFieldを定義する。power,mod,modInvはRSAで実装したものと同じである。
各演算は中置演算で有限体クラスが左となっている場合のみサポートしている。例えばGField(1,modulo)+1はGField(1,modulo).+(1)と解釈されるため、GFieldのdef +(other:Int):GFieldが呼び出されるのだが、もし1+GField(1,prime)なら1.+(GField(1,prime))となり、1の+演算子にはGFieldクラスを引数とするものがなくエラーを起こす。

有限体上での楕円曲線

package EncUtils                                                                                                                                             

object elliptic{
    import EncUtils.math._
    import scala.util.Random

    class EC(val prime:Int){
            val (a,b):(GField,GField) = chooseEC
            def chooseEC:(GField,GField) = {
                var m = GField(Random.nextInt(prime),prime)
                var n = GField(Random.nextInt(prime),prime)
                while( discriminant(m,n) == GField(0,prime)) {
                    m = GField(Random.nextInt(prime),prime)
                    n = GField(Random.nextInt(prime),prime)
                }
                (m,n)
            }
            def apply(p:ECPoint):GField = p.x**3 + p.x * this.a + this.b - p.y**2
            def discriminant(m:GField,n:GField):GField = m**3 * 4 + n**2 * 27
    }

    class ECPoint (val x:GField,val y:GField,val curve:EC){
        def lambda(q:ECPoint):GField = {
            if (this != q) (q.y - this.y) / (q.x - this.x) else  ( this.x ** 2 * 3 + this.curve.a ) / ( this.y * 2 )
        }
        def +(q:ECPoint):ECPoint = {
            if (q.isInstanceOf[IfPoint]) {
                this
            }else if (this.x == q.x & (this.y + q.y) == GField(0,this.x.modulo)){
                new IfPoint(GField(-1,x.modulo),GField(-1,x.modulo),this.curve)
            }else{
                val x3:GField = lambda(q)**2 - this.x  - q.x
                new ECPoint(x3 ,lambda(q) * (this.x-x3) - this.y,this.curve)
            }
        }
        def *(k:GField):ECPoint = if (k < 2) this  else this + this.*( k - 1 )
    }

    class IfPoint (x:GField ,y:GField ,curve:EC) extends ECPoint(x,y,curve){
        override def +(q:ECPoint):ECPoint = q
        override def *(k:GField):ECPoint = this
    }
    def gfAdd(self:ECPoint,other:ECPoint):ECPoint = new ECPoint(self.x + other.x,self.y + other.y,self.curve)
    def gfSub(self:ECPoint,other:ECPoint):ECPoint = new ECPoint(self.x - other.x,self.y - other.y,self.curve)
}

ECは楕円曲線を表すクラスである。ECを初期化するとランダムに判定式Dが0でない楕円曲線を選ぶ。このECのインスタンスをapplyすると、楕円曲線の多項式の値を返し、その値を0と比較すれば方程式を解くことが出来る。
ECPointは楕円曲線上の点を表す。メンバ変数xとyはそれぞれ座標であり、curveはどの楕円曲線上に点があるのか表している。
ECPointのサブクラスIfPointとして無限遠点を定義している。無限遠点とは楕円曲線上での演算における単位元のことである。座標において限りなく遠くにある点のことで、(∞,∞)で表される。どの座標平面上をどの方向に進んでもその点に到達するものと定義され、美術でいう消失点に近い。このIfPointを被演算子にとる楕円曲線上の演算では、加算した時に左辺か右辺の値がそのまま返り値となるように表現されている。
なお、gfAddとgfSubは暗号化と復号で必要になる楕円曲線上ではない足し算と引き算である。つまり、単純に座標同士を足し算する。

楕円曲線Elgamal暗号

package EncUtils

object encryption{
    import scala.util.Random
    import scala.math.{sqrt,floor}
    import EncUtils.math._
    import EncUtils.elliptic._

    class PublicKey(val prime:Int,val curve:EC,val p:ECPoint,val y:ECPoint)
    class SecretKey(val x:GField)

    def genPrime(low:Int,high:Int):Int = {
        def isPrime(num:Int):Boolean = ( 2 to floor(sqrt(num)).toInt ).foldLeft(true)((result,i) => result & (if( num%i == 0 ) false else true))
        val num:Int = Random.nextInt(high-low)+low
        if (isPrime(num)) num else genPrime(low,high)                                                                                                            }
    def chooseBP(modulo:Int,curve:EC):ECPoint = {
        var m:GField = GField(Random.nextInt(modulo),modulo)
        var n:GField = GField(Random.nextInt(modulo),modulo)
        while(curve(new ECPoint(m,n,curve)) != GField(0,modulo)){
                m = GField(Random.nextInt(modulo),modulo)
                n = GField(Random.nextInt(modulo),modulo)
        }
        new ECPoint(m,n,curve)
    }
    def genKey(k:Int)={
        val low:Int = 1 << k -1
        val high:Int = 1 << k
        val prime:Int = genPrime(low,high)
        val curve:EC = new EC(prime)
        val basePoint:ECPoint = chooseBP(prime,curve)
        val sk:SecretKey = new SecretKey(GField(Random.nextInt(prime),prime))
        val y:ECPoint = basePoint * sk.x
        val pk:PublicKey = new PublicKey(prime,curve,basePoint,y)
        (pk,sk)
    }
    def encrypt(m:ECPoint,pk:PublicKey):(ECPoint,ECPoint)={
        val r:GField = GField(Random.nextInt(pk.prime),pk.prime)
        val c1:ECPoint = pk.p * r
        val c2:ECPoint = gfAdd(pk.y * r,m)
        (c1,c2)
    }
    def decrypt(c:(ECPoint,ECPoint),pk:PublicKey,sk:SecretKey):ECPoint= gfSub(c._2,c._1 * sk.x)
}

鍵生成から暗号化、復号のプログラムである。暗号スキームについては、参考文献になる「暗号技術のすべて」や楕円 ElGamal 暗号の実装を読んで欲しい。素数生成するgenPrimeはRSAの実装と同じである。chooseBPは楕円曲線上、つまり方程式を満たすx、yを基準点とする。
暗号に適した楕円曲線を選択するには、点の個数が大きな素数で割れる必要があるが、位数を求める方法が分からなかったので今回は実装できていない。

テスト

object Main extends App{                                                                                                                                         import EncUtils.math._
    import EncUtils.elliptic._
    import EncUtils.encryption._
    import scala.util.Random

    val (pk,sk) = genKey(10)
    val a = chooseECP(pk.prime,pk.curve)
    val b = chooseECP(pk.prime,pk.curve)

    val cipher1:(ECPoint,ECPoint) = encrypt(a,pk)
    val cipher2:(ECPoint,ECPoint) = encrypt(b,pk)

    val decResult1:ECPoint=decrypt(cipher1,pk,sk)

    val ax = a.x
    val ay = a.y

    val x1 = decResult1.x
    val y1 = decResult1.y

    println("----------------test1----------------")
    println(s"plaintext1:$ax,$ay")
    println(s"decrypt result1:$x1,$y1")

    val decResult2=decrypt(cipher2,pk,sk)

    val bx = b.x
    val by = b.y

    val x2 = decResult2.x
    val y2 = decResult2.y

    println("----------------test2----------------")
    println(s"plaintext2:$bx,$by")
    println(s"encrypt result2:$x2,$y2")

}

平文は平文を楕円曲線上の点に変換する埋め込みアルゴリズムを使用せず、最初から楕円曲線上の点をランダムに与える。

----------------test1----------------
plaintext1:GField(712,1013),GField(281,1013)
decrypt result1:GField(712,1013),GField(281,1013)
----------------test2----------------
plaintext2:GField(818,1013),GField(769,1013)
encrypt result2:GField(818,1013),GField(769,1013)

平文と復号後の結果が一致しており、正しく暗号化と復号が成功したことが分かる。

まとめ

楕円曲線を使って暗号化し、それが復号できることを確認できた。
平文の埋め込みアルゴリズムや暗号に適切な楕円曲線を選択するようにアルゴリズムを作ることで改善したい。

参考文献

IPUSIRON 「暗号技術のすべて」2017
瀬良和弘、水島宏太、河内崇、麻植泰輔、青山直紀　「実践Scala入門」2018
楕円 ElGamal 暗号の実装
The Scala Programming Language
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方
拡張ユークリッドの互除法〜一次不定方程式 ax + by = c の解き方〜
楕円曲線暗号をプログラムしたらこうなった

github