Use Sage to answer the following questions. Show all your sage input/output: Suppose your RSA public key factors as p = 6569 and q = 8089, and the public exponent e is 11. Suppose you were sent the Ci

Using Sage we can simulate an RSA Encryption and Decryption.

sage: # randomly select some prime numbers

sage: p = random_prime(1000); p

191

sage: q = random_prime(1000); q

601

sage: # compute the modulus

sage: N = p*q

sage: R = IntegerModRing(N)

sage: phi_N = (p-1)*(q-1)

sage: # we can choose the encrypt key to be anything

sage: # relatively prime to phi_N

sage: e = 17

sage: gcd(d, phi_N)

sage: # the decrypt key is the multiplicative inverse

sage: # of d mod phi_N

sage: d = xgcd(d, phi_N)[1] % phi_N

sage: d

60353

sage: # Now we will encrypt/decrypt some random 7 digit numbers

sage: P = randint(1,127); P

sage: # encrypt

sage: C = R(P)^e; C

46685

sage: # decrypt

sage: R(C)^d

sage: P = randint(1,127); P

sage: # encrypt

sage: C = R(P)^e; C

75843

sage: # decrypt

sage: R(C)^d

sage: P = randint(1,127); P

sage: # encrypt

sage: C = R(P)^e; C

288

sage: # decrypt

sage: R(C)^d

Also, Sage can just as easily do much larger numbers:

sage: p = random_prime(1000000000); p

114750751

sage: q = random_prime(1000000000); q

8916569

sage: N = p*q

sage: R = IntegerModRing(N)

sage: phi_N = (p-1)*(q-1)

sage: e = 2^16 + 1

sage: d = xgcd(e, phi_N)[1] % phi_N

sage: d

237150735093473

sage: P = randint(1,1000000); P

955802

sage: C = R(P)^e

sage: R(C)^d

955802