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 wont have trouble with excel.


3. Set up a spreadsheet which does Euclids 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 Euclids 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.