# Cryptography Theory and Practice, Second Edition --- Errata List

This errata list pertains to the second edition of Cryptography Theory and Practice. I will be working on this list on an ongoing basis. Please send me e-mail concerning any errors that you find in the book so I can add them to this list.

The following people have pointed out errors to me:

Nils Andersen, Antoon Bosselaers, Ajay Daptardar, Lean Fuglsang, Mark Gjøl, Klaus Hansen, Thomas Horton, Heng Swee Huay, Jim Huggins, Jun-Cheol Jeon, Patrick Kerharo, Torleiv Kløve, Lars Knudsen, Mark Michael, Michael Mossinghoff, James Muir, Anders Nielsen, Kaisa Nyberg, Phil Rose, Robert St. Pierre, Joe Sunday, Tamir Tassa, Rob Thies, John van Rees, Mike Wiacek, Rebecca Wright, and Xukai Zou.

Thanks for taking the time to do so!

Page 10, line -7 should be
11^{-1} = 19

Page 17, corollary 1.4. "11 x (7 - 8 x 3)" should be "(11 x 7 - 8 x 3)"

Page 24, line -6. The ciphertext should be "ZVRQ ...".

Page 33, Example 1.12. The indices for m=4 are 0.042, 0.039, 0.045 [not 0.046], and 0.040.

Page 35, Table 1.4. Some entries in this table are incorrect in the third decimal place. Here is a corrected version of the table:
i=1
.035 .031 .036 .037 .035 .039 .028 .028 .048
.061 .039 .032 .040 .038 .038 .045 .036 .030
.042 .043 .036 .033 .049 .043 .042 .036
i=2
.069 .044 .032 .035 .044 .034 .036 .033 .029
.031 .042 .045 .040 .045 .046 .042 .037 .032
.034 .037 .032 .034 .043 .032 .026 .047
i=3
.048 .029 .042 .043 .044 .034 .038 .035 .032
.049 .035 .031 .035 .066 .035 .038 .036 .045
.027 .035 .034 .034 .036 .035 .046 .040
i=4
.045 .032 .033 .038 .060 .034 .034 .034 .050
.033 .033 .043 .040 .033 .029 .036 .040 .044
.037 .050 .034 .034 .039 .044 .038 .035
i=5
.034 .031 .035 .044 .047 .037 .043 .038 .042
.037 .033 .032 .036 .037 .036 .045 .032 .029
.044 .072 .037 .027 .031 .048 .036 .037

Page 40, Exercise 1.16(b).
The ciphertext was actually encrypted using the permutation pi^{-1}.

Page 40, Exercise 1.18.
"z_4" in the initialization vector should be "z_3".

Page 41, Exercise 1.23.
The ciphertext should be "RUPOTENTOIFV".

Page 42, Exercise 1.26.
Replace "m=4, n=3" by "m=3, n=4".

Pages 43-44, Exercise 1.30.
The encryption and decryption rules are written incorrectly. They should be as follows:
e_K(x) = pi(x) + z mod 26
and
d_K(y) = pi^{-1}(y - z mod 26).

Page 60, line 10. Delete the superfluous left parenthesis.

Page 62, Reword the sentence in lines 8-10 as follows:
The conditional entropy H(K|C) ... is a measure of the amount uncertainty of the key remaining when the ciphertext is known.

Page 70, Exercise 2.3.
The probability of key (a,b) should be
Pr[a] / 26.

Page 71, Exercise 2.7(b).
The encryption matrix is a Latin square of order 2^n, in which the symbols are the elements of (Z_2)^n.

Page 71, Exercise 2.14.
Here, you should assume that keys are used equiprobably, and that the plaintext probability distribution is equiprobable.

Page 72, Exercise 2.18.
You should assume that keys are used equiprobably.

Page 72, Exercise 2.20.
You should assume that all the cryptosystems in this question have equiprobable keys.

Page 75, line -2. "v^r" should be "w^r".

Page 75, line 3. It would be better to use the notation
x = x_< 1 > || x_< 2 > || ... x_< n >
here and elsewhere. Then line 5 of page 75 would be written as
x_< i > = (x_(i-1)l+1, ... , x_il)
which is less confusing.

Page 87, line -9. "S_4^2" should be "S_2^4".

Page 101, third paragraph. "distrubuted.net" should be "distributed.net".

Page 105, line 6 of Example 3.5. "x^3" should be "x".

Page 107, line -3. "Rcon" should be "RCon".

Page 113, Exercise 3.1.
Note that each of the round keys in the decryption algorithm must be permuted in a suitable way.

Page 113, Exercise 3.4(b).
"comtains" should be "contains".

Page 113, Exercise 3.4(b).
The number of bits of memory required should be 2^{n+1}(m * ell + n).

Page 113, Exercise 3.4(c).
"simultaneaouly" should be "simultaneously".

Page 114, Algorithm 3.7. The input to this algorithm should be y instead of x.

Page 115, Exercise 3.12(b). Replace "2^m - 1" with "2^{m-1}" and replace "0 <= a" with "0 < a".

Page 115, Exercise 3.12(c). Replace
"For all integers a such that 0 <= a <= 2^m-1"
by
"For all integers b such that 0 <= b <= 2^n-1".

Page 115, Exercise 3.13(1). Replace "2^m - 1" with "2^{m-1}" and replace "0 <= b" with "0 < b".

Page 116, Exercise 3.14.
In part (d), Algorithm 3.3 should be Algorithm 3.2.

Page 119, Problem 4.1. Replace "f(x)=y" with "h(x)=y".

Page 121, line 6. Replace "the the" by "the".

Page 122, line 3. Replace "let let" by "let".

Page 122, line 4. Replace "Proposition 4.1" by "Theorem 4.1".

Page 122, Algorithm 4.3. Replace "X \ {x}" by "X".

Page 123, line -9. Replace "E_{i-i}" with "E_{i-1}"

Page 124, line 3. This is actually an equality, not an approximation.

Page 125, Algorithm 4.4. Because Oracle2ndPreimage is assumed to be a Las Vegas algorithm, it is not necessary to check that x' is not = x and h(x') = h(x). This reduces the number of hash queries by 2.

Page 126, line 3. Replace "(1,q) algorithm" by"(1,q)-algorithm".

Page 126, proof of Theorem 4.5. Additional comment: Note that the hypotheses imply that h is surjective, as stated on the bottom of page 125.

Page 129, line 6 of Algorithm 4.6 should be "d gets k(t-1) - n"

Page 130, line 18. Replace "which is a collision for h" by "which is a collision for compress".

Page 134. Replace "K_i" by "K_t".

Page 134. Replace "f_i" by "f_t" (this occurs twice).

Page 136, lines 3-5. Replace the sentences
For example, collisions in the compression functions of MD4 and MD5 were discovered. (No collisions in the "complete" hash functions are presently known.)
with the following:
For example, collisions in the "complete" hash function MD4 were discovered, as well as collisions in the compression function of MD5.

Page 136, line -5. Replace "," with "||".

Page 141, line 6. Replace "n >= 2" with "n >= 3".

Page 141, line 7. Insert the following sentence:
"For 1 <= i <= q and 3 <= l <= n, define x_l^i = x_l."

Page 141, line 12. Insert the following sentences before "Note":
In the computation of the MAC of each x^i, values y^i_0, ... , y^i_n are computed, and y^i_n is the resulting MAC. Now suppose that x^i and x^j have identical MACs.

Page 141, line 15. Add "that is not all 0's" to the end of the first sentence.

Page 141, line -2. Replace "(0,epsilon), (1,epsilon)" by "(epsilon,0), (epsilon,1)".

Page 142, line 1. Replace "q = 0, 1" by "q >= 0".

Page 144, lines 5 and 6. Delete the superfluous left parentheses after "[".

Page 144. Equation (4.2) is incorrect; it should read as follows:
Pd1 = Max _x { Min_y { Max_{x',y'} { Payoff(x',y';x,y) } } },
where (x,y) is in V and x' is not equal to x.

Page 146, line 1. Change the subscript "a,b" to "(a,b)".

Page 149, line 4.. Replace "datails" by "details".

Page 149, lines 14 and 15. Replace "Bossalaers" by "Bosselaers".

Page 149, line 15. Add the following: and by Dobbertin (see CryptoBytes, volume 2, number 2, Summer 1996, pages 1-6).

Page 149, line -15. There should be a space after "secure".

Page 150, Exercise 4.1(c). The term "2N" should be "2S".

Page 151, Exercise 4.4.
In part (b), Algorithm 4.1 should be Algorithm 4.2.

Page 151, Exercise 4.5(a).
You should assume that m > 1.

Page 152, Exercise 4.7. Replace "in the proof" by "after the proof".

Page 152, second line in Exercise 4.8. "H" should be "h".

Page 152, Exercise 4.10. In the second last line of Algorithm 4.9, "g_{k+1}" should be replaced by "g_k".

Page 153, line 2 of Exercise 4.12. Replace "n >=" by "n >= 2".

Page 153, line 2 of Exercise 4.13. Replace "n >=" by "n >= 2".

Page 153, Exercise 4.13(b). You should assume that m > 2 and y is different from x. Also, the forgery to be outputted should be computed as 4x' modulo 2^m.

Page 153, line 9. Change "Section 3.7" to "Section 4.4.2".

Page 154, line 5 of Exercise 4.17. Replace "y_1" by "y_i".

Page 160, Algorithm 5.2: Insert "r gets b_0" immediately before the "return" statement.

Page 161, Algorithm 5.3: Replace "if r not equal to 1" by "if b_0 not equal to 1". Also, in the second last line, replace "n" by "a".

Page 166, Theorem 5.8. Replace "p is prime" by "p > 2 is prime".

Page 168, step 1 of Algorithm 5.4. Note that p and q should be distinct.

page 170, line 3. Insert "provided that the inverse exists" at the end of this line.

Page 172, line 11. Replace "one one" by "one".

Page 182, line 1. Replace "z y^{-1}" by "x y^{-1}".

Page 183, line -9. Insert "are" before "expected".

Page 189, line 3 of Example 5.12. Replace "64, 65" by "60, 61".

Page 193, line 16. Replace "2^{2^11} - 1" by "2^{2^11} + 1".

Page 193, line 25. Replace "2^{2^9} - 1" by "2^{2^9} + 1".

Page 200, lines -10 and -11 (Therefore we have that ...). These two lines can be omitted, as they are not used in the proof.

Page 201, line -3. This should read "3 = 3 x 1".

Page 202, lines -6 and -9. Replace "n/b" by "b/n".

Page 203, Wiener's Algorithm.
A corrected version of the algorithm (in postscript) is here

Page 203, line -1. Replace "60523347" by "160523347".

Page 205, line 19. Replace "C" by "y".

Page 206, line -2. Replace "if and only if" by "if".

Page 207, line -17. Replace "z+r" by "x+r".

Page 212, line 3 following Problem 5.3. Insert "be" after "to".

Page 219, Exercise 5.2.
In parts (b) and (c), you should prove that m is O(log a) and O(log b) respectively. (The exercises are not, strictly speaking, incorrect, but they are not as I intended them to be.)

Page 220, Exercise 5.13.
In line 3 of this exercise, replade "y^a" by "y^d". In parts (b) and (c), a value of d needs to be specified. You should use the value d = 1234577.

Page 221 Exercise 5.19.
You should assume that epsilon (n-1) is the number of non-zero ciphertexts that A can successfully decrypt.

Page 224 Exercise 5.23(c).
You should replace the "floor" symbols by "ceiling" symbols.

Page 229, line 3: "anaylzing" should be "analyzing".

Page 246, lines -18 and -19. Replace "any non-zero field element" by "any field element other than 0 or 1".

Page 248, line -2. Replace " R " by " R' ".

page 259, line -9. "2 ell/3 in the second case" should be "ell/3 in the second case"

Page 260, item 5. We have defined ellipic curves over F_p only for p a prime > 3. Elliptic curves can be defined over any finite field, though a different equation is required if the field has characteristic 2 or 3.

Page 266, line -15. Replace "public key" by "private key".

Page 269, Exercise 6.9.
Exercise 5.6 should be Exercise 5.12.

Page 271, Exercise 6.12.
"x^x" should be "x^2" (this happens twice).

Page 275, Definition 7.1. "ver" should be "ver_K", and "sig" should be "sig_K" (this happens twice).

Page 276, line -2. Replace "on x" by "on z".

Page 279, first line of Section 7.2.1. Delete the first occurrence of "with".

Page 284, line -10. Add "and gcd(gamma, p-1) = 1" to the end of this line. Comment: if this gcd > 1, then the desired inverse does not exist.

Page 287, Cryptosystem 7.3. Comment: all exponentiations are to be performed modulo p (i.e., reduced mod p).

Page 291, Cryptosystem 7.5. We have defined ellipic curves over F_p only for p a prime > 3. Elliptic curves can be defined over any finite field, though a different equation is required if the field has characteristic 2 or 3.

Page 298, line 16. Comment: We will be using q_h to denote the exact number of oracle queries. So it would be better to replace "is allowed to make" with "makes".

Page 301, Cryptosystem 7.8. In line 2 of the description, replace Z_p by Z_p^*. In step 1 of the verification, replace Z_q^* by Z_q.

Page 300, Theorem 7.2. Insert "after making q_h queries to the random oracle," before "using".

Page 301, line -1. The equality should be a congruence.

Page 302, proof of Theorem 7.3. Comment: We are assuming that Alice actually sends a response d which is in the group G. If Alice sends no response, then Bob will reject. Page 303, Algorithm 7.3. In step 1 and step 5, replace Z_q^* by Z_q.

Page 307, Lemma 7.6. Torleiv Kløve made the following observation:
The proof could be much shorter. Since ver_K(x,y) only involves gamma_1, gamma_2, x, and y and these values are the same for ver_K'(x,y), the lemma follows immediately without any computations.

Page 311-312, Exercise 7.3.
The k_i's should be defined modulo (p-1). Also, in part (b), sig(x_i) should be denoted as sig(x_i,k_i) and sig(x_{i+1}) should be denoted as sig(x_{i+1},k_{i+1}).

Page 312, Exercise 7.7.
You should take SHA-1(x) = 52 instead of x=52.

Page 313, Exercise 7.11(c).
"Exlpain" should be "Explain".

Page 314, Exercise 7.15.
Bob's challenges are \$c\$ and \$C\$, and Alice's responses are \$d\$ and \$D\$.

Page 321, references [61] and [62]. Replace "Bossalaers" by "Bosselaers". Also, the publication dates of these two references should be interchanged: [61] was published in 1992 and [62] was published in 1994.