用 Kotlin 寫一個簡單的橢圓曲線密碼 ECC

來看一個橢圓曲線(elliptic curve)與直線(line)的聯立方程式,已知兩個交點分別是 P(xp, yp)及 Q(xq, yq),直線斜率是 s
            y² = x³ + ax² + bx    --- (1)
            y   = s(x -xp) + yp     --- (2)
先假設 P 與 Q 是兩個不同點,通過這兩點的直線斜率 s 可以很容易計算出來:
            s  = (yp - yq) / (xp - xq)    --- (3)
將第(2)式代入第(1)式得到
          (s(x - xp) + yp)² = x³ + ax² + bx     --- (4)
我們已知上述聯立方程式應該有 3 個解,我們目的就是要解出最後的第 3 交點(解),假設它是 R(xr, yr), 這 3 個交點的 x 座標分別是 xp, xq, xr, 正好是方程式的解,換句話說這 3 個解一定是上述聯立方程式的根,因此(4)式就可以寫成:
          (x - xp)(x - xq)(x - xr) = 0   --- (5)
將第(4)式與第(5)式分別展開,但只需關注 x² 項的係數就可,無需全部展開:
            (a - s²)  x ²       =        - (xp +  xq  + xr)  x²        --- (6)
比較係數得出 xr 的關係式,加上第(2)與(3)式,就可以定義出一個 ECC 的加法運算法則(因為 P + Q = - R),經此推導.可知第 3 交點位置在 R(xr, yr)
           s  = (yp - yq) / (xp - xq) --- (7)
          xr = s² - xp - xq - a           --- (8)
        -yr = s(xp - xr) - yp            --- (9)
可是當  P 與 Q 重疊時(dual root), 導致第(7)式的斜率無法運算,兩個點重疊(double)的斜率其實就是橢圓曲線的切線斜率,因此將式(1)分別對 x 作微分並移項得到
           dy/dx  = (3 x² + 2 a x + b) / 2y  --- (10)
