Cryptography Made Simple: Errata

1. Page 5: Line 5.
   Missing 2 in the denominaotor of the first term.
2. Page 10: Figure 1.1.
   The number by the line connecting F_{p^2} and F_{p^4} should be 2 not 4.
3. Page 15: Algorithm 1.2.
   The penultimate line should assign t' and s' to x and y, and not t and s.
4. Page 24: Line 5.
   Should be \frac{n \cdot (n-1)}{2 \cdot m} \le \frac{n^2}{2 \cdot m}
5. Page 41: Lines 20 and 21.
   Replace `p-1 = 135 978 -1 =' with `p-1 = 135 978 =', and `q-1 = 115 978 -1 =' with `q-1 = 115 978 ='.
6. Page 76: Line -12.
   Should be a_2 \cdot X^2 not a_2 \cdot X in the equation.
7. Page 166. Lemma 9.2.
   This should clearly be stated as `if and only if'.
8. Page 205: Line -1.
   g:M->{0,1} should be g:P->{0,1}.
9. Page 210: Theorem 11.8.
   The algortihm B should be against m-IND-CCA. With the number of LR-queries of B equal to the number of RoR queries of A.
10. Page 211: Theorem 11.9.
    The algortihm A should be against m-IND-CCA. With the number of RoR-queries of B equal to the number of LR queries of A.
11. Page 218: Line 7.
    Spelling mistake. Should be UnForgeable.
12. Page 245: Theorem 13.1.
    2⁶⁴ should be 2⁵⁶ in both cases; but note the use of the word "about".
13. Page 226: Number of small typos on this page.
    A corrected page is here.
14. Page 232: Figure 12.9.
    States s_{12} and s_{14} are swapped around.
15. Page 234: Line -1.
    "described" is spelt wrong.
16. Page 238: Lines 6,7, 8 and 12
    Mistyping means the equations make Trivium linear! The correct equations are. a_i = c_{i-111} + c_{i-110} \cdot c_{i-109} + c_{i-66} + a_{i-69}
    b_i = a_{i-93} + a_{i-92} \cdot a_{i-91} + a_{i-66} + b_{i-78}
    c_i = b_{i-84} + b_{i-83} \cdot b_{i-82} + b_{i-69} + c_{i-87}
    r_i = c_{i-111} + a_{i-93} + b_{i-84} + b_{i-69} + c_{i-66} + a_{i-66}
    
17. Page 257: The estimation of winning the ECB game for a PRP is correct, but the proof is wrong. A corrected page is here.
18. Page 259: The proof of CBC mode has a number of bugs. The corrected pages are here.
19. Page 264: Line -9.
    Replace "a new nonce" with "another nonce".
20. Page 265: Theorem 13.11.
    The theorem is stated for the Random-IV variant, which should go in the theorem statement. The sentence afterwards should say that the above advantage statement also applies in the nonce-based setting assuming the restriction of the nonce (on the previous page) is respected.
21. Page 271: Line 11 of first main paragraph.
    Replace O(2^t) with \Omega(2^t).
22. Page 277: Line 15.
    Padding method four could also be used here.
23. Page 281: Algorithm 14.3.
    There is an unfortunate double use of the letter f to denote both the round function for SHA-1 and the bit-wise operations used to define the round function. Hopefully the usage of the letter f is clear from the context.
24. Page 285: Line 7.
    Should be "we first pad m out to a multiple of b using zero's (i.e. we apply padding method zero)".
25. Page 288: Figure 14.8
    In the box containing pad_4 it should be clearer that this is added onto k||m and not just the padding passed through. So the box should probably be k||m||pad_4(|k||m|,r)
26. Page 296: Line -3.
    Should be "breaking the RSA cryptosystem is no easier than solving the RSA problem."
27. Page 304: Section 15.3.4.
    The moduli used in the example give Euler phi values which are all divisible by three, which is not compatible with encryption exponent three. Thus make the following changes:
    1. The moduli N_1, N_2 and N_3 should be 253, 213 and 901 respectively.
    2. The ciphertexts c_1, c_2 and c_3 should be 199, 7 and 730 respectively.
28. Page 315: Line 2 and 3.
    Should be "If b=b'" then algorithm B returns that j is not a quadrative residue, otherwise it returns that it is".
29. Page 315: Line 8.
    Swap the two probabilities on this line around to make it match in order with the line which follows.
30. Page 319: Line 3.
    The group order should be \phi(N^2)=... not \phi(N)=....
31. Page 321: Line -5.
    Should be \log_{256} not \log_{8}
32. Page 327: Line 1.
    Should be "Note that C's target..."
33. Page 327: Line 2.
    Should be "... unless B aborts..."
34. Page 327: Line 4.
    Should be "... winning (or loosing) their game."
35. Page 333: Line -1.
    Replace both occurances of s with h.
36. Page 335: Line -12.
    The public key h should be y.
37. Page 336: Lines 1,6,9.
    The public key h should be y.
38. Page 337: Lines 10 and 19.
    The public key h should be y.
39. Page 412: Line -2.
    Replace F_p with F_q.
40. Page 422: Second displayed equation should read $c_2 \oplus H({c_1}^x) = m \oplus H(h^k) \oplus H({c_1}^x) = m \oplus H(g^{xk}) \oplus H(g^{kx}) = m $.
41. Page 437: Line 13.
    The parties compute the final tally by taking t+1 values and not t.
42. Page 444: Last paragraph replace with...
    In our example we can now assess what party B has learnt from the computation. Party B knows that the output of the final OR gate is zero, which means that the inputs must also be zero, which means that the output of the AND gate is zero and the output of the exclusive-or gate is zero. However, since party B knows the output of the AND gate is zero and his own input was one, then party A's first input wire must be zero. In addition, party B also learns that party A's second input wire also represented zero, since otherwise the exclusive-or gate would not have output zero. Thus the output (and Party B's input) totally reveals Party A's inputs. This is what we meant by a protocol keeping the inputs private, bar what could be deduced from the output of the function.
43. Page 447: Multiple corrections and clarifications.
    1. Line 11:
       Change "each party obtains its row" to "each party obtains its column".
    2. First table:
       Swap the row/column labels i and j around.
    3. First line after first table change to:
       "As an exercise you should work out the associated polynomial corresponding to each row. For example the polynomial for the first row/variable is given by $68 \cdot X^2 + 57 \cdot x + 20$."
       (Where all numbers are encoded in red)
    4. Line 3 and 4 after first table change to:
       "by each multiplying the first two elements in their column of the above table"
    5. Before second table add the line:
       "For example the value $33 = 44 \cdot 26 \pmod{101}$ obtained by party one, is shared by them using the polynomial $2 \cdot X^2 + 57 \cdot X + 33$, resulting in the six shares $(92,54,20,91,65,43)$."
       (Where all numbers are encoded in red)
    6. After the second table change the line to:
       "Each party then takes the six values obtained (i.e. it's column) and recovers..."