Cryptography, An Introduction : Errata to First Edition

1. Page 3: Line -5.
   Replace "positive" with "non-negative".
2. Page 5: Line -2.
   Insert "either" between "obtained by" and add "or by use of the inverse operation" after "group operation".
3. Page 5: Line -1.
   Replace "addition every" with "addition, every positive".
4. Page 6: Line 3.
   Add "Every negative integer can be obtained from a positive integer by use of the additive inverse.". Replace "In this case we say", by "Hence, we have".
5. Page 8: Line -4.
   Replace $\F_p^*$ with $\Z$.
6. Page 9: After Line 19.
   Insert "To ease notation we will often write $\F_p[X]/f(X)$ for the latter ring."
7. Page 17: Line 8.
   Should read

     x = a (mod M)    and     x = b (mod N).
   

8. Page 18: Line -1.
   Replace 2 by 4.
9. Page 19: Line -10.
   "Shank's" should be "Shanks'".
10. Page 21: Line 9.
    Denominator in Jacobi symbol should be $n$ and not $N$.
11. Page 27: Line -7.
    Replace $g^q$ with $g^{(p-1)/q}$.
12. Page 37: Line 5.
    "is a usually" should be "is usually".
13. Page 39: Line 15.
    The term $a X Z^2$ should be $a X Z^4$.
14. Page 40: Line 3.
    The term $a_2 X^2 Z^4$ should be $a_2 X^2 Z^2$.
15. Page 40: Line 15.
    Add the line "where $d_6 = \sqrt[4]{a_6}$."
16. Page 56: Line 19.
    Replace "the most famous 19th century" with "the most famous cipher, during the 19th century,".
17. Page 56:Line 20.
    Add between "cipher" and "was a" the text ", invented in 1553 by Giovan Batista Belaso,".
18. Page 69: Line 10.
    "decided" should be "decide".
19. Page 70: Lines -17,...,-10.
    Replace $M$ by $P$.
20. Page 72: Line 17.
    To aid clarity Replace "This means for all m and all c" by "This means for each m that for all c".
21. Page 77: Line -11 and -10.
    Should read

       H(K) \approx 1.5, \\
       H(C) \approx 1.9944.
    

    Replace "1.5 bits" on line -9 with "two bits".
    This is repeated on Page 80 and produces the follow through errors
    
    1. Page 80: Line 17

         H(K|C) \approx 1.9527+1.5 - 1.9944 \approx 1.4583
       

    2. Page 80: Line 20

       After all there are only 1.5 bits of uncertainty about the
       key to start with, one ciphertext leaves us with 1.4583 bits
       of uncertainty. Hence, 1.5-1.4583 = 0.042 bits of information
       about the key are revealed by a single ciphertext.
       

22. Page 79: Line 14.
    Remove the minus sign.
23. Page 82: Line 6.
    Should be "On** up** a t**e t**re **s a **rl **ll** **ow **it*."
24. Page 89: Line -2.
    Replace "Kerchhoff's" with "Kerckhoffs'". Also needed on Page 120 Line -5 and in the index on Page 431.
25. Page 103: Line 15.
    Replace "of degree three" with "of degree less than four".
26. Page 104: Main matrix equation.
    Need to add the column vector $(1,1,0,0,0,1,1,0)$. Doh!!! How stupid can I be.
27. Page 105: Line 6.
    "degree 3" should be "degree 3 (or less)".
28. Page 115: Figure 5.19.
    This picture is wrong. The corrected picture can be found in our Advanced Crypto course web site, the bit on stream ciphers.
29. Page 117: Main matrix equation.
    Second row of right hand column vector should be $s_{L+1}$.
30. Page 121: Exercise 5.3.1.
    The blue $k$ in the first displayed equation should be in red.
31. Page 156: Line -2.
    Replace "of order divisible by" with "of prime order".
32. Page 156: Line -1.
    Replace with

       g = r^{(p-1)/q} \ne 1 \mbox{ for some } r \in \F_p^*.
    

33. Page 164: Add Exercise 7.3.8.
    Show that the RSA algorithm also works when the message is taken from the set $\{0, \ldots, N-1 \}$ as opposed to the set $(\Z/N\Z)^*$ as used in the text.
34. Page 166: Line 14.
    Replace $177$ with $355$.
35. Page 166: Line 15.
    Insert "odd" before "numbers of size $2^{512}$".
36. Page 169: Replace the given Miller-Rabin algorithm with

    Write n-1 = 2^s m , with m odd;
    for (j=0; j < k; j++)
      { Pick a from [2,..,n-2]
        b=a^m mod n;
        if (b!=1 && b!=(n-1))
          { i=1;
            while (i < s && b!=(n-1))
              { b=b^2 mod n;
                if (b==1) { Output (Composite,a); }
                i++;
              }
            if (b!=(n-1)) { Output (Composite,a); }
          }
      }
    Output "Probable Prime";
    

37. Page 172: Line 5.
    Replace $p=1$ with $p=2$.
38. Page 177: Line 8.
    Replace $B=$ with $F=$.
39. Page 192: Lines 11 and 26.
    Replace $337$ by $397$.
