【笔记】⽤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) 的时候，就可以做出直线：
(1)b
y−y=
1k x−x+
其中：
有了这两个式⼦再和椭圆曲线：
相联⽴，就可以得到⼀个关于x的⼀元三次⽅程组，解出x3再代⼊1式就可以得到结果的点了。
接下来是⼀个点和⾃⼰相加。
按照定义，⼀个点和⾃⼰相加时画这个点的切线，得到切线的斜率后再带⼊13式就可以得到结果了。
计算切线的斜率可以通过求导的⽅式计算得出：
联⽴计算，就可以得出（我不会算，我直接抄的qaq）：
最后再注意下，有的时候斜率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 ;
k =x −x 21
x −y 21
y =2x +3ax +b
js代码加密软件F x =()x +3ax +b −y 2
F =x ′
3x +2a F =y ′
−2y
k =−=F x ′F y
′
2y 3x +a 2x =3k −2x −1x 2
y =3y +1k (x −2x )
1
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);
}
简单的验证
（节选⾃）
对于椭圆曲线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'+ Uint32(i).toString(16)).slice(-8));
return hexes.join('');
});
hashBrowser('hello').then(console.log);
//2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
若是nodejs环境可以使⽤crypto库
var crypto =require('crypto');
/
/<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>然后是把上述两者转换成数字的函数：
发表评论