加密货币安全基石：直观理解ECC椭圆曲线加密算法
背景: ECC 是一种极其巧妙的非对称加密算法, 其完美利用了 椭圆曲线几何累加 不可逆的性质，拥有 密钥体积小，计算速度快的优势，被广泛用于各种区块链，移动端APP的认证过程。 此文章致力于用最少的数学公式解释 ECC 椭圆曲线加密算法 ，包括椭圆曲线加法/乘法性质，推广到有限域上面的加法/乘法性质，到椭圆曲线上的离散对数问题，进而推导到非对称加密， 安全性分析.
什么是 椭圆曲线
x, y 符合以下定义的曲线就是 椭圆曲线:
y2=x3+ax+b,且4a3+27b2≠0y^2 = x^3 + a x +b , 且 4 a^3 +27 b^2 \neq 0 y2=x3+ax+b,且4a3+27b2=0
它可以是下面的各种形状:
椭圆曲线 上的加法
接上面, 椭圆曲线长上面那种样子都无所谓，我们这里不care它的形状的, 我们来讨论在椭圆曲线上面做加法。
假设有一个点P 和 点Q， 那么我们定义 P + Q 为 : 经过 P,Q 两点的直线与 椭圆曲线的交点, 再将这个交点做 关于 X轴的对称， 关于 x 轴的对称点 就是 P+Q 。 比如下面这幅图:
聪明的你可能会问如果P,Q两点重合怎么办, 重合的话 就是 P+P =2P, 也就是 P点的切线 与椭圆曲线的交点, 再将这个交点做 关于 X轴的对称， 关于 x 轴的对称点 就是 2P.
椭圆曲线上 两点相加计算公式
如果有两个点 (x1,y1)(x_1, y_1)(x1,y1) ， (x2,y2)(x_2, y_2)(x2,y2), 那么 两点相加得到 (x3,y3)(x_3, y_3)(x3,y3) 公式如下:
x3=k2−x1−x2y3=k∗(x1−x3)−y1k=(y2−y1)/(x2−x1),当x1≠x2时k=(3x12+a)/2y1,当x1=x2时 x_3 = k^2 - x_1 -x_2 \newline
y3 = k*(x_1 - x_3) - y_1 \newline
k = (y_2-y_1)/ (x_2-x1), 当 x_1 \neq x_2 时 \newline
k = (3 x_1^2 +a) / 2 y_1, 当 x_1 = x_2 时 x3=k2−x1−x2y3=k∗(x1−x3)−y1k=(y2−y1)/(x2−x1),当x1=x2时k=(3x12+a)/2y1,当x1=x2时
上面这个公式其实就是 给定两点 求直线, 再求 直线与椭圆曲线的交点，然后关于 x 轴对称的结果， 计算过程非常复杂，需要解三次方程， 你只需要知道有这个公式即可
椭圆曲线 上的加法 推广到 乘法
有了 2P, 那么同样的方法 求出3P。 我们将 过 P点和2P点做一条直线, 这条直线与 椭圆曲线的交点的 关于 X轴 对称就是 3P, 比如下面这样:
依次类推, 我们可以画出 4P, 5P... NP, 只要不停地连接两点画直线 找出与 椭圆曲线的交点, 再关于 X轴对称即可。我们把这叫做 椭圆曲线上的乘法。
事实上计算NP并不是需要一步步进行计算, 比如计算 100P， 并不用计算 1P, 2P, 3P, ..., 99P. 我可以直接告诉你一个结论 那就是 椭圆曲线上的加法符合结合律。我把 计算100P展开来说：
100P = 50P+50P, 而 50P =25P+ 25P , 25P =1P +24P, 24P = 12P +12P, 12P=6P+6P, 6P=3P+3P, 3P=1P+2P, 2P=1P+1P， 也就是计算 100P ，我实际上并不需要做100次加法， 而只需要做 8次加法即可，每当 NP(N为偶数时), 都可以将 NP 拆成 两个 N/2 * P 之和。 所以正向的椭圆曲线上的乘法是很快的。
从连续的椭圆曲线 推广到 有限域
根据上面的分析， 你已经知道了椭圆曲线在连续曲线上的加法和乘法了。
但如果要在计算机上面使用椭圆曲线的乘法, 则还需要解决两个问题
将连续的曲线进行离散化处理，计算机是不能处理 1.111111111111111... 这种精度无穷大的小数的
将离散化的曲线个数进行有限化，计算机无法处理一个无穷大的数字的
解决方法也很简单，对症下药既可：
对连续的曲线进行取整, 对x只考虑整数
对曲线表达式两边同时进行 取模 操作, 取模操作约束了 等式左右两边的大小
如此一来, 离散且有限的"曲线" 表达式就变成下面这样:
y2≡x3+a∗x+b(modp),x∈Z且4∗a3+27∗b2≠0y^2 \equiv x^3 + a*x + b (mod p) , x \in Z 且 4*a^3 +27*b^2 \neq 0 y2≡x3+a∗x+b(modp),x∈Z且4∗a3+27∗b2=0
这条曲线记作 GF(p)GF(p)GF(p), 特别的是 p 一般取质数(实际应用中会取大质数)。 之所以取质数，是为了取值的多样性，为了最后结果的抗碰撞性。
在 GF(p)GF(p)GF(p) 上的加法变成了这样:
x3≡k2−x1−x2（modp)y3≡k∗(x1−x3)−y1（modp）k≡(y2−y1)/(x2−x1)(modp),当x1≠x2时k≡(3∗x12+a)/2∗y1(modp),当x1=x2时 x_3 \equiv k^2 - x_1 -x_2 （mod p) \newline
y3 \equiv k*(x_1 - x_3) - y_1 （modp）\newline
k \equiv (y_2-y_1)/ (x_2-x1) (mod p), 当 x_1 \neq x_2 时 \newline
k \equiv (3*x_1^2 +a) / 2*y_1 (mod p), 当 x_1 = x_2 时
x3≡k2−x1−x2（modp)y3≡k∗(x1−x3)−y1（modp）k≡(y2−y1)/(x2−x1)(modp),当x1=x2时k≡(3∗x12+a)/2∗y1(modp),当x1=x2时
我们用 python 画一下 y2≡x3+x+1(mod23) y^2 \equiv x^3 + x +1 (mod 23)y2≡x3+x+1(mod23)的图像
import matplotlib.pyplot as plt
# 定义有限域上的曲线方程
def curve(x):
return (x**3 + x + 1) % 23
# 生成离散的数据点
x = []
y = []
txt = []
for i in range(23):
for j in range(23):
if curve(i) == j**2 % 23:
x.append(i)
y.append(j)
txt.append('(' +str(i)+',' + str(j)+')')
# 绘制曲线图像
plt.figure(figsize=(13, 10))
plt.scatter(x, y, marker='o' , s=50)
for i in range(len(x)):
plt.annotate(txt[i], xy = (x[i], y[i]), xytext = (x[i]+0.05, y[i]+0.1),fontsize=15)
plt.xlabel('x', fontsize=20)
plt.ylabel('y', fontsize=20)
plt.title('y^2 ≡ x^3 + x + 1 (mod 23)',fontsize=25)
plt.xlim(-1,15)
plt.ylim(-2,24)
plt.grid(True)
plt.show()
图上的每一点都满足 y2≡x3+x+1(mod23) y^2 \equiv x^3 + x +1 (mod 23)y2≡x3+x+1(mod23)。 比如(3,10)这个点，恒等式左边 102mod(23)=100(mod23)=810^2 mod(23) = 100 (mod23) =8102mod(23)=100(mod23)=8, 恒等式右边 33+3+1mod(23)=8 3^3 + 3 +1 mod(23) = 833+3+1mod(23)=8.
接下来试试有限域上面的加法, 给定一点 P=(3,10)P=(3,10)P=(3,10), 求 2P2P2P
解:
2P=P+Pk≡(3∗x12+a)/2∗y1（mod23）=(3∗32+1)/(2∗10)=7/5(mod23)令n≡7/5(mod23)→5∗n≡7mod(23)=7→n=6故k=6x3=62−3−3(mod23)=7(mod23)=7y3=6∗(3−7)−10=−34(mod23)=12即:2P=（7，12）2P= P+P \newline
k \equiv (3*x_1^2 +a) / 2*y_1 （mod 23） = (3*3^2 +1) / (2* 10) = 7/5 (mod23) \newline
令 n \equiv 7/5 (mod23) \rightarrow 5*n \equiv 7 mod(23)=7 \rightarrow n=6 \newline
故 k=6 \newline
x_3 = 6^2-3-3 (mod 23) = 7 (mod23)= 7 \newline
y_3 = 6*(3-7)-10 = -34 (mod 23) =12 \newline
即: 2P= （7，12）2P=P+Pk≡(3∗x12+a)/2∗y1（mod23）=(3∗32+1)/(2∗10)=7/5(mod23)令n≡7/5(mod23)→5∗n≡7mod(23)=7→n=6故k=6x3=62−3−3(mod23)=7(mod23)=7y3=6∗(3−7)−10=−34(mod23)=12即:2P=（7，12）
依此类推, 可以计算 3P, 4P ...， kP
我们用python计算 P, 2P, ..., 22P
import matplotlib.pyplot as plt
# 定义有限域GF(p)
p = 23
# 定义椭圆曲线方程 y^2 = x^3 + ax + b (mod p)
a = 1
b = 1
# 定义椭圆曲线上一个点P(x, y)
P = (3, 10)
# 点乘运算 Q = dP
def ecc_point_multiply(P, d, a, p):
Q = (0, 0)
for i in range(d):
Q = ecc_point_add(Q, P, a, p)
return Q
# 点加法
def ecc_point_add(P, Q, a, p):
if P == (0, 0):
return Q
if Q == (0, 0):
return P
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 != y2:
return (0, 0)
if P == Q:
return ecc_point_double(P, a, p)
s = (y2 - y1) * pow(x2 - x1, p - 2, p) % p
x3 = (s*s - x1 - x2) % p
y3 = (s*(x1 - x3) - y1) % p
return (x3, y3)
# 点倍运算
def ecc_point_double(P, a, p):
if P == (0, 0):
return (0, 0)
x1, y1 = P
s = (3*x1*x1 + a) * pow(2*y1, p-2, p) % p
x3 = (s*s - 2*x1) % p
y3 = (s*(x1 - x3) - y1) % p
return (x3, y3)
k=[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]
Q=[]
txt = []
for i in range(len(k)):
Q.append ( ecc_point_multiply(P, k[i], a, p) )
txt.append(str(i+1)+'P')
plt.figure(figsize=(15, 10))
for i in range(len(Q)):
plt.scatter(Q[i][0], Q[i][1], marker='o' , s=50, color ='gray')
for i in range(len(Q)):
plt.annotate(txt[i], xy = (Q[i][0], Q[i][1]), xytext = (Q[i][0]+0.1, Q[i][1]+0.1),fontsize=15)
for i in range(len(Q)-1):
plt.plot([Q[i][0],Q[i+1][0]] , [Q[i][1],Q[i+1][1]] )
plt.xlabel('x', fontsize=20)
plt.ylabel('y', fontsize=20)
plt.title('y^2 ≡ x^3 + x + 1 (mod 23), p=（3，10), Q=kP',fontsize=20)
plt.xlim(-1,20 )
plt.ylim(-1,23)
plt.grid(linewidth=0.5, color='gray')
plt.show()
说明一下这里计算 Q=kP 还是使用了暴力计算(和逆求解k相同)，并没有使用 将 逐步二分拆解的优化(比如100P = 50P+50P, 而 50P =25P+ 25P , 25P =1P +24P, 24P = 12P +12P, 12P=6P+6P, 6P=3P+3P, 3P=1P+2P, 2P=1P+1P, 只需计算8次这种优化) 。这里的 k 和 p都 比较小, 放上代码只作为一个 demo。实际应用中还是得通过优化将为 logK。
可以看到在有限域上的乘法操作非常的无序，混乱，完全没有任何规律。这种杂乱无章的特性就非常适合用来加密， 让人无从下手，找不到任何规律，才能保障密文的安全性。
从 椭圆曲线上的乘法 推广到 非对称加密
椭圆曲线上的离散对数问题
在上面的章节中，我们讲解了什么是椭圆曲线上的加法乘法，也推广到了有限域上面的椭圆曲线的加法乘法。我们总结一下 有限域 上面的乘法的性质:
乘法很快
乘法的系数不同，最后的结果千差万别，非常混乱
回顾一下有限域上面的乘法问题，可以总结成下面这个公式(对几个符号做了重新对命名，和大多数教程保持一致):
Q=dGQ=dGQ=dG， Q为终点, G为起点, k 乘法为系数
因为是有限域，我们不妨把上面这个式子写的直白些:
Q(modp)≡dG(modp)Q(modp)\equiv dG(modp)Q(modp)≡dG(modp)
上式子可以推导出:
Gd≡Q(modp) G^d \equiv Q(modp)Gd≡Q(modp), G^d 和 dG 是一样的操作, 这里有点累比, 因为有限域上面只有 一个数字乘一个点，点和点是无法的直接相乘的只能相加，但因为多个点相加是杂乱无序的，所以可以类比成数字中的 求高次方。
现在问题来了，针对以下这个式子:
Gd≡Q(modp) G^d \equiv Q(modp)Gd≡Q(modp), 如果 p 是一个很大的质数， 给定你一个数字很大起点G(或者你累比成一个数字)和一个数字很大的终点Q（或者你累比成一个数字），你将如何求解d.
答案是非常难以求解，并没有什么高效的算法，这个问题也就是大名鼎鼎的 离散对数问题。
这个性质是不是很熟悉？正向容易计算, 逆向极其困难， 是不是和RSA有点像了？ RSA 根据 私钥计算公钥很容易, 公钥反推私钥几乎不可能。
rsa 加密算法的安全性保障在于 大整数的质因数分解 非常困难， 而ecc 加密算法的安全性保障就在于 离散对数问题的求解问题非常困难。 如果你发明了什么方法可以有效求解这个问题，那么 菲尔兹奖 就非你莫属了hhh
从 椭圆曲线上的离散对数问题 到非对称加密
如果我们将 d 看作私钥, 那么 G 就可以被看作公钥， 这就是 椭圆曲线非对称加密算法的原理, 椭圆曲线加密算法的强度保障就在于 给定G 和 d 计算 Q是否容易, 但反之 给定G和Q 想要计算 d 则是否困难。
具体如何加解密:
选定一条椭圆曲线, 选定起点(也叫基点)G(通常选得非常大)， 选取一个整数 d( k 加密过程如下: 选取一个随机整数r ( r CipherText=[CipherText1,CipherText2]=[rG,M+rQ]=[rG,M+rdG]其中M为原始数据在椭圆曲线上的编码,也是一个坐标点 CipherText= [CipherText1, CipherText2] =[rG, M+r Q] =[rG, M+rdG] \newline 其中 M 为 原始数据在 椭圆曲线上的 编码, 也是一个坐标点CipherText=[CipherText1,CipherText2]=[rG,M+rQ]=[rG,M+rdG]其中M为原始数据在椭圆曲线上的编码,也是一个坐标点 解密过程如下: M+rdQ−rdG=M+drG−drG=M其中rG为CipherText1 M+rdQ - rdG= M+drG-drG= M \newline 其中 rG 为 CipherText1M+rdQ−rdG=M+drG−drG=M其中rG为CipherText1 如何直观理解这种加解密方式呢 相信你看到这里，总算看懂了ecc加密的原理，但是还差那么一点意思才能醍醐灌顶，就是加密公式为什么要这么设计。 其实这么设计加密和解密的公式非常直观, 可以从以下几个方面考虑: 利用 Q=dG 对原文 M 做运算, 很自然想到用 M + dG, 因为椭圆曲线上 只能有 点和点的加法 和 点和数字的乘法, 已经有了 dG 是一个点, 所以只能拿这个点 去 + M 增加随机性, 所以在 dG 前面带了个随机数 r, 加密公式变成了 M+rdG =M+rQ, Q为公钥 因为解密的公式需要计算 rG, 所以加密方需要将 rG 一起发送到解密方 椭圆曲线非对称加密 安全性分析 椭圆曲线参数公开, 基点P公开, Q 公开, 私钥 d 解密方保密, r 为加密方保密(一次性随机数) CipherTextCipherTextCipherText 加密需要 公开的 Q, M ,以及 一次性随机数 r CipherTextCipherTextCipherText 解密需要 公开的 CipherTextCipherTextCipherText 以及 私钥 d 欲截获 CipherTextCipherTextCipherText 并破解 只有两种可能: 想办法获取到私钥 d, 若私钥不泄露则无此风险 直接通过 M+rQ−rdG=M M+rQ-rdG= MM+rQ−rdG=M, 此处有两重困难： d只能通过 终点Q 和 基点G 反推, 上面分析过极其困难 r只能通过 终点 rG 和 基点G 反推, 也是极其困难的, 并且r 是一次性随机数, 本身就没有任何规律 Golang 中使用 ECC 如果想知道在 golang 中如何使用 ecc 加密，欢迎移步我的另一篇文章: 看完符合安全厂商标准的密码体系，再看看你公司的密码体系够安全吗 总结 至此，我已经完整地定性地推导了一次ECC椭圆曲线算法。 回顾一下, 我们从椭圆曲线的 几何加法说起, 从加法推广到乘法, 接着我们从连续的椭圆曲线推广到离散且有界的椭圆曲线(有限域)，接着推广到了椭圆曲线上的离散对数问题，这是椭圆曲线加密的 安全性根基，最后展示了 如何利用椭圆曲线上的 起点乘法单向性 进行加密和解密。