为什么我在 Python 中的 RSA 实施不起作用？
Why is my RSA Implementation in Python not working?
出于学习目的，我正在尝试在 Python 中实现 RSA Public-Key Cryptography。我已经查看了示例代码并搜索了整个 Whosebug 以试图找到答案。
我的实现没有正常工作，我不知道为什么。
我可以轻松生成 Public- 和私钥。当我使用 public 密钥进行加密时，我得到类似
的信息
16102208556492
我认为这看起来是正确的。当我现在尝试解密密文时，它会给我随机的 ASCII 符号。所以我认为解密一定是错误的，但看起来也很好。
几天来我一直在努力寻找计算错误！
我一开始使用的是 Darrel Hankerson、Alfred Menezes 和 Scott Vanstone 合着的 "Guide to Elliptic Curve Cryptography" 一书中的数学算法。
算法 1.1：RSA 密钥对生成
INPUT: Security parameter l
OUTPUT: RSA public key e, private key d and n
1. Randomly select two primes p and q with same bitlength l/2
2. Compute n = pq and phi = (p-1)(q-1)
3. Select an arbitrary integer e with 1 < e < phi and gcd(e, phi)==1
4. Compute the integer d satisfying 1 < d < phi and ed == 1 mod phi
5. Return(n, e, d)
算法 1.2：基本 RSA 加密
INPUT: RSA public key e, n, plaintext m
OUTPUT: Ciphertext c
1. Compute c = m**e mod n
2. Return(c)
算法 1.3：基本 RSA 解密
INPUT: RSA private d, n, ciphertext c
OUTPUT: Plaintext m
1. Compute m = c**d mod n
2. Return(m)
我理解它在数学上是如何工作的，所以我这样实现它：
Python
中的算法 1.1
# INPUT: Secure parameter l
def Generation(l):
# Randomly select 2 primes with same Bitlength l/2
p = Randomly_Select_Prime_w_Bitlength(l/2)
q = Randomly_Select_Prime_w_Bitlength(l/2)
# Compute
n = p * q
phi = (p - 1) * (q - 1)
# Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
e = int(Arbitrary_Int_e(phi))
# Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
d = inverse(e, n)
# Return n e d
print("Public Key: " + str(e))
print("Private Key: " + str(d))
print("n = " + str(n))
Python
中的算法 1.2
# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
c = [pow(ord(char),e,n) for char in m]
print(''.join(map(lambda x: str(x), c)))
return c
Python
中的算法 1.3
# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
m = [chr(pow(char, d, n)) for char in c]
print(''.join(m))
return ''.join(m)
我在这里编写的代码似乎并没有错，但无论如何这里或其他函数中肯定有问题。
这是我的完整 python 代码
# RSA
# Imports
import random
# INPUT: Secure parameter l
def Generation(l):
# Randomly select 2 primes with same Bitlength l/2
p = Randomly_Select_Prime_w_Bitlength(l/2)
q = Randomly_Select_Prime_w_Bitlength(l/2)
# Compute
n = p * q
phi = (p - 1) * (q - 1)
# Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
e = int(Arbitrary_Int_e(phi))
# Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
d = inverse(e, n)
# Return n e d
print("Public Key: " + str(e))
print("Private Key: " + str(d))
print("n = " + str(n))
# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
c = [pow(ord(char),e,n) for char in m]
print(''.join(map(lambda x: str(x), c)))
return c
# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
m = [chr(pow(char, d, n)) for char in c]
print(''.join(m))
return ''.join(m)
def mrt(odd_int):
odd_int = int(odd_int)
rng = odd_int - 2
n1 = odd_int - 1
_a = [i for i in range(2,rng)]
a = random.choice(_a)
d = n1 >> 1
j = 1
while((d&1)==0):
d = d >> 1
j += 1
t = a
p = a
while(d>0):
d = d>>1
p = p*p % odd_int
if(d&1):
t = t*p % odd_int
if(t == 1 or t == n1):
return True
for i in range(1,j):
t = t*t % odd_int
if(t==n1):
return True
if(t<=1):
break
return False
def gcd(a, b):
while b:
a, b = b, a%b
return a
def Randomly_Select_Prime_w_Bitlength(l):
prime = random.getrandbits(int(l))
if (prime % 2 == 1):
if (mrt(prime)):
return prime
return Randomly_Select_Prime_w_Bitlength(l)
def Arbitrary_Int_e(phi):
_e = [i for i in range(1, phi)]
e = random.choice(_e)
if(gcd(e, phi) == 1 % phi):
return e
return Arbitrary_Int_e(phi)
def inverse(e, phi):
a, b, u = 0, phi, 1
while(e > 0):
q = b // e
e, a, b, u = b % e, u, e, a-q*u
if (b == 1):
return a % phi
else:
print("Must be coprime!")
正如 Marek Klein 在他的评论中所述，我用错误的参数调用了 "inverse()" 函数。
它是 d = inverse(e, n) 而不是 d = inverse(e, phi)。
But also from logical point of view, n is public, e is public, thus if that worked anyone can compute d that is supposed to be private.
The function Randomly_Select_Prime_w_Bitlength() often produces numbers with fewer bits than required, and sometimes produces a runtime error (because odd_int is too small in mrt()). If p and q are too small, you won't be able to encrypt as many bits of data as expected.
Randomly_Select_Prime_w_Bitlength() 现在正在检查随机素数是否大于 3，因此它不会 return 运行时错误，因为它变得比可能的小。
这是更正后的代码：
# RSA
# Imports
import random
# INPUT: Secure parameter l
def Generation(l):
# Randomly select 2 primes with same Bitlength l/2
p = Randomly_Select_Prime_w_Bitlength(l/2)
q = Randomly_Select_Prime_w_Bitlength(l/2)
# Compute
n = p * q
phi = (p - 1) * (q - 1)
# Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
e = int(Arbitrary_Int_e(phi))
# Compute the integer d statisfying 1 < d < phi and e*d == 1 % phi
d = inverse(e, phi)
# Return n e d
print("Public Key: " + str(e))
print("Private Key: " + str(d))
print("n = " + str(n))
# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
c = [pow(ord(char),e,n) for char in m]
print(''.join(map(lambda x: str(x), c)))
return c
# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
m = [chr(pow(char, d, n)) for char in c]
print(''.join(m))
return ''.join(m)
def mrt(odd_int):
odd_int = int(odd_int)
rng = odd_int - 2
n1 = odd_int - 1
_a = [i for i in range(2,rng)]
a = random.choice(_a)
d = n1 >> 1
j = 1
while((d&1)==0):
d = d >> 1
j += 1
t = a
p = a
while(d>0):
d = d>>1
p = p*p % odd_int
if(d&1):
t = t*p % odd_int
if(t == 1 or t == n1):
return True
for i in range(1,j):
t = t*t % odd_int
if(t==n1):
return True
if(t<=1):
break
return False
def gcd(a, b):
while b:
a, b = b, a%b
return a
def Randomly_Select_Prime_w_Bitlength(l):
prime = random.getrandbits(int(l))
if (prime % 2 == 1 and prime > 3):
if (mrt(prime)):
return prime
return Randomly_Select_Prime_w_Bitlength(l)
def Arbitrary_Int_e(phi):
_e = [i for i in range(1, phi)]
e = random.choice(_e)
if(gcd(e, phi) == 1 % phi):
return e
return Arbitrary_Int_e(phi)
def inverse(e, phi):
a, b, u = 0, phi, 1
while(e > 0):
q = b // e
e, a, b, u = b % e, u, e, a-q*u
if (b == 1):
return a % phi
else:
print("Must be coprime!")
在 python 中有一种更简单的方法来实现 RSA：
bits = 2048 # the bit length of the rsa key, must be multiple of 256 and >= 1024
E = 65537 # (default) the encryption exponent to be used [int]
from Crypto.PublicKey import RSA
key = RSA.generate(bits,E)
with open('my_key.pem','w') as file:
file.write(key.exportKey())
file.write(key.publickey().exportKey())
使用 Crypto.PublicKey 需要（在 windows CMD 或 mac 终端）：
pip install pycrypto
对于某些系统 运行 python 3（比如我的）：
pip3 install pycrypto
public密钥（模数+加密指数）和私钥（解密指数）都是base64格式，转成16进制作他用：
from base64 import b64decode
base64_string = 'AAAAbbbb123456=='
hex_string = b64decode(base64string).hex()
Two keys generated within a short time between each other may have their most significant digits equal:
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCpLVejQvo2xJwx04Oo2qotAge9
wWQDsk62hb0ua8r9+VM837+cArMStt9BoSTOCmNz7cYUXzGjQUsUi7tnHXM+Ddec
EG7J3q/w12ox2QN3wTndsW+GO9BD2EHY674t8A3JLSJP/bcD/FGBtjzytyd5hmQJ
Fife8rr4sAMkTXwoIwIDAQAB
和（彼此之间约 10 秒）
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCz9un7Xq248zlmkwVuXze2tUMy
a30BaodLJXYuAktGuiMAFwpprql0N9T06HdiphZmr+hT45gG57ZOlJn/yzN4U30Q
DXevDVapq6aYJ/Q21CO2bkLkMjEMy5D4IdwMeBgK+5pJFYETB6TzLfDkEcTQMr++
f7EHosWd0iBGm01cKQIDAQAB
出于学习目的，我正在尝试在 Python 中实现 RSA Public-Key Cryptography。我已经查看了示例代码并搜索了整个 Whosebug 以试图找到答案。
我的实现没有正常工作，我不知道为什么。
我可以轻松生成 Public- 和私钥。当我使用 public 密钥进行加密时，我得到类似
的信息16102208556492
我认为这看起来是正确的。当我现在尝试解密密文时，它会给我随机的 ASCII 符号。所以我认为解密一定是错误的，但看起来也很好。
几天来我一直在努力寻找计算错误！
我一开始使用的是 Darrel Hankerson、Alfred Menezes 和 Scott Vanstone 合着的 "Guide to Elliptic Curve Cryptography" 一书中的数学算法。
算法 1.1：RSA 密钥对生成
INPUT: Security parameter l
OUTPUT: RSA public key e, private key d and n
1. Randomly select two primes p and q with same bitlength l/2
2. Compute n = pq and phi = (p-1)(q-1)
3. Select an arbitrary integer e with 1 < e < phi and gcd(e, phi)==1
4. Compute the integer d satisfying 1 < d < phi and ed == 1 mod phi
5. Return(n, e, d)
算法 1.2：基本 RSA 加密
INPUT: RSA public key e, n, plaintext m
OUTPUT: Ciphertext c
1. Compute c = m**e mod n
2. Return(c)
算法 1.3：基本 RSA 解密
INPUT: RSA private d, n, ciphertext c
OUTPUT: Plaintext m
1. Compute m = c**d mod n
2. Return(m)
我理解它在数学上是如何工作的，所以我这样实现它：
Python
中的算法 1.1# INPUT: Secure parameter l
def Generation(l):
# Randomly select 2 primes with same Bitlength l/2
p = Randomly_Select_Prime_w_Bitlength(l/2)
q = Randomly_Select_Prime_w_Bitlength(l/2)
# Compute
n = p * q
phi = (p - 1) * (q - 1)
# Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
e = int(Arbitrary_Int_e(phi))
# Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
d = inverse(e, n)
# Return n e d
print("Public Key: " + str(e))
print("Private Key: " + str(d))
print("n = " + str(n))
Python
中的算法 1.2# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
c = [pow(ord(char),e,n) for char in m]
print(''.join(map(lambda x: str(x), c)))
return c
Python
中的算法 1.3# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
m = [chr(pow(char, d, n)) for char in c]
print(''.join(m))
return ''.join(m)
我在这里编写的代码似乎并没有错，但无论如何这里或其他函数中肯定有问题。
这是我的完整 python 代码
# RSA
# Imports
import random
# INPUT: Secure parameter l
def Generation(l):
# Randomly select 2 primes with same Bitlength l/2
p = Randomly_Select_Prime_w_Bitlength(l/2)
q = Randomly_Select_Prime_w_Bitlength(l/2)
# Compute
n = p * q
phi = (p - 1) * (q - 1)
# Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
e = int(Arbitrary_Int_e(phi))
# Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
d = inverse(e, n)
# Return n e d
print("Public Key: " + str(e))
print("Private Key: " + str(d))
print("n = " + str(n))
# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
c = [pow(ord(char),e,n) for char in m]
print(''.join(map(lambda x: str(x), c)))
return c
# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
m = [chr(pow(char, d, n)) for char in c]
print(''.join(m))
return ''.join(m)
def mrt(odd_int):
odd_int = int(odd_int)
rng = odd_int - 2
n1 = odd_int - 1
_a = [i for i in range(2,rng)]
a = random.choice(_a)
d = n1 >> 1
j = 1
while((d&1)==0):
d = d >> 1
j += 1
t = a
p = a
while(d>0):
d = d>>1
p = p*p % odd_int
if(d&1):
t = t*p % odd_int
if(t == 1 or t == n1):
return True
for i in range(1,j):
t = t*t % odd_int
if(t==n1):
return True
if(t<=1):
break
return False
def gcd(a, b):
while b:
a, b = b, a%b
return a
def Randomly_Select_Prime_w_Bitlength(l):
prime = random.getrandbits(int(l))
if (prime % 2 == 1):
if (mrt(prime)):
return prime
return Randomly_Select_Prime_w_Bitlength(l)
def Arbitrary_Int_e(phi):
_e = [i for i in range(1, phi)]
e = random.choice(_e)
if(gcd(e, phi) == 1 % phi):
return e
return Arbitrary_Int_e(phi)
def inverse(e, phi):
a, b, u = 0, phi, 1
while(e > 0):
q = b // e
e, a, b, u = b % e, u, e, a-q*u
if (b == 1):
return a % phi
else:
print("Must be coprime!")
正如 Marek Klein 在他的评论中所述，我用错误的参数调用了 "inverse()" 函数。
它是 d = inverse(e, n) 而不是 d = inverse(e, phi)。
But also from logical point of view, n is public, e is public, thus if that worked anyone can compute d that is supposed to be private.
The function Randomly_Select_Prime_w_Bitlength() often produces numbers with fewer bits than required, and sometimes produces a runtime error (because odd_int is too small in mrt()). If p and q are too small, you won't be able to encrypt as many bits of data as expected.
Randomly_Select_Prime_w_Bitlength() 现在正在检查随机素数是否大于 3，因此它不会 return 运行时错误，因为它变得比可能的小。
这是更正后的代码：
# RSA
# Imports
import random
# INPUT: Secure parameter l
def Generation(l):
# Randomly select 2 primes with same Bitlength l/2
p = Randomly_Select_Prime_w_Bitlength(l/2)
q = Randomly_Select_Prime_w_Bitlength(l/2)
# Compute
n = p * q
phi = (p - 1) * (q - 1)
# Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
e = int(Arbitrary_Int_e(phi))
# Compute the integer d statisfying 1 < d < phi and e*d == 1 % phi
d = inverse(e, phi)
# Return n e d
print("Public Key: " + str(e))
print("Private Key: " + str(d))
print("n = " + str(n))
# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
c = [pow(ord(char),e,n) for char in m]
print(''.join(map(lambda x: str(x), c)))
return c
# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
m = [chr(pow(char, d, n)) for char in c]
print(''.join(m))
return ''.join(m)
def mrt(odd_int):
odd_int = int(odd_int)
rng = odd_int - 2
n1 = odd_int - 1
_a = [i for i in range(2,rng)]
a = random.choice(_a)
d = n1 >> 1
j = 1
while((d&1)==0):
d = d >> 1
j += 1
t = a
p = a
while(d>0):
d = d>>1
p = p*p % odd_int
if(d&1):
t = t*p % odd_int
if(t == 1 or t == n1):
return True
for i in range(1,j):
t = t*t % odd_int
if(t==n1):
return True
if(t<=1):
break
return False
def gcd(a, b):
while b:
a, b = b, a%b
return a
def Randomly_Select_Prime_w_Bitlength(l):
prime = random.getrandbits(int(l))
if (prime % 2 == 1 and prime > 3):
if (mrt(prime)):
return prime
return Randomly_Select_Prime_w_Bitlength(l)
def Arbitrary_Int_e(phi):
_e = [i for i in range(1, phi)]
e = random.choice(_e)
if(gcd(e, phi) == 1 % phi):
return e
return Arbitrary_Int_e(phi)
def inverse(e, phi):
a, b, u = 0, phi, 1
while(e > 0):
q = b // e
e, a, b, u = b % e, u, e, a-q*u
if (b == 1):
return a % phi
else:
print("Must be coprime!")
在 python 中有一种更简单的方法来实现 RSA：
bits = 2048 # the bit length of the rsa key, must be multiple of 256 and >= 1024
E = 65537 # (default) the encryption exponent to be used [int]
from Crypto.PublicKey import RSA
key = RSA.generate(bits,E)
with open('my_key.pem','w') as file:
file.write(key.exportKey())
file.write(key.publickey().exportKey())
使用 Crypto.PublicKey 需要（在 windows CMD 或 mac 终端）：
pip install pycrypto
对于某些系统 运行 python 3（比如我的）：
pip3 install pycrypto
public密钥（模数+加密指数）和私钥（解密指数）都是base64格式，转成16进制作他用：
from base64 import b64decode
base64_string = 'AAAAbbbb123456=='
hex_string = b64decode(base64string).hex()
Two keys generated within a short time between each other may have their most significant digits equal:
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCpLVejQvo2xJwx04Oo2qotAge9
wWQDsk62hb0ua8r9+VM837+cArMStt9BoSTOCmNz7cYUXzGjQUsUi7tnHXM+Ddec
EG7J3q/w12ox2QN3wTndsW+GO9BD2EHY674t8A3JLSJP/bcD/FGBtjzytyd5hmQJ
Fife8rr4sAMkTXwoIwIDAQAB
和（彼此之间约 10 秒）
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCz9un7Xq248zlmkwVuXze2tUMy
a30BaodLJXYuAktGuiMAFwpprql0N9T06HdiphZmr+hT45gG57ZOlJn/yzN4U30Q
DXevDVapq6aYJ/Q21CO2bkLkMjEMy5D4IdwMeBgK+5pJFYETB6TzLfDkEcTQMr++
f7EHosWd0iBGm01cKQIDAQAB