这学期开了一门网络安全课，应老师要求，最近要做RSA加密算法。前一篇文章中已经提到，我是用Python来实现的整个程序，而且速度上嘛，比用C实现的慢了很多。我还不清楚到底是寻找素数的算法存在问题，还是Python本身的问题。

关于RSA算法的讲解，最好的莫过于wikipedia上的RSA词条。里面已经非常详细地说明了，这里就不再赘述。整个算法中要用到的数学算法有：Extended Euclidean algorithm，Miller-Rabin primality test。当然，你还需要Modulo operation的知识。

整个算法最关键的是找到合适的P，Q，以及求D。前者尤为关键，它几乎决定了整个程序的运行速度。所以，找到一个搜索大素数的好算法是核心问题。关于求D，我并没有使用Extended Euclidean algorithm，而是用了蛮力求解，没关系，这影响不大，关键还是刚才说的那个。

寻找素数的算法我使用了Miller-Rabin primality test，参考了gmp库源代码中nextprime的实现。但速度上仍然远不如C的实现。详细代码如下：

!/usr/bin/env python

import random
import string
import math
import sys

DEBUG = False

def nextprime(n):
i = n + 1 - n%2
while not probably_prime(i):
i+=2
return i

#i = n + 1 - n%2
#m = 2*n
#while i  0):
    r.append(n % 2)
    n = n / 2
return r

def test(a, n):
“””
Returns:

  - True, if n is complex.
  - False, if n is probably prime.
"""
b = toBinary(n - 1)
d = 1
for i in xrange(len(b) - 1, -1, -1):
    x = d
    d = (d * d) % n
    if d == 1 and x != 1 and x != n - 1:
        return True
    if b[i] == 1:
        d = (d * a) % n
if d != 1:
    return True # Complex
return False # Prime

def MillerRabin(n, s = 15):
“””
Returns:

    - True, if n is probably prime.
    - False, if n is complex.
"""
for j in xrange(1, s + 1):
    a = random.randint(1, n - 1)
    if (test(a, n)):
        return False # n is complex
return True # n is prime

def probably_prime(n):
return MillerRabin(n)

def gcd(m, n):
while n:
m, n = n, m % n
return m

def genkey(bits=100):
BIG_NUM = []
P_INT = 0
Q_INT = 0
global P, Q, X, N, D, E

for i in range(bits):
    BIG_NUM.append(random.choice('0123456789'))

P_INT = int(''.join(BIG_NUM))

for i in range(bits):
    BIG_NUM[i] = random.choice('0123456789')

Q_INT = int(''.join(BIG_NUM))

if DEBUG:
    print "p=%d"%P_INT
    print "q=%d"%Q_INT

P = nextprime(P_INT)
Q = nextprime(Q_INT)

if DEBUG:
    print "next prime to p is %d"%P
    print "next prime to q is %d"%Q

N = P*Q
if DEBUG:
    print "n=%d"%N

X = (P-1)*(Q-1)
if DEBUG:
    print "x=%d"%X

while True:
    if gcd(X, E)==1:
        break
    E+=2

if DEBUG:
    print "e=%d"%E

n = 1
while (n*X+1)%E!=0:
    n+=1
D = (n*X+1)/E

if DEBUG:
    print "d=%d"%D

def rsa_encrypt(msg):
enc = []
for c in msg:
enc.append(pow(ord(c), E, N))
return enc

def rsa_decrypt(cmsg):
dec = []
tmp = []
for ec in cmsg:
tmp.append(pow(ec, D, N))
for c in tmp:
dec.append(“%c”%c)
return dec

X = N = D = P = Q = 0
E= 65537

if name==”main“:
DEBUG = True

argc = len(sys.argv)
if argc==1:
    genkey()
elif argc==2:
    genkey(string.atoi(sys.argv[1]))
else:
    sys.exit(-1)

msg = raw_input()
enc = rsa_encrypt(msg)
if DEBUG:
    print enc
dec = rsa_decrypt(enc)
print ''.join(dec)