Idea Transcript
Mathematics of Public Key Cryptography Steven Galbraith 2012
Cambridge University Press amazon.co.uk
Reviews Featured in Computing Reviews list of notable computing items published in 2012. AMS MathSciNet Mathematical Reviews, by José Ignacio Farrán. "Written by an active researcher in the topic, this book aims precisely to explain the main ideas and techniques behind public key cryptography, from both historical and future development perspectives. Because of the abundance of examples, proofs and exercises, it is suitable as a textbook for an advanced course, or even for self-study. For more advanced readers, it is a basic reference for crucial topics such as the Pollard algorithms, elliptic curves and isogenies, algebraic tori, and lattices." Zentralblatt MATH, by Juan Tena Ayuso. "the book gathers the main mathematical topics related to public key cryptography and provides an excellent source of information for both students and researchers interested in the field" MAA Reviews, by Darren Glass. "I enjoy Galbraith's exposition, and am very happy to have a copy of this book on my shelf"
Bonus Material Table of notation Hints and Solutions to Exercises
Errata Section 2.3, page 26, Lemma 2.3.3, line -8: t_{i} should be t_{i-1}. The correct formula is a = r_{i} (-1)^{i-1} t_{i-1} + r_{i-1} (-1)^{i} t_{i}. (Error noticed by Wang Maoning.) Section 5.2, page 73. Part 1 of Lemma 5.2.20: varphi_i^{-1}^* is not a k-algebra homomorphism (consider the sum of two polynomials of different total degree). Part 6 of Lemma 5.2.20: f should be homogeneous. Also proof of part 2 of Lemma 5.2.25: f should be homogeneous. (Errors noticed by Parinaz Shahabi.) Section 5.3, page 76, Theorem 5.3.8: The theorem is clearly false, since if f is the square of an irreducible polynomial then V( f ) is irreducible, but f is not. An extra condition, that f has no repeated factors is required. A correct proof is given on the pdf file on this webpage. Section 7.7, page 113, Proof of Lemma 7.7.10 (second line): "\iota(P) = \iota(P) = " should just be "\iota(P) = ". (Error noticed by Parinaz Shahabi.) Section 8.1, page 122, Definition 8.1.6: A field F between phi^*( k( C_2 )) and k( C_1 ) with those properties does not necessarily exist if the extension is not normal. The treatment should be the other way around: k(C_1)/F purely inseparable and F/phi^*( k( C_2 )) separable. (Error noticed by Alexander Schiller.) Section 9.6, page 151, Proof of Theorem 9.6.21: Formula should be \hat{\phi} = \alpha_1^{-1} \circ \phi^* \circ \alpha_2. (Error noticed by Yan Bo Ti.) Section 9.11, page 165, Example 9.11.6: F(x) lies in F_q[x]. Section 9.11, page 166, Lemma 9.11.8: R[x] should be R[T]. Section 12.2.1, page 241, line -5: The standard definition of a Sophie Germain prime is a prime p such that 2p+1 is prime. The book defines 2p+1 to be the Sophie Germain prime, which is not standard. (Error noticed by Florian Weingarten.) Section 15.4, page 312, line 20: Replace c/(3c') with c'/(3c''). (Error noticed by Alfred Menezes) Section 15.5.1, page 314, line -13: Change "do not lie in" to "do not necessarily lie in". (Error noticed by Alfred Menezes) Section 15.5.1, page 315, line 12: Delete "B = ". (Error noticed by Alfred Menezes) Section 15.5.4, page 322, lines 10-19: Several small errors. (n / c \log(n))^{1/3} should be (n / \log(n))^{1/3} / \sqrt{c}. kd should be 2^k d_A. 2^k d should be 2^k d_A. (n / log(n))^{1/3} should be (n \log(n)^2)^{1/3}. (Errors noticed by Alfred Menezes) Section 15.5.1, page 315, line -12: The value c = (2 / 3 \log(2))^{2/3} gives the theoretical value for the running time. But this is not necessarily an accurate value for implementing the algorithm. One needs to ensure that enough smooth pairs (C(x),D(x)) are available to get enough relations. (Comment made by Alfred Menezes) Section 15.8.3, page 332, Theorem 15.8.4: Replace F_{q^n}^* by E( F_{q^n} ) in two places. (Error noticed by Samuel Neves.) Section 18.2, page 371, line 1: According to the definition used in the book, [7/2] = [3.5] = 4 and so the correct vector should be 4 b_1 + 2 b_2 = (10, 8, 6). But this ruins the moral of Example 18.2.4 (pages 372-373) that Babai nearest plane and Babai rounding can give different results (which is true in general, just not in this case). (Error noticed by Bart Coppens.) Section 18.4, page 376, line -3: The equation $0 \le x_n \le \sqrt{A / B_i}$ should be $0 \le x_n \le \sqrt{A / B_n}$. (Error noticed by Sean Murphy.) Section 25.2, page 523, line -3: It is not true that Phi_{ell}( j(E), j( tilde{E} ) = 0 implies there is an isogeny from E to tilde{E}, as the isogeny might be to a twist of tilde{E}. Correct wording would be to replace "cyclic kernel from E to tilde{E}" to "cyclic kernel from E to a twist of tilde{E}". (Error noticed by Drew Sutherland.)
Sample Chapters NOTE: Most of these chapters are "extended versions" of chapters in the book and so have additional material. Chapter 19a is an additional chapter. Section/Theorem/Lemma/page numberings do not necessarily match those in the published version of the book. Table of contents Acknowledgements Table of notation 1. Introduction Part I: Background 2. Basic Algorithms 3. Hash Functions Part II: Algebraic Groups 4. Preliminary remarks on Algebraic Groups 5. Varieties 6. Tori, LUC and XTR 7. Curves and Divisor Class Groups 8. Rational Maps on Curves and Divisors 9. Elliptic Curves 10. Hyperelliptic Curves Part III: Exponentiation, Factoring and Discrete Logarithms 11. Basic Algorithms for Algebraic Groups 12. Primality Testing and Integer Factorisation using algebraic groups 13. Basic Discrete Logarithm Algorithms 14. Factoring and Discrete Logarithms Using Pseudorandom Walks 15. Factoring and Discrete Logarithms in Subexponential Time Part IV: Lattices 16. Lattices 17. Lattice Reduction 18. Algorithms for the Closest and Shortest Vector Problem 19. Coppersmith's Method and Other Applications 19a. Cryptosystems Based on Lattices (does not appear in published version of book) Part V: Cryptography Related to Discrete Logarithms 20. The Diffie-Hellman Problem and Cryptographic Applications 21. The Diffie-Hellman Problem 22. Digital Signatures Based on Discrete Logarithms 23. Public Key Encryption Based on Discrete Logarithms Part VI: Cryptography Related to Integer Factorisation 24. The RSA and Rabin Cryptosystems Part VII: Advanced Topics in Elliptic and Hyperelliptic Curves 25. Isogenies of elliptic curves 26. Pairings on elliptic curves Appendices A. Background Mathematics B. Hints and Solutions to Exercises References Index