All problems are of equal value:

Problem 1: In class I suggested the following algorithm for Alice to securely send to Bob a secret number X. Alice chooses a random value r and sends Bob the value X+r. Bob chooses a random value s and sends Alice X+r+s. Alice subtracts her random value r from X+r+s to get X+s and sends this to Bob. Bob now subtracts s from this last message to get X. Eve only sees X plus a random value in each message. There is something fundamentally wrong with this protocol. What is it? (Thanks to Dan Hore for this question.)

Problem 2: Use the repeated squaring algorithm to compute 35¹¹¹ mod 83. (Show your work, i.e., the values that are computed at each step of the algorithm.) How many multiplications does it take? Can you find a way to compute it using fewer multiplications? How many multiplications are needed to compute a ¹⁵ using the repeated squaring algorithm? Can you do it with fewer? Show that your algorithm uses the least number of multiplications, i.e., no other algorithm could use fewer multiplications.

Problem 3: Assume Bob's public key is n = 18721 and e = 25 . Further assume that Alice sends a message to Bob by representing each alphabetic character of the message as an integer between 0 and 25 with a = 0, b = 1,..., z =25, and then encrypting and sending each letter separately. Describe how Eve might attack such a system without factoring n . Illustrate your attack on the following message: 365, 0, 4845, 14930, 2608, 2608, 0.

Problem 4: Alice, Bob and Charlie want to share a single common secret key to use for their symmetric key cipher communications. Design a protocol along the lines of Diffie-Hellman that allows them to agree upon a common key value by exchanging messages over an open communication channel. Argue that your protocol is as hard to break as the original Diffie-Hellman protocol, i.e., if someone could break your protocol they could break Diffie-Hellman.

Problem 5:

1. Prove that if a and b are both even, then gcd(a,b) = 2 gcd (a/2,b/2).
2. Prove that if a and b are both odd, then gcd(a,b) = gcd ((a-b)/2, b).
3. Prove that if a is odd and b is even, then gcd(a,b) = gcd (a,b/2).
4. Use the above facts to describe another algorithm for computing the gcd(a,b) . Compare the efficiency of the new algorithm to Euclid's algorithm.

Bonus: Decode the following RSA encoded message. (Hint: n = 39757 and e = 7.)

7083352749453679329396849144940198040705040411839 6252625156353832537039098652119973757941943063667 1399490566146911824750663091686206116707947161038 7919121312685923988724156016580572779817318380946 0632649976177443034330659539087093836836829609288 0051276252652305341836088829638343716237572217617 1180003958858234419165133913993146975307924216916 5571028122262268215991960131078677899955916064826 8016096726798199254176167381343567377123806608152 9608491377711903154189873286819541681400724597217 6051223472849478541759640621462538315066959793945 48823397948731359248967015118

Report problems to dkrizanc at wesleyan.edu