將切點(xp, yp)代入公式就可算出切點的斜率,因為此時 P 與 Q 點重疊(xr, xq) = (yr, yq),我們可以定義出所謂的加倍運算法則(因為 P + P=2P = -R' 就是加倍的意思),只要修正用橢圓曲線的切點斜率(等於定義了兩個交點在同一位置)去取代直線斜率,這樣就可計算出另外第 3 交點的位置在 R'(xr, yr)
             s = (3 x² + 2a x + b) / 2y      where  (x, y)=(xp, yp)   -- (11)
           xr = s² - 2xp - a              --- (12)
          -yr = s(xp - xr) - yp        --- (13)
綜合上述,我們在橢圓曲線與直線交點的基礎規範下,進行 P + Q = -R 的運算,可以用加法程序(在第 7, 8, 9 式)或加倍程序(在第 11 ,12, 13 式)來計算出第 3 交點 R(xr, yr).其中加法程序是用在兩個不同點的相加, 而加倍程序則用在相同點的累加,只要知道一個交點,我們稱為之基準點(G),先透過加倍程序,找出其 2 倍(2P)座標點(也就是2G),利用加法程序將 2 倍座標點(2G)與基準座標點(G)相加(add)算出 3 倍座標點(3G),再利用兩倍的兩倍,累加計算出 4 倍座標點(4G),  ... 以此類推得到 n 倍基準座標點(nG).這個 n(稱為 scale) 倍數的座標點,利用的是倍加原理(double and add)的疊代運算逐漸產生新的座標點,但有一點要注意的是當兩個座標點累加去計算出另一座標點的時候(不管是 P + Q = -R 或是 P + P =2P),我們不是要曲線與直線的交點座標 R, 而是要它鏡像點的座標 -R,上面聯立方程式推導的(xr, yr)是交點的座標,因為在 y 軸上,交點與其鏡像點座標是互為反數的關係,因此我們只要將上述推導出的 y 軸座標值轉成負數就可,這就是上述式子中用 -yr 的原因,因為它代表了座標點的位置. 用 Kotlin 語法加上它有 operator overloading 的特性,可以寫出很容易明瞭的程式:


import java.math.BigInteger // 大數運算先要載入 java.math.BigInteger 的模組:
class Curve383187 (key: BigInteger = BigInteger.ONE) { // Curve383187 :: y²=x³ + ax² +bx    mod   p
    private val p = BigInteger("2").pow(383).subtract( BigInteger("187") ) //  p = 2³⁸³ - 187
    private val a = BigInteger("229969") // a = 229969
    private val b = BigInteger("1")   // b=1
    private var x = BigInteger("5") 
    private var y = BigInteger("4759238150142744228328102229734187233490253962521130945928672202662038422584867624507245060283757321006861735839455")
    init {       //       key * G(x,y)
            if (key != BigInteger.ONE)    scale(key, x, y)
    }  
    private infix fun BigInteger.mod(another: BigInteger)   : BigInteger { return rem(another)            }   // %
    private operator fun BigInteger.plus(another: BigInteger)  : BigInteger { return add(another) mod p      }// +
    private operator fun BigInteger.minus(another: BigInteger) : BigInteger { return subtract(another) mod p }// -
    private operator fun BigInteger.times(another: BigInteger) : BigInteger { return multiply(another) mod p }// *   
    private operator fun BigInteger.div(another: BigInteger)   : BigInteger { return multiply(another.modInverse(p)) mod p } // ÷
    fun isPoint() : Boolean {    return    y * y == x * x * x + a * x * x + b * x  } // y² = x³ + ax² +bx
    operator fun times(n: BigInteger) : Curve383187 {
        var c = Curve383187( )    // new object
        return   c.scale(n, this.x, this.y)   // return c object
    } 
    private fun scale(n: BigInteger, Gx: BigInteger, Gy: BigInteger ) : Curve383187 {
       var k = 1024               // number of bits
       val num = n  mod  p  // Double And Add algorithm to scale G(x,y)  
       if (num == BigInteger.ZERO) { println("Error, scale num is 0");   return this }
       val big3=BigInteger("3")
       val big2=BigInteger("2")
       while( k-- > 0 )     if ( num.testBit(k) )  break               
       x = Gx;  y = Gy            // initialize P(x, y) = G(x,y)
       while( k-- > 0 ){   // Doubler slope = (3x² + 2ax + b) / 2y 
          var xp = x                  // store  x  to caculate  2P(x, y) = -R'(x, y)    
          var s = (big3 * x * x + big2 * a * x + b) / (big2 * y)
          x = s * s - big2 * xp - a  //    R'.x = s² - 2xp - a
          y = s * (xp - x) - y             //  - R'.y = s(xp - x) - yp
          if ( num.testBit(k) ) {    //   P(x, y) + G(x,y) = - R(x, y)
               s = (y - Gy )/( x - Gx)   //   Adder slope = (y - G.y) / (x - G.x)
               x = s * s - x - Gx - a      //   R.x = s² - x - G.x - a
               y = s * (Gx - x) - Gy      //  -R.y = s(G.x - x) - G.y
           }  
        }       
        if (x < BigInteger.ZERO) x = x + p mod p
        if (y < BigInteger.ZERO) y = y + p mod p
        return this // return self object
    } // end of scale
    fun listpoint() {
        println("\n\tx="+x.toString(16)+"\n\ty="+y.toString(16))
    }
}// End of class Curve383187
fun main(args:Array < String > ) {  
   var keyA = BigInteger("9").pow(87).subtract(BigInteger("65") ) // Alice pickup a key
    var keyB = BigInteger("4").pow(32).subtract(BigInteger("10") ) // Bob pickup a key
    var key  =  keyA*keyB         // Nobody knowns this share key
    var pubA =  Curve383187(keyA) // Alice send public key to Bob
    var pubB =  Curve383187(keyB) // Bob send public key to Alice
    var keyECC=  Curve383187(key) // Caculate the ECC of the secret to double check
    var Alice= pubB * keyA        // Alice use self key to decode pubB sent from Bob
    var Bob  = pubA * keyB        //  Bob use self key to decode pubA sent from Alice
    pubA.listpoint()  ; println("Public@ECC(x,y) from Alice key:\n\t"+keyA.toString())
    pubB.listpoint()  ; println("Public@ECC(x,y) from Bob key:\n\t"  +keyB.toString())
    keyECC.listpoint(); println("Share @ECC(x,y) from Secret key:\n\t"+key.toString())     
    Alice.listpoint() ; println("Alice key decode:")
    Bob.listpoint()   ; println("Bob key decode:")                               
    println("\nAlice on curve ? "+Alice.isPoint()+ " Bob on curve ? "  +Bob.isPoint())
}
輸出結果:
    x=2a4c00dc2e8acb66b527ae0cddaeb9b373dfe0e7b3ef9b86e38b7b39d55e3f24f25cc5608a45e66acc96eddd40578daf
    y=5c18f88677e650fa6cad33a14a961adc0db96739fcfb39c7b600a3e106ed0aafe705271408a522dd582ff6ce9d8fe37f
Public@ECC(x,y) from Alice key:
    104495676331778315966103878903450701989608781073244439950619431748912396904023371704

    x=2989c08b718a4fc3bfe8cc3da96e5d7d975f6c58802700eb2f5ca018e70bbdb3d5c03671053eed8ee94adaed23dfcac0
    y=37eb8fa79a5ee1caa076518b1abf3249e5fd560a95acf3ad6e22a27055d51c9dcb974988c9a2f99b6f68afcece7c7570
Public@ECC(x,y) from Bob key:
    18446744073709551606

    x=381dcd3a1bdea34760212d276c7d21940d315a4d547af3c520aba80a2ff4e38e0e548dd9d0038c1ce5c3eb36acf6960b
    y=3491be994e90f4e9b28352b5c0495c5f395dba99fe2fa870553351be77e363c67392e3c3feb2fed711b5d187c63afbbb
Share @ECC(x,y) from Secret key:
    1927604998101503106558917489994263425013278054390180757461516411290410360277764861810797121646108156624

    x=381dcd3a1bdea34760212d276c7d21940d315a4d547af3c520aba80a2ff4e38e0e548dd9d0038c1ce5c3eb36acf6960b
    y=3491be994e90f4e9b28352b5c0495c5f395dba99fe2fa870553351be77e363c67392e3c3feb2fed711b5d187c63afbbb
Alice key decode:

    x=381dcd3a1bdea34760212d276c7d21940d315a4d547af3c520aba80a2ff4e38e0e548dd9d0038c1ce5c3eb36acf6960b
    y=3491be994e90f4e9b28352b5c0495c5f395dba99fe2fa870553351be77e363c67392e3c3feb2fed711b5d187c63afbbb
Bob key decode:

Alice on curve ? true Bob on curve ? true