ECC Notebook

An Interactive Introduction to Elliptic Curve Cryptography

By Maike Massierer and the CrypTool team (www.cryptool.org)
Version 1.3, January 2011

Any feedback regarding this notebook is appreciated. Please mail to [email protected] or [email protected].

If you haven't used Sage before, click here for some instructions to get you started. And even if you are familiar with Sage, please note: In order to have access to the full functionality of the ECC Notebook, you need to click "Edit this" and "Action -> Evaluate All" on (the top left of) every worksheet. If you are still having trouble, please consult the Instructions page.

Table of Contents

• Introduction and Overview
• 1.1 This Document
• 1.2 Roadmap
• Motivation for the Use of Elliptic Curves in Cryptography
• 2.1 The Diffie-Hellman Key Exchange Protocol
• 2.2 Security of the Diffie-Hellman Key Exchange
• 2.3 Generalizing the Diffie-Hellman Key Exchange
• Elliptic Curves in Cryptography
• 3.1 Finite Fields
• 3.2 Definition of Elliptic Curves
• 3.3 Point Addition on Elliptic Curves
• 3.4 Elliptic Curve Group Structure
• 3.5 Scalar Multiplication of Elliptic Curve Points
• 3.6 Elliptic Curve Group Order
• 3.7 The Elliptic Curve Discrete Logarithm Problem
• Cryptographic Protocols in ECC
• 4.1 Domain Parameters
• 4.2 Key Pair Generation
• 4.3 Key Establishment Protocols
• 4.4 Public-Key Encryption Protocols
• 4.5 Digital Signature Schemes
• Domain Parameter Generation for ECC Systems
• 5.1 Restrictions Based on General-Purpose Attacks on the DLP
• 5.2 Restrictions Based on Attacks which Exploit Structural Weaknesses
• 5.3 Domain Parameter Generation and Validation
• Conclusion and Further Topics
• 6.1 A Comparison of ECC and RSA
• 6.2 Elliptic Curve Cryptography in Use Today
• 6.3 Further Topics
• References

List of Figures and Applications

• 2.1 Diffie-Hellman key exchange (1)
• 2.2 Number of possible keys
• 2.3 Calculation of primitive roots
• 2.4 Diffie-Hellman key exchange (2)
• 2.5 Diffie-Hellman key exchange (3)
• 2.6 DLP brute-force search
• 2.7 Running time comparison of exponential, sub-exponential and polynomial-time algorithms


• 3.1 Elliptic curves defined by y^2=x^3+ax+b
• 3.2 Elliptic curves over the real numbers
• 3.3 Elliptic curves over finite fields
• 3.4 Point addition
• 3.5 Point doubling
• 3.6 Point at infinity
• 3.7 Point addition for elliptic curves over the rational numbers
• 3.8 Point addition for elliptic curves over finite fields
• 3.9 Double-and-add algorithm
• 3.10 Comparison of the three methods of scalar multiplication


• 6.1 Recommended key lengths