COMP 165 - Fall 2016 - Homework 4

Due Wednesday, 19 October, 2016 in class

Report problems to ablumer via email

  1. 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.
  2. (This is a version of Problem 9.11) Suppose that Eve knows that Alice and Bob are communicating using RSA to generate a one-time 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?
  3. Give another reason why one wouldn't use RSA to generate a one-time pad.
  4. (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, Eb(M), B) from Alice to Bob, followed by the return acknowledgement (B, Ea(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.
  5. Show how changing the messages to (A, Eb(M, A), B) and (B, Ea(M, B), A) would defeat this attack.