from random import getrandbits
def is_prime(p):
return pow(2, p-1, p) == 1 #费马小定理
def get_prime(bits):
while True:
p = getrandbits(bits)
if is_prime(p):
break
return p
def get_inverse(a, b): #欧几里德扩展, FUCK, 太难写了
if a < b:
a, b = b, a
oa, ob = a, b
pp = [1, 0]
p = [0, 1]
while b != 1:
m = a % b
t = (a - m)/b
x = [pp[0]-p[0]*t, pp[1]-p[1]*t]
#print pp, '-', p, '*', t, '->', x
pp = p
p = x
a, b = b, m
return (x[1] + oa) % oa
# x^phi(n) = 1 mod n 欧拉定理 phi(n) = n-1 if n is prime
# x^phi(n)+1 = x mod n
# x^de = x mod n
# de = phi(n)+1
# de = 1 mod phi(n)
bits = 304
e = 0x10001
p = get_prime(bits/2)
q = get_prime(bits/2)
n = p*q
f = (p-1)*(q-1) #欧拉函数
d = get_inverse(e, f)
m = 0x7878787878 # lower than bits
c = pow(m, e, n)
t = pow(c, d, n)
print 'N: %X' % n
print 'E: %X' % e
print 'D: %X' % d
print 'RSA(%X):\n%X' % (m, c)
print 'RSA(%X):\n%X' % (c, t)
assert m == t
