EC Cryptography Tutorials - Herong's Tutorial Examples

EC Cryptography Tutorials

- Herong's Tutorial Examples

v1.03, 2024

Herong Yang

Copyright © 2019-2024 Herong Yang. All rights reserved.

ISBN: 978-0-359-60490-6

This EC (Elliptic Curve) cryptography tutorial book is a collection of notes and sample codes written by the author while he was learning cryptography technologies himself. Topics include rule of chord and point addition on elliptic curves; Abelian groups with additive/multiplicative notations; EC as Abelian groups; DLP (Discrete Logarithm Problem) and trapdoor function; Galois fields or finite fields with Additive/Multiplicative Abelian Group; Prime fields, binary fields, and polynomial fields; EC fields reduced with modular arithmetic; EC subgroup and base points; EC private key and public key pairs; ECDH (Elliptic Curve Diffie-Hellman) protocol; ECDSA (Elliptic Curve Digital Signature Algorithm); ECES (Elliptic Curve Encryption Scheme) protocol; Java tool/program to generate EC keys. Updated in 2024 (Version v1.03) with minor changes.

Table of Contents

About This Book

Geometric Introduction to Elliptic Curves

What Is an Elliptic Curve?

Elliptic Curve Geometric Properties

Addition Operation on an Elliptic Curve

Prove of Elliptic Curve Addition Operation

Same Point Addition on an Elliptic Curve

Infinity Point on an Elliptic Curve

Negation Operation on an Elliptic Curve

Subtraction Operation on an Elliptic Curve

Identity Element on an Elliptic Curve

Commutativity of Elliptic Curve Operations

Associativity of Elliptic Curve Operations

Elliptic Curve Operation Summary

Algebraic Introduction to Elliptic Curves

Algebraic Description of Elliptic Curve Addition

Algebraic Solution for Symmetrical Points

Algebraic Solution for the Infinity Point

Algebraic Solution for Point Doubling

Algebraic Solution for Distinct Points

Elliptic Curves with Singularities

Elliptic Curve Point Addition Example

Elliptic Curve Point Doubling Example

Abelian Group and Elliptic Curves

What Is Abelian Group

Niels Henrik Abel and Abelian Group

Multiplicative Notation of Abelian Group

Additive Notation of Abelian Group

Modular Addition of 10 - Abelian Group

Modular Multiplication of 10 - Not Abelian Group

Modular Multiplication of 11 - Abelian Group

Abelian Group on Elliptic Curve

Discrete Logarithm Problem (DLP)

Doubling or Squaring in Abelian Group

Scalar Multiplication or Exponentiation

What Is Discrete Logarithm Problem (DLP)

Examples of Discrete Logarithm Problem (DLP)

What Is Trapdoor Function

DLP and Trapdoor Function

Scalar Multiplication on Elliptic Curve as Trapdoor Function

Finite Fields

What Is Finite Field

Prime Fields GF(p) - Finite Fields with Modular Arithmetic

Prime Field Example - GF(11)

Binary Fields GF(2n) on Binary Polynomials

Binary Field Example - GF(2²) with Modulo x²+x+1

Binary Field Example - GF(2³) with Modulo x³+x+1

Binary Format of Binary Fields GF(2n)

Binary Format for GF(2³) with Modulo x³+x+1

Polynomial Fields GF(pn) on Prime Polynomials

Polynomial Field Example - GF(3²) with Modulo x²+1

Field Order and Field Characteristic

Field Characteristic Is a Prime Number

Field Order Is Prime Power

Generators and Cyclic Subgroups

What Is Subgroup in Abelian Group

What Is Subgroup Generator in Abelian Group

What Is Order of Element

Every Element Is Subgroup Generator

Order of Subgroup and Lagrange Theorem

What Is Cyclic Group

Element Generated Subgroup Is Cyclic

Reduced Elliptic Curve Groups

Converting Elliptic Curve Groups

Elliptic Curves in Integer Space

Python Program for Integer Elliptic Curves

Elliptic Curves Reduced by Modular Arithmetic

Python Program for Reduced Elliptic Curves

Point Pattern of Reduced Elliptic Curves

