2906.sagews

# A complete example of the RSA Public-Key Cryptosystem
# Find a prime, p, of 200 digits 
p = ZZ.random_element(10^201)
i = 1 
while (not is_prime(p)):    
    i += 1 
    p = ZZ.random_element(10^201)
print "Number of tries", i 
print " " 
print "First Prime number = ", p

# Now find a second prime, q, also of 200 digits 
q = ZZ.random_element(10^201)
i = 1 
while (not is_prime(q)):    
    i += 1 
    q = ZZ.random_element(10^201)
print "Number of tries", i 
print " "
print "Second Prime number = ", q

# Multiply p and q to get n 
n = p*q; n

# Compute the Euler function of n, which we know to be (p-1)(q-1) 
phiofn = (p-1)*(q-1); phiofn

# Create a public key, e, relatively prime to phiofn 
e = ZZ.random_element(phiofn - 1)
i = 1 
while (not gcd(e,phiofn) == 1):    
    i += 1 
    e = ZZ.random_element(phiofn - 1)
print "Number of tries", i 
print " "
print "Public Key = ", e

# Then find its inverse mod phiofn, d. This will be the secret key. 
d = inverse_mod(e,phiofn); d

# Just verifying 
mod(e*d, phiofn)

# Now the RSA system is established. The public key is (e, n); 
# the secret key (d, p, q)
# Choose a message, which when interpreted as an integer, 
# is less than n 
m = ZZ.random_element(n-1)
print "The message is:  ", m

# To encrypt, compute c = m^e (mod n). 
c = power_mod(m,e,n)
print "The cipher is: ", c

# To decrypt, compute c^d (mod n), using the secret key d.
# Just for checking purposes, call this value mdecry, 
# as in m decrypted. 
mdecry = power_mod(c,d,n)
print "The decrypt is: ", mdecry

# Again just to verify, subtract mdecry from the original message. 
# We'd better get zero. 
print "Making sure we're right: ", m-mdecry