首页
论坛
专栏
课程

ECC椭圆曲线加密学习笔记

2019-8-8 21:32 1876

ECC椭圆曲线加密学习笔记

2019-8-8 21:32
1876

0x00 前言

之前做题的时候遇到一个ECC相关的题目,学习了好几篇大佬的文章ECC的剖析文章,学习之后也记录一下,写一遍加强自己的巩固。
此文章严格意义上来讲应该算是读书笔记,在总结过程中观摩了很多位前辈的帖子和书籍资料,一字一句的写下来最后也只是勉强理解了ECC,所以难免会有说的不严谨或是思考错误的地方,大佬们轻喷,也希望跟我一样刚开始学习的伙伴能够对ECC多一点点认识。

0x01 ECC介绍

椭圆曲线密码学(Elliptic curve cryptography),简称ECC,和RSA、ElGamel算法等类似,是一种公开秘钥加密的算法,也就是非对称加密。ECC被公认为在给定秘钥长度下最安全的加密算法。

0x02 数学引入

1. 平行线谈起

从初中数学开始,我们就知道两条平行线是永不相交的。不过到了近代这个结论也被质疑了,目前为止我们所见到的都是有限远的平行线,在有限远的距离内,平行线的确是永不相交的,可是在我们看不到的无穷远处呢,平行线会不会最终相交,这就变成一个问题。
所以平行线 a // b 永不相交是一个假设
所以也可以假设 a和b 最终会在一个无穷远处 P∞相交
根据这个假设做出下图:
图片描述

 

假设平行线a和平行线b相交于无穷远处P∞
所以P∞就是平行线的交点,为了区别, 之后将平面上的点称为平常点。
根据上面的简单分析可以得到以下几个特点:
(1) 直线L上只有一个无穷远点P∞
(2) 平面上一组相互平行的直线有公共的无穷远点,比如图中的a和b,所以所有平行线都应该相交于同一个无穷远点P∞
(3) 平面上任何相交的直线L1 和 L2有不同的无穷远点。(无穷远点是平行线的交点,既然L1和L2相交与平面了,那么他们的无穷远点肯定是不同的)
(4) 平面上全体无穷远点会构成一条无穷远直线。
(5) 平面上全体无穷远点与全体平常点构成射影平面。

2. 射影平面

射影平面的概念是从普通直角坐标系引入的,也就是中学时候笛卡尔积坐标系。
我们都知道,笛卡尔积坐标系是没有设置无穷点的,所以为了表示无穷远点,就产生了一个叫做射影平面坐标系的东西,这个射影平面坐标系可以同时表示无穷远点和平常点。
接下来看具体是如何建立射影平面坐标系的。
这是普通的笛卡尔积坐标系:
图片描述

 

坐标系上有一个点A,坐标为 A(4,3) x=4 y=3
现在令 x = x/z , y = y/z (z!=0),则可以将A点表示为A(x,y,z)
现在就在平面直角坐标系的基础上建立了一个新的坐标体系
代入运算一下:
这里 x/z = 4 y/z=3 (z!=0)
所以 x = 4z y = 3z
所以新的坐标系中A点坐标表示为A(4z,3z,z)
所以A(4,3,1)
B(8,6,2)
C(12,9,3)
...
等表示形式为(4z,3z,z)的点都是A点在新坐标系中的坐标表示。

3. 直线方程

中学的时候就知道,直线方程为:Ax + By +C = 0 (AB不同时为0)
根据上面的分析可以得到直线在新坐标系中的表示为: A(x/z) + B(y/z) + C = 0
左右乘以z可以得到新的直线方程为: Ax+ By + Cz = 0
现在假设有两条平行线:
L1: Ax + By + C1z = 0
L2: Ax + By + C2z = 0
C1 != C2 ,根据平行线的定义(斜率相同)可以得知L1 平行于L2
联立两条直线方程求解可以得知:
L1 : C1z = -(Ax + By)
L2 : C2 z = -(Ax + By)
所以C1z = C2z = -(Ax + By)
又因为C1 !=C2 所以 z = 0 所以-(Ax + By) = 0,也就是(Ax+By=0)
所以表达式为:Ax + By + C*0 = 0
所以无穷远直线表达式对应 z= 0
举个栗子:
假设现在有两条平行线:
L1 : x + 2y +3z =0
L2: x + 2y + z = 0
这里要求无穷远的交点,因为L1 // L2 所以可以得知z=0,所以x+2y=0
所以x = -2y
代入坐标点表示的话就是:
(注意无穷点处z=0)
(-2y:y:0)
所以
(-2:1:0)
(-4:2:0)
等形如(-2y:y:0) y !=0 的坐标表示就可以表示无穷点。
由此可见,新的坐标系可以表示平常点,也可以表示无穷远点。把这个可以表示平面上所有点的坐标系就称为射影平面坐标系。

