Handbook of Elliptic and Hyperelliptic Curve Cryptography (Discrete Mathematics and Its Applications)

Contributors in mathematics, computer science, and engineering introduce students and other professionals in any of their fields to the theory and algorithms involved in elliptic and hyper-elliptic curve cryptology in great detail. The text contains very few proofs, but provides all the essential background in mathematics, and contains many algorithms, some of which appear here for the first time in print. Accommodation is made for readers interested primarily in the mathematical parts, and for those who just want to implement the algorithms as quickly as possible. The discrete logarithm problem based on elliptic and hyperelliptic curves has gained a lot of popularity as a cryptographic primitive. The main reason is that no subexponential algorithm for computing discrete logarithms on small genus curves is currently available, except in very special cases. Therefore curve-based cryptosystems require much smaller key sizes than RSA to attain the same security level. This makes them particularly attractive for implementations on memory-restricted devices like smart cards and in high-security applications. The Handbook of Elliptic and Hyperelliptic Curve Cryptography introduces the theory and algorithms involved in curve-based cryptography. After a very detailed exposition of the mathematical background, it provides ready-to-implement algorithms for the group operations and computation of pairings. It explores methods for point counting and constructing curves with the complex multiplication method and provides the algorithms in an explicit manner. It also surveys generic methods to compute discrete logarithms and details index calculus methods for hyperelliptic curves. For some special curves the discrete logarithm problem can be transferred to an easier one; the consequences are explained and suggestions for good choices are given. The authors present applications to protocols for discrete-logarithm-based systems (including bilinear structures) and explain the use of elliptic and hyperelliptic curves in factorization and primality proving. Two chapters explore their design and efficient implementations in smart cards. Practical and theoretical aspects of side-channel attacks and countermeasures and a chapter devoted to (pseudo-)random number generation round off the exposition. The broad coverage of all- important areas makes this book a complete handbook of elliptic and hyperelliptic curve cryptography and an invaluable reference to anyone interested in this exciting field. Table of Contents......Page 12 List of Algorithms......Page 24 Preface......Page 30 1 Introduction to Public-Key Cryptography......Page 36 2 Algebraic Background......Page 54 3 Background on p-adic Numbers......Page 74 4 Background on Curves and Jacobians......Page 80 5 Varieties over Special Fields......Page 122 6 Background on Pairings......Page 150 7 Background on Weil Descent......Page 160 8 Cohomological Backgroundon Point Counting......Page 168 9 Exponentiation......Page 180 10 Integer Arithmetic......Page 204 11 Finite Field Arithmetic......Page 236 12 Arithmetic of p-adic Numbers......Page 274 13 Arithmetic of Elliptic Curves......Page 302 14 Arithmetic of Hyperelliptic Curves......Page 338 15 Arithmetic of Special Curves......Page 390 16 Implementation of Pairings......Page 424 17 Point Counting on Elliptic and Hyperelliptic Curves......Page 442 18 Complex Multiplication......Page 490 19 Generic Algorithms for Computing Discrete Logarithms......Page 512 20 Index Calculus......Page 530 21 Index Calculus for Hyperelliptic Curves......Page 546 22 Transfer of Discrete Logarithms......Page 564 23 Algebraic Realizations of DL Systems......Page 582 24 Pairing-Based Cryptography......Page 608 25 Compositeness and Primality Testing Factoring......Page 626 26 Fast Arithmetic in Hardware......Page 652 27 Smart Cards......Page 682 28 Practical Attacks on Smart Cards......Page 704 29 Mathematical Countermeasures against Side-Channel Attacks......Page 722 30 Random Numbers Generation and Testing......Page 750 References......Page 772 Notation Index......Page 812 General Index......Page 820 The Handbook Of Elliptic And Hyperelliptic Curve Cryptography Introduces The Theory And Algorithms Involved In Curve-based Cryptography. After A Very Detailed Exposition Of The Mathematical Background, It Provides Ready-to-implement Algorithms For The Arithmetic Of Elliptic And Hyperelliptic Curves And The Computation Of Pairings. It Explores Methods For Point Counting And Constructing Curves With The Complex Multiplication Method. It Also Surveys Generic Methods To Compute Discrete Logarithms And Details Index Calculus Methods For Hyperelliptic Curves As Well As Transfers Of Discrete Logarithm Problems For Special Curves. It Ends Up With Concrete Realizations Of Cryptosystems In Smart Cards, Including Efficient Implementation In Hardware And Side-channel Attacks As Well As Countermeasures--jacket. 1. Introduction To Public-key Cryptography / Roberto M. Avanzi And Tanja Lange -- 2. Algebraic Background / Christophe Doche And David Lubicz -- 3. Background On P-adic Numbers / David Lubicz -- 4. Background On Curves And Jacobians / Gerhard Frey And Tanje Lange -- 5. Varieties Over Special Fields / Gerhard Frey And Tanje Lange -- 6. Background On Pairings / Sylvain Duquesne And Gerhard Frey -- 7. Background On Weil Descent / Gerhard Frey And Tanje Lange -- 8. Cohomological Background On Point Counting / David Lubicz And Frederik Vercauteren. [scientific Editors] Henri Cohen, Gerhard Frey ; Roberto Avanzi ... [et Al.]. Includes Bibliographical References (p. 737-775) And Indexes. This carefully constructed state-of-the-art volume is a thorough study of nearly all the mathematical aspects of public key cryptography based on the discrete log system and explores both theory and applications