Integer Points of First Region as Element Set

Reduced Point Additive Operation

Modular Arithmetic Reduction on Rational Numbers

Reduced Point Additive Operation Improved

What Is Reduced Elliptic Curve Group

Reduced Elliptic Curve Group - E23(1,4)

Reduced Elliptic Curve Group - E97(-1,1)

Reduced Elliptic Curve Group - E127(-1,3)

Reduced Elliptic Curve Group - E1931(443,1045)

What Is Hasse's Theorem

Finite Elliptic Curve Group, Eq(a,b), q = pn

Elliptic Curve Subgroups

Subgroups of Reduced Elliptic Curve Groups

Python Program for Point Addition

Point Addition Extended with Identity

Python Program for Scalar Multiplication

Python Program for Generating Subgroup

Subgroup Example - G(15,13) of E17(0,7)

tinyec - Python Library for ECC

What Is tinyec

Download and Install tinyec

Build New Curves with tinyec

Perform Point Addition with tinyec

Find Subgroup with Point Addition

Set Subgroup Order to Higher Value

EC (Elliptic Curve) Key Pair

EC Private and Public Key Pair

Is EC Private Key Secure

EC Private Key Example - secp256k1

Generate secp256k1 Keys with OpenSSL

EC Key in PEM File Format

EC Key File with Curve Name

Create EC Public Key File

ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

What Is ECDH Key Exchange

Is ECDH Key Exchange Secure

ECDSA (Elliptic Curve Digital Signature Algorithm)

ECDSA Digital Signature Generation

ECDSA Digital Signature Verification

ECDSA Problem If k Used Twice

Find ECDSA Public Key from Signature

Download and Install pycoin

pycoin.ecdsa.ellipticcurve Module

pycoin.ecdsa.generator_secp256k1 Object

Generate EC Key Pair with pycoin.ecdsa

pycoin.ecdsa.ecdsa.sign() - Signature Generation

pycoin.ecdsa.ecdsa.sign() - Signature Verification

'openssl dgst' - Signing and Verification

ECES (Elliptic Curve Encryption Scheme)

ECES Plaintext Encryption

ECES Ciphertext Decryption

Download and Install PyCryptodome

ECES Encryption with Crypto.Cipher.AES

ECES Decryption with Crypto.Cipher.AES

EC Encryption of Plaintext Point

EC Cryptography in Java

keytool -keyalg EC - Generate EC Key Pair

keytool -groupname ... - Select Curve Name

Java Program to Generate EC Keys

Legacy SunEC curve disabled Error

EC Curves Supported by Java

Standard Elliptic Curves

What Are Standard Elliptic Curves

openssl ecparam -list_curves - Curves Supported by OpenSSL

secp256r1 - For 256-Bit ECC Keys

secp256k1 - For 256-Bit ECC Keys

sect283r1 - For 256-Bit ECC Keys

brainpoolP256r1" - For 256-Bit ECC Keys

brainpoolP256t1" - For 256-Bit ECC Keys

Terminology

References

Keywords: Cryptography, EC, Elliptic Curve, Tutorial, Example

EC Cryptography Tutorials - Herong's Tutorial Examples

∟ About This Book

This section provides some detailed information about this book - EC Cryptography Tutorials - Herong's Tutorial Examples.

Title: EC Cryptography Tutorials - Herong's Tutorial Examples

Author: Herong Yang - Contact by email via [email protected].

Category: Computers / Security / Cryptography & Encryption

Version/Edition: v1.03, 2024

Number of pages in PDF format: 242

Description: This EC (Elliptic Curve) cryptography tutorial book is a collection of notes and sample codes written by the author while he was learning cryptography technologies himself. Topics include rule of chord and point addition on elliptic curves; Abelian groups with additive/multiplicative notations; EC as Abelian groups; DLP (Discrete Logarithm Problem) and trapdoor function; Galois fields or finite fields with Additive/Multiplicative Abelian Group; Prime fields, binary fields, and polynomial fields; EC fields reduced with modular arithmetic; EC subgroup and base points; EC private key and public key pairs; ECDH (Elliptic Curve Diffie-Hellman) protocol; ECDSA (Elliptic Curve Digital Signature Algorithm); ECES (Elliptic Curve Encryption Scheme) protocol; Java tool/program to generate EC keys. Updated in 2024 (Version v1.03) with minor changes.