4. 椭圆曲线

终于差不多讲到正题了, 之前花了比较长的篇幅讲射影平面坐标系,是因为椭圆曲线方程是建立在射影平面坐标系下的。
看看维基百科上对椭圆曲线是如何定义的:
图片描述

 

所以一条椭圆曲线在射影平面上满足Weierstrass方程的话表示为:
图片描述

 

对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,得到如下方程:
图片描述

 

约掉一个Z^3
图片描述

 

最后会得到一个简化版的方程:
图片描述

 

其中有三点需要注意:
(1) 椭圆曲线方程是一个齐次方程
(2) 曲线上的每个点都必须是非奇异的(光滑的),所谓非奇异,是指曲线上任意一点的偏导数Fx(x,y,z),Fy(x,y,z),Fz(x,z,y)不能同时为0。简单来说就是满足方程的任意一个点都存在切线。
(3) 椭圆曲线并与椭圆没有关系

 

根据上面的式子:现在举例一个椭圆曲线方程:
y^2 z = x^3 + xz^2 + z^3
当z=1 时推导出下面的方程式
y^2 = x ^3 +x + 1
得到的椭圆曲线图片:
图片描述

 

或者一个比较经典的椭圆曲线:
y^2 = x^3 -x
图片描述

5. 椭圆曲线阿贝尔群

在数学中,群是一种代数结构,由一个集合以及一个二元运算组成,已知集合和
运算(G,)如果是群则必须满足如下要求:
a. 封闭性:∀a,b∈G,a
b ∈ G
b. 结合性: ∀a,b,c∈G ,有 (ab)c = a (bc)
c. 单位元:ョe∈G, ∀a ∈G,有ea = ae = a
d. ∀a ∈G ,ョb∈G 使得 ab = ba = e

 

如果是阿贝尔群的话还需要满足交换律公理: a b = b a
比如在整数内的加法运算就是一个阿贝尔群(Z,+)
a. 封闭性满足:a和b都 ∈ Z 那么 a+b一定也∈Z
b. 结合性满足:(a+b) + c = a+ (b +c )
c. 单位元满足: 0即为单位元,因为所有整数来说 a+0=0+a=a
d. 逆向满足:a的逆元为-a 因为a+(-a) = 0 就是单位元
所以整数Z的加法运算(Z,+)属于阿贝尔群

 

同样的,椭圆曲线也可以定义加法和阿贝尔群。
还是以上面作图的椭圆曲线为例:
y^2 = x^3 -x
在曲线上找一个点P和Q,过P和Q作一条直线,交椭圆曲线为点R',再过R'点 作垂直于x轴的直线,交曲线另一点为R。定义P+Q = R如下图所示:
图片描述

 

当P=Q的时候,则过P点的切线相交与椭圆曲线为R',作x轴的垂直线相交与R
(作图是上面的图,右图是P=Q)
图片描述

 

根据定义,在左边的图中,R=P+Q
在右边的图中:R=P+P
所以这里可以把R称为2P 写作 R= 2P
同样的,可以得知 3P= P + P + P =R+P
椭圆的加法定义如下:
如同上图,我们在椭圆中取了P和Q做直线交椭圆与R',然后通过R'作垂线得到R所以得到R=P+Q
这样PQR'都在同一条直线上了
现在取R与P或者R与Q连接,继续做直线,将会与椭圆曲线有一个新的交点R2',然后过R2'作对称性又可以得到R2。所以R2=R+P或者R2=R+Q
在右边图这种情况的时候,P=Q
我们已经得到了R=P+P
那么现在连接R和P作一条新的直线与曲线相交于R2
那么R2 = R+P
也就是R2 = P+P+P
往复循环,R3 = P+P+P+P

 

图片描述

 

