RSA.sagews

USE THIS WORKSHEET TO DO THE IN CLASS PROJECT on 11/2/17. If you don't finish it in class finish it before Class on Tuesday!

Copy the functions powmod, binary and fermat from your SMC Assignment 4. If you don't have them, get them from someone else!

#Paste the functions here

Check that your functions work by testing whether 8675309 and 8675307 are prime using the fermat function and several different bases. Which one is prime?

Try out the command randint(a,b) which generates a random number between a and b.

randint(10,20)

17

Use randint and your fermat code (you may need to use a while loop or something else!) to generate two random prime numbers p and q with 60 digits.

Use p and q to compute n and phi(n).

n=p*q 
phin=(p-1)*(q-1)

Put your name along with your public key (use the encryption exponent e=65537) in a row of the spreadsheet here: https://docs.google.com/spreadsheets/d/1IDEtc38-w61g94SkiMksVOiw4CiyRcvo4HxDtbOU1YA/edit?usp=sharing

Sage has a built in xgcd command you can use to compute inverses. Test it out by using it to compute the inverse of 17 mod 67. (Note: you should get 4)

xgcd(67,17)

Now use your xgcd function in the same way to compute your decryption exponent, by finding the inverse of e modulo phi(n)

xgcd(phin,65537)

d=    #Put your decryption exponent here!

Now use the info in the spreadsheet to send others in the class a message. Use the following method to convert letters into numbers: let a->00 b->01 ... z->25 and write a message by concatenating the digits. So "HI" becomes 0708=708, Write a message with 6-10 letters in it. Then encrypt it using someone else's public key (You'll need the powmod function again) in the spreadsheet and send it to them by pasting it in columns D or E.

m=    # Put your name encoded into numbers here

C= powmod(m,65537,??)  #Replace the question marks with the modulus of someone else's public key!

Once someone sends you an encrypted text (ask someone else to if no one has) decrypt the message by raising the message they sent to your secret decryption key mod n. Verify that the message actually decrypts to someones name!

powmod(??,d,n)  #Replace the question marks with the ciphertext that someone sends you in the spreadsheet!