非对称算法 ECC、RSA、ECDH
ECC
一、阿贝尔群
椭圆曲线也可以有运算，像实数的加减乘除一样，这就需要使用到加群。19世纪挪威的尼尔斯·阿贝尔抽象出了加群（又叫阿贝尔群或交换群）。数学中的群是一个集合，我们为它定义了一个“加法”，并用符号+表示。假定群用 表示，则加法必须遵循以下四个特性：
- 封闭性：如果a和b都是 的成员，那么a+b也是 的成员；
- 结合律：(a + b) + c = a + (b + c);
- 单位元：a+0=0+a=a，0就是单位元；
- 逆元：对于任意值a必定存在b，使得a+b=0。
如果再增加一个条件，交换律：a + b = b + a，则称这个群为阿贝尔群，根据这个定义整数集是个阿贝尔群。
二、椭圆曲线的加法
过曲线上的两点A、B画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A+B，即为加法。如下图所示：A + B = C
三、椭圆曲线的二倍运算
上述方法无法解释A + A，即两点重合的情况，因此在这种情况下，将椭圆曲线在A点的切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A + A，即2A，即为二倍运算。
四、同余运算
同余就是有相同的余数，两个整数 a、 b，若它们除以正整数 m所得的余数相等，则称 a， b对于模m同余。
五、乘法逆元
在模7乘法中：
- 1的逆元为1 (1*1)%7=1
- 2的逆元为4 (2*4)%7=1
- 3的逆元为5 (3*5)%7=1
- 4的逆元为2 (4*2)%7=1
- 5的逆元为3 (5*3)%7=1
- 6的逆元为6 (6*6)%7=1
六、有限域
椭圆曲线是连续的，并不适合用于加密；所以必须把椭圆曲线变成离散的点，要把椭圆曲线定义在有限域上。而椭圆曲线密码所使用的椭圆曲线是定义在有限域内，有限域最常见的例子是有限域GF(p)，指给定某质数p，由0,1,2...p-1共p个元素组成的整数集合中加法、二倍运算。例如GF(233)就是
七、椭圆曲线加解密算法原理
设私钥、公钥分别为d、Q，即Q = dG，其中G为基点，椭圆曲线上的已知G和dG，求d是非常困难的，也就是说已知公钥和基点，想要算出私钥是非常困难的。
公钥Q加密：选择随机数r，将消息M生成密文C，该密文是一个点对，C = {rG, M+rQ}，其中Q为公钥。
私钥d解密：M + rQ - d(rG) = M + r(dG) - d(rG) = M，其中d、Q分别为私钥、公钥。
八、ECDSA签名验签过程
假设要签名的消息是一个字符串：“Hello World!”。DSA签名的第一个步骤是对待签名的消息生成一个消息摘要，不同的签名算法使用不同的消息摘要算法，而ECDSA256使用SHA256生成256比特的摘要。
摘要生成结束后，应用签名算法对摘要进行签名：
1. 签名部分：
已知，A想要把m安全的发送给B，并且使用ECDSA做数字签名。我们在此不讨论它是怎么安全的送过去的，我们就假设反正是安全的保密的送给B了，但是需要验证。
1，首先，对m消息 做一次hash，即H(m)，可以使用sha一类的算法实现。
2，我们得构造一个临时的公钥，构造办法还是和之前的相同，我们再次随机安全的产生一个随机数k，以及对应的公钥kG，这一步是必须得有的，并且，每和一个人对话就应该构建一个新的随机数k才能保证安全。k随机才是最安全的。
3，对于这个临时公钥kG，必然存在一个对应的椭圆曲线上的点kG=(x,y)，即 ，因为G本身就是一个点，对它自身进行n次的加法，还是在这个椭圆曲线上。
然后取x部分，求它的逆，即：r=x^-1mod n ，
对一个已知数 ,在模 的情况下求逆，也就是使得 ,通常来说，为了保证安全，这个数都是非常大的，直接瞪眼法估计是搞不出来，得采用扩展欧几里得算法求逆，我们不谈，反正只要知道这个是可解的就可以了。同理，在本文里面，我们就默认，所有的基于一个数求逆都是可解的，省略点篇幅。
就算法看来，到底选择的是 还是 似乎没有什么区别。
4，开始构造签名。令：
处理结束，把（r , sign）发送过去，签名的工作就结束了。
2. 验证过程
这个ECC算法应该也是公开的，因此它的G就是已知的，同样，这个公钥部分本身就应该公开，也就是dG。
已知
构造
那么，
得到kG，即可计算kG=(x,y)，得到x，再顺着签名过程计算r，最后核对r是否一致即可。
3. 不能用相同的k
因为有：
所有知道k之后就可以计算出私钥d。
两次使用相同的k，对不同的H签名，既可以计算k：
sign1=k^(-1)(H1+dr)
sign2=k^(-1)(H2+dr)
求得：
k=(H1-H2)/(sign1-sign2)
RSA
RSA 算法的数学基础
RSA 算法的安全性依赖于数论中的一些重要概念和定理，主要包括：
质数与互质
- 质数：大于 1 的自然数，除了 1 和它本身外，不能被其他自然数整除。
- 互质：两个整数的最大公约数为 1，称为互质。
欧拉函数
欧拉函数 ϕ(n)，ϕ(n) 表示小于或等于 n 的正整数中与 n 互质的数的个数。对于质数 p，有：ϕ(p)=p−1；ϕ(p)=p−1对于两个不同的质数 p和 q，有：ϕ(p×q)=(p−1)×(q−1)
模运算
模运算是指求一个数除以另一个数的余数。RSA 算法中大量使用了模运算的性质，例如：
- (a×b)modn=[(a mod n)×(b mod n)]modn
- a^bmodn可以通过快速幂算法高效计算。
欧拉定理
欧拉定理指出，如果两个正整数 a 和 n互质，则：a^ϕ(n)≡1modn 欧拉定理是 RSA 算法的核心数学基础。
一、密钥计算方法
1.选择两个大素数p和q(典型值为1024位)
2.计算n=p×q和z=(p-1)×(q-1) // z是n表示欧拉函数
3.选择一个与z互质的数，令其为d
4.找到一个 e 使满足e*d= 1 (mod z)
5.公开密钥为(e，m)，私有密钥为(d，m)
二、加密方法
1.将明文看成比特串，将明文划分成k位的块 P 即可，这里k是满足 2*k<n 的最大整数。
2.对每个数据块 P，计算 C= P^e(mod n),C 即为P的密文。
加密
C = P^e (mod n)
三、解密方法
对每个密文块 C，计算 P=C^d(mod n),P即为明文
解密：
P = （P^e）^d (mod n)=P^(ed) (modn)=
P=P^(ed)(mod n)
ECDH共享参数
Alice和Bob进行ECDH密钥协商之前双方要有共同的ECDH共享参数即必须选择相同的椭圆曲线方程、大素数p、生成源G，实际中这些椭圆曲线已经被相关组织标准，比如上边的secp256r1、secp384r1，通过这个双方就确定了这些共享参数
ECHD密钥协商
1.Alice选择一个比椭圆曲线阶小的随机数dA作为私密参数,计算QA=dA G=(xA,yA)发送给Bob
2.Bob选择一个比椭圆曲线阶小的随机数dB作为私密参数,计算QB=dB G=(xB,yB)发送给Alice
3.Bob收到QA并计算得到共享密钥参数KB=dB QA=dB(dA G)
4.Alice收到QB并计算得到共享密钥参数KA=dA QB=dA(dB G)
根据椭圆曲线结合律dB(dA G) = dA(dB G) = (xQ,yQ),即获得共享密钥KA=KB，KA和KB是一个坐标点，所以共享密钥可以是xQ,yQ两部分也可以是xQ单一部分，若共享曲线是secp256r1，则xQ,yQ长度均256比特，如共享曲线是secp384r1，则xQ,yQ长度均384比特
如下图：
