RSA正确性证明以及python实现

RSA是一种非对称加密方式。RSA主要基于了一个事实：寻找1个大素数是简单的，但将一个数拆分为2个大素数是困难的。

令 ϕ ( n ) phi (n) ϕ(n)为欧拉函数，其表示大于0小于n且与n互素（即最大公因数为1）的整数个数。若n为质数，显然n与 { x ∣ 1 ≤ x ≤ n − 1 , x ∈ Z } { x|1le x le n-1 ,x in mathbb{Z} } {x∣1≤x≤n−1,x∈Z} 集合中所有元素互素，此时 ϕ ( n ) = n − 1 phi (n)=n-1 ϕ(n)=n−1；若n为合数，可以将n拆分为 l l l个素数的幂的乘积，假设 n = ∏ i = 1 l n i k i n=prod_{i=1}^{l}n^{k_i}_{i} n=∏i=1l​niki​​, n i n_{i} ni​为素数， k i k_i ki​为对应的阶， ϕ ( n ) = ∏ i = 1 l ϕ ( n i ) n i k i − 1 = ∏ i = 1 l ( n i − 1 ) n i k i − 1 phi (n)=prod_{i=1}^{l}phi (n_i)n_i^{k_i-1}=prod_{i=1}^{l}(n_i-1)n_i^{k_i-1} ϕ(n)=∏i=1l​ϕ(ni​)niki​−1​=∏i=1l​(ni​−1)niki​−1​，如求 ϕ ( 12 ) = ϕ ( 2 ) 2 2 − 1 ϕ ( 3 ) 3 1 − 1 = ( 2 − 1 ) ∗ 2 ∗ ( 3 − 1 ) ∗ 1 = 4 phi (12)=phi (2)2^{2-1}phi(3)3^{1-1}=(2-1)*2*(3-1)*1=4 ϕ(12)=ϕ(2)22−1ϕ(3)31−1=(2−1)∗2∗(3−1)∗1=4

定义模 n 的乘法群为 ( Z n ∗ , ⋅ n ) (mathbb{Z}^*_n, cdot_n) (Zn∗​,⋅n​)， Z n ∗ mathbb{Z}^*_n Zn∗​是所有大于0小于n与n互素的整数组成的集合， ⋅ n cdot_n ⋅n​表示在模n上的乘法，即 Z n ∗ = { x ∣ 1 ≤ x ≤ n − 1 , x ∈ Z , g c d ( x , n ) = 1 } mathbb{Z}^*_n={x|1le x le n-1 ,x in mathbb{Z} ,gcd(x,n)=1} Zn∗​={x∣1≤x≤n−1,x∈Z,gcd(x,n)=1},其中 g c d ( a , b ) gcd(a,b) gcd(a,b) 表示计算 a , b a,b a,b 最大公因数。
模乘法计算例子如 5 ∗ 6 m o d    ( 11 ) ≡ 30 m o d    ( 11 ) ≡ 8 m o d    ( 11 ) 5*6 mod (11)equiv 30 mod (11)equiv 8mod (11) 5∗6mod(11)≡30mod(11)≡8mod(11)
乘法群满足以下基本性质:

• 封闭性：对所有 a , b ∈ Z n ∗ a,b in mathbb{Z}^*_n a,b∈Zn∗​,有 a ⋅ n b ∈ Z n ∗ a cdot_n b in mathbb{Z}^*_n a⋅n​b∈Zn∗​。
• 单位元：存在元素 e ∈ Z n ∗ e in mathbb{Z}^*_n e∈Zn∗​,被称为单位元，满足对所有 a ∈ Z n ∗ ain mathbb{Z}^*_n a∈Zn∗​, a ⋅ n e = e ⋅ n a = a a cdot_n e =e cdot_n a= a a⋅n​e=e⋅n​a=a
• 结合律：对 a , b , c ∈ Z n ∗ a,b,c in mathbb{Z}^*_n a,b,c∈Zn∗​，有 ( a ⋅ n b ) ⋅ n c = a ⋅ n ( b ⋅ n c ) (a cdot_n b )cdot_n c =a cdot_n (b cdot_n c) (a⋅n​b)⋅n​c=a⋅n​(b⋅n​c)
• 逆元：对于每个 a ∈ Z n ∗ a in mathbb{Z}^*_n a∈Zn∗​，存在唯一元素b，为a的逆元，有 a ⋅ n b = b ⋅ n a = e acdot_n b=bcdot_n a=e a⋅n​b=b⋅n​a=e
  下表为模5上的乘法群，在该群中比5小且与5互素的整数为1,2,3,4，因而群中的元素为1,2,3,4，该群中的单位元为1，1的逆元为1， 2的逆元为3， 3的逆元为2，4的逆元为4。通过查表是很容易得到逆元的。

下表为模8上的乘法群，该群的单位元为1，1的逆元为1，3的逆元为3。

对于任意整数 n > 1 n>1 n>1, a ϕ ( n ) ≡ 1 m o d    n a^{phi(n)}equiv1 mod n aϕ(n)≡1modn，对所有 a ∈ Z n ∗ a in mathbb{Z}^*_n a∈Zn∗​（等价于a与n互素）成立。

