8.7. Exercises

1:	A cryptographer once stated that cryptography could provide complete security, and that any other computer security controls were unnecessary. Why is he wrong? (Hint: Think of an implementation of a cryptosystem, and ask yourself what aspect(s) of the implementation can cryptography not protect.)
2:	Decipher the following ciphertext, which was enciphered using the Caesar cipher: TEBKFKQEBZLROPBLCERJXKBSBKQP.
3:	If one-time pads are provably secure, why are they so rarely used in practice?
4:	Prove that the DES key consisting of all 0-bits and the DES key consisting of all 1-bits are both weak keys. What are the other two weak keys? (Note: Differences in the parity bits, which the PC-1 permutation drops, do not count; the keys must differ in the 56 bits that are used to generate the key schedule.)
5:	Prove that the DES cipher satisfies the complementation property (see page 109).
6:	Let k be the encipherment key for a Caesar cipher. The decipherment key differs; it is 26 k. One of the characteristics of a public key system is that the encipherment and decipherment keys are different. Why then is the Caesar cipher a classical cryptosystem, not a public key cryptosystem? Be specific.
7:	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 8.2.2.1 for the index of coincidence from this definition.
8:	The following message was enciphered with a Vigenère cipher. Find the key and decipher it. TSMVM MPPCW CZUGX HPECP RFAUE IOBQW PPIMS FXIPC TSQPK SZNUL OPACR DDPKT SLVFW ELTKR GHIZS FNIDF ARMUE NOSKR GDIPH WSGVL EDMCM SMWKP IYOJS TLVFA HPBJI RAQIW HLDGA IYOUX
9:	In the example enciphering HELLO WORLD using the RSA cipher (the second example in Section 8.3.1), the modulus was chosen as 77, even though the magnitude of the cleartext blocks is at most 25. What problems in transmission and/or representation might this cause?
10:	Prove the following: If p is a prime, f(p) = p 1. If p and q are two distinct primes, f(pq) = (p 1)(q 1).
11:	Fermat's Little Theorem says that, for integers a and n such that a and n are relatively prime, af(n) mod n = 1. Use this to show that deciphering of an enciphered message produces the original message with the RSA cryptosystem. Does enciphering of a deciphered message produce the original message also?
12:	Consider the RSA cryptosystem. Show that the ciphertexts corresponding to the messages 0, 1 and n 1 are the messages themselves. Are there other messages that produce the same ciphertext as plaintext?
13:	It is often said that breaking RSA is equivalent to factoring the modulus, n. Prove that if n can be factored, one can determine the private key d from the modulus n and the public key e. Show that it is not necessary to factor n in order to determine the private key d from the modulus n and the public key e. (Hint: Look closely at the equation for computing the private key from n and e.) Show that it is not necessary to factor n in order to determine the plaintext m from a given ciphertext c, the public key e, and the modulus n. (Hint: Look closely at the equation for computing the ciphertext c.)
14:	Prove the fundamental laws of modular arithmetic: (a + b) mod n = (a mod n + b mod n) mod n ab mod n = ((a mod n)(b mod n)) mod n
15:	How would you use the law ab mod n = ((a mod n)(b mod n)) mod n to reduce to 13 the number of multiplications required to compute 3577 mod 83 from 76 multiplications? Can you reduce it any further?
16:	The section on public key cryptosystems discussed nonrepudiation of origin in the context of public key cryptosystems. Consider a secret key system (in which a shared key is used). Bob has a message that he claims came from Alice, and to prove it he shows both the cleartext message and the ciphertext message. The ciphertext corresponds to the plaintext enciphered under the secret key that Alice and Bob share. Explain why this does not satisfy the requirements of nonrepudiation of origin. How might you modify a classical cryptosystem to provide nonrepudiation?
17:	Suppose Alice and Bob have RSA public keys in a file on a server. They communicate regularly using authenticated, confidential messages. Eve wants to read the messages but is unable to crack the RSA private keys of Alice and Bob. However, she is able to break into the server and alter the file containing Alice's and Bob's public keys. How should Eve alter that file so that she can read confidential messages sent between Alice and Bob, and forge messages from either? How might Alice and/or Bob detect Eve's subversion of the public keys?
18:	Is the identity function, which outputs its own input, a good cryptographic checksum function? Why or why not?
19:	Is the sum program, which exclusive or's all words in its input to generate a one-word output, a good cryptographic checksum function? Why or why not?
20:	Assume that a cryptographic checksum function computes hashes of 128 bits. Prove that the probability of finding two messages with the same hash (that is, with the value of neither message being constrained) is 264.
21:	The example involving the DES-MAC cryptographic hash function stated that a birthday attack would find collisions given 232 messages. Alice wants to take advantage of this to swindle Bob. She draws up two contracts, one that Bob has agreed to sign and the other that Bob would not sign. She needs to generate a version of each that has the same checksum. Suggest how she might do this. (Hint: Adding blank spaces, or inserting a character followed by a backspace, will not affect the meaning of either contract.)