根据上面的定义可以得知:当给定点P时,“已知数x求点xG的运算”不难,因为有加法的性质,运算起来可以比较快。但反过来,“已知点xG求x的问题”则非常困难,因为只能遍历每一个x做运算。这就是椭圆曲线密码中所利用的“椭圆曲线上的离散对数问题”。
这里的xG表示为x倍的G,G表示基点,也就是说已知椭圆曲线上一个点G,也知道x,求xG的话直接x个G相加即可得到,但是如果只知道G和xG,要想求出x的话,几乎不可能。
但是这个运算光是这样还不能满足阿贝尔群的性质,如果想要满足,则还需要引入一个无穷远点O∞
现在假设椭圆曲线无穷远点O∞与椭圆曲线上一个点P的连线交于了P',过P'作y轴的平行线相交与P,所以有无穷远点O∞ + P = P,这样无穷远点的O∞的作用于普通加法中0的作用就差不多了,比如0+5=0这种。所以无穷点远O∞也被成为零元,P'成为P的负元,简称负P,记做-P。

 

图片描述

 

根据上面的描述又可以得知:如果椭圆曲线上三个点P1 P2 P3在同一条直线上的话,那么他们的和等于零元。也就是
P1 + P2 + P3 = O∞
现在椭圆曲线满足阿贝尔群了。
有限域上的椭圆曲线
但是上面介绍的所有内容,都是在实数域的基础上完成的,并不能用于加密上,要想把椭圆曲线应用到加密上,还需要把椭圆曲线变成离散的点。
椭圆曲线之所以是连续的,是因为椭圆曲线上的坐标是实数,实数是连续的,所以曲线也是连续的,所以如果将椭圆曲线定义到有限域上,才能够使用椭圆曲线进行加密。
现在定义一个有限域Fp
a. Fp中p(p为质数)个元素0,1,2,…, p-2,p-1
b. Fp的加法是a+b≡c(mod p)
c. Fp的乘法是a×b≡c(mod p)
d. Fp的除法是a÷b≡c(mod p),即 a×b^(-1)≡c (mod p),b-1也是一个0到p-1之间的整数,但满足b×b-1≡1 (mod p)
e. Fp的单位元是1,零元是 0
f. Fp域内运算满足交换律、结合律、分配律
椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
y^2 = x^3 + ax + b(mod p)
当这条曲线位于有限域F23的时候可以写作:
图片描述

 

这样表示等式左边与等式右边的值模23同余,图像表示如下:
图片描述

 

如果我们以椭圆曲线上的点P =(3,10)为基点,按照椭圆曲线“加法”运算的规则计算2P,3P,4P...结果如下图所示。
图片描述

 

我们可以看到,所产生的点可以说是无规律可言,例如点P = (3,10),点23P = (9,7)。在这里求离散对数问题就相当于已知点(3,10)和点(9,7),求23。在这个例子中p=23,问题还不难解,如果当p数值非常大时,要求出这个解是十分困难的。
这里还有一个概念:
有限域椭圆曲线点的阶:
指的是如果椭圆曲线上一点p,存在最小的正整数n使得数乘nP = O∞,则将n称为P的阶,若p不存在,则P是无阶的。

0x03 实际应用

上面已经提到过:
图片描述
其实椭圆曲线加密中,给定椭圆曲线E,基点G和点xG,即称xG为公钥,x值为私钥。上面已经分析过,已知私钥求公钥很简单,而已知公钥求私钥几乎是不可能的事情。
所以通过对椭圆曲线的分析,已经拿到了秘钥对,有了这个秘钥对,我们就可以进行加密通讯了。
还是经典的Alice要和Bob通讯为列子
现在分析一下椭圆曲线加密的流程:
首先Alice选定一个椭圆曲线Ep(a,b),并在椭圆上取一个基点G
Alice选择一个私钥k(k<n),并生成公开秘钥K = kG
Alice现在将E(椭圆曲线),K(公钥)和G(基点)传给Bob
Bob收到了Alice的信息,将待传输的明文编码到Ep(a,b)上的一点M,编码方式有很多..自行选择,并且在此时会产生一个随机数r (r<n)
Bob计算点C1 = M + rK和C2 = rG
Bob将计算得出的C1和C2传给Alice
Alice收到Bob的信息后,计算C1-kC2即可得到M
化解一下C1-kC2
C1 = M+rK
C2 = rG
所以C1 - C2 = M+rK - krG
根据乘法分配律 krG = r(kG)
根据第二条可以得知,K = kG
所以krG = rK
所以C1 - C2 实际上等于M + rK-rK = M
所以Alice只需要拿到这个C1和C2之后相减即可得到M,然后对M进行解码就可以得到明文。
我们来分析一下在传输过程中传输了一些什么
首先是Alice:Alice选定了曲线Ep,传输了自己的公钥K,以及选定的基点G
然后看Bob:Bob选定了随机数r,传输了通过r计算出来的C1和C2
这个传输为什么安全呢,接着往下看:(作了一张丑图)
图片描述

 

