Cryptography Theory and Practice --- Errata List

last modified October 1, 1996

I will be working on this errata 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.

Thanks to everyone who has pointed out errors to me, including Christer Berg, Jean-Francois Blanchette, Marc Branchaud, Gilles Brassard, Amanda Chou, Alfredo De Santis, Bernard Desruisseaux, Joan Feigenbaum, Hans Flack, K. Gopalakrishnan, Jerrold Grossman, Ketil Heggtveit, Tor Helleseth, Be Hubbard, Raj Iyer, Mike Just, Jeong Soo Kim, Andy Klapper, Robert Lewis, Sharon Lim, Helger Lipmaa, Spyros Magliveras, Kevin McCurley, Brent Modzelewski, Rolf Oppliger, Pierre Ouellet, Kunsoo Park, Riccardo Pucella, Rino Ranheim, Daniel Sandberg, Willy-Bernhard Strothmann, Tran van Trung, Serge Vaudenay, Dan Velleman, Kenny Wolf and Seth Zirin.

Page 4, Line 5: Change "property 4" to "property 2".

Page 10, Line -8: Change "multilicative" to "multiplicative".
Page 16, Line 4: Change "correpsonding" to "corresponding".
Page 17, Line -1: Change "Z_m" to "Z_{26}".
Page 19, Line -2: Change "j = pi(i)" to "i = pi(j)".
Page 25, line -9: Change "dificult" to "difficult".
Page 26, line 4 of text: Change "0.023" to "0.028".
Page 27, Table 1.2: "D" occurs 7 times and "P" occurs 2 times.
Page 27, line 4 of text: Change "6" to "7".
Page 33, line 1: The ciphertext string CHR actually occurs in five places in the ciphertext.
Pages 34-35: Change all occurrences of K_1, K_2, K_3, K_4 and K_5 to k_1, k_2, k_3, k_4, and k_5, respectively..
Page 35, line 1: Change "0.65" to "0.065".
Page 35, line 2: Change "0.31" to "0.031".
Page 37, first paragraph: it is the matrix X that should be invertible (rather than Y).
Page 35, line 3: Change "0.45" to "0.045".
Page 39, line 2: Change the last bit in the plaintext string from "1" to "0".
Page 43, line 19: Change "the the" to "the".
Page 51, line 2: Change "widepread" to "widespread".
Page 56, line -10: Delete "if".
Page 61, line 12: Change "4.76" to "4.70".
Page 61, line -5: This should read as "H(P^2) / 2 is approximately 3.90".
Page 62, line 4: Change the first occurrence of "is" to "it".
Page 64, line -13: Delete the period at the beginning of the line.
Page 64, line -9: Change "E_K" to "e_K".
Page 81, line -3: Change "L_16 R_16" to "R_16 L_16".
Page 83, line 4: Change "10^6 keys" to "10^6 chips".
Page 85, Fig 3.5: In the second diagram (decryption), the arrows should originate from y_1 and y_2 instead of x_1 and x_2.
Page 86, beginning of line 23: Change "Ocsar" to "Oscar".
Page 86, end of line 23: Change "Oscar" to "Bob".
Page 87, line 14: Delete "provides".
Page 89, line 7: Delete the blank at the beginning of the line.
Page 92, line 6: There is no J^*.
Page 100, line -2: Change "a defined to be" to "defined to be a".
Page 101, step 1 in Figure 3.13: Change "40080000" to "04000000".
Page 101, line -6: Change "(1/16) / (1/3) = 3/16" to "(1/16) / ( (1/16) + (15/16)(1/3) ) = 1/6".
Page 110, line -17: Change "plaintext" to "ciphertext".
Page 111, line 11: Change "E01FF01FFF10FF10" to "E01FE01FF10EF10E".
Page 112, Input for Figure 3.16: Change "L_3R_3" to "L_4R_4" and change "L_3^*R_3^*" to "L_4^*R_4^*".
Page 114, line 16: Change "could by made" to "could be made".
Page 116, line 9: Change "the the" to "the".
Page 119, Fig 4.1: Step 17 of the "if" statement should not be indented, since it is performed after the "while" loop terminates.
Page 126, step 3 of Figure 4.3: Change "0 < b" to "1 < b".
Page 127, line -5: Change "multiplcations" to "multiplications".
Page 129, line 4: Delete the space before the comma.
Page 130, line -6: Change the first occurrence of "+/- 4" to "+/- 5".
Page 130, line -3: Change ":" to ".".
Page 131, line -2: Change "prime" to "odd prime".
Page 132: Lines -16 and -15 should read as follows: "If this equation holds, then n is called an Euler pseudo-prime to the base a. For example, 91 is an Euler pseudo-prime to the base 10 ...".
Page 132: Lines -12 and -11 should read as follows: "However, it can be shown that, for any odd composite n, n is an Euler pseudo-prime to the base a for at most half the integers a such that 1 <= a <= n-1 (see the exercises)".
Page 136, lines -14 to -12: Reword this sentence as follows: "An elementary analysis shows that its complexity is O((log n)^3), as in the case of the Solovay-Strassen test."
Page 136, line -2: Delete "in step 2".
Page 139, line -15: Replace "epsilon" by "1 - epsilon".
Page 139, line -13: Insert "and n" after "b".
Page 146, line -2 of Figure 4.13: The computation is to be done modulo n.
Page 147, line 11: Replace "omega (x + B/2)" by "omega (x + B/2) - B/2".
Page 147, line 12: Replace "- omega (x + B/2)" by "- omega (x + B/2) - B/2".
Page 147, line -14: Replace "b" by "B".
Page 151, Figure 4.15, step 4: Insert "if".
Page 155, line -54: Change "Holdredge" to "Holdridge".
Page 159, line -14: Change "crpyotsystem" to "cryptosystem".
Page 159, line -13: Change "decryption" to "encryption".
Page 159, line -4: Change "945" to "43".
Page 160: Exercise 4.11. The input should also include the encryption exponent, b. Change "n" to "n-1" in line 3 of this exercise. Also, change "failure probability" to "success probability". Finally, "A" should be in bold type (three times).
Page 160: Exercise 4.13 should read as follows: "For n = 837, 851 and 1189, find the number of bases b such that n is an Euler pseudoprime to the base b".
Page 162, line -9: Change "have at at least" to "have at least".
Page 163, Fig. 5.2: Change "intractible" to "intractable".
Page 164, line -13: Change "was plaintext" to "was the plaintext".
Page 164, line -7: Change "exhasutive" to "exhaustive".
Page 177, line 15: Change "x_{i+1} = L_2(beta)" to "x_0 = L_1(beta)".
Page 178, line -14: Change "muliplication" to "multiplication".
Page 184, line 9: Change "2^n" to "2^n - 1".
Page 187, line 8: There is an extra right parenthesis which should be deleted.
Page 187, line -10: Delete "indexcyclic group".
Page 187, line -1: Insert "about" after "size".
Page 188, line 3: Change "look" to "look at".
Page 188, line 11: Change the final "," to a ".".
Page 192, Figure 5.12, step 7: change this step to "if T = 0". (Note: this change is required bacause the value of T is changed during the algorithm. It would be all right if the value of T used were the initial value.)
Page 196, line -6: Change "gives rose" to "gives rise".
Page 196, line -2: Change "presently" to "present".
Page 201, Exercise 5.9: Change "Z_34* x Z_34*" to "Z_31* x Z_31*".
Page 203, line 4: Change "such a" to "such as".
Page 205, line -11: Replace this line by the following: "x = e_{Bob}(x) and y = sig_{Alice}(z)".
Page 205, line -6: Replace this line by the following: "y' = sig_{Oscar}(z)".
Page 205, line -5: Insert "z=" before "e_{Bob}(x)".
Page 206, first line of Fig 6.2: Change "intractible" to "intractable".
Page 206, last line of Fig 6.2: Change "ver" to "ver_K".
Page 208, lines 18-22: It is better not to substitute for gamma in the exponent, since gamma is defined modulo p and exponents are computed modulo p-1. Change the proof as follows:

