18.310 Assignment 7: RSA Coding Due Monday November 1 -- Wednesday November 3, 2004

 

1. Find all the primes in the range 94404000 to 94404100 using your spreadsheet.

 

2. Find two 4 digit primes, p and q and consider the RSA code based in their product. Choose a value z relatively prime to (p-1)(q-1)  and construct an encoder, which raises any 8 number less than p*q to power x mod N. Hint: choose p and q both to be under 3000 and you won’t have trouble with excel.

 

3. Set up a spreadsheet which does Euclid’s algorithm starting with A and B, and works backward to express the gcd it gets as a linear combination of A and B (that is, find the coefficients, a and b of A and B in the equation

 

gcd(A,B) = a*A + b*B

 

Use this spreadsheet to find the power you need to raise a received message to, mod N in order to decode it (by using Euclid’s algorithm appropriately)

 

4. Build a decoder spreadsheet that will decode your encoded message to give back  the original message, and get it to work so it actually does so.