参考文献
- 《PKI/CA 与数字证书技术大全》书籍
-
ECC加密算法入门介绍
如有理解bug, 请大家指正。
非对称加密算法有多种，比如 RSA, Elgamal, 背包算法, Rabin， D-H, ECC, SM2 等。如下仅仅对 RSA, ECC, SM2 算法进行解释。
RSA
RSA 算法是由美国三位科学家 Rivest、Shamir 和 Adleman 于1976年提出并在1978年正式发表的公开密码加密算法，其命名取自三位创始者的首字母缩写。该算法基于数论中的大数分解难题，即：根据数论，寻求两个大素数比较简单，而将它们的乘积分解开则极为困难。
理论来源于数论
欧拉函数 ：
欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n) 。
完全余数集合：
定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。 显然 |Zn| ＝φ(n) 。
有关性质：
对于素数 p ，φ(p) = p -1 。
对于两个不同素数 p， q ，它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1) 。
这是因为 Zn = {1, 2, 3, ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} ， 则 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) ＝φ(p) * φ(q) 。
欧拉定理 ：
对于互质的正整数 a 和 n ，有 a^φ(n) ≡ 1 mod n 。
因此， RSA 算法中，用户有两个密钥：公钥为 PK = {e, n} 和私钥 SK = {d, n}, n 为两个素数p, q的乘积,即 n = p * q（素数p，q一般为100位以上的十进制数）, e 和 d 满足一定的关系，如只知道 e, n 很难计算出 d，这里是 a ^ (e * d) ≡ a (mod n) 。即 e * d ≡ 1 mod φ(n) 。<b>根据上述定理可得出 p， q ，φ(n) 均小于 n。</b>
简单从上述公式可看出 公钥加密与私钥解密，及私钥加密与公钥解密 是能到达同样的效果，但通常是公钥会发布公告，所以用公钥解密的是不安全的。
具体过程如下：
(1) 加密/解密过程
若用整数X表示明文，用整数Y表示密文，则加密和解密运算过程为：
加密： Y = (X ^ e) mod n
解密： X = (Y ^ d) mod n
(2) 秘钥产生过程
- 获取两个长度大于 100 位的素数 p, q;
- 计算 n = p * q;
- 计算出 n 的欧拉函数 φ(n) = φ(p * q) = (p - 1) * (q - 1) ;
- 计算 e，从 (0, φ(n) ] 中任选一个与 φ(n) <b>互素</b>的数字 e, 作为公钥的加密指数
- 计算 d，通过计算出满足公式 e * d = 1 mod φ(n) 的 d 作为解密指数
即 公钥: PK = {e, n} ; 私钥 SK = {d, n}
ECC
ECC 是椭圆曲线密码 (Elliptic Curve Cryptography) 的缩写。1985 年， Koblitz 和 Miller 提出基于椭圆曲线离散对数问题 (ECDLP, Elliptic Curve Discrete Logarith Problem) 的公钥密码体制，即 椭圆曲线密码体制 ECC 。 它是用椭圆曲线有限群代替基于有限域上离散对数问题公钥密码中的有限循环群所得到的一类密码体制。由于在一般的椭圆曲线群中没有亚指数时间算法解，所以椭圆曲线密码成了目前最流行的公钥密码体制。
ECC 算法的基本原理如下：
(1) 有限域 Fp 与椭圆曲线
有限域 Fp 是由小于素数 p 的非负整数组成的集合{0, 1, 2, 3, ...., p - 1} ，其上的运算是模 p 的算术运算。
Fp 上的椭圆曲线是满足方程 y^2 =x^3+ax+b 的 Fp 上的点 (x, y) 组成的集合，其中常量 a 和 b也是 Fp 中的元素。
为了详细描述一条 Fp 上的椭圆曲线，应该给出如下参数：
- 素数 p 的值， 为满足 ECC 的安全性的要求， p 应该为 160 以上位长的素数。
- 常数 a 和 b 的值， 其中 a 可以取 -3 以提高点运算效率。
- 椭圆曲线上的一个基点 G (称为生成元)
- 基点 G 的阶为 n， 一般情况下要求n为素数且等于椭圆曲线上的点数。
选择两个满足下列条件的小于 p (p为素数) 的非负整数a、b
4 * (a^3) + 27 * (b^2) ≠ 0 (mod p)
则满足下列方程的所有点 (x,y)，再加上 无穷远点O(∞,∞) ，构成一条椭圆曲线。
y^2 = x^3 + ax + b (mod p)
其中 x, y属于 0 到 p-1 间的整数，并将这条椭圆曲线记为 Ep(a,b)。
(2) ECC 密钥对
对于给定的椭圆曲线参数 {p, a, b, G, n} ，ECC 的私钥 d 为满足 1 < d < n 的随机数，相应的公钥为 P = d*G。 为满足安全性要求， d 必须通过随机或强伪随机发生器产生。
(3) ECC 加密/解密机制
1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。
2、用户A选择一个私有密钥k，并生成公开密钥K=kG。
3、用户A将Ep(a,b)和点K，G传给用户B。
4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（r<n）。
5、用户B计算点C1=M+rK；C2=rG。
6、用户B将C1、C2传给用户A。
7、用户A接到信息后，计算C1-kC2，结果就是点M。因为
C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M
再对点M进行解码就可以得到明文。
(4) ECC 签名机制
软件作者按如下方法制作注册机（也可称为签名过程）
1、选择一条椭圆曲线Ep(a,b)，和基点G；
2、选择私有密钥k（k<n，n为G的阶），利用基点G计算公开密钥K=kG；
3、产生一个随机整数r（r<n），计算点R=rG；
4、将用户名和点R的坐标值x,y作为参数，计算SHA（Secure Hash Algorithm 安全散列算法，类似于MD5）值，即Hash=SHA(username,x,y)；
5、计算sn≡r - Hash * k (mod n)
6、将sn和Hash作为 用户名username的序列号
软件验证过程如下：（软件中存有椭圆曲线Ep(a,b)，和基点G，公开密钥K）
1、从用户输入的序列号中，提取sn以及Hash；
2、计算点R≡sn*G+Hash*K ( mod p )，如果sn、Hash正确，其值等于软件作者签名过程中点R(x,y)的坐标，因为
sn≡r-Hash*k （mod n）
所以
sn*G + Hash*K
=(r-Hash*k)*G+Hash*K
=rG-Hash*kG+Hash*K
=rG- Hash*K+ Hash*K
=rG=R ；
3、将用户名和点R的坐标值x,y作为参数，计算H=SHA(username,x,y)；
4、如果H=Hash 则注册成功。如果H≠Hash ，则注册失败(为什么？提示注意点R与Hash的关联性)。
简单对比一下两个过程：
作者签名用到了：椭圆曲线Ep(a,b)，基点G，私有密钥k，及随机数r。
软件验证用到了：椭圆曲线Ep(a,b)，基点G，公开密钥K。
Cracker要想制作注册机，只能通过软件中的Ep(a,b)，点G，公开密钥K ，并利用K=kG这个关系获得k后，才可以。而求k是很困难的。
SM2
SM2 算法由国家密码局于2012年12月17日发布的椭圆曲线公钥密码算法，主要满足电子认证服务系统等应用需求。
该算法主要参数如下：
- 推荐使用素数域为 256 位椭圆曲线。
- 椭圆曲线方程： y^2 = x^3 + ax + b
- 曲线参数：
p = FFFFFFFE FFFFFFFFFFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
a = FFFFFFFE FFFFFFFFFFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
b = 28E9FA9E 9D9F5E344D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
n = FFFFFFFE FFFFFFFFFFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
Gx = 32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7
Gy = BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0
