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，ab ∈ 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,+)属于阿贝尔群

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课