当前位置:首页 > 编程 > 算法 > 正文内容

ECC加密算法的理解

七星1年前 (2020-08-15)算法1138

写在最前面:

阅读本文需要心平气和,认认真真的读, 要带着思考与记忆阅读, 不能跳着读.


ECC算法和RSA一样, 是基于三大数学难题实现的.

他的数学难题是 椭圆曲线的离散对数难题

160位的ECC和1024位的RSA算法安全度差不多相同.所以ECC诞生了.

比特币和中国二代身份证都使用了256 比特的椭圆曲线密码算法.


说起椭圆曲线,可能立刻就会想起高中的椭圆曲线方程:

image.png

其实这里的椭圆曲线和上面这个无关.这里椭圆曲线的椭圆一词,来源于椭圆周长积分公式

image.png

所以得到的椭圆曲线是:

    E(a,b):y**2 = x**3 + ax + b

其中:

    1. Δ=−16(4*(a**3) + 27*b), Δ != 0 ,用来保证曲线是光滑的(没有奇点),即曲线的所有点都没有两个或者两个以上的不同的切线

    2. a,b∈K, K为E的基础域.

    3. 点 O 是曲线的唯一的无穷远点

下面举两个例子:

椭圆曲线:

image.png

上面这个在曲线的任何地方,都有唯一的切线.

再看看非椭圆曲线:

image.png

他在(0,0)点没有切线,他有一个奇点.

好了,现在搞懂了椭圆曲线的基本条件.


了解了基本条件,就来更深的探讨一下椭圆曲线.

我们定义这样一个椭圆曲线:y**2 = x**3 - x

然后在这个图像上找两个点,P和Q.过P,Q做一条直线, 交于R'.

再过R'做垂直于X轴的线,交于曲线的R点:

image.png

定义:R=P+Q.


当P=Q时,这条线就是切线:

image.png

此时,R = P+Q = P+P = 2P


现在取R与P或者R与Q连接,继续做直线,将会与椭圆曲线有一个新的交点R2',

然后过R2'作垂线又可以得到R2.所以R2=R+P或者R2=R+Q


当P=Q时, R = 2P.

所以R2 = 2P+P = 3P

然后循环,就能得到Rn = (n+1)P


image.png

上图说明: 给定一个G(也就是之前的P)点,使G=Q, 得到点2G', 做垂线得到2G.

连接2G和G连线,得到3G'.做垂线,得到3G.


通过上面的例子可以得知:

当给定一个点G时,“已知数k求点kG的运算”不难,因为有加法的性质,运算起来可以比较快。

但反过来,“已知点kG求k的问题”则非常困难,因为只能遍历每一个k做运算。

这就是椭圆曲线密码中所利用的“椭圆曲线上的离散对数问题”。


这个k就是椭圆曲线的阶


如果现在还没搞清楚, 可以重新阅读, 不要求全懂, 但至少得摸清楚上面最后这幅图中3G是怎么来的.


看到这, 可能已经对这个东西有了一点点的概念了.


接着我们引进另外一个东西, 叫无穷远点: O

在理解这个概念之前呢, 先得来看看平行线会不会相交这个问题.

在初中课本上, 平行线平行是一个公理.公理是啥,就是没有人证明它对不对, 但目前人们一致认为它是对的.

现在,我们假设, 在很远很远的地方, 没人看见的地方,平行线相交了, 那么, 这个交点就是无穷远点.

在椭圆曲线里面也可以用这种思考方式去思考下面这个东西:

image.png

上面这个图,已知椭圆曲线Ep:y**2 = x**3 +1.

在Ep(a,b)上,有个无穷远点,过这个无穷远点,做X轴的垂线, 交于圆锥曲线的P点与P'点.

而且,P'=-P, 也就是说, 这条线, 平行于Y轴.

根据之前讲的,此时就有了: O∞ = P + (- P)

通过这个加法可以看出, 这个无穷远点,相当于,没有.所以我们也称他为零元

这个P'就是P的负元,

所以,概念来了:

如果椭圆曲线上三个点P1 P2 P3在同一条直线上的话,那么他们的和等于零元,即:

