Introduction | Mathematical Background | Finite Field Arithmetic | Elliptic Curve Arithmetic | Elliptic Curve Protocols | Implementation | Cryptanalysis |

Mathematical Background

Objectives

• Understand the Number Theory
• Understand the use of Euclidean Algorithm
• Use the Extended Euclidean Algorithm in ECC
• Understand Congruence and Modular Arithmetic
• Understand Fermat’s Little Theorem
• Use of  Rings, Group and Fields

Introduction

Elliptic curve cryptography use arithmetic operations, which are based on abstract algebra and in particular finite fields. In this chapter, an over view of the abstract algebra required to understand the elliptic curve operations is presented. The chapter begins with the introduction to number theory, Euclidean algorithm, extended Euclidean algorithm, congruence, modular arithmetic, Fermat’s little theorem, rings, groups and fields.

Number Theory

Number Theory is the study of integers. It is one of the oldest branches of pure mathematics, and serves as the fundamental of the underlying operations of Elliptic Curve Cryptography. The most important theorems of Elliptic Curve Cryptography are Euclidean Algorithm, Congruence, the Extended Euclidean Algorithm Theorem and Fermat’s Theorem.

Euclidean Algorithm

The Euclidean Algorithm was discovered by Euclid of Alexandria (325-265 BC) for computing the greatest common divisor (GCD) of two positive integers. The GCD of two positive integers a and b is the largest integer which divides both a and b. In general, let a and b be positive integers, with b > 0, there are unique q and r such that a = qp + r, where 0 ≤ r ≤ b-1, q is called the quotient and r the remainder. Here, the modular operation “mod” can also be used to denote the remainder r, that is r = a mod b.

The Euclidean Algorithm states that the GCD of a and b can be found by repeated application of equation a = qb + r. Example the repeatedly dividing the divisor by the remainder r until the remainder is zero. The last non-zero remainder is the GCD of a and b. It also can be expressed as GCD(a, b) = GCD(b, r). Algorithm nn listed the pseudo-code for the Euclidean Algorithm. The run time complexity is O(( log a)( log b)) bit operations.

Example: GCD(81543254, 57435333) = 17.

Extended Euclidean Algorithm

Based on the Euclidean Algorithm, the Extended Euclidean Algorithm (EEA) provides a method to find the inverse of a number mod m. It states, for any two integers a and b, there are two integers x and y such that ax + by = gcd (a, b). Hence, if gcd (a, b) = 1, x is then the inverse of a mod b.

To find x, the Extended Euclidean Algorithm computes an auxiliary number, p_i, at each step of the Euclidean Algorithm (Algorithm nn). The first two auxiliary numbers are initialized as p₀ = 0 and p₁ = 1. Then for the remaining steps, p_i is calculated recursively by p_i = p_{i – 2} – p_{i – 1}q_{i – 2} (mod m), where q_i is the quotient obtained at each step. The calculation is repeated for one step beyond the last step of the Euclidean Algorithm.

Congruence and Modular Arithmetic

If a, b, n  Z and m ≠ 0, then we say that a and b are congruent modulo m, written as a ≡ b (mod m), if m divides a - b. It is equivalent to say, if a ≡ b (mod m), a and b have the same remainder when divided by m. For example, 38 ≡ 5 (mod 11), since 11 divides 38 -5.

The number m is called the modulus, and the quantity b is called the residue or remainder. There are several types of residues. The common residue defined to be nonnegative and smaller than m, while the minimal residue is c or c – m, whichever is smaller in absolute value.

Congruencies also apply to fractions. If ab ≡ 1 (mod m), the inverse of a mod b is a^-1 ≡ b (mod m). For example, 2 × 4 ≡ 1 (mod 7), so 2^-1 ≡ 4 (mod 7).

The three most important properties of congruencies are:

·                  The reflexive property: If a is any integer, a ≡ a (mod m),

·                  The symmetric property: If a ≡ b (mod m), then b ≡ a (mod m),

·                  The transitive property: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).

Modular arithmetic is the arithmetic of congruence discovered by K. F. Gauss (1777-1855) in 1801. It is the central mathematical concept in ECC. In general, the expression, a mod m, means to divide a by m and keep the remainder.

Define the set Zn as the set of nonnegative integers less than n: Zn = 0, 1, 2, …, n–1. The following properties hold when performing modular arithmetic within the set.

·                  Commutative law: (a + b) mod m = (b + a) mod m, (a × b) mod m = (b × a) mod m

·                  Association law: [(a + b) + c] mod m = [a + (b + c)] mod m, [(a × b) × c] mod m = [a × (b × c)] mod m

