ECC
一、阿贝尔群
椭圆曲线也可以有运算，像实数的加减乘除一样，这就需要使用到加群。19 世纪挪威的尼尔斯·阿贝尔抽象出了加群（又叫阿贝尔群或交换群）。数学中的群是一个集合，我们为它定义了一个'加法'，并用符号 + 表示。假定群用 $G$ 表示，则 加法 必须遵循以下四个特性：
- 封闭性：如果 a 和 b 都是 $G$ 的成员，那么 a+b 也是 $G$ 的成员；
- 结合律：(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 做数字签名。我们需要验证。
- 首先，对 m 消息做一次 hash，即 H(m)，可以使用 sha 一类的算法实现。
- 我们得构造一个临时的公钥，构造办法还是和之前的相同，我们再次随机安全的产生一个随机数 k，以及对应的公钥 kG，这一步是必须得有的，并且，每和一个人对话就应该构建一个新的随机数 k 才能保证安全。k 随机才是最安全的。
- 对于这个临时公钥 kG，必然存在一个对应的椭圆曲线上的点 kG=(x,y)，即 kG = (x, y)。因为 G 本身就是一个点，对它自身进行 n 次的加法，还是在这个椭圆曲线上。 然后取 x 部分，求它的逆，即：r=x^-1 mod n。 对一个已知数，在模 n 的情况下求逆，也就是使得 k*r ≡ 1 (mod n)，通常来说，为了保证安全，这个数都是非常大的，需通过扩展欧几里得算法求逆。此处假定基于一个数求逆都是可解的。 就算法看来，到底选择的是 r 还是 n-r 似乎没有什么区别。
- 开始构造签名。令： s = k^-1(H(m) + r*d) mod n 处理结束，把（r , s）发送过去，签名的工作就结束了。
2. 验证过程
这个 ECC 算法应该是公开的，因此它的 G 就是已知的，同样，这个公钥部分本身就应该公开，也就是 dG。 已知 r, s, H(m), Q (公钥)。 构造 w = s^-1 mod n u1 = H(m)w mod n u2 = rw mod n 那么，P = u1G + u2Q 得到 kG，即可计算 kG=(x,y)，得到 x，再顺着签名过程计算 r，最后核对 r 是否一致即可。