Keywords: ECC, Elliptic Curve, Cryptography, Private Key, Tutorial, Example.

Copyright:

This book is under Copyright © 2019-2024 Herong Yang. All rights reserved.

Material in this book may not be published, broadcasted, rewritten or redistributed in any form.

The example codes is provided as-is, with no warranty of any kind.

Revision history:

Version v1.03, 2024. Minor updates.

Version v1.00, 2019. Started with basics of ECC.

Web version: https://www.herongyang.com/EC-Cryptography - Provides free sample chapters, latest updates and readers' comments. The Web version of this book has been viewed a total of:

222,214 times as of December 2023.

161,277 times as of December 2022.

107,714 times as of December 2021.

55,667 times as of December 2020.

21,574 times as of December 2019.

PDF/EPUB version: https://www.herongyang.com/EC-Cryptography/PDF-Full-Version.html - Provides information on how to obtain the full version of this book in PDF, EPUB, or other format.

All chapters and their main topics are list below to guide you reading through this book:

Geometric Introduction to Elliptic Curves - Point addition on an elliptic curve can be defined using the Rule of the chord geometrical algorithm.

Algebraic Introduction to Elliptic Curves - Rule of the chord geometrical algorithm can be expressed in algebraic formula.

Abelian Group and Elliptic Curves - Points on an elliptic curve with point addition forms an Abelian group.

Discrete Logarithm Problem (DLP) - Scalar multiplication in elliptic curve Abelian group creates a DLP and is a good trapdoor function.

Finite Fields - Finite field is a set with finite elements that forms an additive Abelian group and a multiplicative Abelian group. This chapter is not closely related to elliptic curve Abelian groups.

Generators and Cyclic Subgroups - Element in an Abelian group can be used to generated a cyclic Abelian subgroup.

Reduced Elliptic Curve Groups - All integer points on a reduced elliptic curve and the reduced point addition forms a finite Abelian group.

Elliptic Curve Subgroups - Any point in a reduced elliptic curve group can be used to generated a cyclic Abelian subgroup, which is the basis for Elliptic Curve Cryptography (ECC).

tinyec - Python Library for ECC - tinyec is a Python library that allows you to build an elliptic curve subgroup and explore its properties.

EC (Elliptic Curve) Key Pair - Scalar multiplication in an elliptic curve subgroup, d*G = Q, can be used to generate a private-public key pair (d, Q), where G is the base point (the subgroup generator).

ECDH (Elliptic Curve Diffie-Hellman) Key Exchange - ECDH key exchange protocol is to perform a scalar multiplication of one's own EC private key and other's EC public key to obtain the common secret key.

ECDSA (Elliptic Curve Digital Signature Algorithm) - EC digital signature is calculated as, s = (h + r*d)/k, where h is the message hash, d is the private key, r is the x-coordinate of k*G, k is a random number, and G is the base point.

ECES (Elliptic Curve Encryption Scheme) - ECES uses the ECDH key exchange protocol to derive a common secret key, which is then used to encrypt plaintext message.

EC Cryptography in Java - JDK (Java Development Kit) offers functionalities to generate EC key pairs on a number of pre-defined elliptic curve Abelian subgroups.

Standard Elliptic Curves - Some elliptic Curves Abelian subgroups are recommended by different organizations to generated secure EC private-pubic key pairs.

EC Cryptography Tutorials - Herong's Tutorial Examples

∟ Geometric Introduction to Elliptic Curves

This chapter provides a geometric introduction of elliptic curves and the associated addition operation. Topics includes what is an elliptic curve and its geometric properties; geometric algorithm defining an addition operation; infinity point or identity element; commutativity and associativity of the addition operation.

What Is an Elliptic Curve?

Elliptic Curve Geometric Properties

Addition Operation on an Elliptic Curve

Prove of Elliptic Curve Addition Operation

Same Point Addition on an Elliptic Curve

Infinity Point on an Elliptic Curve