(beta ^ gamma) (gamma ^ delta) \equiv (beta ^ gamma) (alpha ^i beta ^j) ^ (- gamma j ^(-1))

\equiv (beta ^ gamma) (alpha ^ ( - i gamma j ^(-1))) (beta ^ (-gamma))

\equiv alpha ^ (- i gamma j ^(-1))

\equiv alpha ^ x

Page 209, line -10: Change "gamma" to "delta" and change "delta^{-1}" to "gamma^{-1}".
Page 210: Change "delta_2 - delta_1" to "delta_1 - delta2" (all 6 occurences).
Page 210, line 19: Change "p" to "p-1".
Page 211, line 6: Change "encypted" to "encrypted".
Page 211, line 14: Change "forseeable" to "foreseeable".
Page 211, line 18: Change "160" to "512".
Page 211, line -16 and line -13: Change "alpha" to "a".
Page 212, line 3 and line -5 of Digital Signature Standard: Change "Z_p*" to "Z_q*". (Remark: This is necessary, since otherwise two messages that are congruent modulo q will have the same signature. In practice, the DSS is used in conjunction with the secure hash standard (see Chapter 7). The hash function, produces a 160-bit message digest which is then signed.)
Page 213, Example 6.3. Change "1234" to "22". (Remark: 22 = 1234 mod 101. This change takes care of the problem mentioned in the previous point.)
Page 214, line -5. Change "the each" to "each".
Page 216, line -3. Change "n" to "2n".
Page 217, line 2 of Figure 6.5. Change "n" to "2n".
Page 217, line -15. Change "n" to "2n".
Page 218, step 1 of Figure 6.6. Change "X" to "x".
Page 220, line -3. Change "resonse" to "response".
Page 223, line -6. Change "that" to "at".
Page 223, lines -13,-12,-11,-8. Change "y^{e_1 f_1}" to "y^{e_1 a^{-1} f_1}".
Page 225, line -18: Change "fail-safe" to "fail-stop".
Page 228, line -3: Change "ver" to "ver_K".
Page 231, Exercise 6.6. Change "5001" to "52" (since 52 = 5001 mod 101).
Page 234, Definition 7.1. Reword this as follows: Let x be a message. A hash function h is weakly collision-free for x if it is computationally infeasible to find a message x' different from x such that h(x) = h(x').
Page 234, line -8. Reword this line as follows: Observe that a hash function h is strongly collision-free if and only if it is computationally infeasible to find a message x such that h is not weakly collision-free for x.
Page 238, lines 3,5,7,8,9,11: Change "n" to "2n".
Page 240, line -10: Interchange "alpha" and "beta".
Page 240, line -1: Change "x_1" to "x_2".
Page 241, line 2: Change "x_3" to "x_4".
Page 244, line -1: Change "continuing" to "continue".
Page 247, Section heading for Section 7.6: Change "From" to "from".
Page 248, step 1 of Figure 7.6 should be "d = (447 - |x|) mod 512".
Page 250, line -6: Change "two" to "three".
Page 253, step 16 of Figure 7.10: Insert a left parenthesis before the second occurrence of "B".
Page 256, line 6: The circle should be above the second "a" in "Damgard" rather than above the first one.
Page 260, line 9: Insert "to" before "design".
Page 268, Section 8.3: Change "Kerboros" to "Kerberos" throughout this section.
Page 269, step 6 of Figure 8.4: Change "e_K" to "d_K".
Page 270, line -16: Change "transmiited" to "transmitted".
Page 280, line 2: Change "mod" to "mod n".
Page 284, line 6 of Figure 9.1: Change "2" to "3".
Page 286, line 12 of Figure 9.2: Change "I" to "ID(Alice)".
Page 289, line 7: Change "2^t / epsilon" to "2^t epsilon".
Page 289, line 8: Change "mod p" to "mod q".
Page 290, line 9: Delete the second occurrence of "then".
Page 290, line -8: Change "1444" to "1344".
Page 291, line -3 before Section 9.3: Change "1444+512=1956" to "1344+512=1856".
Page 291, line -9: Change "14573" to "14574".
Page 292, line 10 of Figure 9.4: Change "I" to "ID(Alice)".
Page 294, line 11: Change "a_1 - b_1" to "a_2 - b_2".
Page 297, line 8 of Figure 9.6: Change "u" to "v", and change the style of the subscript "TA" to roman.
Page 297, line 10 of Figure 9.6: Change "I" to "ID(Alice)".
Page 298, line 6 of Figure 9.7: Change the style of the subscript "TA" to roman.
Page 302, lines -5 and -7: Change "Fiege" to "Feige".
Page 304, Exercises 9.6 and 9.7: Change "Quisquater" to "Guillou-Quisquater".
Page 308, line 8: Change "K_0 = (1,1)" to "K_0 = (1,0)".
Page 313, Equation 10.4: Change "p(K)" to "p_{\cal K}(K)".
Page 317, line -5: Change ".." to ".".
Page 318, lines -5 and -6: Change "R_2" to "R_1" (three occurrences).
Page 321, line -2: Insert "|{\cal S}| = k" before "|{\cal A}| = n".
Page 328, Figure 11.1: Change "w >= p+1" to "p >= w+1".
Page 331, line -6: Change "(x_1-x_3)(x_1-x_5)" to "(x_3-x_1)(x_5-x_1)". (This does not affect the answer, but it makes the computation consistent with the formula presented earlier.)
Page 333, line -13: Delete "scheme".
Page 334, line -2: Insert "have" after "can".
Page 348, line -2: Change "(0,1)" to "(1,1)".
Page 348, line -1: Change "(1,1)" to "(2,1)".
Page 349, line 1: Change "(1,2)" to "(2,1)".
Page 350, line 5: Insert "the" before "other".
Page 358, line -8: Change the second occurrence of "D_1" to "D_2".
Page 360, Exercise 11.3: Change "1/2" to "1/3".
Page 368, line -8: Change "12.3" to "12.1".
Page 369, line -12: Change "A_i" to "A".
Page 370, line 15: Q_i is defined but never used.
Page 370, line -8: Change "z_{l-1}" to "z_{i-1}".
Page 371, lines 19 and 20: Change "q_{i-1}" to "q_{i}".
Page 372, line 2: Change "epsilon_A" to "E_A" (three occurrences).
Page 373, line -15: Insert a "." at the end of the sentence.
Page 374, line 4 of Figure 12.6: Change "1" to "0".
Page 376, Figure 12.7. This should be rewritten as follows:
  1. Compute s_0 = x^2 mod n and compute z_0 = s_0 mod 2
  2. Use the BBS generator to compute z_1, ... , z_{l-1} from seed s_0
  3. Compute z = B_0(z_0, ... , z_{l-1})
  4. If (x mod 2) = z then answer "x in QR(n)" else answer "x in QR-tilde(n)".
