建设厅网站查询三类人员,制作网站协议书,拍卖网站建设,汽车网站 源码ECDSA#xff08;Elliptic Curve Digital Signature Algorithm#xff09;是一种基于椭圆曲线密码学的数字签名算法。它用于确保数字数据的完整性和身份验证#xff0c;通常在信息安全和加密通信中使用。在日常使用中#xff0c;通常会使用一些函数库来实现完成这个算法的功… ECDSAElliptic Curve Digital Signature Algorithm是一种基于椭圆曲线密码学的数字签名算法。它用于确保数字数据的完整性和身份验证通常在信息安全和加密通信中使用。在日常使用中通常会使用一些函数库来实现完成这个算法的功能但是有部分情况是需要自高度自定义ECDSA相关逻辑的这里分享JavaScript语言在不借助第三方库的前提下纯手写的ECDSA算法代码并对其实现原理进行解释。 文章目录 1.ECDSA算法原理1.密钥生成算法2.签名算法3.验证算法4.正确性证明 2.纯手写ECDSA 应用场景说明3.JS实现的几大主要问题1.大数运算2.椭圆曲线群上的加法和乘法 4.完整代码以secp256k1为例 1.ECDSA算法原理
这里我直接copy之前自己文章中对其的详细描述。
ECDSA(Elliptic Curve Digital Signature Algorithm) 是使用椭圆曲线密码ECC对数字签名算法DSA的模拟。
ECDSA安全性依赖于基于椭圆曲线的有限群上的离散对数难题。与基于RSA的数字签名和基于有限域离散对数的数字签名相比在相同的安全强度条件下,ECDSA方案具有如下特点:
签名长度短密钥存储空间小特别适用于存储空间有限、带宽受限、要求高速实现的场合(如在智能卡中应用)。
1.密钥生成算法
设 G F ( p ) GF(p) GF(p)为有限域 E E E是有限域上 G F ( p ) GF(p) GF(p)上的椭圆曲线。选择 E E E上一点 G ∈ E G\in E G∈E G G G的阶为满足安全要求的素数 n n n即 n G O nGO nGO O O O为无穷远点。选择一个随机数 d d d d ∈ [ 1 , n − 1 ] d \in [1, n-1] d∈[1,n−1]计算 Q Q Q使得 Q d G QdG QdG那么公钥为 ( n , Q ) (n, Q) (n,Q)私钥为 ( d ) (d) (d)。
2.签名算法
签名者 A l i c e Alice Alice对消息 m m m签名的过程如下
1随机选取整数 k k k k ∈ [ 1 , n − 1 ] k \in [1,n-1] k∈[1,n−1]计算 k G ( x , y ) kG(x,y) kG(x,y) r ≡ x ( m o d n ) r \equiv x(mod \ n) r≡x(mod n)2计算 e h ( m ) eh(m) eh(m) h h h为安全的散列函数3计算 s ≡ ( e r d ) k − 1 ( m o d n ) s \equiv (erd)k^{-1}(mod \ n) s≡(erd)k−1(mod n)。如果 r 0 r0 r0或 s 0 s0 s0则令选取随机数 k k k重新执行上面的过程。消息 m m m的签名为 ( r , s ) (r,s) (r,s)。
3.验证算法
签名接收者 B o b Bob Bob对消息 m m m签名 ( r , s ) (r,s) (r,s)的验证过程如下
1计算 e h ( m ) eh(m) eh(m)2计算 u ≡ s − 1 e ( m o d n ) u \equiv s^{-1}e(mod \ n) u≡s−1e(mod n) v ≡ s − 1 r ( m o d n ) v \equiv s^{-1}r(mod \ n) v≡s−1r(mod n) ( x 1 , y 1 ) u G v Q (x_{1}, y_{1})uGvQ (x1,y1)uGvQ r 1 ≡ x 1 ( m o d n ) r_{1} \equiv x_{1}(mod \ n) r1≡x1(mod n)3若 r r 1 rr_{1} rr1则签名有效否则签名无效。
4.正确性证明
由于 Q d G s ≡ ( e r d ) k − 1 ( m o d n ) k G ( x , y ) u ≡ s − 1 e ( m o d n ) v ≡ s − 1 r ( m o d n ) ( x 1 , y 1 ) u G v Q QdG\\ s \equiv (erd)k^{-1}(mod \ n)\\ kG(x,y)\\ u \equiv s^{-1}e(mod \ n)\\ v \equiv s^{-1}r(mod \ n)\\ (x_{1},y_{1})uGvQ QdGs≡(erd)k−1(mod n)kG(x,y)u≡s−1e(mod n)v≡s−1r(mod n)(x1,y1)uGvQ 则有 k ≡ ( e r d ) s − 1 ≡ s − 1 e s − 1 ≡ u v d ( m o d n ) ( x , y ) k G u G v d G u G v Q ( x 1 , y 1 ) r 1 x 1 m o d n x m o d n r k \equiv (erd)s^{-1} \equiv s^{-1}es^{-1} \equiv uvd (\ mod \ n)\\ (x,y)kGuGvdGuGvQ(x_{1},y_{1})\\ r_{1}x_{1} \ mod \ n x \ mod \ nr k≡(erd)s−1≡s−1es−1≡uvd( mod n)(x,y)kGuGvdGuGvQ(x1,y1)r1x1 mod nx mod nr
2.纯手写ECDSA 应用场景说明
从头开始手写的ECDSA算法毫无疑问在算法的效率上以及拓展性上要比封装好的函数库低不少那么为什么还需要自己纯手写实现ECDSA的逻辑呢如果存在以下需求从头手写是一个好的选择。
1.如果需要对算法的逻辑进行高度的定制常见的函数库提供的拓展功能都无法满足需求。例如需要高度定义其随机数的产生部分函数库提供对随机数函数的拓展但是拓展能力有限、需要取到中间变量做一些其他的操作。2.想在客户端隐蔽的使用ECDSA算法不想直接使用三方包这样特征太明显。从攻击的角度来看对着一个经过混淆后纯手写的ECDSA算法代码如果不是对算法特别熟悉分析难度还是不小的。
当你想使用自己手写的ECDSA的时候就必须接受不能将其作为一个广泛应用、高频调用的算法包因为算法的效率会差不少。
3.JS实现的几大主要问题
我们回顾下上面算法的细节发现在JavaScript中实现主要有两个方面的问题需要解决
1.大数运算如何实现。2.如何做椭圆曲线群上的加法和乘法操作。
1.大数运算
对于第一个问题自从ECMAScript 2020ES11引入BigInt类型以来JavaScript原生支持大整数运算。BigInt类型用于表示任意精度的整数可以执行标准的算术操作。不需要额外的库但在一些老版本的浏览器中可能不受支持。
2.椭圆曲线群上的加法和乘法
对于第二个问题我们尝试推导下。
首先明确椭圆曲线上加法的定义假设有一根椭圆曲线 E : y 2 x 3 a x b E: y^2x^3axb E:y2x3axb其中 a a a 和 b b b 是曲线的参数 x x x 和 y y y 是曲线上的点坐标。在椭圆曲线上的加法操作定义如下
点加法给定曲线上的两个点 P P P和 Q Q Q点加法操作 P Q PQ PQ的结果是曲线上另一个点 R R R。加法规则 如果 P P P和 Q Q Q是相同的点那么点加法操作是对 P P P的倍乘即 P P PP PP。如果 P P P和 Q Q Q是不同的点并且它们不是垂直于 x 轴的那么点加法操作的步骤是连接 P P P和 Q Q Q计算直线 L L L找到直线与曲线 E E E的交点 R R R R R R关于x轴的对称点 − R -R −R就是 P Q PQ PQ的结果。特殊情况在某些情况下点加法操作可能会遇到特殊情况例如 P P P 与 Q Q Q 垂直于 x 轴或 P P P 与 Q Q Q 是互为相反元素。这些情况需要根据具体的椭圆曲线参数和实现进行处理。
从上可以看出我们主要需要处理的情况就是找到两点所确定的直线和曲线的交点对于这个交点我们尝试建立方程进行解出。
设 P P P的坐标为 ( x 1 , y 1 ) (x_{1},y_{1}) (x1,y1) Q Q Q的坐标为 ( x 2 , y 2 ) (x_{2},y_{2}) (x2,y2)两点所确立的直线为 y − y 1 k ( x − x 1 ) b y-y_{1}k(x-x_{1})b y−y1k(x−x1)b k x 1 − x 2 y 1 − y 2 k \frac{x_{1}-x{2}}{y_{1}-y_{2}} ky1−y2x1−x2。
通过求导的方式计算出 E E E上某点的斜率 F ( x ) x 3 a x b − y 2 F x ′ 3 x 2 a F y ′ − 2 y k − F y ′ F x ′ 3 x 2 a 2 y F(x)x^3axb-y^2\\F_{x}3x^2a\\F_{y}-2y\\k-\frac{F_{y}}{F_{x}}\frac{3x^2a}{2y} F(x)x3axb−y2Fx′3x2aFy′−2yk−Fx′Fy′2y3x2a
联立上式子可以解得直线 L L L与曲线 E E E的交点 x 3 k 2 − x 1 − x 2 y 3 y 1 k ( x 2 − x 1 ) x_{3}k^2-x_{1}-x_{2}\\y_{3}y_{1}k(x_{2}-x_{1}) x3k2−x1−x2y3y1k(x2−x1)
椭圆曲线上的乘法只需采用快速幂的方式进行加法运算即可。
至此用JS纯手写的两大核心问题都解决了具体细节处理见代码。
4.完整代码以secp256k1为例
下面代码已经过完整测试并以用于具体生产项目中。其中签名产生的v值为以太坊中相关约定不需要可以去除。签名值保证了s一定小于n的一半以太坊相关约定所以提取随机数的时候是会有两种可能。不需要该处逻辑可以去除。 // 椭圆曲线点定义
class Point{constructor(x,y){this.x BigInt(x);this.y BigInt(y);}
}
// secp256k1曲线
const secp_p BigInt(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F); // 2n ** 256n - 2n ** 32n - 977n;
const secp_n BigInt(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141); // 2n ** 256n - 432420386565659656852420866394968145599n;
const secp_a BigInt(0);
const Gx BigInt(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798);
const Gy BigInt(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8);
const secp_G new Point(Gx, Gy);function get_inv(x, y, p){return x 1n ? 1n : get_inv(y % x, y, p) * (y - y / x) % p;
}// 求模逆元
function modInverse(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, p){// 零点相加if(pa.x 0n pa.y 0n || pb.x 0n pb.y 0n){return new Point(pa.xpb.x, pa.ypb.y);}// 对称点相加if(pa.x pb.x pa.y ! pb.y){return new Point(0, 0);}// 定义斜率k的分母和分子let k, k_num, k_den;// k的分子分母计算if(pa.x pb.x pa.y pb.y){// 自己和自己相加 斜率为该点切线k_num 3n * pa.x * pa.x secp_a;k_den 2n * pa.y;} else {// 两点确定斜率k_num pa.y - pb.y;k_den pa.x - pb.x;}// k符号记载let neg 0;if(k_num * k_den 0n){neg 1;k_num k_num 0n ? k_num : -k_num;k_den k_den 0n ? k_den : -k_den;}// k化简分子分母let gcd get_gcd(k_num, k_den);k_num / gcd;k_den / gcd;// 分母不为1计算逆元if(k_den ! 1n){k_den modInverse(k_den, p);}k k_num * k_den % p;if(neg 1) {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);
}// 椭圆曲线点快速乘法
function point_mul(n, g, p){n BigInt(n)let ans new Point(0, 0);while(n 0n){if(n 1n){ans point_add(ans, g, p);}g point_add(g, g, p);n 1n;}return ans;
}export default {// 由私钥生成公钥generatePublicKey(privateKey) {// 私钥类型校验if(typeof privateKey ! bigint) {throw new Error(私钥不是BigInt类型);}const publicKey point_mul(privateKey, secp_G, secp_p);return publicKey;},ecSign(privateKey, msgHash, k) {// k类型校验if(typeof k ! bigint) {throw new Error(随机数k不是BigInt类型);}// k大小校验if(k 1n || k secp_n - 1n) {throw new Error(随机数k不符合要求);}// 私钥类型校验if(typeof privateKey ! bigint) {throw new Error(私钥不是BigInt类型);}// msg校验// if(typeof msg ! string) {// throw new Error(msg不是string类型);// }const d privateKey;//const e keccak256Int(msg);const e BigInt(0x msgHash);const kG point_mul(k, secp_G, secp_p);const r kG.x;var s modInverse(k, secp_n) * (e r * d) % secp_n;if(r 0n || s 0n) {throw new Error(随机数k不符合要求);}const v (kG.y % 2n) ^ (s * 2n secp_n ? 0n : 1n);if(s * 2n secp_n) {s secp_n - s;}return [r, s, v];},ecVerify(publicKey, msgHash, sign) {// msg校验// if(typeof msg ! string) {// throw new Error(msg不是string类型);// }const r sign[0];const s sign[1];const Q publicKey;//const e keccak256Int(msg);const e BigInt(0x msgHash);const s_inv modInverse(s, secp_n);const u s_inv * e % secp_n;const v s_inv * r % secp_n;const uG point_mul(u, secp_G, secp_p);const vQ point_mul(v, Q, secp_p);const uG_add_vQ point_add(uG, vQ, secp_p);const r1 uG_add_vQ.x;return r r1;},// 提取ECDSA随机数 s有两个可能会产生两个可能的k// privateKey msgHash 都是bigint sign [r, s]extractRandomK(privateKey, msgHash, sign) {// 私钥类型校验if(typeof privateKey ! bigint) {throw new Error(私钥不是BigInt类型);}// msg校验// if(typeof msg ! string) {// throw new Error(msg不是string类型);// }function recoverK(s) {const d privateKey;const r sign[0];//const s secp_n - sign[1];//const e keccak256Int(msg);const e BigInt(0x msgHash);const s_inv modInverse(s, secp_n);const k s_inv * (e r * d) % secp_n;return k;}return [recoverK(sign[1]), recoverK(secp_n - sign[1])];},
} ATFWUS 2023-09-02
