基础知识点
分解质因数难题
取两个很大的素数P1、P2
假设都是长度都在150位左右
求积N = P1 * P2
N长度300多位
若只知道N，倒推计算P1、P2是非常复杂的
同余
符号：≡
两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。
记作：a≡b (mod m)
例如 26≡2(mod 12)
a与b对m取模的结果一样，相减后自然能整除m
欧拉函数（Phi函数）φ(N)
定义： 1~ N 中与 N 互质的数的个数叫欧拉函数
对于任何质数P
φ(P) = P - 1
因为质数跟比它小的数都没有公约数
如果a，b互质，有φ(a*b)= φ(a) * φ(b)
例：φ(7 * 11) = φ(7) * φ(11) = 6 * 10 = 60
对应【分解质因数难题】
φ(N) = φ(P1) * φ(P2)
欧拉定理
对任意两个正整数 a, n，如果两者互质，那么 a^φ(n)≡1(mod n)。
时钟算术
例：
明文m = 3
取模（Modulus）N = 17
指数（Exponent） E，公开的
计算余数(Remainder) c = m ^ E mod N
| 指数Exponent | 余数Remainder(m ^ E mod N) |
|---|---|
| 1 | 3 |
| 2 | 9 |
| 3 | 10 |
| 4 | 13 |
| 5 | 5 |
| 6 | 15 |
| 7 | 11 |
| 8 | 16 |
| ... | ... |
结论：
若只知道一组E、c、N，则很难反推出m
解密过程：
c ^ d mod N = m
已知：m ^ E mod N = c
得 (m ^ E) ^ d mod N = m
即 m ^ (E * d) mod N = m
E为加密，公开的，公钥
d为解密，私钥
因此需要一个方法构建一对密钥E和d
E会公开，而d要很难被计算出来
实践
生成一对密钥
生成两个同位数的素数
P1 = 53
P2 = 59
N = P1 * P2 = 3127
φ(N) = (P1 - 1) * (P2 - 1) = 52 * 58 = 3016
选公钥e（条件如下）
- 必须是质数
- 1 < 公钥 < φ(N)
- 和φ(N)没有公约数
在此选择了e = 3
计算私钥d（条件如下）
- (d * e) % φ(N) = 1
即 d = (k * φ(N) + 1) / e
原因：
根据【欧拉定理】
n是非常大的两个素数相乘
自然满足
m ^ φ(n) ≡ 1 (mod n)
变换（两边都自乘k次）
m ^ (k * φ(n)) ≡ (1^k) (mod n)
即
m ^ (k * φ(n)) ≡ 1 (mod n)
再变换（两边同乘以m）
m ^ (k * φ(n)) * m ≡ (1 * m) (mod n)
即
m ^ (k * φ(n) + 1) ≡ m (mod n)
可得 e * d = k * φ(n) + 1
经计算k=2时有解
d = (2 * φ(N) + 1) / e = (2 * 3016 + 1) / 3 = 2011
公钥(e,N)分发
私钥(d,N)自己保留
加密
明文m = hi 填充法转化为
m = 89
计算密文c = m ^ e mod N
= 89 ^ 3 mod 3016
= 1394
解密
c ^ d mod N
= 1394 ^ 2011 mod 3127
= 89
= m（明文）
注：私钥加密的密文，用公钥也能解密
