Contents
1 Introduction 3
2 Perfectly Secret Encryption 7
3 Private-Key Encryption 19
4 Message Authentication Codes 35
5 CCA-Security and Authenticated Encryption 47
6 Hash Functions and Applications 51
7 Practical Constructions of Symmetric-Key Primitives 63
8 Theoretical Constructions of Symmetric-Key Primitives 77
9 Number Theory and Cryptographic Hardness Assumptions 93
10 Factoring and Computing Discrete Logarithms 107
11 Key Management and the Public-Key Revolution 111
12 Public-Key Encryption 117
13 Digital Signature Schemes 133
14 Post-Quantum Cryptography 137
15 Advanced Topics in Public-Key Encryption 145
B Basic Algorithmic Number Theory 157
iii
,
,Chapter 1
Introduction – Solutions
1.1 Decrypt the ciphertext provided at the end of the section on mono-
alphabetic substitution.
Solution: The ciphertext decrypts to the following plaintext (we have
added punctuation, spaces, and capitalization):
Cryptographic systems are extremely difficult to build. Never-
theless, for some reason many non-experts insist on designing
new encryption schemes that seem to them to be more se-
cure than any other scheme on earth. The unfortunate truth,
however, is that such schemes are usually trivial to break.
We would expect students to describe the methodology they used to
derive the solution.
1.2 Provide a formal definition of the Gen, Enc, and Dec algorithms for the
mono-alphabetic substitution cipher.
Solution: For this exercise, we identify numbers and letters in the
natural way. That is, a = 0, b = 1, and so on.
• Gen: Choose a random permutation π of {0, . . . , 25} and let the
key be this permutation. (A random permutation on {0, . . . , 25}
can be chosen as follows: for i = 0 to 25, set π(i) equal to a random
number from {0, . . . , 25} that has not been chosen so far.)
• Enc: Given a plaintext m = m1 , . . . , m` (where mi ∈ {0, . . . , 25})
and a key π, set ci := π(mi ) and output c1 , . . . , cn .
• Dec: Given a ciphertext c = c1 , . . . , cn and key π, set mi := π −1 (ci )
where π −1 is the inverse of π and output m1 , . . . , mn .
1.3 Provide a formal definition of the Gen, Enc, and Dec algorithms for
the Vigenère cipher. (Note: there are several plausible choices for Gen;
choose one.)
Solution: As in the previous exercise, we identify numbers and letters
in the natural way. That is, a = 0, b = 1, and so on.
• Gen: Choose a random period: this can be chosen uniformly in a
fixed set of some size, or it can be chosen according to some valid
3
, 4 Introduction to Modern Cryptography – 3rd Edition Solutions Manual
probability distribution over the integers (e.g., assign the length
5 + i with probability 2−i ). Denote the chosen period by t. For
i = 0, . . . , t − 1 choose uniform ki in {0, . . . , 25}. Output the key
k = k0 , . . . , kt−1 .
• Enc: Given a plaintext p = p0 , . . . , pn and a key k = k0 , . . . , kt−1 ,
set ci := [pi + k[i mod t] mod 26]. Output c0 , . . . , cn .
• Dec: Given a ciphertext c = c0 , . . . , cn and a key k = k0 , . . . , kt−1 ,
set pi := [ci − k[i mod t] mod 26]. Output p0 , . . . , pn .
1.4 Say you are given a ciphertext that corresponds to English-language text
that was encrypted using either the shift cipher or the Vigenère cipher
with period greater than 1. How could you tell which was the case?
Solution: The index of coincidence method described in this chapter
can be used to find the key length (i.e., period) of the Vigenère cipher.
Since the shift cipher corresponds to the Vigenère cipher with a period
of 1, the index of coincidence method can be used to determine which
scheme was used.
1.5 Implement the attacks described in this chapter for the shift cipher and
the Vigenére cipher.
Implementation exercise – no solution given.
1.6 The shift and Vigenère ciphers can also be defined on the 256-character
alphabet consisting of all possible bytes (8-bit strings), and using XOR
instead of modular addition.
(a) Provide a formal definition of both schemes in this case.
(b) Discuss how the attacks we have shown in this chapter can be
modified to break each of these modified schemes.
Solution: We describe the solution for the Vigenère cipher, which is
the more complex case.
(a) Key generation chooses a period t (say, uniform in {1, . . . , tmax } for
some specified tmax ) and then, for i = 0, . . . , t − 1, chooses uniform
ki ∈ {0, 1}8 . The encryption of a plaintext m = m1 , . . . , m` is
c = c1 , . . . , c` , where ci := mi ⊕ k[i mod t] . Decryption is done in
the natural way.
(b) The attacks described in the text can be adapted to apply here
as well. One must be careful to let pi be the frequency of the
ith byte—so, e.g., non-ASCII characters have frequency 0; the fre-
quency of ‘A’ is different from the frequency of ‘a’; and frequencies
of the space character and punctuation are also taken into account.
1 Introduction 3
2 Perfectly Secret Encryption 7
3 Private-Key Encryption 19
4 Message Authentication Codes 35
5 CCA-Security and Authenticated Encryption 47
6 Hash Functions and Applications 51
7 Practical Constructions of Symmetric-Key Primitives 63
8 Theoretical Constructions of Symmetric-Key Primitives 77
9 Number Theory and Cryptographic Hardness Assumptions 93
10 Factoring and Computing Discrete Logarithms 107
11 Key Management and the Public-Key Revolution 111
12 Public-Key Encryption 117
13 Digital Signature Schemes 133
14 Post-Quantum Cryptography 137
15 Advanced Topics in Public-Key Encryption 145
B Basic Algorithmic Number Theory 157
iii
,
,Chapter 1
Introduction – Solutions
1.1 Decrypt the ciphertext provided at the end of the section on mono-
alphabetic substitution.
Solution: The ciphertext decrypts to the following plaintext (we have
added punctuation, spaces, and capitalization):
Cryptographic systems are extremely difficult to build. Never-
theless, for some reason many non-experts insist on designing
new encryption schemes that seem to them to be more se-
cure than any other scheme on earth. The unfortunate truth,
however, is that such schemes are usually trivial to break.
We would expect students to describe the methodology they used to
derive the solution.
1.2 Provide a formal definition of the Gen, Enc, and Dec algorithms for the
mono-alphabetic substitution cipher.
Solution: For this exercise, we identify numbers and letters in the
natural way. That is, a = 0, b = 1, and so on.
• Gen: Choose a random permutation π of {0, . . . , 25} and let the
key be this permutation. (A random permutation on {0, . . . , 25}
can be chosen as follows: for i = 0 to 25, set π(i) equal to a random
number from {0, . . . , 25} that has not been chosen so far.)
• Enc: Given a plaintext m = m1 , . . . , m` (where mi ∈ {0, . . . , 25})
and a key π, set ci := π(mi ) and output c1 , . . . , cn .
• Dec: Given a ciphertext c = c1 , . . . , cn and key π, set mi := π −1 (ci )
where π −1 is the inverse of π and output m1 , . . . , mn .
1.3 Provide a formal definition of the Gen, Enc, and Dec algorithms for
the Vigenère cipher. (Note: there are several plausible choices for Gen;
choose one.)
Solution: As in the previous exercise, we identify numbers and letters
in the natural way. That is, a = 0, b = 1, and so on.
• Gen: Choose a random period: this can be chosen uniformly in a
fixed set of some size, or it can be chosen according to some valid
3
, 4 Introduction to Modern Cryptography – 3rd Edition Solutions Manual
probability distribution over the integers (e.g., assign the length
5 + i with probability 2−i ). Denote the chosen period by t. For
i = 0, . . . , t − 1 choose uniform ki in {0, . . . , 25}. Output the key
k = k0 , . . . , kt−1 .
• Enc: Given a plaintext p = p0 , . . . , pn and a key k = k0 , . . . , kt−1 ,
set ci := [pi + k[i mod t] mod 26]. Output c0 , . . . , cn .
• Dec: Given a ciphertext c = c0 , . . . , cn and a key k = k0 , . . . , kt−1 ,
set pi := [ci − k[i mod t] mod 26]. Output p0 , . . . , pn .
1.4 Say you are given a ciphertext that corresponds to English-language text
that was encrypted using either the shift cipher or the Vigenère cipher
with period greater than 1. How could you tell which was the case?
Solution: The index of coincidence method described in this chapter
can be used to find the key length (i.e., period) of the Vigenère cipher.
Since the shift cipher corresponds to the Vigenère cipher with a period
of 1, the index of coincidence method can be used to determine which
scheme was used.
1.5 Implement the attacks described in this chapter for the shift cipher and
the Vigenére cipher.
Implementation exercise – no solution given.
1.6 The shift and Vigenère ciphers can also be defined on the 256-character
alphabet consisting of all possible bytes (8-bit strings), and using XOR
instead of modular addition.
(a) Provide a formal definition of both schemes in this case.
(b) Discuss how the attacks we have shown in this chapter can be
modified to break each of these modified schemes.
Solution: We describe the solution for the Vigenère cipher, which is
the more complex case.
(a) Key generation chooses a period t (say, uniform in {1, . . . , tmax } for
some specified tmax ) and then, for i = 0, . . . , t − 1, chooses uniform
ki ∈ {0, 1}8 . The encryption of a plaintext m = m1 , . . . , m` is
c = c1 , . . . , c` , where ci := mi ⊕ k[i mod t] . Decryption is done in
the natural way.
(b) The attacks described in the text can be adapted to apply here
as well. One must be careful to let pi be the frequency of the
ith byte—so, e.g., non-ASCII characters have frequency 0; the fre-
quency of ‘A’ is different from the frequency of ‘a’; and frequencies
of the space character and punctuation are also taken into account.
