Homework 2

Due: October 22, 2021 — Note change of due date)
Points: 100

1. (20 points) An affine cipher has the form c = (am + b) mod n. Suppose m is an integer between 0 and 25, each integer representing a letter.
   1. Let n = 26, a = 3, and b = 123. What is the ciphertext corresponding to the phrase THIS IS A CIPHER MESSAGE.
   2. A requirement for a cipher is that every plaintext letter correspond to a different ciphertext letter. If a and b are not relatively prime to n, does the affine cipher meet this property? Either prove it does or present a counterexample.

2. (20 points) Alice and Bob are creating RSA public keys. They select different moduli n_Alice and n_Bob. Unknown to both, n_Alice and n_Bob have a common factor.
   1. How could Eve determine that n_Alice and n_Bob 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.

3. (20 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 r₁ and n, to be able to parse the portion of the first message that is enciphered with k_Alice. 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 r₁, r₂, n, or k_session, 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?

4. (20 points) Suppose a user wishes to edit the file xyzzy in a capability-based system. How can he be sure that the editor cannot access any other file? Could this be done in an ACL-based system? If so, how? If not, why not?

5. (20 points) Consider Multics procedures p and q. Procedure p is executing and needs to invoke procedure q. Procedure q’s access bracket is (5, 6) and its call bracket is (6, 9). Assume that q’s access control list gives p full (read, write, append, and execute) rights to q. In which ring(s) must p execute for the following to happen?
   1. p can invoke q, but a ring-crossing fault occurs.
   2. p can invoke q provided that a valid gate is used as an entry point.
   3. p cannot invoke q.
   4. p can invoke q without any ring-crossing fault occurring, but not necessarily through a valid gate.

Extra credit

1. (20 points) The index of coincidence was defined as “the probability that two randomly chosen letters from the ciphertext will be the same.” Derive the formula in Section 10.2.2.1 for the index of coincidence from this definition.

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 235A, Computer and Information Security Version of October 7, 2021 at 10:20PM

You can also obtain a PDF version of this.