ECC椭圆曲线加解密
概念
1、椭圆曲线密码学（Elliptic Curve Cryptography,缩写ECC）是一种基于椭圆曲线数学的公开密钥加密算法。
2、ECC的主要优势是它相比RSA加密算法使用较小的密钥长度并提供相当等级的安全性
3、椭圆曲线密码学的算法是在2004年至2005年开始广泛应用。
image.png
y 的2次方 x 的3次方
不断改变a,b 的值 生成不同的曲线
这是一个光滑的曲线，也就是说他是一个处处可导的曲线
计算机不擅长计算浮点数，所以我们修改它的定义为有限域 只要整数部分
椭圆曲线的基础知识
image.png
相反数操作
image.png
image.png
加法
image.png
A+B 如图所示
image.png
3A = 2A 然后垂直
image.png
image.png
椭圆曲线算法：入门（1）
https://www.jianshu.com/p/2e6031ac3d50
https://www.cnblogs.com/HachikoT/p/15991277.html
[声明下，因为编辑器的问题，下文中将用P=(xP,yP)(P是下标)来表示这种等式，否则一直贴图排版很累]
如果xP≠xQ(P和Q是下标)，那么该直线的斜率是：
image.png
该直线与椭圆曲线相交的第三个点R(xR,yR)(R是下标)：
image.png
或者也可以写成：
image.png
特别强调一下 (xP,yP)+(xQ,yQ)=(xR,−yR)（P，Q，R都是下标）。
如果要检查结果是否正确，我们需要检查R是否在椭圆曲线上，以及P，Q和R是否都在直线上。检查这些点是否在直线上是显而易见的，然而检查R是否属于椭圆曲线并不是，因为我们不得不解决一个一点都不有趣的三次方程问题。
考虑这么一个例子：根据我们给出的visual tool，给定的P=（1，2）和Q=（3，4）都在曲线上y2=x3−7x+10（y的2次方，x的3次方），那么P+Q=-R=（-3，2）。反过来去根据我们前面的公式验证该结果是否正确：
image.png
验证正确！
注意，即使P或者Q是切点，该等式依然成立。拿P=(-1,4) Q=(1,2)尝试下：
image.png
得到的结果是P+Q=(1,-2)，该结果与用该工具visual tool计算是一样的。
另一种情况P=Q则需要另外处理了：关于xR以及yR的公式是一样的，但是针对直线的斜率必须用另外的方式处理：
image.png
image.png
注意，该公式是由一下公式推导出来的：
image.png
为了证明该公式的正确性，有必要验证R是否属于椭圆曲线上，以及P和R连成的直线与椭圆曲线有且仅有2个交点。但是在这里，我们不作证明，先做个测试：P=Q=(1,2)
image.png
所以得出 P+P=-R=(-1, -4)。正确
标量乘法
除了加法之外，我们定义另外一个运算：标量乘法：
image.png
在这里n是一个自然数。嗯，我写了个visual tool用来玩标量乘法，有兴趣点击去试试吧。
该公式看起来计算nP需要计算n次加法。如果n是k个二进制位，那么该算法复杂度是O(2k)（2的k次方），计算量有点大。但是其实存在更快速的方案。
其中一个就是先做倍数再做加法。要了解基本原理还是直接看例子会比较快。假设n=151，其对应的二进制是10010111。而该二进制数字可以转化为：
image.png
image.png
所以我们可以这么写：
image.png
所以，该运算过程是这样的：
1、获取P
2、取P的2倍，得到2P
3、2P加上P
4、把2P再取2倍，得到4P
5、4P加上2P加上P
6、4P再取2倍，得到8P
7、不取8P做运算
8、8P取2倍，得到16P
9、16P加上4P加上2P加上P
……
最终，要得到151P我们只是做了一些简单的倍数以及加法。
如果倍数和加法都是复杂度为O(1)的运算，那么该算法的复杂度就是O(log n)（或者O(k)）（考虑到k个bit的长度）。依然比O(n)的复杂度要好。
image.png
image.png
image.png
按照这个方法可以计算 3P 4P 8P等 这个叫 倍频计算
除法
image.png
t相当于y^-1
除法计算过程
image.png
找出比较小的有限域 GF(5) 只有5个元素
image.png
image.png
实际上不是通过观察 3*2=1 的 是通过扩展欧几里得算法得到的
image.png
有限域上的椭圆
image.png
计算 17P 的点，可以观察到这些点都是无规律的、离散的 不可预测的
nP无穷大问题
image.png
image.png
n=5 5P=0 从5之后 结果都发生了重复
image.png
image.png
点的数量 为 5 其他都是重复的 找到 nP=0无穷大
nP的问题
image.png
乘法理论上也是加法
最后都是异或运算
image.png
将O(n) 复杂度的问题 转化为 logn 的复杂度
image.png
转化为 4次相加的结果
image.png
公钥与私钥定义
image.png
Q公钥 无法推导出 私钥
加密
image.png
image.png
image.png
这两个点计算出来以后 打包一起发送给 bob
Cm1 Cm2 这两个点合在一起 就是密文
解密
image.png
image.png
Pm 就是原始消息的点
原理解析
image.png
Cm2 是 Alice 计算出来的
加密示例演示计算过程
image.png
私钥选择101 也就是小写kB
image.png
image.png
解密示例演示
image.png
image.png
比特币系统选用的secp256k1
image.png
image.png
image.png
ECC安全性浅析
image.png
image.png
