# Homework 3

Due: November 8, 2016 (note extension!)
Points: 100

## Questions

1. (20 points) The relations certified (see ER1) and allowed (see ER2) can be collapsed into a single relation. Please do so and state the new relation. Why doesn’t the Clark-Wilson model do this?

2. (28 points) Consider the RSA cipher with p = 5 and q = 7. Show that d = e for all choices of public key e and private key d.

3. (20 points) Alice and Bob are creating RSA public keys. They select different moduli nAlice and $n_\mathrm{Bob}$. Unknown to both, nAlice and nBob have a common factor.
1. How could Eve determine that nAlice and nBob have a common factor without factoring those moduli?
2. Having determined that factor, show how Eve can now obtain the private keys of both Alice and Bob.

4. (32 points) Consider the Otway-Rees protocol. Assume that each enciphered message is simply the bits corresponding to the components of the message concatenated together. So, for example, in the first message, one must know the names “Alice” and “Bob”, and the length of the random numbers r1 and n, to be able to parse the portion of the first message that is enciphered with kAlice. The separate parts of the enciphered message have no indicators; the recipient is expected to determine them.
1. Consider Alice when all 4 steps of the protocol have been completed. How does Alice know that steps 2 and 3 have taken place?
2. Massicotte asks us to assume that an adversary Edgar is impersonating Bob, and has sufficient control over the exchange so that he receives the messages intended for Bob. Bob never sees them. What components of the protocol does Edgar know — that is, does he know r1, r2, n, or ksession, or the names of “Alice” and “Bob”? How?
3. Given this, in step 4 of the protocol, how might Edgar provide Alice with a session key that he knows?
4. How might someone fix this?

## Extra Credit

1. (30 points) Assume that a cryptographic checksum function computes hashes of 128 bits. Prove that the probability is 0.5 that at least one collision will occur after hashing 264 randomly selected messages.

 You can also obtain a PDF version of this. Version of October 23, 2016 at 10:58PM