在Python中实现RSA

Question

我正在尝试用Python实现RSA算法（我对Python还很陌生），但是我写的代码在处理超过4位数的数字时出现了问题。你知道为什么会这样吗？请给我一些建议。

p =0
q=0
n=0#modules
phyPQ = 0
e = 0 #public key exponent
d = 0#private key exponent
c = ''
m = ''

def getPrimes():
    global p
    global q
    p = long(raw_input("Enter first prime p :   "))
    q = long(raw_input("Enter second prime q :  "))

def computeModules(prime1,  prime2):
    global n
    n = prime1 * prime2
    print "Modules is = "+ `n`
    return n

def computePhyPQ(prime1,  prime2):
    global phyPQ
    phyPQ = (prime1 -1) * (prime2 -1)
    print "The phyPQ is " + `phyPQ`

def computePublickeyExponent(x):
    pubKeyExponentList= []
    for i in range(1, x):
        if  x % i != 0: 
            pubKeyExponentList.append(i)
    print pubKeyExponentList
    global e
    e =  long(raw_input("Pick a public key exponent from the list above :  "))

def computePrivateKeyExponent(phyQP,  pubKeyExpo):
    flag = 1
    count = 0
    while flag == 1:
        count = count + 1
        if (count * phyQP + 1) % phyQP == 1:
            result = (count * phyQP + 1) / float(pubKeyExpo)
            if result % 1 == 0:
                global d
                d = long(result)
                print 'The private key exponent exponent is:' +  `d`
                flag = 0

def encryptMessage(exponent,  modules):
    #c= m ^e mod n
    global c
    message= long(raw_input("Enter a value to be encrypted:"))

    c = long((message ** exponent) % modules)
    print'The encrypted message is :' + `c`

def decryptMessage(modules,  privateKeyExpo, cryptedMessage):
    #m = c^d % n
    global m
    m = (cryptedMessage ** privateKeyExpo) % modules
    print 'message after decrypting is :' + `m`

def mainMethod():
    getPrimes()
    computeModules(p, q)
    computePhyPQ(p,  q)
    computePublickeyExponent(phyPQ)
    computePrivateKeyExponent(phyPQ, e)
    encryptMessage(e, n)
    decryptMessage(n, d, c)

mainMethod() 

Answer 1

你不能用普通的数字计算来进行加密。因为数字通常会有很大的指数，比如1000。你可以使用一个叫gmpy2的Python库，它可以处理非常大的整数计算。

首先，导入这个库：

import gmpy2

然后，比如说，把下面这行代码：

result = (count * phyQP + 1) / float(pubKeyExpo)

改成：

result = gmpy2.f_divmod(count * phyQP + 1, pubKeyExpo)

如果结果的第一个值大于0，并且第二个值等于0：

Answer 2

c = long((message ** exponent) % modules) 这个写法不太合适，因为它运行得非常慢。

你可以用平方-乘法的方式来计算指数，或者用滑动窗口法，或者用蒙哥马利阶梯法来替代。

一个不错的例子可以在这里找到：http://code.activestate.com/recipes/572196-rsa/

Answer 3

你的问题很可能出在浮点数运算上：

        result = (count * phyQP + 1) / float(pubKeyExpo)

在这个算法中，使用任意精度的整数运算是非常重要的。

你可以在实现的某些地方用到三参数版本的pow()函数。pow(x, y, z)这个函数可以计算(x ** y) mod z，并且支持任意精度的整数。