Hello everyone! Welcome to the first, but certainly not the last, post in the elliptic curve cryptography series. Previously, we discussed public-key cryptography and RSA encryption. In this series, we will discuss the elliptic curve cryptography by beginning with essence of finite fields and their use in elliptic curve cryptography.

Finite Prime Fields
1. Definition
2. Example
3. NIST Primes
4. Why finite fields?
What is an elliptic curve?
1. Overview
2. Elliptic Curve Groups

Finite Prime Fields

Before getting into the finite fields, let us recall the general group and field definitions from Wikipedia:

Groups

A group G is a finite or infinite set of elements together with a binary operation (called the group operation) that together satisfy the four fundamental properties of closure, associativity, the identity property, and the inverse property. The operation with respect to which a group is defined is often called the "group operation," and a set is said to be a group "under" this operation. Elements A, B, C, ... with binary operation between A and B denoted AB form a group if

Closure: If A and B are two elements in G, then the product AB is also in G.

Associativity: The defined multiplication is associative, i.e., for all A,B,C in G, (AB)C=A(BC).

Identity: There is an identity element I (a.k.a. 1, E, or e) such that IA=AI=A for every element A in G.

Inverse: There must be an inverse (a.k.a. reciprocal) of each element. Therefore, for each element A of G, the set contains an element B=A^(-1) such that AA^(-1)=A^(-1)A=I.

Fields

Formally, a field is a setF together with two binary operations on F called addition and multiplication. A binary operation on F is a mapping F × F → F, that is, a correspondence that associates with each ordered pair of elements of F a uniquely determined element of F.The result of the addition of a and b is called the sum of a and b, and is denoted a + b. Similarly, the result of the multiplication of a and b is called the product of a and b, and is denoted ab or a ⋅ b. These operations are required to satisfy the following properties, referred to as field axioms (in these axioms, a, b, and c are arbitrary elements of the field F):

Associativity of addition and multiplication: a + (b + c) = (a + b) + c, and a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c.

Commutativity of addition and multiplication: a + b = b + a, and a ⋅ b = b ⋅ a.

Additive and multiplicative identity: there exist two distinct elements 0 and 1 in F such that a + 0 = a and a ⋅ 1 = a.

Additive inverses: for every a in F, there exists an element in F, denoted −a, called the additive inverse of a, such that a + (−a) = 0.

Multiplicative inverses: for every a ≠ 0 in F, there exists an element in F, denoted by a⁻¹ or 1/a, called the multiplicative inverse of a, such that a ⋅ a⁻¹ = 1.

Distributivity of multiplication over addition: a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c).

The most popular field examples are:

$(\mathbb{Q}, +, \cdot)$,
$(\mathbb{R} , +, \cdot)$, and
$(\mathbb{C}, +, \cdot)$ with $\cdot$ operation is defined as
- $(a+bi) \cdot (c + di) = (ac -bd) + (bc + ad)i$.

Notice that all these fundamental examples are infinite fields. So let's see how finite ones look like!

Definition

Let $p$ be a prime number. The integers modulo $p$, consisting of integers $\{ 0, 1, 2, ... , p-1 \}$ with addition and multiplication performed modulo $p$, is a finite field of order $p$. We shall denote this field by $\mathbb{F}_p$.

Example ($\mathbb{F}_{29}$)

The elements of $\mathbb{F}_{29}$ are $\{ 0, 1, 2, ... , 28 \}$. The followings are some examples of arithmetic operations in $\mathbb{F}_{29}$:

$17 + 20 = 8$ since $37 \ mod \ 29 = 8$.
$17 - 20 = 26$ since $-3 \ mod \ 29 = 26$.
$17 \cdot 20 = 21$ since $340 \ mod \ 29 = 21.$
$17^{-1} = 12$ since $17 \cdot 12 \ mod \ 29 = 1$.

NIST Primes

You can construct a prime field by setting the $p$ as any prime, but there is a standard recommends elliptic curves over the five prime fields with moduli:

$$p_{192} = 2^{192} - 2^{64} - 1$$

$$p_{224} = 2^{224} - 2^{96} + 1$$

$$p_{256} = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$$

$$p_{384} = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1$$

$$p_{521} = 2^{521} - 1$$

These primes have the property that they can be written as the sum or difference of a small number of powers of 2. Furthermore, except for $p_{521}$, the powers appearing in these expressions are all multiple of 32. These properties yield reduction algorithms that are especially fast on machines with wordsize 32.

Why finite fields?

Basis of the security of elliptic curve cryptography is formed by the discrete logarithm problem (DLP), which we will cover in upcoming parts with more details, and DLP is more tractable in finite fields compared to infinite fields. This means that elliptic curve cryptography can achieve high levels of security with relatively smaller key sizes compared to other cryptographic schemes, such as RSA.

What is an elliptic curve?

Overview

Let $p$ be a prime number and let $\mathbb{F}_p$ denote the field of integers modulo $p$. An "elliptic curve" $E$ over $\mathbb{F}_p$ is defined by an equation of the form

$$y^2 = x^3 + ax + b,$$

where $a,b \in \mathbb{F}_p$ satisfy $4a^3+ 27b^2 \neq 0 \ (mod \ p) $ . A pair $(x, y)$, where $x,y \in \mathbb{F}_p$ is a point on the curve if it satisfies the curve equation. The point at infinity, denoted by $\infty$, is also said to be on the curve. The set of all points on $E$ is denoted by $E(\mathbb{F}_p)$.

For example, if $E$ is an elliptic curve over $\mathbb{F}_7$ with defining equation

$$y^2 = x^3 + 2x + 4,$$

then the points on $E$ are

$$E(\mathbb{F}_7) = \{ \infty, (0,2), (0,5), (1,0), (2,3), (2,4), (3,3), (3,4), (6,1), (6,6) \}.$$

Please see point addition to see how to add 2 points up to obtain another point on the curve.

As we are able to define an addition operation on elliptic curves, we can also construct a group structure on elliptic curves

Elliptic Curve Groups

With the point addition rule, the set of points $E(\mathbb{F}_p)$ forms a group with $\infty$ serving as the identity element.

This kind of group structures are called "elliptic curve groups".

Conclusion

In this post, some fundamental concepts and notions are mentioned. In the next post, we will discuss key generation and encryption schemes in elliptic curve cryptography.

Furkan's Blog