漫谈网络通讯加密(1)加密学算法之ECC

Tags:

ECC算法

直观认识什么是椭圆曲线

椭圆曲线,指的是满足这个维尔斯特拉斯通用式的曲线:

\[ y^{2} = x^{3} + ax + b , 且 4a^{3} + 27 b^{2} ≠ 0 \]

判别式(discriminant )不为0时,曲线才没有奇异点,才能用于加密。

3.png

到这里就能发现椭圆曲线第一个特点:整个曲线是关于x轴对称的

各类加密货币使用的椭圆曲线代号是secp256k1,长这样子:

5.png

用这个在线工具可以打印椭圆曲线:

import numpy as np
import pylab as pl

def f(x):
    return x**3 - x  # 替换掉这个方程,然后重新run

Y, X = np.mgrid[-10:10:100j, -10:10:100j]
pl.contour(X, Y, Y**2 - f(X), levels=[0])
pl.show()

7.png

ECC算法细节

曲线基本特点

  • 如果一条(不垂直于x轴的)直线与椭圆曲线相交(有2个相交点),那么必然存在第三个相交点。(证明过程?)
  • 第三个点相当于公钥
  • 椭圆曲线关于x轴镜像对称

无穷远点0 Point at infinity

无穷远点,或理想点,指理想化地认为一条直线在无穷远处有一个终点,一般以0表示。

椭圆曲线上的点的取反操作

因为椭圆曲线关于x轴对称,所以可定义:

对于任意椭圆曲线上的点P,对P取反后得到-P,-P为P关于x轴镜像对称点。

P + Q = R

前面已经提到,任意直线与椭圆曲线如果相交,那么必然有3个相交点。(记得相交线不能和x轴垂直)

在椭圆曲线加密算法中,定义了一个阿贝尔群,该群的的加法操作定义如下:

对于任意相交点P、Q、-R(这里取反是有意义的),若P!=-Q,有等式 P + Q + (-R) = 0 成立,即 P + Q = R。

  • 首先要注意,这个加法并不是欧氏几何加法,例如看下图, P + Q在欧氏几何中的结果是(-2.45,-1.024),而不是(3.89,5.62)
  • 该定义中,要求P!=-Q,也是有深意的:如果P=-Q,说明P和Q是关于x轴对称的2个点,那么P和Q应是R和-R,所以P!=-Q这个前提条件保证了P和Q不是那个特殊的R

8.png

base point P

在椭圆曲线加密算法中,第一步是定一个基准点P。

第二步是,找出从P到P的直线方程。此时会疑惑2个一样的点怎么构成直线,当然是可以的,这个直线是经过P点的和椭圆曲线相切的切线

8.png

根据前面小节的说明,这条切线必然会与椭圆曲线相交于另外一点-R,又因为P + Q = R(-R的镜像点),所以有 P + P = 2P = R:

8.png

这一个过程还可以迭代下去:因此此时已有P和2P两个点,如果让它们相加,即 P + 2P,那么又会得到新的一个镜像点3P:

8.png

继续迭代这个过程,就能得到4P、5P、6P······

nP + rP = (n+r)P

假设现在要求出10P,那么按上一节的迭代算法,就需要计算:

\[ P+P+P+P+P+P+P+P+P+P \]

这是很慢的过程,不过可以用群加法其中一个性质来加速:

\[ nP + rP = (n+r)P \]

当然还是不能一步到位,而是从9次加法变成了4次加法:

\[ P + P = 2P \]

\[ 2P + 2P = 4P \]

\[ 4P + 4P = 8P \]

\[ 2P + 8P = 10P \]

x为大数时,xP的计算问题

假设x是一个超大正整数,例如有256bits,32个字节这么大。那么要得到xP,得做多少次群加法呢?

这是个二进制的问题。首先假设x等于十进制的246(值很小,只用一个字节就能表示,是为了讨论方便),并把x二进制展开(binary expansion,是叫二进制展开吧?):

\[ 2^{7} + 2^{6} + 2^{5} + 2^{4} + 2^{2} + 2^{1} = 128 + 64 + 32 + 16 + 4 + 2 = 246 \]

等式两边都乘以P:

\[ 2^{7}P + 2^{6}P + 2^{5}P + 2^{4}P + 2^{2}P + 2^{1}P = 246 P \]

此时x=246的xP问题就解决了:先算出一系列\(2^{n} P\),n从0到255(255次群加法),然后用5次群加法就得到了246P,总共需要260次群加法。

当x的256bits都为1,即x取最大值时,也只需要做255+255=510次群加法。

逆向求xP的x

假设Bob和Alice玩一个椭圆曲线的游戏:Bob先保密地随机取一个256bits的x,并算出X = xP,把X点坐标告诉Alice;Alice也知道这个椭圆曲线方程以及P点,那么Alice是否可以求出x的值?

再复述下Alice掌握的信息:

  • 椭圆曲线方程,如:\(y^{2} = x^{3} - 7x \)
  • P点坐标,如:(-2.35, -1.86)
  • X点坐标,如:(123.456,789.123)(瞎写的)

Alice是否可以知道X是做了多少次对P的群加法得到的?如果能,需要多久?

答案是,现在世界上并没有一个快速算法求出x。唯一可行的笨办法是,遍历整个256bits范围的整数集,从1P开始,不断+P,直到发现nP=X,此时的n就是要求的x。

也有同样复杂度的逆算法:不断对X减P,直到减完时刚好就是P,此时统计减的次数,就是x了。

x落在\( [0, 2^{256} - 1] \),平均值为\( 2^{128} \)。因此平均需要暴力地做2128次群加法。

公钥私钥

基于上一节的讨论,x和X适合用来做非对称加密的私钥公钥:

  • 私钥:大数x
  • 公钥:椭圆曲线上的坐标X

非对称加密的公钥私钥必然要满足一个性质:给定一个公钥,很难去推导出它对应私钥。可见,x和X满足这个性质。

但X、x公钥私钥对并不能直接用于加密数据。这个事情后面再说。

谁才是主人公?持有私钥证明 part1

Bob持有私钥x,是事实,但Bob怎么向别人证明自己持有X对应的私钥x呢?

这个事情有点复杂,首先要改进下椭圆曲线的模型。

上面的椭圆曲线模型有个问题:xP这个点的坐标x、y可能会超大,x和y加起来可能大过一个公钥的存储极限,例如512bits。

解决方案是:在有限域上定义一个椭圆曲线。为此有2个新的限制:

  • 坐标点的分量限制为整数
  • 坐标点的分量取值范围不是无穷远

公式上的改变如下:

把 \( y^{2} = x^{3} + ax + b\) 改成:

\[ ( y^{2} ) \% p = ( x^{3} + ax + b ) \% p\]

p是一个大质数,例如在secp256k1椭圆曲线中,p的取值是【0, \( 2^{256} \) 】范围内的最大质数。

这么一转换后,椭圆曲线就变成大概这样子的东西:

8.png

离散的点集,但仍然有关于x轴的对称性。

而且,前面讨论的东西仍然是有效的。

谁才是主人公?持有私钥证明 part2

如何才能在不暴露x的前提下告诉别人“我”持有私钥呢?

首先拿出前面提到的加法结合律:

\[ n \cdot P + r \cdot P = ( n + r ) \cdot P \]

然后把n替换为这个东西:

\[ hash(m, \ r \cdot P) \cdot n \]

得到:

\[ hash(m, r \cdot P) \cdot n \cdot P + r \cdot P = ( hash(m, r \cdot P) \cdot n + r ) \cdot P \]

引入了一个新的m,以及关于m和rP的hash函数。

假设\(n \cdot P = X \)(X就是公钥X),代入上式,得到:

\[ hash(m, r \cdot P) \cdot X + r \cdot P = ( hash(m, r \cdot P) \cdot n + r ) \cdot P \]

又因为\(n \cdot P = X \),所以有n = x(x就是私钥x),继续代入,得到:

\[ hash(m, r \cdot P) \cdot X + r \cdot P = ( hash(m, r \cdot P) \cdot x + r ) \cdot P \]

此时再设2个新的对象R和s:

\[ R = r\cdot P \]

\[ s = hash(m, R)\cdot x + r \]

把R代入上面的方程,变成:

\[ hash(m, R) \cdot X + R = ( hash(m, R) \cdot x + r ) \cdot P \]

然后再代入s,最终得到:

\[ hash(m, R) \cdot X + R = s \cdot P (持有私钥证明方程)\]

这条方程就是持有私钥证明了:谁能够给出任意m、R、s,使得m、R、s代入上述方程使得等式成立,那么这个人就必然持有私钥x。

那么对持有人来说,怎么得到m、R、s呢?很简单:

  1. 随机生成m
  2. 随机生成r
  3. 计算\( R = r\cdot P \)
  4. 计算\( s = hash(m, R)\cdot x + r \)

这里提2个问题。一个是私钥安全问题:

对第三者来说,未知数是r和x,假设r泄露了给第三者,那么第三者就可以根据第4步的式子的变换,导出私钥x:

\[ x = \frac { s - r } { hash(m, R) } \]

所以r必须是用完就丢的。因为持有者只需要给出R就足够用予持有私钥证明。

另一个是暴力破解问题:

第三者是否可以暴力地找到合适的m、R、s代入持有私钥证明方程,使得方程成立?

假设可行,那么第一步应是先任意找出一组合适的参数:h( h = hash(m, R) )、R、s,使得\( hash(m, R) \cdot X + R = s \cdot P \) 成立,这肯定是办得到的。

然后下一步是,解出一个m,使得hash(m, R) = h成立。然而,如果选择了一个优质的cryptographic hash functions,是很难办到的。这也被称为原像攻击(Preimage attack ),即给定hash值,找出能hash出这个值得输入。

ECC的应用:数字签名(ECDSA)

前面已经论证了只有私钥持有者能给出m、R、s三元组,那么当m是一段有意义的消息(依然是一段字节序),而与这个m匹配的R、s,就成为这个消息m的签名了。

因为攻击者理论上并不能用自己随意篡改的m',使得m'、R、s能成功代入持有私钥证明方程。

ECC的应用:比特币

简单来说,要生成一个新的比特币钱包,需要先随机生成一个256bits的私钥x,然后根据比特币所用的椭圆曲线参数(secp256k1),计算X = xP,X就是这个钱包的公钥。

然后呢,X大有所为,X可以随便公开,X相当于钱包的银行账号,例如比特币转入这个钱包,就需要用到X。

转入问题是解决了,但怎么证明你是这个钱包的主人,并转出(消费)比特币呢?答案就是用上一节的方法,做一个持有私钥声明(即数字签名),转出事务广播开后,每个人都可以简单地验证这个持有声明的真伪性。

如果去观察比特币的事务消息,就会发现他它的数字签名部分就是一个椭圆曲线上的某坐标R和一个随机的256bits的s的组合。

ECC的参数集合(Elliptic Curve Domain Parameters)

纠正下前面介绍ECC相关参数的命名。

椭圆曲线算法有很多参数,被称为Elliptic Curve Domain Parameters:

  • a:椭圆曲线方程\( y^{2} = x^{3} + ax + b \) 里的a
  • b:椭圆曲线方程\( y^{2} = x^{3} + ax + b \) 里的b
  • G:即上文说的P,椭圆曲线上任意取得基准点坐标
  • p:质数p,用来控制值域范围的
  • n:基准点G的阶(order),即使得nG=0(无穷远点)的最小正整数。
  • h:辅因子(cofactor),h等于\( \frac {1}{n} | E(F_{p}) | \)。当h为最理想的1时,整个点群#E都可以被使用,否则,可用的点群大小只有#E/h。

可以这样理解n:nP = iP + jP = 0, 即椭圆曲线上某2个点iP、jP,它们的和nP为无穷远点,即经过iP、jP的直线垂直于x轴,当i+j=n取到最小值时,即为G点的阶。

8.png

