Chapter 07 : 椭圆曲线（Elliptic Curve）算法¶
约 726 个字 1 张图片 预计阅读时间 4 分钟
ECC 算法简介¶
椭圆曲线可以定义成所有满足方程 \(E:y^2=x^3+ax+b\) 的点 \((x,y)\) 所构成的集合，若 \(x^3+ax+b\) 没有重复的因式或 \(4a^3+27b^2\neq 0\)（称为判别式），则 \(E:y^2=x^3+ax+b\) 成定义成为一个群、
数学基础¶
运算规则¶
椭圆曲线在素域 \(Z_{p}\) 上的运算规则如下：
- \(P+O=O+P=P\)
- 如果 \(P=(x_{1},y_{1}),Q=(x_{2},y_{2})\)，且有 \(x_{1}=x_{2}\) 以及 \(y_{1}=y_{2}=0\)，或有 \(x_{1}=x_{2}\) 及 \(y_{1}=-y_{2}\neq 0\)，则 \(P+Q=0\)
- 如果 \(P=(x_{1},y_{1}),Q=(x_{2},y_{2})\)，且排除上述两种情况，则 \(P+Q=(x_{3},y_{3})\)，其中：
- \(x_{3}=\lambda^{2}-x_{1}-x_{2}\)
- \(y_{3}=\lambda(x_{1}-x_{3})-y_{1}\)
- 当 \(P\neq Q\) 时，\(\lambda=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}\)
- 当 \(P=Q\) 时，\(\lambda=\frac{3x_{1}^{2}+a}{2y_{1}}\)
欧拉准则¶
设 \(p>2\) 是一个素数，\(x\) 是一个整数，\(\gcd(x,p)=1\)，则：
- \(x\) 是模 \(p\) 的平方剩余当且仅当 \(x^{\frac{(p-1)}{2}}\equiv 1(\text{ mod }p)\)
- \(x\) 是模 \(p\) 的平方非剩余当且仅当 \(x^{\frac{(p-1)}{2}}\equiv -1(\text{ mod }p)\)
点加运算¶
对于一条椭圆曲线，其由 6 个参数 \(a,b,p\)（确定素域 \(Z_{p}\) 上的椭圆曲线）和基点 \(G\)，\(G\) 的阶以及余因子，其中：
- 余因子为曲线的阶（即曲线上点的个数）除以 G 的阶，此值通常为 1
- 基点 G 是曲线上的一个点，通常是一个随机选取的点
- G 的阶是指 G 点的倍点数，即 \(kG=O\) 的最小正整数 \(k\)，其中 \(O\) 是椭圆曲线上的无穷远点
假设我们有 \(G=(2,7),a=1,b=6,p=11\)，点加运算 \(2G\) 方法如下：
- \(\lambda=\frac{3x_{1}^2+a}{2y_{1}}=8\text{ mod }11\)
- \(x_{3}=\lambda^2-x_{1}-x_{2}=8^2-2-2=5\text{ mod }11\)
- \(y_{3}=\lambda(x_{1}-x_{3})-y_{1}=8(2-5)-7=2\text{ mod }11\)
- 因此 \(2G=(5,2)\)
- 以此类推可以算到 \(13G=O\)
ECC 算法难以破解的重要原因在于其将 \(k\) 作为私钥，将 \(kG\) 作为公钥，且 \(k\) 的值通常非常大（比如 256 位），从 k 和 G 算出 kG 很容易，但从 kG 和 G 反推出 k 是极其困难的，因此无法通过暴力破解来找到 \(k\) 的值
ECC 加解密¶
ECC 算法将一个点 \(R=d*G\) 作为公钥点，私钥 \(d\) 是一个随机数，且 \(d<n\)，其中 \(n\) 是 \(G\) 的阶
加密而成的密文包括两部分：
- \(r=(k*G).x\)，其中 \(k\) 是一个随机数且 \(k<n\)
- \(s=m*(k*R).x\text{ mod }n\)，其中 \(m\) 是明文
解密过程为 \(m=\frac{s}{(dr).x}=\frac{m*(kR).x}{(d*(kG)).x}=\frac{m*(k*d*G).x}{(k*d*G).x}\)
ECC 算法签名验证¶
ECDSA¶
ECDSA 签名过程为 \(r=kG,s=\frac{m+r*d}{k}\)，其中 \(k\) 为随机数，\(m\) 为明文/Hash，\(d\) 为私钥
验证过程为 \((m/s)*G+(r/s)*R==r\)，如果伪造 \(m\) 或 \(d\)，都无法通过验证
ECNR¶
ECNR 签名过程为 \(r=kG+m,s=k-r*d\)
验证过程为 \(r-(s*G+r*R)==m\)