【笔记】用Javascript实现椭圆曲线加密算法

之前为了一个项目所以去学了下椭圆曲线加密算法，本来是想写篇笔记细写算法的，但写了半天也没写出来什么，所以不如把自己摸索的东西用代码写出来了。之前项目用的nodejs，所以这里就用js写了。所有代码几乎全部可以直接在F12的控制台中运行。

0x01 点的定义

ecc中最基础计算单位自然就是一个个点了，点的定义非常简单，只要new一个对象然后赋予其点的xy坐标即可。

class Point{
    constructor(x,y){
        this.x = BigInt(x);
        this.y = BigInt(y);
    }
}

由于在实际进行计算的时候涉及的数据通常都很大，所以这里把点的坐标都转换成大整数以方便后续计算。
在ECC中，点只有两种运算：加法和数乘。所以这里我们先来实现这两个算法。

0x02 点的加法

因为点的加法的定义：

画一条线穿过P和Q，则此直线必和曲线相交第三个点R。取R关于x轴的对称点-R，就是P+Q的结果。

所以当我们有点 (x1, y1) (x2, y2) 的时候，就可以做出直线：
$$
y-y_1=k\left(x-x_1\right)+b
$$

其中：
$$
k=\frac{x_2-y_1}{x_2-x_1}
$$
有了这两个式子再和椭圆曲线：
$$
y^2=x^3+ax+b
$$
相联立，就可以得到一个关于x的一元三次方程组，解出x3再代入1式就可以得到结果的点了。
接下来是一个点和自己相加。
按照定义，一个点和自己相加时画这个点的切线，得到切线的斜率后再带入13式就可以得到结果了。
计算切线的斜率可以通过求导的方式计算得出：
$$
F\left(x\right)=x^3+ax+b-y^2
$$
$$
F_x^{‘}=3x^2+a
$$
$$
F_y^{‘}=-2y
$$
$$
k=-\frac{F_y^{‘}}{F_x^{‘}}=\frac{3x^2+a}{2y}
$$
联立计算，就可以得出（我不会算，我直接抄的qaq）：
$$
x_3=k^2-x_1-x_2
$$
$$
y_3=y_1+k(x_2-x_1)
$$
最后再注意下，有的时候斜率k会是一个分数，这个时候我们不能直接计算小数，而要去求分母的逆元再去相乘，计算的时候忽略两个点关于x轴对称和有原点的特殊情况，就可以开始写代码了。

function get_inv(x, y, p){
    return x === 1n ? 1n : get_inv(y % x, y, p) * (y - y / x) % p;
}
function get_inverse(b,p){
    return get_inv(b%p,p,p);
}
//这里直接给出一种逆元的求法，下面的函数是对上面的简单封装。关于逆元的内容以后再补吧。。。

//一种最大公约数算法
function get_gcd(x,y){
    return y?get_gcd(y,x%y):x;
}

//在有限域下计算的求模
function mod(a, b) {
    const result = a % b;
    return result >= 0n ? result : b + result;
}

function point_add(pa, pb, a, p){
    //p是预先设好的大质数，例如 secp256k1 的p为: 2n ** 256n - 2n ** 32n - 977n;
    
    //点和零点相加还得原来的点
    if(pa.x === 0n && pa.y === 0n || pb.x === 0n && pb.y === 0n){
        return new Point(pa.x+pb.x, pa.y+pb.y);
    }
    //对称的点相加得零点
    if(pa.x === pb.x && pa.y !== pb.y){
        return new Point(0, 0);
    } 
    //定义分母和分子
    let k,num,den;
    if(pa.x === pb.x && pa.y === pb.y){
        //点自己和自己相加，求切线斜率
        num = 3n * pa.x * pa.x + a;
        den = 2n * pa.y;
    } else {
        //否则就是Δy/Δx
        num = pa.y - pb.y;
        den = pa.x - pb.x;
    }
    //为了方便后面计算，先把分母和分子都换成正数。
    let flag = 1;
    if(num * den < 0n){
        flag = 0;
        num = num>0n?num:-num;
        den = den>0n?den:-den;
    }

    //求公约数
    let gcd = get_gcd(num, den);
    num /= gcd;
    den /= gcd;

    //如果还有分母，则计算逆元
    if(den !== 1n){
        den = get_inverse(den, p);
    }
    k = num * den;
    k %= p;
    
    if(flag === 0)k = -k;

    //最终计算得到两点相加的结果
    let x3 = mod(k*k - pa.x - pb.x, p);
    let y3 = mod(k * (pa.x - x3) - pa.y, p);

    return new Point(x3, y3);

}

