MATH/CSCI 4116 Cryptography
Sample Midterm Exam – Solutions
• Any page and section numbers refer to the course notes. *****************************************
1. Describe the differences between a code and a cipher. See Section 1.1.2 on p. 1.
2. The Vigen`ere cipher, the Hill cipher, and the permutation cipher are not secure. Explain why.
All three ciphers are affine linear block ciphers, and can therefore be easily broken; see Section 2.8.3 on p. 31.
3. (a) Find all the invertible residue classes mod 12 and their inverses.
This is very similar to Q. 3(a) on Assignment 2. Here we have to find those elements a ∈ Z12 that satisfy gcd(a, 12) = 1; these are a = 1, 5, 7, 11. We see that each element is its own inverse; for instance, 7 · 7 ≡ 1 (mod 12).
(b) Determine the group of units and the zero divisors of Z/16Z.
This is exactly Q. 3(b) on Assignment 2. Please see the solution posted there.
4. Is security of the affine cipher with a given modulus m increased if one encryption is followed by a second encryption with a different key? Give details.
This is Q. 2 on Assignment 3. See the solution there.
5. (a) State the definition (not a formula) of Euler’s φ-function. See Definition 2.14 on p. 13.
(b) Find φ(2016). [Here you may use an appropriate formula].
It is important to completely factor the given number: 2016 = 25 · 32 · 7. Either one of the formulas (2.3) or (2.4) on p. 14 would work equally well. If you want to avoid fractions, then (2.4) gives
φ(2016)=(25 −24)(32 −31)(71 −70)=16·6·6=576.
(c) We know that φ(ab) = φ(a)φ(b) whenever gcd(a, b) = 1. Give an example that shows
that the identity is, in general, not true when gcd(a, b) ̸= 1. This is Q. 1 on Assignment 5. See the solution there.
6. Suppose that you know that a Hill cipher with alphabet Z26 and block length 2 is being used, and you have obtained the ciphertext string (7, 0, 13, 3), along with the corresponding plaintext string (5, 14, 14, 19). Find the key.
This is very similar to the example at the end of Section 2.8.3, p. 31/32. Only here, plaintext and ciphertext are interchanged. From what’s given, we have the matrices
W=5 14 and C=713. 14 19 0 3
Now det W = 5·19−142 = −101, so gcd(det W, 26) = 1 and also, since −101 ≡ 3 (mod 26), we have
So, finally, the key is
03 419 125
Remark: It’s always a good idea to check whether your result is correct. Here it means, is A really the key? (I checked, and it is).
(detW)−1 ≡ 3−1 ≡ 9 (mod 26). So 19−14 154
W′≡9· −14 5 ≡ 419 (mod26). A≡CW′≡713154≡115 (mod26).