我决定用Python编写一个简单的RSA加密实现,但是每次运行它时,解密时都会在IndexError: list out of range
中输出错误find_key
。
这是错误:
p 937 q 353 n 330761 phi 329472 e 5 d 264609 Traceback (most recent call last): File "rsa.py", line 94, in print dec_rsa(b, d, n) File "rsa.py", line 88, in dec_rsa char_array.append(decrypt_byte(i, d, n)) File "rsa.py", line 77, in decrypt_byte return find_key(alpha, (c**d)%n) File "rsa.py", line 67, in find_key return [k for k, v in dic.iteritems() if v == val][0] IndexError: list index out of range
The code:
import fractions, sys, random, math
def isPrime( no ):
if no < 2: return False
if no == 2: return True
if not no&1: return False
for x in range(3, int(no**0.5)+1, 2):
if no%x == 0:
return False
return True
def primes_range(low, high):
primes = []
for i in range(high-low):
if isPrime(i+low):
primes.append(i+low)
return primes
let = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789~!@#$%^&*()_+'";:[]/<>,."
a, alpha = 2, {}
for i in let:
alpha[i] = a
a+=1
Low = 29
High = 1000
p = random.choice(primes_range(Low, High))
q = random.choice(primes_range(Low, High))
while p == q:
q = random.choice(primes_range(Low, High))
print "p ",p
print "q ",q
#p = 104729
#q = 3
p, q = int(p), int(q)
n = p*q
phi = (p-1)*(q-1)
print "n ",n
print "phi ",phi
for i in range(2, q if q>p else p):
if fractions.gcd(i, phi) == 1:
e = i
break
print "e ",e
def egcd(a,b):
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a
def modInverse(e, phi):
return egcd(e, phi)[0]%n
d = modInverse(e, n)
print "d ",d
def find_key(dic, val):
#print "val ",val
#print "dic ",list(dic.iteritems())
return [k for k, v in dic.iteritems() if v == val][0]
def encrypt_byte(byte, e, n):
try:
m = alpha[byte]
except:
m = int(byte)
return (m**e)%n
def decrypt_byte(c, d, n):
return find_key(alpha, (c**d)%n)
def enc_rsa(string, e, n):
char_array = []
for i in range(len(string)):
char_array.append(encrypt_byte(alpha[string[i]], e, n))
return char_array
def dec_rsa(enc_arr, d, n):
char_array = []
for i in enc_arr:
char_array.append(decrypt_byte(i, d, n))
return ''.join(char_array)
a = "hello, world"
b = enc_rsa(a, e, n)
#print b
print dec_rsa(b, d, n)
最佳答案
希望您喜欢学习Python!
有两件事:
(1)您的isPrime已损坏:它认为1是质数,2和3不是,但是25、35、121、143、289、323、529、841、899都是。获得复合 Material 会导致问题。
(2)您也不必检查p!= q。
(3)您的alpha [str(byte)]应该是alpha [byte](否则您将得到“96llo,worl5”)。
(4)您采用了错误的乘法模逆。您需要modInverse(e,phi(n)),而不是modInverse(e,n);参见this worked example。
修复这些问题后,它似乎对我有用。
以下不是错误,而是建议:您可能应该使用pow(c,d,n)而不是(c ** d)%n;对于大量用户,前者将更快。同样,如果您想将一个字母转换为数字,而实际上并不在乎什么数字,则可以使用“ord”/“chr”功能,甚至不需要词典。无论如何,您可能希望交换字典中的键和值:现在,您的find_key可能也使用列表,因为您只需搜索所有k,v对,直到找到匹配项即可。
希望对您有所帮助!