CSSE/MA479: Cryptography

Homework 6 (60 pts), due on the date listed on the schedule page

4/12/2011: added current choice 3 and made it so that you can choose any 4 of 5.

1. Trappe and Washington, section 6.9: #8
2. #10 (a,b only)
3. #13 (Miller-Rabin)
4. #14. Note: (This one needs the general form of the Chinese Remainder Theorem): Your search will probably lead you to problem 3.13.24. Its step 3 should say x = a₁y₁z₁ + ... a_ky_kz_k (mod m₁m₂...m_k)

   Also, to take a cube root of x in Maple, use surd(x,3), or iroot().

   Submit a printout of your program (or a transcript of your Matlab/Maple session) and your results, along with any explanations of your work.

5. (15 pts) Solve 2^x = 12 (mod 19) using the Pollig-Hellman method. We'll hopefully start this in class on Friday.

BONUS: A person, using public keys
e= 14171
n = 47175870329407903885361746834641431178447600689579923010018954106190773045495123647160120041508873811309337286850351982107411134611
sends the message
43726198248769252947911976905432598115258108900903080580409697331380824611055578917544946060676831627279290841164054802058495542167
Decode the message. You may use any software you write or download to factor this number.

BONUS: A person, using public keys
e= 65537
n = 5179882962680223701492090545890640814585072653798871836048552437290684109327634426002180977320762762353246168450504471871488000000000059
sends the message
2922247964826923572673472775511955265925152326624921313193634795343106138357892068362850546777379886965965810552252359207791429407343570
Decode the message. You may use any software you write or download to factor this number.

Thanks to Dr Rickert for problem #3.