可以直观的看到传输过程中事Ep K G 以及C1 C2
根据几个表达式可以发现,想要通过公开传输的这几个信息拿到关键的r或者k几乎是不可能的。
所以在密码学中,描述一条Fp上的椭圆曲线常用到六个参量:T = (p,a,b,G,n,h)
其中p a b 用于确定一条椭圆曲线,G是用户A取得基点,n是点G的阶,h是椭圆曲线上所有点的个数m与n相处的整数部分。
这几个参量会直接决定加密的强度和安全性,所以一般要求:

  1. p取值越大越安全,但是加大强度带来的是性能上面的损失。一般情况下是200位左右
  2. n 应该是质数
  3. h<=4
  4. p != n*h
  5. pt !=1 (mod n) (1<=t<=20)
  6. 4a^3 + 27b^2 !=0 (mod p)

0x04 代码验证:

先测试一下,然后再补全,使用Python2.7环境
根据之前的分析,椭圆曲线的上取点p和q连成直线会与椭圆曲线相交于点R
逻辑为
r = p + q
if p != q
c = (py-qy)/(px-qx)
rx = c^2 - px-qx
ry = c(px-rx)-py
if q==p
c = (3px^2+a)/2py,rx = c^2-2px,ry=c(px-rx)-py

 

所以编写如下的函数计算r

def get_r(p, q,mod=MOD, a=A):
   p = map(lambda x: x % mod, p)
   q = map(lambda x: x % mod, q)
   if p[0] == q[0] and (p[1]+q[1])%mod==0:
       return [np.infty,np.infty]
   if p != q:
       c = (p[1]-q[1])*invert(p[0]-q[0], mod)%mod
   else:
       c = (3*p[0]**2+a)*invert(2*p[1],mod)%mod
   rx = (c**2-p[0]-q[0])%mod
   ry = (c*(p[0]-rx)-p[1])%mod
   return [rx,ry]

其中invert函数为:

def invert(element, mod):
   if element >= mod:
       element = element%mod
   if element == 0:
       return None
   for index in xrange(1, mod):
       if element*index%mod == 1:
           return index

get_add函数为

def get_add(G, multiple):
   lr = G
   for index in xrange(1, multiple):
       lr = get_r(lr, G)
   return lr

现在我们取一个基点G(1,18)
k=40
所以公钥K = kG
取一个r=16
取一个加密点M(34,24)
现在
C1 = get_r(M,get_add(pubkey, r))
C2 = get_add(G, r)
我们尝试通过C1和C2计算M的值
代码如下:

# -*- coding: utf-8 -*-  
A = 0
B = 7
MOD = 79
def get_r(p, q,mod=MOD, a=A):
   p = map(lambda x: x % mod, p)
   q = map(lambda x: x % mod, q)
   if p[0] == q[0] and (p[1]+q[1])%mod==0:
       #互为逆元点和为无穷远点,方便处理 记为[np.infty,np.infty]
       return [np.infty,np.infty]
   if p != q:
       c = (p[1]-q[1])*invert(p[0]-q[0], mod)%mod
   else:
       c = (3*p[0]**2+a)*invert(2*p[1],mod)%mod
   rx = (c**2-p[0]-q[0])%mod
   ry = (c*(p[0]-rx)-p[1])%mod
   return [rx,ry]

def invert(element, mod):
   if element >= mod:
       element = element%mod
   if element == 0:
       return None
   for index in xrange(1, mod):
       if element*index%mod == 1:
           return index

def get_add(G, multiple):
   lr = G
   for index in xrange(1, multiple):
       lr = get_r(lr, G)
   return lr
G = (1,18)
prikey = 40
pubkey = get_add(G, prikey)
r = 16
M = (34,24)
C1 = get_r(M,get_add(pubkey, r))
C2 = get_add(G, r)
temp = get_add(C2,prikey)
print get_r(C1,(temp[0], MOD-temp[1]))

图片描述



[公告]安全服务和外包项目请将项目需求发到看雪企服平台:https://qifu.kanxue.com

最后于 2019-8-9 11:51 被顾何编辑 ,原因:
打赏 + 5.00
打赏次数 1 金额 + 5.00
收起 
赞赏  雪衫   +5.00 2019/08/09
最新回复 (7)
看场雪 3 2019-8-8 22:38
2
0
深入浅出,娓娓道来。入门好文!