·                  Distributive law: [(a × (b + c)] mod m = [(a × b) + (a × c)] mod m

·                  Identities: (0 + a) mod m = a mod m, (1 × a) mod m = a mod m

·                  Additive Inverse: -a mod m = b mod m such that (a + b) mod m = 0 mod m

·                  Multiplicative Inverse: a^-1 mod m = b mod m such that (a × b) mod m = 1 mod m, where m is a prime number

Fermat’s Little Theorem

A prime number, simply called “prime”, is a positive integer p > 1 that has no positive integer divisors other than 1 and p itself. Since prime numbers have important applications in ECC, the way to find a prime becomes a question of interest.

The simplest way to determine whether a number is a prime is to divide it by all primes less than or equal to the square root of the number. If none of these divide the number evenly, the number is a prime number; otherwise it is a composite number. This method works well for small numbers. However, when checking a large number, it becomes very computationally intensive because the list of the primes less than and equal to its square root maybe unknown and need to compute.

The Fermat’s Little Theorem provides a very efficient way to determine whether a number is a prime. It states that, if p is a prime and p does not divide a, then a^p ≡ 1 (mod p). In another word, if p is a prime, then a^p ≡ a (mod p). Hence the primality of a number p can be determined by calculating a^p mod p for some small number a and checking whether a^p ≡ a (mod p). If a^p ≠ a (mod p), then p is a composite number. Otherwise p is a pseudo-prime to the base a. Since the modular exponentiation can be done very fast, the Fermat’s Little Theorem is very efficient in finding primes.

Rings, Groups, and Fields

While the number theory was presented in section 2.1, this section deals with the abstract algebra which the ECC operations are based on.

Rings

The ring consists of a set  with two operations arbitrarily denoted  (addition) and  (multiplication) on , satisfying the following axioms:

·                  is an Abelian group with identity 0

·                 The operation  is associative. That is,  for all

·                 There exits an identity  with  such the

·                 The operation  is destructive over  i.e.  and  for all

A ring is commutative ring if  for all .

Groups

A group is a set of number with a custom defined arithmetic operation. Two groups used in cryptography are , the additive group of integers modulo a number , and , the multiplicative group of integers modulo a prime number .

The group

The group Additive Group,  has integers range from  to . The basic operation in the additive group is addition, which ends by reducing the result modulo , . The calculation in additive group yield numbers in the group, i.e. the modular reduction by  ensures that all result in the number  and .  This is called closure.

The additive group  used the integer from 0 to 22. A simple example of the  addition is as follow: (5 + 13) mod 23 = 18 mod 23 =18. In , the addition of 10 and 13 is 0 (10+13=0). Adding 15 and 13 is 5 in  (15+13 = 5). The resultant calculations have answers between 0 and 22.

Additive Inverses

Each number  in an additive group has an additive inverse element in the group. The integer  is the inverse element such that  in the group. In , -4 = 19 since (4 + 19) mod 23 = 23 mod 23 =0.

Subtraction operation in

The subtraction operation can be derived from the addition operation. For example, the subtraction can be replaced by the addition  mod . In , 1 - 4 = 1 +(-4) = 1 + 19 mod 23 = 20. The result lies between 0 and 22.

Multiplication operation in

The multiplication operation in  is performed by repeated addition. For example, the multiplication 4(7) in  can be archived by adding together 7 + 7 + 7 +7 mod 23 = 28 mod 23 = 5. The result lies between 0 and 22.

The group

Fields

By far the most relevant and important and important of the elementary construction associated with abstract algebra are fields, in particular the finite field. This is because the elements of these fields are used to embed the plaintext upon. Then, a series of well-defined operations are taken on these elements, outputting elements of the same field from which the ciphertext can be extrapolated.

A field  is a set of elements with two custom defined arithmetic operations namely addition  Fand multiplication . The result of adding two elements or multiplying any two elements of the field has to be in the same set and that they be commutative  and associative . In the set, there has to be a zero element, , such that when adding the zero element of the set, gives you the element you started with . An identity element, 1, of the set is an element when multiply any element gives you the element itself . All elements in the set have additive inverse (for all , there is a  such that ) and all nonzero elements have multiplicative inverse (for all , there is a  such the ). Some other familiar properties in field operations are also required. The additive and multiplicative inverse forever element except zero has no multiplicative inverse. The commutative, associative, and distributive laws as in ordinary arithmetic are obeyed in the set. The laws as summarized which include:

·       commutativity for both  and

·       associativity for both  and

·       distributivity

·       identity for  in  (denoted 0)

·       identity for  in  (denoted 1)

·       inverse for  in

·       inverse for  in

The basic operations of set with two elements  are defined by

, , , ;

, , , ;

in a field. We denote this field .

A field is called finite if it has a finite number of elements. The most commonly used finite fields in cryptography are the field  (where p is a prime number) and the field .

Exercises

Exercise 1: Find the greatest common divisor of 26 and 21 using the Euclidean Algorithm by hand. < 1 >

Exercise 2: Find the greatest common divisor of 81 and 54 using the Euclidean Algorithm by hand. < 27 >

Exercise 3: Find the greatest common divisor of 81 and 51 using the Euclidean Algorithm by hand. < 3 >

Exercise 4: Find the greatest common divisor of 3456 and 1720 using the Euclidean Algorithm by hand. < 8 >

Exercise 5: Find the inverse of 5 mod 26. < 21 >

Exercise 6: Find the inverse of 19 mod 26. < 11 >

Exercise 7: Find the inverse of 13 mod 22. < 17 >

Exercise 8: Find the inverse of 5 mod 26 using the Extended Euclidean Algorithm by hand. < 21 >

Exercise 9: Find the inverse of 19 mod 26 using the Extended Euclidean Algorithm by hand. < 11 >

Exercise 10: Find the inverse of 13 mod 22 using the Extended Euclidean Algorithm by hand. < 17 >