P1 + P2 + P3 = O


当把上面的东西都理解了, 那么, 也就理解了椭圆曲线所满足的阿贝尔群了.

这里不详细写阿贝尔群,读者也可以不用管.知道有这么个概念就行了,反正已经满足条件了.


但是上面讲的所有内容,都是在实数域的基础上完成的,并不能用于加密.

要想把椭圆曲线应用到加密上,还需要把椭圆曲线变成离散的点.

椭圆曲线之所以是连续的,是因为椭圆曲线上的坐标是实数.

实数是连续的,所以曲线也是连续的.

所以将椭圆曲线定义到有限域(由有限个元素成的域,又叫伽罗瓦域)上,才能够使用椭圆曲线进行加密


现在定义一个有限域Fp,Fp满足以下条件:

  1. Fp中的p为质数.Fp有p个元素.

  2. Fp的加法是: a+b≡c(mod p) 

    这表示, 等式两边的运算值,除以p的余数应该恒等.

  3. Fp的乘法是: a*b≡c(mod p)

  4. Fp的除法是: a/b≡c(mod p),即a*b**(-1)≡c(mod p),b**(-1)也是一个0到p-1之间的整数,但满足b*b(-1)≡1(mod p)

然后定义一个椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]

于是就有了:

y**2 = x**3 + ax + b (mod p)

当有限域是F23的时候,E23(1,1)的图像长这样:

image.png

我们只需要他的整数点, 于是就有了这27个整数点:

image.png

上图,坐标为1的点,就是椭圆曲线在E23这个域里面的离散点,总共27个.

我们找一个基点,就比如(3,10)这个点.

然后我们就可以根据加法规则,求出圆锥曲线E23这个有限域内的所有阶(阶这个概念之前讲了,红色的字):

image.png


在这里我们发现, 这些点毫无规律可言,把之前的概念再搬过来品一品:

image.png

现在根据上面的图, 已知椭圆曲线Ep(a,b),基点G(3,10)和k=12,a=1,b=1.求12P.

得到的结果是kG(3,13),这个过程很容易.

但是,只知道基点G(3,10)和kG(3,13),求k,这里因为k比较小,所以可以通过穷举的方法得到k.

但是当k非常大时,得到k是困难的.


讲到这里,应该都明白密钥怎么来的了吧:

给定椭圆曲线Ep,基点G和点kG,即称kG点为公钥,k值为私钥.


在上述问题中的公钥私钥获取:

椭圆曲线E23(1,1):y**2 = x**3 + x + 1

n为E23的最大阶,所以n=27

基点G(3,10)和kG(3,13),k=12

    (k需要小于n,至于为什么,我想你应该秒懂,如果不懂,请回去接着看那个离散图的生成.)

其中kG就是公钥,写做K.所以就有了K=kG.

k就是私钥.


至此,密钥生成部分讲完.下面贴上密钥生成脚本:

image.png

image.png

image.png

image.png


密钥生成代码:

enECC.txt


对于攻防世界那一道新手题,可以说是so easy的:

image.png


这个椭圆曲线的函数图:

image.png

image.png

发现数字太大了,不做分析,直接上脚本:

好了,脚本卡了..散点图画不了.对于这道题, 没有必要画散点图.

因为基点G题目已经给了.

所以我们把画散点图的函数调用注释掉:

image.png

再次执行代码:

好了,又卡了.因为他在计算最大阶n.在题目里面已经给了k,所以代码再改改, 把求n的计算步骤省掉:

image.png

随便给个n.还是卡住了.

image.png


直接用github一个项目secp256k1来做,代码自己改改:

image.png


ECC_key.txt


终于写完了.等有空就把ECC对数据的加密和解密部分更新一下.


七星|qixingbit.com

相关文章

算法_逆波兰表达式求值

算法_逆波兰表达式求值

题目:根据逆波兰表示法,求表达式的值.有效的运算符包括: +  -  *  /每个运算对象可以是整数, 也可以是另一个逆波兰表达式.说明:  1.整数除法只保留...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。