(观察此图,发现5P + P = 6P = 0,P点的阶为6。进一步阅读

当阶数n和#E一样大时,h取到最佳值1。h的计算,必然要先理解透彻群论的知识,这里不做展开,可以阅读这2个链接:

https://math.stackexchange.com/questions/1394251/calculating-elliptic-curve-cofactor-h

https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves

ECC的应用:加密通讯 ECDH

要仅仅用ECC来加密数据,那么就要用到ECIES这个。

ECIES,即基于椭圆曲线的整合加密方案,与其类似的还有基于离散对数的整合加密方案 (DLIES)。

ECIES,也被称为Elliptic Curve Augmented Encryption Scheme(基于椭圆曲线的增强加密方案) 或简单地叫 Elliptic Curve Encryption Scheme(基于椭圆曲线的加密方案)。

Anyway,先以一个例子介绍下ECIES:Alice和Bob进行加密通讯。

通讯前准备:

  • 一个椭圆曲线和参数集合(p,a,b,G,n,h)
  • Alice已获得Bob的公钥\( K_{B} \)。\( K_{B} = k_{B}G , k_{B} \in [1, n - 1] \), \( k_{B} \)是Bob自己随机生成的私钥。(再次注意,\( k_{B} \)是值, 而\( K_{B} \)是一个椭圆曲线上的点。)
  • 双方共享信息: \( S_{1} ,S_{2}\) (nonce)

加密流程:(Alice加密原文m)

  1. 生成随机数r,计算R = rG
  2. 计算\(P = (P_{x}, P_{y}) = rK_{B} \),取P的x分量\(P_{x}\)作为共享密钥S。
  3. 用KDF密钥导出函数,导出定长的对称加密密钥\(k_{E} \)和MAC密钥\(k_{M} \),\( k_{E} || k_{M} = KDF(S || S_{1}) \)
  4. 加密消息:\( c = E( k_{E}, m) \),E代表Encrypt函数。
  5. 计算MAC:\( d = MAC(k_{M}, c|| S_{2}) \)
  6. 输出\(R || c || d\)

解密流程: ( Bob已收到\(R || c || d\) )

  1. Bob先求出Alice也在使用的共享密钥\(P_{x}\), \(P = (P_{x}, P_{y}) = rK_{B} = rk_{B}G = k_{B}R \),R是Alice发来的,\( k_{B} \)是本地的。
  2. Bob也用一样的方法求出2个密钥,\( k_{E} || k_{M} = KDF(S || S_{1}) \)
  3. 检查收到的d和自己算的d‘是否一致,不一致的话说明c被中间人篡改了:\( d' = MAC(k_{M}, c|| S_{2}) \)
  4. 此时就可以用对称加密密钥,解出消息m:\( m = E^{-1}(k_{E}, c) \) ,\(E^{-1}\)代表Decrypt函数(一般等同于Encrypt函数)。

其实这个流程就是非常著名的ECDH算法了。Alice和Bob利用ECC算法,进行了密钥交换,得到了\( P_{x} \)。

资料:

https://crypto.stackexchange.com/questions/31602/how-does-encryption-work-in-elliptic-curve-cryptography

补充:已知P、Q,怎么求R

这个问题其实是解方程组问题,一个是直线的方程: \(y = kx + c\),一个是椭圆曲线的方程:\( y^{2} = x^{3} + ax + b \)。

(推荐一个在线解方程组的工具:wolframalpha )

以这幅图为例:

8.png

假设已知的只有:

  • 椭圆曲线方程:\( y^{2} = x^{3} - 7x \)
  • P(-2.35089, -1.86107)
  • Q(-0.0999884, 0.836014)

现在目标是求,直线与曲线的第三个交点R(应该叫-R)的坐标。

第一步,化解方程组:

\[ y = kx + m, y^{2} = ax^{3} + bx^{2} + cx + d \]

\[ (kx + m)^{2} = ax^{3} + bx^{2} + cx + d \]

\[ 0 = ax^{3} + (b - k^{2}) x^{2} + (c - 2km)x + d - m^{2}\]

本例的椭圆方程的系数为:

\[ a = 1, b = 0, c = -7, d = 0\]

代入上式,得到:

\[ 0 = x^{3} - k^{2}x^{2} - (7 + 2km)x - m^{2}\]

第二步,搬出韦达公式,对于一元三次方程,它的根之间有如下关系式:

8.png

用到我们这里,就是:

\[ x_{1} + x_{2} + x_{3} = -\frac {b}{a} = -\frac { -k^{2} }{1} = k^{2} \]

\[ x_{1} * x_{2} * x_{3} = -\frac {d}{a} = -\frac { -m^{2} }{1} = m^{2} \]

\[ x_{1}x_{2} + x_{2}x_{3} + x_{1}x_{3} = \frac {c}{a} = \frac {- (7 + 2km)}{1} = - (7 + 2km) \]

又因为\(x_{1}、x_{2}、x_{3}\)其实就是\( P_{x}、Q_{x}、R_{x} \) ,所以有:

\[ R_{x} = k^{2} - (P_{x} + Q_{x}) \]

这样就求出了\(R_{x} \)。而R的y分量可以用斜率公式推出:

\[ \frac { R_{y} - P_{y} } { R_{x} - P_{x} } = k \]

\[ R_{y} = k (R_{x} - P_{x} ) + P_{y} \]

这里面还有个未知数斜率k,也是用斜率公式求出:

\[ k = \frac { Q_{y} - P_{y} } { Q_{x} - P_{x} } = 1.19822222 \]

最终的:

\[ R_{x} = (1.19822222)^{2} - ((-2.35089) + (-0.0999884)) = 3.8866148938271605 \approx 3.89 \]

\[ R_{y} = (1.19822222) (3.8866148938271605 - (-2.35089) ) + (-1.86107) = 5.6128469750035 \approx 5.61 \]

\[ -R = (3.89, 5.61),R = (3.89, -5.61) \]

和图片里的数值一样。

(未经授权禁止转载)
Written on April 4, 2018

博主将十分感谢对本文章的任意金额的打赏^_^