Page 376, line 4 after Figure 12.7. Change "z_0" to "z".
Page 376, line -3. Change "3" to "2".
Page 379, line 9: Change "471" to "461".
Page 379, line -5: Change "LFSR" to "PRBG" (two occurrences).
Page 380, line 12: Change "text" to "test".
Page 380, line 3 of Definition 12.3: Insert "{\cal R} is a set of {\it randomizers}" before "and.
Page 381, line -14: Change "(-1)" to "(y)".
Page 381, line -14: Change "y/n" to "y/p".
Page 381, line -12: Change "y/n" to "y/p".
Page 382, step 4 (encrypt): Change "y" to "e_K(x,r)".
Page 382, step 8 (decrypt): Insert "is" before "x".
Page 383, line 3: Change "(1/p)" to "(x/p)".
Page 383, line 14: Change "roots" to "root".
Page 385, line 2 of Figure 12.11: Change "1" to "0".
Page 386, Exercise 12.5: Change "1/(delta epsilon^2)" to "O(1/(delta epsilon^2))".
Page 388: the second property should be "soundness".
Page 390, line 11: Insert "is" after "this".
Pages 396-397, Proof of Theorem 13.2: Interchange "i_j" and "i_j'" in the proof.
Page 399, line 6 after Figure 13.9: Change "n" to "log_2 n".
Page 400, line -5: Delete the space before "computational".
Pages 403-407, Section 13.4: In this section, n and m are each used in two different ways. n denotes the the number of vertices in G, and is also used in the bit commitment scheme. m denotes the the number of edges in G, and is also used in the bit commitment scheme. The integers n and m in the bit commitment scheme should be given new names.
Page 406, line -7: Change "ji" to "ij".
Page 406, line -6: Change "ji" to "ij".
Page 407, line -10: Change "NP-complete problem" to "problem in NP".
Page 409, Table 13.1: Interchange "concealing blobs" and "binding blobs".
Page 409: Line -16 should not start a new paragraph.
Page 417, lines 4,7,10: The circle should be above the second "a" in "Damgard" rather than above the first one.
Page 418, ref. [FFS88]: The page numbers should be 77-94.
Page 419, ref. [GMW91]: Change "A. Micali" to "S. Micali".
Page 419, ref. [GM84]: Change "A. Micali" to "S. Micali".
Page 420, ref. [LO91]: Change "finite" to "prime".
Page 420: Ref. [KO87a] appears twice.

Back to the home page for the book: click here

dstinson@cacr.math.uwaterloo.ca