40. Page 198: Lines 10,14,15,16.
    Replace $\F_{607}$ by $\F_{607}^*$. Same on Page 200 Line 19.
41. Page 216: Lemma 10.1
    This is actually false, there is a counter example, pounted out by Ron Rivest and Christopher Peikert, and to be found in HAC p 320.

    Let $g$ denote a collision resistant hash function with outputs of bit length $n$. Define a new hash function $h(x)$ with outputs of bit length $n+1$ to be $0 \Vert x$ if $|x|=n$ and to be $1 \Vert g(x)$ otherwise. This is collision resistant but is not one-way, since we can invert half of the range of $h$.

    Hence, having an oracle which breaks one-wayness may not help in finding collisions.

    However, the Lemma is true if one assumes that the oracle which breaks the one-way property can find a preimage for almost every element in the range of $h$.

42. Page 237: Line 12.
    Replace "multiplication" with "multiplications".
43. Page 240: Lines 10-15.
    Since the idea in the sliding window method is to use exponents that are at least w apart, the decomposition here is wrong and should have been

      215 = 27+5·24+7. 
    

    Some of the following execution steps are therefore also wrong. The first four steps should have been

          y=1 (unchanged), 
          y=y·x=x^1, 
          y=y^8=x^8, 
          y=y·x^5=x^{13}, 
    

    from where it continues as in the text.
44. Page 243: Line -13.
    Remove "obtain".
45. Page 246: Lines -9, -10 and -16
    Replace x[i] with r[i].
46. Page 247: Line 18.
    To explain the N that suddenly appears here, replace "We then" by "To do arithmetic modulo N we".
47. Page 249: Line -11.
    In the eduction program replace the command

      z+=u*N*b;
    

    by the two commands

      z+=u*N; z*=b;
    

48. Page 252: Line -6.
    "if we choose" should more precisely be "if we may choose", since for some values of n (such as n=73 or 103) this is not possible.
49. Page 253: Line -18.
    First line of multiplication program

      z=0; i=0;
    

    should be expanded to

      z=0; i=0; ans=0;
    

50. Page 283: Line 6.
    Insert "only" before "after".
51. Page 283: Proof of Lemma 13.2.
    This depends on your attack model for binding. If the sender is in control of the selection of both the originally committed value and the replacement value. then you actually need collision-resistance, and not just second-preimage resistance, in order to guarantee computational binding.
52. Page 284: Line 8.
    Insert "The scheme based given by $B_a(x)$ is called Pedersen's scheme". Also insert index entry to Pedersen's scheme for this page.
53. Page 284: Lemma 13.3.
    General comment. For $B(x)$ to be concealing we need the space of all possible committed values $x$ to be computationally impossible to search. Hence, we are implicitly assuming that $x$ is chosen uniformly at random from the set of integers modulo $q$.
54. Page 298: Line 4.
    Should be $p_0 = a_0$ and $q_0=1$.
55. Page 298: Line -12.
    "small encryption exponent d" should be "small decryption exponent d".
56. Page 303: Line -7.
    "via a unimodular transformation" should be "via a unimodular integer transformation".
57. Page 305: Line -15.
    "be a positive" should be "be positive".
58. Page 307: Line 2.
    If we set $b_1 = A u$ with $u=(u_1,...,u_6)$ then $h(x)$ on line 2 should be replaced with the $b_1^{(i)}$'s equal to $u_i$.
59. Page 308: Line -14.
    Should be $m_1 = f(m_2) \pmod{N}$.
60. Page 310: Line -5.
    "half of the most significant bits" should more precisely be expressed as "the upper (most significant) half of the bits".
61. Page 310: Line -2.
    "0 \lt i \le e" should be "0 \lt i \lt e".
62. Page 311. Line 4.
    Replace sentance with "Now when $e=3$ it is clear that $k$ must be even, and so we must have $k=2$ and so..."
63. Page 311. Line -6.
    < Replace "an even" with "a".
64. Page 312. Line 1.
    Remove "even".
65. Page 317: Line 2.
    "encrypted under the private key x corresponding to y" should be "encrypted under y".
66. Page 317: Line -5.
    As in the other occurrences, the index in c_b should be red.
67. Page 319: Line -3.
    "given" should be "given the ciphertext C of".
68. Page 324: Line -9.
    In the set formula, a should be x.
69. Page 336: Line 5.
    In the formula, \ge should be strict \gt, and for clarity the outer index i should be changed to j so that the formula becomes

        w_j \gt sum_{i=1}^{j-1} w_i. 
    

70. Page 338: formula in the middle.
    In the formula for the norm of y with square roots and two equality signs, the last "=" should be \lt.
71. Page 361: Line 1.
    Replace G with V.
72. Page 386: Line -1.
    Swap $id_A$ and $id_B$.
73. Page 393. Line 3.
    Add "when $m=n$ we often write $M_n$ instead of $M_{n \times n}$.
74. Page 401. Line -1, -2.
    Replace with "A ring is an additive finite abelian group with an extra operation, usually denoted by multiplication, such that the multiplication operation is associative and has an identity element".