其他
ECC椭圆曲线加密学习笔记
本文为看雪论坛优秀文章
看雪论坛作者ID：顾何
此文章严格意义上来讲应该算是读书笔记，在总结过程中观摩了很多位前辈的帖子和书籍资料，一字一句的写下来最后也只是勉强理解了ECC，所以难免会有说的不严谨或是思考错误的地方，大佬们轻喷，也希望跟我一样刚开始学习的伙伴能够对ECC多一点点认识。
>>>> 1. 平行线谈起
1. 平行线谈起
所以平行线 a // b 永不相交是一个假设。
所以也可以假设 a和b 最终会在一个无穷远处 P∞相交。
根据这个假设做出下图：
所以P∞就是平行线的交点，为了区别， 之后将平面上的点称为平常点。
根据上面的简单分析可以得到以下几个特点：
>>>> 2. 射影平面
2. 射影平面
我们都知道，笛卡尔积坐标系是没有设置无穷点的，所以为了表示无穷远点，就产生了一个叫做射影平面坐标系的东西，这个射影平面坐标系可以同时表示无穷远点和平常点。
接下来看具体是如何建立射影平面坐标系的。
这是普通的笛卡尔积坐标系：
>>>> 3. 直线方程
3. 直线方程
根据上面的分析可以得到直线在新坐标系中的表示为：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
联立两条直线方程求解可以得知：
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. 椭圆曲线
4. 椭圆曲线
看看维基百科上对椭圆曲线是如何定义的：
y^2 z = x^3 + xz^2 + z^3
当z=1 时推导出下面的方程式：
y^2 = x ^3 +x + 1
得到的椭圆曲线图片：
y^2 = x^3 -x
>>>> 5. 椭圆先阿贝尔群
5. 椭圆先阿贝尔群
比如在整数内的加法运算就是一个阿贝尔群（Z，+）。
还是以上面作图的椭圆曲线为例：
y^2 = x^3 -x
在曲线上找一个点P和Q，过P和Q作一条直线，交椭圆曲线为点R'，再过R'点 作垂直于x轴的直线，交曲线另一点为R。定义P+Q = R如下图所示：
在右边的图中：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
这里的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 = O∞
现在椭圆曲线满足阿贝尔群了。
有限域上的椭圆曲线
但是上面介绍的所有内容，都是在实数域的基础上完成的，并不能用于加密上，要想把椭圆曲线应用到加密上，还需要把椭圆曲线变成离散的点。
椭圆曲线之所以是连续的，是因为椭圆曲线上的坐标是实数，实数是连续的，所以曲线也是连续的，所以如果将椭圆曲线定义到有限域上，才能够使用椭圆曲线进行加密。
现在定义一个有限域Fp：
y^2 = x^3 + ax + b(mod p)
当这条曲线位于有限域F23的时候可以写作：
这里还有一个概念：
所以通过对椭圆曲线的分析，已经拿到了秘钥对，有了这个秘钥对，我们就可以进行加密通讯了。
还是经典的Alice要和Bob通讯为列子.
现在分析一下椭圆曲线加密的流程：
我们来分析一下在传输过程中传输了一些什么。
首先是Alice：Alice选定了曲线Ep，传输了自己的公钥K，以及选定的基点G
然后看Bob：Bob选定了随机数r，传输了通过r计算出来的C1和C2。
这个传输为什么安全呢，接着往下看：（作了一张丑图）
根据几个表达式可以发现，想要通过公开传输的这几个信息拿到关键的r或者k几乎是不可能的。
所以在密码学中，描述一条Fp上的椭圆曲线常用到六个参量：T = (p,a,b,G,n,h)
其中p a b 用于确定一条椭圆曲线，G是用户A取得基点，n是点G的阶，h是椭圆曲线上所有点的个数m与n相处的整数部分。
这几个参量会直接决定加密的强度和安全性，所以一般要求：
根据之前的分析，椭圆曲线的上取点p和q连成直线会与椭圆曲线相交于点R
逻辑为：
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]
if element >= mod:
element = element%mod
if element == 0:
return None
for index in xrange(1, mod):
if element*index%mod == 1:
return index
lr = G
for index in xrange(1, multiple):
lr = get_r(lr, G)
return lr
代码如下：
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]))
看雪ID：顾何
https://bbs.pediy.com/user-757351.htm
推荐文章++++
* ollvm源码分析 - Pass之SplitBaiscBlocks