Negation Operation on an Elliptic Curve

Subtraction Operation on an Elliptic Curve

Identity Element on an Elliptic Curve

Commutativity of Elliptic Curve Operations

Associativity of Elliptic Curve Operations

Elliptic Curve Operation Summary

Takeaways:

An elliptic curve is symmetric about the x-axis.

A straight line can only intersect with an elliptic curve at up to 3 locations.

An operation, called addition, can be defined on an elliptic curve using a geometric algorithm called rule of the chord.

The infinity point can be considered as part of an elliptic curve and used as the identity element of the addition operation.

The addition operation is commutative and associative.

EC Cryptography Tutorials - Herong's Tutorial Examples

∟ Geometric Introduction to Elliptic Curves

∟ What Is an Elliptic Curve?

This section describes what is elliptic curve - A set of 2 dimensional points of (x, y) that satisfy the y² = x³ + ax + b equation with given values of a and b.

What Is an Elliptic Curve? An elliptic curve is the set of 2 dimensional points of (x, y) that satisfy the following mathematical equation with given values of a and b:

y² = x³ + ax + b

Here are two examples of elliptic curves (source: wikipedia.org):

Examples of Elliptic Curves

Here are more examples of elliptic curves (source: wikipedia.org):

More Examples of Elliptic Curves

Here are some elliptic curves superposed like contour lines (source: cosec.bit.uni-bonn.de):

Elliptic Curves Superposed Like Contour Lines

By the way, the earliest text book discussing elliptic curves is probably the Arithmetica by the father of algebra, Diophantus of Alexandria in the third century.

EC Cryptography Tutorials - Herong's Tutorial Examples

∟ Geometric Introduction to Elliptic Curves

∟ Elliptic Curve Geometric Properties

This section describes two geometric properties of an elliptic curve: horizontal symmetry and 3 intersections or less with straight lines.

Elliptic curves have two important geometric properties:

1. An elliptic curve is symmetrical about the x-axis. If point P = (x,y) is on an elliptic curve, then -P = (x,-y) is also on the same elliptic curve. We can also say that an elliptic curve is horizontally symmetric.

Here is an example of two symmetrical points P and -P on an elliptic curve (source: slideplayer.com):

Elliptic Curve Symmetrical to X-Axis

2. An elliptic curve will intersect with any straight line in at most 3 points. This property will be used to help defining an addition operation on an elliptic curve.

Here is an example of an elliptic curve intersecting with a straight line in 3 points (source: sysax.com):

Elliptic Curve Intersects with Straight Line

EC Cryptography Tutorials - Herong's Tutorial Examples

∟ Geometric Introduction to Elliptic Curves

∟ Addition Operation on an Elliptic Curve

This section describes the addition operation on an elliptic curve geometrically. The addition of points P and Q on an elliptic curve is a point R on the curve, which is the symmetrical point of -R, which is the third intersection of the curve and the straight line passing through P and Q.

The addition operation on an elliptic curve is defined geometrically as below:

For any given two points P and Q on an elliptic curve, the addition operation of P and Q will result a third point R on the curve by running the following geometrical algorithm:

1. Draw a straight line passing P and Q

2. Mark the third intersection of the straight line and the elliptic curve as -R.

3. Mark the symmetrical point of -R on the other side of the x-axis of the elliptic curve as R.

The above geometrical algorithm is also called rule of the chord.

If we use the plus sign + as the addition operator, the addition operation of points P and Q on an elliptic curve can be expressed as:

P + Q = R

Here is a diagram that illustrates how to perform the point addition operation on an elliptic curve geometrically (source: stackoverflow.com):

Addition Operation on an Elliptic Curve

EC Cryptography Tutorials - Herong's Tutorial Examples

∟ Geometric Introduction to Elliptic Curves

∟ Prove of Elliptic Curve Addition Operation

This section describes how to prove that the addition operation on an elliptic curve can be successfully performed geometrically.

To prove that each and every addition operation on an elliptic curve can be successfully performed, we need to prove the following:

1. Every straight line that passes through two points P and Q on an elliptic curve must intersect with the same curve at a third point -R. Otherwise we will not be able