• 选取两个大素数 p p p和 q q q,且 p ≠ q p ne q p​=q
• 计算 n = p q n=pq n=pq
• 选取与 ϕ ( n ) phi (n) ϕ(n)互质的数 e e e,此时 ϕ ( n ) = ( p − 1 ) ( q − 1 ) phi (n)=(p-1)(q-1) ϕ(n)=(p−1)(q−1)
• 对模 ϕ ( n ) phi (n) ϕ(n)，计算 e e e逆元的 d d d(计算逆元的过程可以使用扩展欧几里得算法求解)，即存在关系 e d ≡ 1 m o d    ϕ ( n ) ≡ 1 m o d    ( p − 1 ) ( q − 1 ) ed equiv 1mod phi(n) equiv1mod (p-1)(q-1) ed≡1modϕ(n)≡1mod(p−1)(q−1)
• 将 P = ( e , n ) P=(e,n) P=(e,n)公开，作为公钥
• 将 S = ( d , n ) S=(d,n) S=(d,n)保密，作为私钥
  对于消息 M M M ，加密过程为 C = M e m o d    n C=M^e mod n C=Memodn， C C C为密文。
  对于密文 C C C，解密过程为 M = C d m o d    n M=C^dmod n M=Cdmodn, M M M为明文。
  注意消息M要在密文空间中，如对于一个16bit的n, 加密消息的长度不能超过16bit。

由RSA加解密过程需证明 M = M e d m o d    n M=M^{ed}mod n M=Medmodn
e d ≡ 1 m o d    ϕ ( n ) ed equiv 1modphi(n) ed≡1modϕ(n)
e d = 1 + k ϕ ( n ) ed=1+kphi(n) ed=1+kϕ(n)
若 M ∈ Z n ∗ M in mathbb{Z}^*_n M∈Zn∗​,即M和n互素则
M e d ≡ M ( 1 + k ϕ ( n ) ) m o d    n M^{ed}equiv M^{(1+kphi(n))} mod n Med≡M(1+kϕ(n))modn
≡ M ∗ M k ϕ ( n ) m o d    n equiv M*M^{kphi(n)}mod n ≡M∗Mkϕ(n)modn
≡ M ∗ M ϕ ( n ) k m o d    n equiv M*M^{phi(n)^k}mod n ≡M∗Mϕ(n)kmodn
∵ M ϕ ( n ) ≡ 1 m o d    n because M^{phi(n)}equiv 1 mod n ∵Mϕ(n)≡1modn(由欧拉定理可得)
≡ M ∗ 1 k m o d    n equiv M*1^{k}mod n ≡M∗1kmodn
≡ M m o d    n = M equiv M mod n=M ≡Mmodn=M
若 M ∉ Z n ∗ Mnotin mathbb{Z}^*_n M∈/​Zn∗​,则M是p或q的倍数,但不可能同时是p和q的倍数。此时假设M是p的倍数即 M = c p M=cp M=cp，则M与q互素。
根据欧拉定理
M ϕ ( q ) ≡ 1 m o d    q M^{phi(q)}equiv1 mod q Mϕ(q)≡1modq
M ϕ ( p ) ϕ ( q ) ≡ M ϕ ( q ) ϕ ( p ) m o d    q ≡ 1 ϕ ( p ) m o d    q ≡ 1 m o d    q M^{phi(p)phi(q)}equiv M^{phi(q)^{phi(p)}} mod qequiv1^{phi(p)}mod qequiv1 mod q Mϕ(p)ϕ(q)≡Mϕ(q)ϕ(p)modq≡1ϕ(p)modq≡1modq
而 M ϕ ( p ) ϕ ( q ) ≡ M ϕ ( n ) m o d    q ≡ 1 m o d    q M^{phi(p)phi(q)}equiv M^{phi(n)} mod qequiv 1 mod q Mϕ(p)ϕ(q)≡Mϕ(n)modq≡1modq
两边同时取k次幂，则 M k ϕ ( p ) ϕ ( q ) ≡ 1 k m o d    q ≡ 1 m o d    q M^{kphi(p)phi(q)}equiv 1^kmod qequiv 1 mod q Mkϕ(p)ϕ(q)≡1kmodq≡1modq
存在整数 d d d使下式成立
M k ϕ ( n ) = 1 + q d M^{kphi(n)}=1+qd Mkϕ(n)=1+qd
M k ϕ ( n ) M = ( 1 + q d ) M M^{kphi(n)}M=(1+qd)M Mkϕ(n)M=(1+qd)M
M k ϕ ( n ) + 1 = ( 1 + q d ) M = M + M q d = M + c p q d = M + n c d M^{kphi(n)+1}=(1+qd)M=M+Mqd=M+cpqd=M+ncd Mkϕ(n)+1=(1+qd)M=M+Mqd=M+cpqd=M+ncd
两边同时取模n则 M k ϕ ( n ) + 1 = M M^{kphi(n)+1}=M Mkϕ(n)+1=M

下面是使用python实现对一段消息的加密，代码写的比较随意，主要想体现rsa加解密的过程。

import rsa

# 密钥空间为16比特，可以一次加密2个字节的消息
pk, sk = rsa.newkeys(16)
print("公钥", pk)
print("私钥", sk)
message = "life is fucking movie"
# 将消息转ASCII编码
messageASCII = [ord(i) for i in message]
print("消息ASCII编码",messageASCII)
messageList = []
# 将2个字节消息进行组合
for i in range(0, len(messageASCII), 2):
    if i + 1 < len(messageASCII):
        messageList.append((messageASCII[i] << 8) + messageASCII[i + 1])
    else:
        messageList.append((messageASCII[i] << 8))
print("组合编码：", messageList)
encryptM = [pow(i, pk.e, pk.n) for i in messageList]
print("密文：", encryptM)
decryptM = [pow(i, sk.d, sk.n) for i in encryptM]
print("解密：", decryptM)
result = ""
for i in decryptM:
    result = result + str(chr(i >> 8)) + str(chr(i & 255))
print(result)