Implementing Elliptic Curve Cryptography

Description

Implementing Elliptic Curve Cryptography proceeds step-by-step to explain basic number theory, polynomial mathematics, normal basis mathematics and elliptic curve mathematics. With these in place, applications to cryptography are introduced. The book is filled with C code to illustrate how mathematics is put into a computer, and the last several chapters show how to implement several cryptographic protocols. The most important is a description of P1363, an IEEE draft standard for public key cryptography.

The main purpose of Implementing Elliptic Curve Cryptography is to help "crypto engineers" implement functioning, state-of-the-art cryptographic algorithms in the minimum time. With detailed descriptions of the mathematics, the reader can expand on the code given in the book and develop optimal hardware or software for their own applications.

Implementing Elliptic Curve Cryptography assumes the reader has at least a high school background in algebra, but it explains, in stepwise fashion, what has been considered to be a topic only for graduate-level students.

Table of Contents

• 1 Introduction
        Why Elliptic Curves?
        Why C?
        Orders of Magnitude
        Structure of Book
        Comments on Style
        Acknowledgements
  
  2 Basics of Number Theory
        Large Integer Math Header
        Large Integer Math Routines
        Multiplication
        Division
        Large Integer Code Example
        Back to Number Theory
        Greatest Common Factor
        Modular Arithmetic
        Fermat's Theorem
        Finite Fields
        Generators
  
  3 Polynomial Math Over Finite Fields
        Polynomial Basis Header Files
        Polynomial Addition
        Polynomial Multiplication
        Polynomial Division
        Modular Polynomial Arithmetic
        Inversion Over Prime Polynomials
        Polynomial Greatest Common Divisor
        Prime Polynomials
        Summary
  
  4 Normal Basis Mathematics
        Squaring Normal Basis Numbers
        Multiplication in Theory
        Type I Optimal Normal Basis
        Type II Optimal Normal Basis
        Multiplication in Practice
        Inversion over Optimal Normal Basis
  
  5 Elliptic Curves
        Mathematics of Elliptic Curves Over Real Numbers
        Mathematics of Elliptic Curves Over Prime Fields
        Mathematics of Elliptic Curves Over Galois Fields
        Polynomial Basis Elliptic Curve Subroutines
        Optimal Normal Basis Elliptic curve Subroutines
        Multiplication Over Elliptic Curves
        Balanced Integer Conversion Code
        Following the Balanced Representation
  
  6 Cryptography
        Fundamentals of Elliptic Curve Cryptography
        Choosing an Elliptic Curve
        Non-supersingular Curves
        Embedding Data on a Curve
        Solving Quadratic Equations in Binary Fields
        The Trace Function
        Solving Quadratic Equations in Normal Basis
        Solving Quadratic Equations in Polynomial Basis
        Quadratic Polynomials, the Code
        Using the T Matrix
        Embedding Data Using Polynomial Basis
        Summary of Quadratic Solving
  
  7 Simple Protocols
        Random Bit Generator
        Choosing Random Curves
        Diffie-Hellman
        ElGamal Protocol
        ElGamal Using Optimal Normal Basis
        ElGamal, Polynomial Basis
        Menezes-Qu-Vanstone Key Agreement Scheme
        MQV the Code, Simple Version
  
  8 Elliptic Curve Encryption
        Mask Generation Function
        Hash Fucntion SHA-1
        Mask Generation, the Code
        ECES, the Code
        Polynomial Basis
        Normal Basis
  
  9 Advanced Protocols, Key Exchange
        Polynomial solution to g^3 = g + 1
        Massey-Omura Protocol
        Massey-Omura, the Code
        MQV, the Standard
        MQV, Normal Basis Version
        MQV, Polynomial Basis Version
  
  10 Advanced Protocols, Signatures
        Message Hash
        Nyberg-Rueppel Signature Scheme
        Nyberg-Rueppel signature, Normal Basis
        Nyberg-Rueppel, Polynomial Basis
        Elliptic Curve DSA
        DSA in Normal Basis
        DSA, Polynomial Basis
  
  11 State of the Art
        High Speed Inversion for ON
        Faster Inversion, Preliminary Subroutines
        Faster Inversion, the Code
        Security from Cryptography
        Counting Points
        Polynomials Base p
        Hyper-Elliptic Curves
  
  References