之前为了一个项目所以去学了下椭圆曲线加密算法,本来是想写篇笔记细写算法的,但写了半天也没写出来什么,所以不如把自己摸索的东西用代码写出来了。之前项目用的nodejs,所以这里就用js写了。所有代码几乎全部可以直接在F12的控制台中运行。
0x01 点的定义 ecc中最基础计算单位自然就是一个个点了,点的定义非常简单,只要new
一个对象然后赋予其点的xy坐标即可。
1 2 3 4 5 6 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轴对称和有原点的特殊情况,就可以开始写代码了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 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 ) { 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 { 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 先把上面的代码都粘贴到控制台,然后:
1 2 3 4 5 6 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));
得到结果:
1 2 Point {x : 17n , y : 20n } Point {x : 7n , y : 12n }
再和答案对比: P+Q=(17,20) 2P=(7,12) 可以验证我们算法的正确性。
0x03 点的乘法 有了点的加法后,乘法就简单多了。 按照定义,nP即代表n个p相加。 我们当然可以写一个循环让P加上n次,不过这样效率太低了,这里我们使用快速算法加速:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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; }
和整数的快速乘法原理基本相同。
简单的验证 1 2 3 4 5 6 7 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的横坐标值作为密钥),交换完毕。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 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; } 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); var x = get_random_256();var xp = get_ng(x, secp, 0n , secp_p)var y = get_random_256();var yp = get_ng(y, secp, 0n , secp_p);var xyp = get_ng(x, yp, 0n , secp_p);var yxp = get_ng(y, xp, 0n , secp_p);console .log(xyp.x);console .log(yxp.x);
0x05 椭圆曲线数字签名算法ECDSA ECDSA算法要用到哈希函数,这里给出一种能直接在浏览器运行的 sha256:
1 2 3 4 5 6 7 8 9 10 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);
若是nodejs环境可以使用crypto库
1 2 3 var crypto = require ('crypto' );crypto.createHash('sha256' ).update("Hello" ).digest();
然后是把上述两者转换成数字的函数:
1 2 3 4 5 6 7 8 9 10 11 12 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算法如何保护数据 , 这里给出代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 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));
运行结果:
1 2 3 4 5 [ 106125970590837898963543318604922501655587713131762488617508912548024413779984n , 46432126777832730161356900205711454009927346565305507216353403867728159578311n ] true
算法的验证 这里我决定使用nodejs中已经有的ecc库 ecccrypto 对刚才的算法进行验证:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 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' ); } 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([ num2buffer(0x30n ), num2buffer(total_len + 4n ), num2buffer(0x02n ), num2buffer(r_len), r_buffer, num2buffer(0x02n ), num2buffer(s_len), s_buffer, ]); 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" ); });
最后输出: