RSA 算法正确性的证明

RAS 的文章网上很多，但是相关的证明和理解比较少，所以就来写一写

RAS

RAS 是基于「大整数分解这一数学困难问题」的公钥密码体制

须知定理

• 欧拉函数：设 m 是一个正整数，则 m 个整数 1，… ，m - 1 中与 m 互素的整数的个数记为 φ(n)，通常叫做欧拉函数
• 若 p 是素数，则 φ(p) = p - 1
• 设 m，n 是互素的两个正整数，则 φ(mn) = φ(m)φ(n) = (m - 1)(n - 1)
• 欧拉定理：设 m 是大于 1 的整数，如果 a 满足 gcd(a, m) = 1 的整数，则：a^φ(m) = 1(mod m)

秘钥的产生

• 选择两个大素数 p 和 q，计算 n = p * q，φ(n) = (p - 1)(q - 1)
• 选一个整数 e，满足 gcd(φ(n), e) = 1 (1 < e < φ(n))
• 计算出满足等式 d * e = 1 (mod φ(n)) 的值 d
• 以 {e, n} 为公钥，{d, n} 为私钥

加密解密

密文为 c，明文为 m c = m^e (mod n)，m = c^d (mod n)

算法解密的正确性证明

已知 c = m^e (mod n)， 则 m = c^d (mod n) = m^ed (mod n) = m^1(modφ(n)) = m^kφ(n)+1 (mod n)， 因此只需证明 m = m^kφ(n)+1 (mod n) 分为两种情况：

① m 与 n 互素

由欧拉定理得 m^φ(n) = 1(mod n)，则 m^kφ(n) = 1(mod n)，则 m^kφ(n)+1 = m(mod n)

② m 与 n 不互素

因为 m < n(原因见下面)，p 和 q 又都是素数，意味着 m 要么是 p 的倍数，要么是 q 的倍数，不能同时是 p 和 q 的倍数（如果同时是 p 和 q 的倍数，那 m > n），不妨设 m 是 p 的倍数，则 m = cp，其中 c 为正整数， 那么 gcd(m, q) = 1，有欧拉定理得：

m^φ(q) = 1(mod q)

那么

m^kφ(q) = 1(mod q)

(m^kφ(q))^φ(p) = 1^φ(p)(mod q)

(m^kφ(q))^φ(p) = 1(mod q)

m^kφ(n) = 1(mod q)

所以，会存在一个整数 r，使得 m^kφ(n) = 1 + rq，两边同同时乘以 m = cp 得：

m^kφ(n)+1 = m + rcpq = m + rcn

即 m^kφ(n)+1 = m(mod n)

综上所述，无论 m 和 n 是否互素，RSA 都能对消息正确地进行解密

注意点

• 加密的时候要求明文 m 要小于 n。如果 m > n，而在计算过程中有用到了 mod 运算，则不能通过解密算法正确求得明文 m，只能得到比 n 小且与 m(mod n) 同余的整数
• 秘钥生成过程中的 p，q，φ(n)，一般都要安全地销毁，p，q 的存在是可以提高 RAS 算法的解密速度的。为什么 n 不用销毁？因为目前来说分解两个大素数仍然一个数学困难问题，也就是说已知 n 来求得 q 和 p 是很困难的。那为什么要把 φ(n) 销毁？因为 φ(n) = (p - 1)(q - 1)，而 n = p * q，根据这两个式子就可以算出 p，q 了