2216.sagews

# A complete example of BREAKING the RSA Public-Key Cryptosystem
# Find a prime, p, of 2 digits

p = 97

print "First Prime number = ", p

First Prime number = 97

# Now find a second prime, q, also of 2 digits

q = 101
print "Second Prime number = ", q

Second Prime number = 101

# Multiply p and q to get n

n = p*q; n

\newcommand{\Bold}[1]{\mathbf{#1}}9797

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

phiofn = (p-1)*(q-1); phiofn

\newcommand{\Bold}[1]{\mathbf{#1}}9600

# 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

Number of tries 3 Public Key = 5437

# Then find its inverse mod phiofn, d. This will be the secret key.

d = inverse_mod(e,phiofn); d

\newcommand{\Bold}[1]{\mathbf{#1}}7573

# Just verifying

mod(e*d, phiofn)

\newcommand{\Bold}[1]{\mathbf{#1}}1

# 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

The message is: 2200

# To encrypt, compute c = m^e (mod n).

c = power_mod(m,e,n)
print "The cipher is: ", c

The cipher is: 1264

# To break the system, we can try a "brute force" method.
# That is, we know e, the public key, and n = p*q; we intercept c, and we need to find m
# In other words, we can break the system 
# if we find m such that m^e = c (mod 9797)
# Consider

i = 1
while (power_mod(i,e,n)<>c):
    i += 1
    
print "The message is", i
print " "

# and verify

print "Raising the message to e power mod n is  ", power_mod(i,e,n)
print "And the intercepted cipher, c, is  ",c

The message is 2200 Raising the message to e power mod n is 1264 And the intercepted cipher, c, is 1264