# Part 1: Fundamental Concepts | Elliptic Curve Cryptography

## A smooth introduction to fundamental concepts in elliptic curve cryptography

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.

# Contents

Finite Prime Fields

Definition

Example

NIST Primes

Why finite fields?

What is an elliptic curve?

Overview

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 set

Ftogether with two binary operations onFcalledadditionandmultiplication. A binary operation onFis a mappingF×F→F, that is, a correspondence that associates with each ordered pair of elements ofFa uniquely determined element ofF.The result of the addition ofaandbis called the sum ofaandb, and is denoteda+b. Similarly, the result of the multiplication ofaandbis called the product ofaandb, and is denotedabora⋅b. These operations are required to satisfy the following properties, referred to asfield axioms(in these axioms,a,b, andcare arbitrary elements of the fieldF):

Associativity of addition and multiplication:

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

a+b=b+a, anda⋅b=b⋅a.Additive and multiplicative identity: there exist two distinct elements 0 and 1 in

Fsuch thata+ 0 =aanda⋅ 1 =a.Additive inverses: for every

ainF, there exists an element inF, denoted −a, called theadditive inverseofa, such thata+ (−a) = 0.Multiplicative inverses: for every

a≠ 0 inF, there exists an element inF, denoted bya^{−1}or 1/a, called themultiplicative inverseofa, such thata⋅a^{−1}= 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.