python中的RSA加密

Question

我决定在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

代码:

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)

Answer 1

我希望你喜欢学习Python!

有几件事:

(1)你的isPrime被打破:它认为1是素数,2和3不是,但25,35,121,143,289,323,529,841,899全部是.获得复合材料会导致问题.

(2)你也不检查p!= q.

(3)你的alpha [str(byte)]应该是alpha [byte](否则你会得到"96llo,worl5").

(4)你正在采用错误的乘法模数逆.你想要modInverse(e,phi(n)),而不是modInverse(e,n); 看到这个有效的例子.

修好后,它似乎对我有用.

以下不是错误,而是建议:你应该使用pow(c,d,n)而不是(c**d)%n; 对于大数字,前者会快得多.同样,如果你想把一个字母变成一个数字,而你真的不在乎什么数字,你可以使用"ord"/"chr"函数,甚至不需要字典.在任何情况下,您可能想要交换字典中的键和值:现在您的find_key也可能使用列表,因为您只是搜索所有k,v对,直到找到匹配项.

希望有所帮助!