RSA 算法：理论与 Python 实现

密码学是通过使用代码和密码来保护通信安全的实践。它包括多种将明文转换为密文、实现安全通信以及保护数据的机密性和完整性的技术。银行、电子邮件、电子商务和其他行业都广泛使用密码学。在本文中，您将了解非对称加密和 RSA 算法。

另请阅读：A* 算法 – 算法简介（带 Python 实现）

非对称加密

非对称加密通常称为公钥加密，使用两个不同的密钥进行加密和解密。公钥广泛用于加密数据并且众所周知，是密钥的一种。另一方面，私钥是保密的，即只有接收者知道它并用于解码数据。

为了使非对称加密成功，公钥和私钥都应该在发送方和接收方都可用。

非对称加密

加密算法接收发送者的纯文本消息，使用接收者的公钥对其进行加密，并生成密码。然后接收者通过传输或通信通道接收该密码。接收方的解密过程使用解密算法和接收方的私钥来恢复原始的明文消息。

非对称加密通常由三个主要组成部分组成：

密钥生成：在此步骤中，用户生成公钥-私钥对。任何想要向用户发送消息的人都可以免费使用公钥，而私钥则由用户保密。
加密：在此步骤中，发送者使用接收者的公钥来加密消息。这确保只有拥有相应私钥的接收者才能解密并读取消息。
解密：在此步骤中，收件人使用其私钥来解密使用其公钥加密的消息。这确保只有收件人才能阅读原始邮件。

尽管公钥和私钥之间存在数学联系，但通过计算这样做是不切实际的。这意味着任何人都可以使用公钥加密数据，但只有私钥的所有者才能解码数据。

注意：使用公钥加密的消息只能使用私钥解密，而使用私钥加密的消息也可以使用公钥解密。

现在让我们了解一下RSA算法。

RSA算法

RSA 算法是一种广泛使用的公钥加密算法，以其发明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的名字命名。它基于素因数分解和模运算的数学概念。

RSA的算法如下：

选择 2 个质数，最好是大质数，p 和 q。
计算 n = p*q。
计算 phi(n) = (p-1)*(q-1)
选择 e 的值，使得 1<e<phi(n) 且 gcd(phi(n), e) = 1。
计算 d，使得 d = (e^-1) mod phi(n)。

这里公钥是{e, n}，私钥是{d, n}。如果 M 是明文，则密文 C = (M^e) mod n。这就是 RSA 算法中数据加密的方式。同样，对于解密，明文 M = (C^d) mod n。

示例：设 p=3 和 q=11（均为素数）。

现在，n = p*q = 3*11 = 33
phi(n) = (p-1)*(q-1) = (3-1)*(11-1) = 2*10 = 20
e 的值可以为 7，因为 1<7<20 且 gcd(20, 7) = 1。
计算 d = 7^-1 mod 20 = 3。
因此，公钥 = {7, 33}，私钥 = {3, 33}。

假设我们的消息是 M=31。您可以使用RSA算法对其进行加密和解密，如下所示：

加密： C = (M^e) mod n = 31^7 mod 33 = 4

解密： M = (C^d) mod n = 4^3 mod 33 = 31

由于我们在解密后收到了纯文本的原始消息，因此我们可以说该算法工作正常。

下面是实现RSA算法的Python代码：

import math
 
# step 1
p = 3
q = 7
 
# step 2
n = p*q
print("n =", n)
 
# step 3
phi = (p-1)*(q-1)
 
# step 4
e = 2
while(e<phi):
    if (math.gcd(e, phi) == 1):
        break
    else:
        e += 1
 
print("e =", e)
# step 5
k = 2
d = ((k*phi)+1)/e
print("d =", d)
print(f'Public key: {e, n}')
print(f'Private key: {d, n}')
 
# plain text
msg = 11
print(f'Original message:{msg}')
 
# encryption
C = pow(msg, e)
C = math.fmod(C, n)
print(f'Encrypted message: {C}')
 
# decryption
M = pow(C, d)
M = math.fmod(M, n)
 
print(f'Decrypted message: {M}')      

输出：

n = 21
e = 5
d = 5.0
Public key: (5, 21)
Private key: (5.0, 21)
Original message:11
Encrypted message: 2.0
Decrypted message: 11.0

能够同时进行加密和数字签名是 RSA 算法的主要优势之一。为了确认消息未被篡改，通过使用发送者的私钥对消息哈希进行加密来进行数字签名。然后，任何有权访问发送者公钥的人都可以验证此加密。

结论

您在本文中了解了对称加密和 RSA 算法的知识。您还了解了如何在 Python 中实现 RSA 算法。

请访问 askpython.com 以获取更多此类易于理解的Python教程。

参考

维基百科