"""
Why calculators aren't as fun (unless yours has a bigger than
usual screen maybe?):
RSA-640
RSA-640 has 193 decimal digits. A cash prize of US$20,000 was
offered by RSA Security for a successful factorization.
On November 2, 2005, F. Bahr, M. Boehm, J. Franke and T. Kleinjung
of the German Federal Office for Information Security announced
that they had factorized the number using GNFS as follows:
[19][20][21]
RSA-640 = 31074182404900437213507500358885679300373460228427275457
20161948823206440518081504556346829671723286782437916272
83803341547107310850191954852900733772482278352574238645
4014691736602477652346609
RSA-640 = 16347336458092538484431338838650908598417836700330923121
81110852389333100104508151212118167511579
× 19008712816648221131268515739354139754718967899685154936
66638539088027103802104498957191261465571
The computation took 5 months on 80 2.2 GHz AMD Opteron CPUs.
The slightly larger RSA-200 was factored in May 2005 by the same team.
See:
http://en.wikipedia.org/wiki/RSA-640#RSA-640
"""
N = int("31074182404900437213507500358885679300373460228427275457" +\
"20161948823206440518081504556346829671723286782437916272" +\
"83803341547107310850191954852900733772482278352574238645" +\
"4014691736602477652346609")
p = int("16347336458092538484431338838650908598417836700330923121"+\
"81110852389333100104508151212118167511579")
q = int("19008712816648221131268515739354139754718967899685154936"+\
"66638539088027103802104498957191261465571")
totient = (p - 1) * (q - 1)
"""
These guys only work in a namespace with N, d already defined
We're setting e = 7 to keep it simple
Euler's Totient Theorem
This theorem is one of the important keys to the RSA algorithm:
If GCD(T, R)== 1 and T < R, then pow (T, phi(R), R) == 1
Or, in words:
If T and R are relatively prime, with T being the smaller
number, then when we multiply T with itself phi(R) times
and divide the result by R, the remainder will always be 1.
"""
from binascii import hexlify, unhexlify
def mknum(phrase):
return eval('0x'+hexlify(phrase)+'L')
def mkphrase(num):
return unhexlify(hex(num)[2:-1])
def gcd(a,b):
"""Return greatest common divisor using Euclid's Algorithm."""
while b:
a, b = b, a % b
return a
def lcm(a,b):
"""
Return lowest common multiple."""
return (a*b)/gcd(a,b)
def bingcd(a,b):
"""Extended version of Euclid's Algorithm (binary GCD)
Returns (m,n,gcd) such that m*a + n*b = gcd(a,b)"""
g,u,v = [b,a],[1,0],[0,1]
while g[1]<>0:
y = g[0]/g[1]
g[0],g[1] = g[1],g[0]%g[1]
u[0],u[1] = u[1],u[0] - y*u[1]
v[0],v[1] = v[1],v[0] - y*v[1]
m = v[0]%b
gcd = (m*a)%b
n = (gcd - m*a)/b
return (m,n,gcd)
def inverse(a,b):
"""If gcd(a,b)=1, then inverse(a,b)*a mod b = 1,
otherwise, if gcd(a,b)!=1, return 0
Useful in RSA encryption, for finding d such that
e*d mod totient(n) = 1"""
inva,n,gcd = bingcd(a,b)
return (gcd==1)*inva
class Sender:
def __init__(self, m):
self.m = mknum(m)
def encrypt(self):
"""RSA algorithm"""
c = pow(self.m, 7, N)
return c
class Receiver:
def __init__(self, c):
self.c = c
def decrypt(self):
"""RSA algorithm"""
d = inverse(7, totient)
m = pow(self.c, d, N)
return mkphrase(m)
def testing123():
print(p)
print(q)
print(p*q)
print(N)
print(N == p*q)
d = inverse(7, totient)
print(d)
print(7*d % totient)
def testingrsa():
bob = Sender("Able was I ere I saw Elba")
c = bob.encrypt()
alice = Receiver(c)
m = alice.decrypt()
print(m)
if __name__ == "__main__":
# testing123()
testingrsa()