COMP 165  Fall 2016  Homework 4
Due Wednesday, 19 October, 2016 in class
Report problems to ablumer via email

Show how knowing the decryption key, d, for RSA in addition to the encryption
key, e, allows you to factor n. Apply this to factor n=846,409 with e = 7, d = 241,303.

(This is a version of Problem 9.11) Suppose that Eve knows that Alice and Bob
are communicating using RSA to generate a onetime pad as the sequence
E(2), E(3), E(4), ... where E(X) means encrypting X using a modulus N known
to Eve and an encryption exponent, e, not known to Eve. Eve doesn't know d either.
Suppose Eve captures E(2) and E(3), knowing that they correspond to 2 and 3.
Show how Eve can calculate a lot of other E(X) values. Which values with X < 100
can she calculate easily?

Give another reason why one wouldn't use RSA to generate a onetime pad.

(This is a version of Problem 9.15)
Suppose Mal is on the same network as Alice and Bob, and Mal can intercept
and modify messages. Everyone on the network knows everyone else's
public key. Alice and Bob communicate by sending messages
such as (A, E_{b}(M), B) from Alice to Bob, followed by the
return acknowledgement (B, E_{a}(M), A). (The first message
is Alice's name concatenated with the message encrypted using Bob's
public key concatenated with Bob's name.) Show how Mal can trick this
protocol into allowing him to obtain M.

Show how changing the messages to (A, E_{b}(M, A), B) and
(B, E_{a}(M, B), A) would defeat this attack.