All problems are of equal value:

Problem 1: Assume you some how have constructed an algorithm that can solve the RSA problem for some inputs but not others. That is, given c = m^e mod n and n and e, it can sometimes find m. Further say it works for about 1 per cent of all values of c for any given n and e. Using this algorithm, describe an algorithm that works for all inputs. That is, given any cipher message c (and the corresponding n and e) your algorithm can find the corresponding plaintext m. Your algorithm should be probablistic in nature. It should always eventually find the right m but it may run for a long time on some inputs. Analyze its expected running time (expressed in terms of calls to the other algorithm). This should be relatively good, i.e., it should be efficient assuming the original algorithm for solving 1 per cent of the problems is efficient.

Problem 2: A spy (Alice) is to be sent into the field for 10 days. Before she leaves, she and her handler (Bob) agree upon a secret value x and a secure hash function H. Each day Alice is to report in and to authenticate herself to Bob, she is to send some value computed using only H and x. (She can not use any other values that might be known to each party such as the date, message number, etc. She also can't manipulate x by, for example, computing x*x or something similar. She basically can only apply H to x repeatedly, computing H(H(x)) for example. This is a big hint!) Describe a scheme whereby she can authenticate herself, but Eve, who has been listening to all of the messages sent and knows H, can not impersonate Alice to Bob. Argue (informally) that your scheme is secure assuming H is secure and x remains secret.

Problem 3: 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? If you can, show that your algorithm uses the least number of multiplications, i.e., no other algorithm could use fewer multiplications.

Problem 4: 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 5: 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.

Report problems to dkrizanc at wesleyan.edu