发现了个经典句:“椭圆曲线并与椭圆没有关系”

另外 请LZ斟酌这几个地方:
1)h是椭圆曲线上所有点的个数m与n相处的整数部分
2)为什么要 h<=4
3)讲述加密之前,建议先讲一下ECDH
4)有2个截图有些模糊,建议高分辨率截图
5)如果LZ方便,最好把ECDSA也介绍一下,好让大家对ecc有个较全面的认识
顾何 1 2019-8-8 23:43
3
0
感谢版主大大的肯定!
也非常感谢您给的宝贵意见,我仔细思考了一下:
(1) 按道理来讲确定一个曲线的六个参数应该是p、a、b、x、y、n,其中(p a b)确定曲线方程,x和y确定基点G的坐标,n表示G点的阶。包括在后面的使用中的确没有用到所谓的h。我查阅了些许资料,发现几乎所有人都千篇一律说到:
" (p 、a 、b 用来确定一条椭圆曲线,G为基点,n为点G的阶,h 是椭圆曲线上所有点的个数m与n相除的整数部分)"
我之前学习到这里的时候,感觉应该是同 p 一般情况下是200位左右的取值一样是一个定理,目前一想,应该是确保基点G的取值取得足够大,保证传输的安全性。这个点我之前没有考虑清楚,之后会再查阅资料补充完整。
(2) 我会仔细检查措辞和图片,把还不明确的地方和模糊的图片补充完整。
(3) 感谢版主给的思路,之后我会利用空闲时间把ECDSA和ECDH详细介绍。
pureGavin 2019-8-9 11:36
4
0
mark,椭圆曲线之前的还能看懂,椭圆曲线之后就莫名其妙的多出来了好多东西,所以想问下高数要学到什么程度??
顾何 1 2019-8-9 11:48
5
0
pureGavin mark,椭圆曲线之前的还能看懂,椭圆曲线之后就莫名其妙的多出来了好多东西,所以想问下高数要学到什么程度??
我刚开始找资料学的时候,大部分资料直接开始从射影平面讲起,也是看得我很莫名其妙,后来去找了一些数据资料发现Weierstrass方程之前的概念基本上都可以用中学数学解释,而Weierstrass方程的推广非常复杂,我大概看了一下就放弃了,转而接着看简化公式。关于我学习ECC的话,其实高数部分还好,后面的内容涉及到了一部分离散数学的知识点。
pureGavin 2019-8-9 13:26
6
0
顾何 [em_85]我刚开始找资料学的时候,大部分资料直接开始从射影平面讲起,也是看得我很莫名其妙,后来去找了一些数据资料发现Weierstrass方程之前的概念基本上都可以用中学数学解释,而Weierst ...
中学数学到底讲了啥??我中学全都在学代码了,数学没咋学啊。。。
薛国兴 2019-9-11 14:56
7
0
pureGavin mark,椭圆曲线之前的还能看懂,椭圆曲线之后就莫名其妙的多出来了好多东西,所以想问下高数要学到什么程度??
椭圆曲线涉及高数不多,主要是涉及代数和复分析。可以看一下《Elliptic Curves — Number Theory and Cryptography》这本书,现在应该是第二版,比较好懂
最后于 2019-9-11 15:01 被薛国兴编辑 ,原因:
GodSurvive 2019-9-11 16:42
8
0
椭圆曲线不是椭圆,之前我弄这个时懵逼了好久ヾ(≧O≦)〃
前段时间构建自己的密码库时,写了个可以内核用的ECC,实现上还有些注意的东西:
0.选个依赖小好用的大整数库
1加法要注意的情况:零元、坐标(x,y) y=0时的情况、逆元情况
2乘法实现一般是分解成二进制的位来计算,这样快很多....ECC暴力破解暴难度大也是在这里(目前没公开的其它捷径)
3明文编码到一个点,通常用概率编码, 代码层面要实现 勒让德符号  来计算 二次剩余。另外还要处理不能编码的小概率情况。
最后,关于密钥创建等还有一堆,比如大质数生成,涉及到的素性校验等等...

系统学理论的,推荐参考书籍:
《密码学-加密演算法》,这个是大学教材
《密码编码学与网络安全 原理与实践 第x版》,这个是翻译国外的

最后于 2019-9-11 16:46 被GodSurvive编辑 ,原因:
游客
登录 | 注册 方可回帖
返回