简单的验证

（节选自ECC椭圆曲线详解(有具体实例)）
对于椭圆曲线E23(1,1) （即y2=x3+x+1, p=23），上两点P(3,10)，Q(9,7)，求(2)P+Q，(3) 2P
先把上面的代码都粘贴到控制台，然后：

var a = 1n;
var p = 23n;
p1 = new Point(3n,10n);
p2 = new Point(9n,7n)
console.log(point_add(p1,p2,a,p));
console.log(point_add(p1,p1,a,p));

得到结果：

Point {x: 17n, y: 20n}
Point {x: 7n, y: 12n}

再和答案对比：
P+Q=(17,20)
2P=(7,12)
可以验证我们算法的正确性。

0x03 点的乘法

有了点的加法后，乘法就简单多了。
按照定义，nP即代表n个p相加。
我们当然可以写一个循环让P加上n次，不过这样效率太低了，这里我们使用快速算法加速：

function get_ng(n, g, a, p){
    n = BigInt(n)

    let ans = new Point(0, 0);

    while(n > 0n){
        if(n&1n){
            ans = point_add(ans, g, a, p);
        }
        g = point_add(g,g,a,p);
        n >>= 1n;
    }

    return ans;
}

和整数的快速乘法原理基本相同。

简单的验证

var i = 0n;
ans = new Point(0n, 0n);
for(i=1n;i<20n;i+=1n){
    ans = point_add(ans, p1, 1n, 23n);
    console.log(ans);
    console.log(get_ng(i, p1, 1n, 23n));
}

输出这里就略掉了，可以看到都是一样的。

0x04 椭圆曲线密钥交换算法（ECDH）

ECDH跟DH的流程基本是一致的。
1.小红和小明约定使用某条椭圆曲线（包括曲线参数，有限域参数以及基点P等）
2.小红生成私钥x，计算xP作为公钥公布出去
3.小明生成私钥y，计算yP作为公钥公布出去
4.小红得知yP后，计算 s=x(yP)=xyP
5.小明得到xP后，计算 s=y(xP)=yxP
6.双方都得到了相同的密钥s（因为s是一个点，实际上会取s的横坐标值作为密钥），交换完毕。

//一个生成256bit随机数的代码
function get_random_256(){
    let i = 0n;
    let ans = 0n;
    for(i=0;i<64;i++){
        ans += BigInt(Math.floor(Math.random()*16));
        ans <<= 4n;
    }
    ans >>= 4n;
    return ans;
}

// 1.小红和小明约定使用某条椭圆曲线（包括曲线参数，有限域参数以及基点P等）
// G x, y values taken from official secp256k1 document
var Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240n;
var Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424n;
var secp_p = 2n ** 256n - 2n ** 32n - 977n;
var secp_n = 2n ** 256n - 432420386565659656852420866394968145599n;
secp = new Point(Gx, Gy);

// 2.小红生成私钥x，计算xP作为公钥公布出去
var x = get_random_256();
var xp = get_ng(x, secp, 0n, secp_p)

// 3.小明生成私钥y，计算yP作为公钥公布出去
var y = get_random_256();
var yp = get_ng(y, secp, 0n, secp_p);

// 4.小红得知yP后，计算 s=x(yP)=xyP
var xyp = get_ng(x, yp, 0n, secp_p);

// 5.小明得到xP后，计算 s=y(xP)=yxP
var yxp = get_ng(y, xp, 0n, secp_p);

// 6.双方都得到了相同的密钥s（因为s是一个点，实际上会取s的横坐标值作为密钥），交换完毕。
console.log(xyp.x);
console.log(yxp.x);
//可以看到，二者是相同的，而且第三方没办法在只知道xP和yP的情况下计算出x或y的值。

0x05 椭圆曲线数字签名算法ECDSA

ECDSA算法要用到哈希函数，这里给出一种能直接在浏览器运行的 sha256：

const hashBrowser = val =>
  crypto.subtle.digest('SHA-256', new TextEncoder('utf-8').encode(val)).then(h => {
    let hexes = [],
      view = new DataView(h);
    for (let i = 0; i < view.byteLength; i += 4)
      hexes.push(('00000000' + view.getUint32(i).toString(16)).slice(-8));
    return hexes.join('');
  });
  hashBrowser('hello').then(console.log); 
  //2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

