基础知识点

分解质因数难题

取两个很大的素数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（明文）

注：私钥加密的密文，用公钥也能解密