RSA
欧拉函数 φ(n)
φ(n) 表示 “小于等于 n 且与 n 互质的正整数的个数”
如果 n 是质数 p，那么 φ(p) = p - 1（因为 1,2,…,p-1 都和 p 互质）
如果 n = p * q，且 p、q 都是质数，那么
φ(n) = (p - 1) * (q - 1)例如 p = 5, q = 11，则 n = 55，φ(55) = 4 * 10 = 40
密钥生成
选两个大质数 p 和 q
实际中 p、q 有 1024 位或 2048 位，这里我们用小数字演示
1 | p = 61 |
计算 n 和 φ(n)
1 | n = p * q = 61 * 53 = 3233 |
选公钥指数 e
要求：
1 < e < φ(n)
e 与 φ(n) 互质（即最大公约数为 1）
小例子中我们选 e = 17
计算私钥指数 d
d 是 e 在模 φ(n) 下的乘法逆元，即满足：
1 | (e * d) mod φ(n) = 1 |
换句话说，存在整数 k 使得：
1 | e * d = k * φ(n) + 1 |
计算 d 可以用扩展欧几里得算法。小例子中，可以验证 d = 2753
加密过程
加密公式：
1 | c = (m ^ e) mod n |
例子：加密明文 m = 65
1 | c = 65 ^ 17 mod 3233 |
直接算 65^17 巨大，但模运算可以逐步取余。结果：
1 | c = 2790 |
解密过程
1 | m = (c ^ d) mod n |
例子：c = 2790, d = 2753, n = 3233
1 | m = 2790 ^ 2753 mod 3233 = 65 |
推导过程
即要证明：
1 | c^d ≡ m (mod n) |
将 c = m^e mod n 代入 c^d：
1 | c^d ≡ (m^e)^d = m^(e*d) (mod n) |
利用 ed = kφ(n) + 1：
1 | m^(e*d) = m^(k*φ(n) + 1) = [m^(φ(n))]^k * m |
所以：
1 | c^d ≡ [m^(φ(n))]^k * m (mod n) |
欧拉定理说：如果 m 和 n 互质（即 gcd(m, n) = 1），那么
1 | m^(φ(n)) ≡ 1 (mod n) |
因此
1 | [m^(φ(n))]^k ≡ 1^k = 1 (mod n) |
于是
1 | c^d ≡ 1 * m = m (mod n) |