若是nodejs环境可以使用crypto库

var crypto = require('crypto');
crypto.createHash('sha256').update("Hello").digest();
//<Buffer 2c f2 4d ba 5f b0 a3 0e 26 e8 3b 2a c5 b9 e2 9e 1b 16 1e 5c 1f a7 42 5e 73 04 33 62 93 8b 98 24>

然后是把上述两者转换成数字的函数：

function hex2num(buf){
    return Bigint('0x'+buf);
}

function buffer2num(buf){
    res = 0n
    for(i = 0;i < buf.length;i++){
        res *= 256n;
        res += BigInt(buf[i]);
    }
    return res;
}

ESCDA的算法可以参考这篇文章：一文读懂ECDSA算法如何保护数据， 这里给出代码：

var privateKey = get_random_256();
var publicKey = get_ng(privateKey, secp, 0n, secp_p);

var rand = get_random_256();

function create_signature(msg, privateKey){
    var rand = get_random_256();
    var hash_num = buffer2num(crypto.createHash('sha256').update(msg).digest());

    var tmp_point = get_ng(rand, secp, 0n, secp_p);

    var sig = (get_inverse(rand, secp_n)*(hash_num+privateKey*tmp_point.x))%secp_n;
    return [tmp_point.x, sig];
}

var sig = create_signature('hello', privateKey);
console.log(sig);

function verify_signature(msg, sig, publicKey){
    var hash_num = buffer2num(crypto.createHash('sha256').update(msg).digest());

    var z = get_inverse(sig[1], secp_n);
    var u1 = (hash_num * z) % secp_n;
    var u2 = (sig[0] * z) % secp_n;

    var tmp_point_a = get_ng(u1, secp, 0n, secp_p);
    var tmp_point_b = get_ng(u2, publicKey, 0n, secp_p);

    var tmp_point_c = point_add(tmp_point_a, tmp_point_b, 0n, secp_p);

    if(tmp_point_c.x === sig[0]){
        return true;
    } else {
        return false;
    }
}

console.log(verify_signature('hello', sig, publicKey));

运行结果：

[
  106125970590837898963543318604922501655587713131762488617508912548024413779984n,
  46432126777832730161356900205711454009927346565305507216353403867728159578311n
]
true

算法的验证

这里我决定使用nodejs中已经有的ecc库 ecccrypto 对刚才的算法进行验证：

var eccrypto = require('eccrypto');
function num2buffer(num){
    res = '';
    table = '0123456789abcdef';
    while(num > 0n){
        res = table[parseInt(num&15n)]+res;
        num >>= 4n;
    }
    if(res.length%2==1){
        res = '0'+res;
    }
    return Buffer.from(res, 'hex');
}

// ecccrypto 生成的公私钥
var privateKeyA;
var publicKeyA;
// 之后用于计算的整数
var privateKeyB;
var publicKeyB;

privateKeyA = eccrypto.generatePrivate();
publicKeyA = eccrypto.getPublic(privateKeyA);

privateKeyB = buffer2num(privateKeyA);
publicKeyB = get_ng(privateKeyB, secp, 0n, secp_p);

sig = create_signature('hello', privateKeyB);
r_buffer = num2buffer(sig[0]);
s_buffer = num2buffer(sig[1]);
r_len = BigInt(r_buffer.length);
s_len = BigInt(s_buffer.length);
total_len = r_len+s_len;

sig_der = Buffer.concat([                // 这里使用DER格式的签名
    num2buffer(0x30n),                    // SEQUENCE TAG
    num2buffer(total_len + 4n),            // SEQUENCE LEN
    num2buffer(0x02n),                    // INTEGER TAG
    num2buffer(r_len),                    // INTEGER LEN
    r_buffer,                            // INTEGER VALUE
    num2buffer(0x02n),                    // INTEGER TAG
    num2buffer(s_len),                    // INTEGER LEN
    s_buffer,                            // INTEGER VALUE
]);
eccrypto.verify(publicKeyA, crypto.createHash("sha256").update('hello').digest(), sig_der).then(function() {
    console.log("Signature is OK");
  }).catch(function() {
    console.log("Signature is BAD");
  });

最后输出：

Signature is OK