Implementation and Performance Testing of Curve Representations

(1)

Elliptic Curve Cryptography

Implementation and Performance Testing of Curve Representations

Olav Wegner Eide

Master’s Thesis Spring 2017

(2)

(3)

Elliptic Curve Cryptography

Implementation and Performance Testing of Curve Representations

Olav Wegner Eide 30th April 2017

(4)

(5)

Abstract

Public-key cryptography makes it possible to create digital signatures and do key negotiation, which is inevitable for today’s commercial and governmental online computer systems. Elliptic curve cryptography (ECC) is a preferred method to implement these services, due to its low computational complexity compared to other modular arithmetic systems such as the Rivest-Shamir-Adleman algorithm (RSA). This thesis investigates how the use of different curve representations impact the performance of the Elliptic Curve Discrete Signing Algorithm (ECDSA) and the Elliptic Curve Diffie-Hellman (ECDH) key-exchange.

This thesis developes a point compression method for Hessian curves over both binary and odd prime characteristic fields, and an addition-subtraction formula for twisted Hessian curves. Using these mechnanisms, the thesis gives a full C implementation of twisted Hessian curves, binary Hessian curves, and binary Edwards curves as an extension to the open source library Miracl [1]. To performance test these curve representations the thesis gives several random curves and presents a detailed test methodology. This methodology lets us compare the complexity of a scalar multiplication in the different curve representations as a number of field multiplications.

Applying this methodology, the thesis compares the already implemented Weierstrass curves and twisted inverted Edwards curves in Miracl with the added curve representations. From these results, twisted inverted Edwards curves over odd prime characteristic fields clearly excel as the best performing curve representation for ECDSA-signature verification. For ECDSA-signature generation and ECDH key-exchange, projective Weier- strass over binary fields using Koblitz curves stands out as the best performing. Further- more, the thesis evaluates the implementation of these curve representations in regards of simple side-channel attack protection.

(6)

(7)

Acknowledgments

First and foremost I would like to thank my supervisor Leif Nilsen for his helpful comments and guidance in the field of cryptography. I would also like to thank him for doing a special mathematics course on elliptic curves in advance of the thesis work.

Furthermore, I would like to thank Certivox for developing Miracl, the library that I have used in my thesis. More specifically, I would like to thank Mike Scott for answering complicated questions regarding Miracl.

I would like to acknowledge Kjetil Birkeland and Aslak Wegner Eide for their thorough proofreading and useful comments.

I would also like to show my gratitude to the people behind the magnificent services of bitbucket.com, wolframalpha.com and mobilefish.com. These served as solid tools during my thesis work. Moreover, I would like to thank the University of Oslo for providing suitable work facilities and access to literature. I also extend my gratitude to my fellow students, in particular Magnus Åsrud and Vetle Volden-Freberg who provided comments and suggestions on the thesis and the production of this document.

Last, but most importantly my biggest gratitude goes to my family and my girlfriend Guro Rudberg. Without their support, kind words and early set alarm clocks this thesis would not have been possible. At last, I would like to dedicate this thesis to my brother Sindre Wegner Eide, whose life was too short.

(8)

(9)

List of Figures

1.1 The hierarchy of ECC over binary fields, figure is created based on p. 15 [2]. 2 2.1 Adding points on an elliptic curve. The figure is generated in Geogebra

with the idea from fig. 2.2 in [17]. . . 15 4.1 The hierarchy of ECC over finite prime fields in Miracl. . . 39 4.2 The hierarchy of ECC over binary fields in Miracl. . . 44 7.1 Chart of the estimated number of M for 1000 point multiplications for

curve representations overFp. . . 70 7.2 Chart of the estimated number of M for 1000 point multiplications for

curve representations overF2ⁿ. NIST K denotes Koblitz curves. . . 71 7.3 Chart of the estimated number of Mfor 1000 double point multiplications

for curve representations over Fp. . . 73 7.4 Chart of the estimated number of Mfor 1000 double point multiplications

for curve representations over F2ⁿ. . . 74

(16)

(17)

List of Tables

2.1 Minimal cofactor . . . 17

5.1 Scale for fields operations inFp . . . 49

5.2 Scale for fields operations inF₂ⁿ . . . 49

5.3 Weierstrass test curves . . . 50

5.4 Edwards test curves . . . 50

5.5 Binary Weierstrass test curves . . . 52

6.1 Running Specifications . . . 57

6.2 Operation Count for doubling, addition and addition-subtraction overFp. Est. gives an estimated number of multiplications at the given bit size level. 58 6.3 Operation Count for doubling and addition formulas overF2ⁿ. Est. gives an estimated number of multiplications at the given bit size level. . . 58

6.4 Estimated number of multiplications (M) for1000ecurve_multin ECDH over Fp. . . 59

6.5 Estimated number of multiplications (M) for 1000 ecurve2_mult in ECDH over F2ⁿ. . . 59

6.6 Estimated number of multiplications (M) for 1000 ecurve_mult2 in ECDSA over Fp. . . 59

6.7 Estimated number of multiplications (M) for 1000 ecurve2_mult2 in ECDSA over F2ⁿ. . . 60

6.8 Results of runningecdhspeedtest.cfor curves over 256 bit prime fields. Note: For Brainpool P-256r1A6=−3. . . 60

6.9 Results of running ecdhspeedtest.cfor curves over 384 bit prime fields. . 61

6.10 Results of running ecdhspeedtest.cfor curves over 512 bit prime fields. . 61

6.11 Results of running ecdhspeedtest2.cfor curves over 283 bit binary fields. 62 6.12 Results of running ecdhspeedtest2.cfor curves over 409 bit binary fields. 62 6.13 Results of running ecdhspeedtest2.cfor curves over 571 bit binary fields. 63 6.14 Results of signing runningecdsaspeedtest.cfor curves over 256 bit prime fields. Note: For Brainpool P-256r1A6=−3. . . 63

6.15 Results of verifying running ecdsaspeedtest.c for curves over 256 bit prime fields. Note: For Brainpool P-256r1A6=−3. . . 64

6.16 Results of signing runningecdsaspeedtest.cfor curves over 384 bit prime fields. . . 64

(18)

6.17 Results of verifying running ecdsaspeedtest.c for curves over 384 bit

prime fields. . . 65

6.18 Results of signing runningecdhspeedtest.cfor curves over 512 bit prime fields. . . 65

6.19 Results of verifying running ecdhspeedtest.c for curves over 512 bit prime fields. . . 66

6.20 Results of signing running ecdsaspeedtest2.c for curves over 283 bit binary fields. . . 66

6.21 Results of verifying running ecdsaspeedtest2.c for curves over 283 bit binary fields. . . 67

6.22 Results of signing running ecdsaspeedtest2.c for curves over 409 bit binary fields. . . 67

6.23 Results of verifying running ecdsaspeedtest2.c for curves over 409 bit binary fields. . . 68

6.24 Results of signing running ecdhspeedtest2.c for curves over 571 bit binary fields. . . 68

6.25 Results of verifying running ecdhspeedtest2.c for curves over 571 bit binary fields. . . 68

7.1 Estimated running time for one single point multiplication using the best performing curve representation over the given field. . . 76

7.2 Estimated running time for one double multiplication using the best performing curve representation over the given field. . . 76

7.3 Estimation of the number of M for one single and double scalar multiplication over F_p, where the cost of doubling is changed to cost of the addition formula. . . 78

7.4 Estimation of the number of M for one single and double scalar multiplication over F₂ⁿ, where the cost of doubling is changed to cost of the addition formula. . . 78

A.1 256-bit random Hessian curve . . . 89

A.4 283-bit random binary Hessian curve . . . 92

A.5 409-bit random binary Hessian curve. Note: #E(F2ⁿ) is composite, the given base point is of unknown order, but#E(F₂ⁿ)∗(x, y) =∞thus the point is on the curve. . . 93

A.6 283-bit random binary Edwards curve named Lucky Number Thirteen . . 94

(19)

Chapter 1 Introduction

Elliptic curve cryptography (ECC) is a public-key cryptography approach that is used in both commercial and governmental computer systems. The two most prominent protocols based on ECC are the Elliptic Curve Discrete Signing Algorithm (ECDSA) for digital signatures, and the Elliptic Curve Diffie-Hellman (ECDH) for key agreement.

Due to the high computational complexity of public-key cryptography, ECC is a preferred method of doing public-key cryptography compared to conventional systems based on modular arithmetic. As ECC is providing a high security level using much shorter key lengths. Several different implementation suggestions have been proposed over the years to further decrease the running time of signing and verification, and encryption and decryption.

1.1 ECC Hierarchy

Due to the complexity of ECC, the implementation suggestions usually aim to improve operations of the ECC hierarchy, as exemplified in figure 1.1 below. A modification to one level of the hierarchy can affect the other levels, and it is crucial to know precisely what the modification will affect and not. Take for example the lowest level operations in the hierarchy. These are field operations and do not affect the rest of the hierarchy if modified, as long as they are correct, see section 2.2 [3]. On the contrary, if an operation of point tripling was added to the second level of the hierarchy, the point multiplication level would need to change as in [4]. Some suggestions also modify the whole hierarchy, such as the proposed edDSA scheme in [5].

The hierarchy only shows the general structure of which operations that are dependent on each other. Operations on some levels may call to a lower level operation far down the hierarchy directly, without going through an intermediate level. For that reason, the hierarchy should not be regarded as an absolute structure of ECC, but rather as a general dependency schematic.

(20)

Figure 1.1: The hierarchy of ECC over binary fields, figure is created based on p. 15 [2].

1.2 Problem Description

This master thesis aims to investigate how the use of different curve representations impact theperformance and security of the ECC-protocols mentioned above.

In ECC we describe curve representations as different mathematical equations to represent the points that builds the elliptic curve. Each such curve representation form a different version of the second level of the ECC hierarchy. In particular this thesis aims to implement and performance test the following curve representations: Weierstrass curves, Edwards curves and Hessian curves over both prime and binary fields.

Performance first of all refers to computational complexity of the formulas for doubling and adding points on the elliptic curve. This thesis proposes that less complexity in these formulas will improve the performance further up the hierarchy. Because point addition and doubling are carried out a large amount of times during point multiplication.

Point multiplication is in turn called by ECDSA during the signing and verification algorithm, or when generating a key for ECDH. Hence, by improving one level, the higher levels of the hierarchy would be affected.

Security can be defined in several different ways, but in the context of cryptography it is usually interpreted as preventing unauthorized access, modification, and inspection of information. The authorization is usually based on the knowledge or possession of a key

(21)

or a token that contains the key. In this thesis, we define security to be at an acceptable level if the number of operations required to retrieve the key is practically infeasible for an attacker (I.e., given the attacker has access to the enciphered text only). Additionally, we investigate whether some of the representations can be revealing information during the execution of them that could be used for side-channel attacks.

1.3 Own Contribution

This thesis develops addition-subtraction formulas for twisted Hessian curves in subsection 2.7.5. Furthermore, it comes up with a method for point compression for twisted Hessian curves and binary Hessian curves using some general mathematical results, see 2.9.2 and 2.9.4. Using these results together with already published material, a full implementation for twisted Hessian curves, binary Hessian curves and binary Edwards curves is given as an extension of the Miracl library, see chapter 4. The thesis also outlines a test methodology for performance testing of curve representations and gives a few random curves that could be useful for performance testing in chapter 5.

1.4 Structure of the Thesis

The thesis will start out by building a mathematical foundation for ECC. Thereafter it will present many concepts of ECC and the selected curve representations. An introduction to some notions of security are also included here. Following this, the thesis will outline some test criteria and give information on the implementation. Lastly, the thesis defines a test methodology and tests, presents and discusses results.

(22)

(23)

Chapter 2 Background Material

This chapter introduces some central background material for the thesis. Firstly, it presents theory on groups and fields. Secondly, it presents the EC by the Weierstrass equation and some of its properties. Following that, will the other curve representations be introduced. Further on, this chapter illustrates how the EC can be used to build cryptographic schemes, before presenting some notions of security around ECC.

2.1 Groups

This section defines groups and some important properties of them. The definitions, theorems and examples in this section have been recompiled from [6]. As they are rather general, we do not include a citation for each single point.

Definition 2.1. A group is a set G, closed under a binary operation ∗, such that the following axioms are satisfied:

1. Associativity:

For all a, b, c∈G (a∗b)∗c=a∗(b∗c).

2. Identity element:

There is an element e∈G such that for all x∈G e∗x=x∗e=x.

3. Inverse:

Corresponding to each a∈G, there is an element a⁰ ∈G such that a∗a⁰ =a⁰∗a=e.

Definition 2.2. A groupG is called abelian or commutative if and only if:

a∗b=b∗afor all a, b∈G.

Much used examples of abelian groups are the set of integers(Z), rational(Q), real(R) and complex(C) numbers under addition. One example where the set and binary

(24)

operation does not form a group, is the set of positive integers(Z⁺) under addition.

This cannot be a group because there is no identiy element, as 0 ∈/ Z⁺. Hence, the second axiom is not fulfilled.

Definition 2.3. IfG is a group, then the order |G|of Gis is the number of elements in G.

Definition 2.4. If a subsetH of a groupGis closed under the induced binary operation of G, then H is a subgroup of G.

Theorem 2.1. Theorem of Lagrange

Let H be a subgroup of a finite group G. Then the order of H is a divisor of the order of G.

Definition 2.5. LetGbe a group anda∈G. If performing the group operation a∗a∗a..

|G| times gives all the elements of the group G. Then a is called the generator or primitive element ofG.

Note that if a does not generate the whole group of G, then ais a generator of the subgroupH < G.

2.2 Fields

As in the former section, this section contains citations of [6]. For the two subsections material is obtained from [3].

Definition 2.6. A field is a setF together with two binary operations+and·, which we call addition and multiplication, defined onFsuch that the following axioms are satisfied:

1. Fis an abelian group under addition.

2. Multiplication is associative.

3. For alla, b, c∈F, the left distributive law,a·(b+c) = (a·b) + (a·c) and the right distributive law(a+b)·c= (a·c) + (b·c) holds.

4. Multiplication is commutative.

5. There is an identity element of multiplication.

6. For all nonzero elementsa∈Fthere exists an unique multiplicative inversea⁻¹∈F such that aa⁻¹ =a⁻¹a= 1.

If only the three first axioms are fulfilled, the algebraic structure is called a ring.

This is the most general algebraic structure with two binary operations. By adding the three last axioms, the algebraic structure is called a commutative division ring, which is better known as a field. The sets of rational, real and complex numbers all form fields. In comparison, integers donot form a field, as e.g. 2does not have a multiplicative inverse.

(25)

Definition 2.7. Given a ring R, if there exists a positive integer n such that n·a= 0 for all a∈R, then the least such positive integer is the characteristic of the ring R. If no such n exists, then R is of characteristic0.

Note that by def. 2.6. a field is also a ring, thus the above definition also applies to fields.

Theorem 2.2. A field F is either of prime characteristic p and contains a subfield isomorphic to Zp or of characteristic 0 and contains a subfield isomorphic toQ.

This theorem states the fieldsZp and Qas building blocks for all fields.

2.2.1 Finite Fields

Definition 2.8. Let F be a field. F is called a finite field or Galois field if and only if F has a finitely number of elements.

Zp is by definition a finite field, as it includes elements{1, ..., p−1}. Qon the other hand, is an infinite set and therefore an infinite field.

Later on, the thesis will refer to Zp as a prime field, or in short Fp. In most bibliography, p is referred to as the modulus, which is used when carrying out usual operations such as addition, subtraction, multiplication and inversion in the field. When these operations are done in the field, they are always done modulop, hence the naming.

A more detailed explanation on how these operations are carried out is given in section 2.3.

2.2.2 Binary Fields

Fields can always be extended to create new fields. In the situation of a finite prime field, Fp can be extended to Fpⁿ. This extension is called a finite extension of degree n. The case is summarized in the theorem below.

Theorem 2.3. There exists a finite field F of orderq if and only ifq is a prime power, i.e., q =pⁿ, wherep is a prime and the characteristic of F andn a positive integer.

1. Ifn= 1, then F=Fp is the prime field as before.

2. Ifn≥2, then Fpⁿ is an extension field of degree n.

Any two finite fields of order q are structurally alike, i.e. there is only one such field up to isomorphism.

Definition 2.9. A finite field of order 2ⁿ or characteristic-two finite fields are called binary fields.

The term of a binary field and the number of elements in such fields are now well established. The next definition explains one way to define the elements in a binary field.

(26)

Definition 2.10. Polynomial Basis Representation

Each element of F2ⁿ is a binary polynomial, i.e. a polynomial with coefficients in F2={0,1}. These polynomials have degree of at mostn−1:

By letting Z2[x] be the polynomial ring with all binary polynomials and f(x) be an irreducible binary polynomial with degreen.

F2ⁿ= Z2[x]/(f(x))

Where the division operation means working modulo the irreducible polynomial f(x), giving the elements: F2ⁿ ={a_n−1xⁿ⁻¹+an−2xⁿ⁻²+...+a1x+a0}, where ai ∈F2 with degree at most n−1

In a computer the polynomial notation can be skipped and only the coefficients need to be stored, ending up with a binary number.

Definition 2.11. Given an element in a binary field F2ⁿ, the element can be expressed in binary form using only the coefficients of: an−1xⁿ⁻¹ +an−2xⁿ⁻² +...+a1x+a0, where ai ∈ F2. Thus, a field element can be represented in binary by the number:

an−1an−2...a₁a₀.

Naturally, the binary representation of the polynomial can be transferred back by multiplying eachai with xⁱ. Note that it also would be possible to transfer the binary representation to the decimal or hexadecimal numeral systems. However, this would complicate the calculation of binary field operations such as addition and multiplication in section 2.4.

The elements could also be represented in normal basis representation:

bn−1x²ⁿ⁻¹+bn−2x²ⁿ⁻²+...+b₁x²+b₀. This form could simplify squaring, but complicate multiplication, p. 3 [7]. This thesis will only use polynomial bases further on.

2.3 Prime Field Operations

This section presents some algorithms to realize field operations in a finite prime field.

Field operations include addition, subtraction, multiplication and inversion modulus a primep, and form the lowest level in the ECC hierarchy. For these algorithms, assume a W-bit architecture, whereW can be8 or16for embedded devices and 32or 64for most computers. To represent larger numbers than W bits, divide thenbits into t=dn/We words and carry out the algorithms on each word. The three first subsections are based on section 2.2 from [3] unless other sources are mentioned.

Additionally, this section includes some theorems to calculate modular square and cube roots, and solving of cubic equations, which are useful for point compression in section 2.9.

(27)

2.3.1 Addition and Subtraction in F^p

Addition modulo p for two n bit numbers can be performed by simple word by word addition. This gives a n+ 1 bit number at most, where the plus one is referred to as the carry bit. To return an element that is less than the modulus, check the size of the resulting number. If it is bigger than the modulus subtract the modulus from the element.

Subtraction can be performed equivalently, but in this setting the carry bit is usually referred to as the borrow bit. Moreover, if the first parameter to the subtraction is less than the second, find the difference of the parameters in absolute value and subtract this from the modulus.

2.3.2 Multiplication and Squaring in Fp

The starting point for an algorithm to multiply two n bit numbers is school-book long multiplication. As commonly known, this method have a complexity O(n²). Many improvements have followed, e.g. the Karatsuba-Ofman method. This method uses a divide and conquer approach and runs in subquadratic time. Squaring can be performed somewhat faster than multiplication and typically runs at half the time of a multiplication, 14.17 [8].

Both multiplication and squaring in Fp requires firstly to do the multiplication or squaring and secondly reduce the result modulo p. If performing several modular multiplications it is possible to reduce the reduction step additionally by using Montgomery form. Montgomery form is the residue class of the field element with respect to someRcoprime to the modulus. Given a field elementa∈Fp, the Montgomery form is aRmodp. Additions, subtraction, multiplication etc. stays as before, but the reduction step is improved. For more details see [9].

The reduction step could also be simplified if the reduction primes have certain properties. If the prime can be written as a sum or difference of a small number of powers of 2, the exponents are multiples of common wordsizes such as 32 and 64. This property makes it possible to write any numberc, where0≤c < p² , as a sum of a few integers with the same bit size asp. To reduce cmodp simply subtractp until less than p. The primes used in the NIST curves have this property, see [10].

2.3.3 Inversion in Fp

Inversion modulus a prime is the most expensive operation to do in a field. However, classic long division does not have higher complexity than multiplication. In practice it usually performs worse. The usual algorithm to calculate inverses over both finite prime fields and binary fields are the extended greatest common divisor algorithm also known as Euclid’s algorithm.

2.3.4 Finding Modular Square Roots

Another field operation that is useful when implementing ECC are modular square roots.

These occur naturally from congruence equations like: x² ≡u (modp) for a nonzero

(28)

u∈Fp. We denote the solutions to this equation√

u (modp). For the solutions to exist u need to be congruent to a perfect square modulo p, due to the square there are two solutions in this case: x=±√

u (modp). To check this condition we check whetheru is a quadratic residue using the following theorem, section 2.4.5 [8].

Theorem 2.4. Euler’s Criterion

Let p be an odd prime. Letu6= 0 (modp) Then

u^p−1² ≡1 (modp) if and only if u is a quadratic residue of p.

u^p−1² ≡ −1 (mod p) if and only ifu is a quadratic non-residue of p.

This criterion makes it easy to determine if the square root exists. The next theorem(Alg. 3.36 in [8]) gives a method to find the root.

Theorem 2.5. Let u be a quadratic residue. Let p≡3 (mod 4) Then√

u=u^(p+1)/4 (modp)

Proof. Becauseu is a quadratic residueu^p−1² ≡1 (modp). x² ≡

u^p+1⁴ 2

=u^p+1² ≡u·u^p−1² ≡u (modp)

The last theorem gives a fast and easy method to calculate the square root as long as we choose a certain prime. Ifp6≡3 (mod 4)then there also exists different methods to find√

u, see section 3.5.1 in [8].

2.3.5 Finding Modular Cube Roots

In the same manner as modular square roots, modular cube roots arise from the equation x³ =u (modp). The solution to this equation is called the cube root of u (modp) often denoted √³

u (modp). The following theorem explains how to find the cube root givenp≡2 (mod 3), p. 704 in [11].

Theorem 2.6. Let p ≡ 2 (mod 3) so all elements of the field is a cube: Then

√3

u=u^(2p−1)³ . Proof.

x³ ≡

u^2p−1³ 3

≡u^2p−1 ≡u^p·u^p−1 ≡u (modp) This proof utilizes Fermat’s little theorem and a corollary(p. 184 [6]):

u^p−1 ≡1 (modp) for a nonzerou∈Z, not divisible by p. u^p ≡u (modp) for any u∈Z, and any primep

(29)

2.3.6 Solving Modular Cubic Equations

There are many ways to solve a cubic equation. Our goal is to find a solution to the Hessian curve equation in subsection 2.7.4, hence the equation is on the form:

Ay³+By²+Cy+D= 0

Where A = 1, B = 0, C = −dxz, D = ax³ +z³. The cubic formula by Cardano [12]

can be used to solve this equation. Simplified, the formula to solve the Hessian curve equation fory is the following:

y = ³ v u u t−D

2 + s

−D 2

2

+ C

3 3

+ ³ v u u t−D

2 − s

−D 2

2

+ C

3 3

Because the curve is overFp, all binary operations need to be done (modp)as described in the former subsections.

2.4 Binary Field Operations

In this section, the thesis discusses some of the algorithms to perform binary field operations. As mentioned earlier, will this section show how the binary representation of the elements leads to fast and easy addition and multiplication of two elements in a binary field. The two first subsections are based on section 2.3 from [3].

As in the former section, this section also presents some theorems to find quadratic and cube roots, and how to solve both quadratic and cubic equations in a binary field.

These theorems are useful for point compression further on.

2.4.1 Addition in F2ⁿ

To add two elements in a binary fieldF2ⁿ, add the two polynomials modulo2. Simplifying the polynomial coefficients to only a binary number, the process becomes bitwise addition modulo 2, also known as the exclusive or operator(⊕). The algorithm adds two n-bit numbers usingt word operations and is fast even for a largen.

Note that only addition is defined for binary fields, because subtraction is equivalent to addition when working modulo2. An easy way to prove this is to create the addition and subtraction tables for F2.

2.4.2 Multiplication and Squaring in F²ⁿ

When multiplying two elements of a binary field, the result could end up having a degree larger thann−1. This contradicts with our definition of the elements inF2ⁿ and breaks the algebraic closure. For that reason, the resulting polynomial needs to be reduced modulo the field polynomial f(x) of degree n as discribed earlier. This would give a polynomial with degree at most n−1. Analogous to prime fields reducing modulo a

(30)

prime, the resulting polynomial is reduced modulo the irreducible field polynomial. Such polynomials exist and are easy to find, see [13] for details.

For software implementations, it is usual to do the multiplication first, e.g. using the Karatsuba-Ofman multiplication. Then the result of the multiplication is reduced giving the resulting polynomial. In hardware implementations this could be done in parallel, hence speeding up the calculation. Binary squaring on the other hand, can be done in linear time by copying each coefficient of the polynomial with degree n−1 to every second coefficient of the resulting polynomial with degree2n−2. Note that initially the resulting polynomial has all the coefficients set to0.

After multiplying or squaring a binary polynomial, it needs to be reduced back to a polynomial with degree at most n−1. By letting the irreducible polynomial be either trinomial or pentanomial, the reduction process can be done word for word. Working modulo certain polynomials can also additionally reduce the complexity.

2.4.3 Finding Square Roots in F2ⁿ

As with prime fields, square roots in binary fields are solutions to the equation x² =u and denoted byx=√

u. Due to the characteristic of the field, this root is a double root.

Moreover, the root always exists, p. 26 in [14] gives the following solution:

Theorem 2.7. Let u∈F2ⁿ for some positiven.

Then√

u=u²ⁿ⁻¹. Proof.

x²=

u²ⁿ⁻¹2

=u^2·2ⁿ⁻¹ =u²ⁿ⁻¹⁺¹ =u²ⁿ =u

2.4.4 Finding Cube Roots in F²ⁿ

Similary, cube roots arise from the equationx³ =u and are denoted √³

u. They can be found in the following manner using [15]:

Theorem 2.8. Let u∈F2ⁿ for an odd n.

Then √³ u=u²

n+1−1

3 is the unique cube root in F2ⁿ. Proof.

x³ =

u²

n+1−1 3

3

=u(²ⁿ⁺¹⁻¹) = u^(2·2ⁿ⁾ u = u²

u =u

The rest of the roots will be in some extension ofF2ⁿ, hence not inF2ⁿ itself. Notice that the theorem only gives cube roots for odd n, this is because n should be a large prime for security reasons, thus odd. For cube roots with an evennwe refer to [15].

(31)

2.4.5 Solving Quadratic Equations Over F²ⁿ

The IEEE 1363 standard gives a method to solve quadratic equations on the form z² +z = α for both a even and odd n, A.4.7 [16]. Because n should be prime and larger than2, see section 2.12.2, this section only shows the method for an odd n. Theorem 2.9. Given an equationz²+z=α over F2ⁿ for an odd n.

A possible solution for z can be given by the half-trace of α:

z=

(n−1)/2

X

i=0

α²²ⁱ

Ifz²+z=α, thenzis the solution and the other solution isz+1. Otherwise, no solution exists.

2.4.6 Solving Cubic Equations Over F2ⁿ

This subsection shows how to solve an equation on the form Ay³+By²+Cy+D= 0 over F2ⁿ, as showed in [15]. As for finite prime field, the goal is to solve the Hessian equation, but this time the binary version later introduced in subsection 2.8.6. Again, let nbe odd, andA= 1, B= 0, C =dx, D=c+x³, so the equation becomes:

y³+dxy+ c+x³

= 0 Lety=z+^dx_z . This gives the equation:

z⁶+ x³+c

z³+ (dx)³

z³ = 0

To find the solution to this equation, consider only the numerator, and letu=z³ to get:

u²+ x³+c

u+ (dx)³ = 0 Letu=v x³+c

v²+v= (dx)³ (x³+c)²

If this equation does not have a solution using the method above, the cubic does not have a solution over F2ⁿ. Otherwise, the equation has two solutions v₁ and v₂. Using these solutions and reversing the above substitutions, the numerator becomes:

z³+e

z³+f

f or e=v1 x³+c

, f =v2 x³+c

Now the solutions ofzcan be obtained by finding the unique cube roots ofeandf using theorem 2.8. A solution to the original equation for y is now available by substituting back with the cube roots ofeand f:

y =√³ e+ dx

√3

e

(32)

2.5 Elliptic curves

Elliptic curves can be applied to many mathematical problems. This section will introduce the EC for usage in cryptography using chapter two of [17] as a main source.

The elliptic curve(E) is presented as the following: E is the graph given by the equation usually named theshort Weierstrass equation:

y²=x³+ax²+b

Where the variables x and y, and the constants a and b belong to a finite field K. In most cases, from a finite prime field Fp, where p > 3. The case of a binary field F2ⁿ is treated later in section 2.8. To denote that a curve E is defined over a finite field, the notationE(K), where K is the finite field, is often used. In addition, the cubic on the right side of the equation is restricted to having distinct roots. This happens exactly when the discriminant is different from zero:

4a³+ 27b² 6= 0

An equation with distinct roots gives a curve with no singularities or cusps, also the tangent is well defined at all points. This property makes is possible to build a group operation for the EC over finite fields.

2.5.1 The Group of Points on the Elliptic Curve

Given a curve E(K) with the restriction of a nonzero discriminant from the former section, it is now possible to define an abelian group with elements that are points(x, y) onE(K). I.e.,x, yfulfills the short Weierstrass equation. Rather than giving a full proof of all the group axioms, this section outline some useful results and consequences that are needed further on in the thesis.

The group operation can graphically be stated as the following: Take a pointP1 and P₂ on E(K)and draw the line through them. The line intersectsE in exactly one other point,P₃⁰, now reflect this point across the x-axis and getP₃. P₃ is the result of adding the two pointsP1 and P2 together.

(33)

Figure 2.1: Adding points on an elliptic curve. The figure is generated in Geogebra with the idea from fig. 2.2 in [17].

As this method would work on a general basis, there are still many points on the curve where it will give some undefined results. Take for example, if P1 = P2 with y-coordinate equal zero, then the tangent line would not intersect any other point on E(K), other than the point itself. For that reason, the point at infinity(∞) is added as the identity element. This point can be viewed as being the top and bottom of they-axis.

Moreover, does the point act as a zero element defining P +∞ =P for allP ∈E(K), and carefully defines the points that are not defined by the general group operation. A proper deriving of the formula with all cases can be found in chapter two of [17]. Below follows a restatement of the full group operation.

Theorem 2.10. The elliptic curve group operation Let E be the elliptic curve defined by y²=x³+Ax+B.

Let P1= (x1, y1) and P2 = (x2, y2) be points on E with P1, P26=∞.

Define P1+P2=P3 = (x3, y3) as follows:

1. Ifx1 6=x2, then

x₃ =m²−x₁−x₂, y₃=m(x₁−x₃)−y₁, where m= _x^y²^−y¹

2−x₁. 2. Ifx₁ =x₂ buty₁ 6=y₂, then P₁+P₂ =∞.

3. IfP₁=P₂ andy₁ 6= 0 then

x₃ =m²−2x₁, y₃ =m(x₁−x₃)−y₁, where m= ^3x_2y²¹^+A

1 . 4. IfP₁=P₂ andy₁ = 0, thenP₁+P₂=∞.

(34)

Additionally, define: P +∞=P for all points P on E.

2.5.2 Negation of a Point

The negation of a pointP on a Weierstrass curveE is equivalent to finding the inverse P⁰ so that P +P⁰ =∞. This point is also called the negative of a point, or −P. By following the second case from the group operation formula above, notice that two points P₁ = (x₁, y₁), P₂ = (x₂, y₂), where x₁ = x₂ and y₁ 6= y₂ always gives P₁+P₂ = ∞. Because x₁ = x₂, y₁ and y₂ are the two roots of the Weierstrass equation, so that y2=−y₁. Hence, following the group operationP⁰ = (x1,−y₁)is the inverse point ofP. The negative of a point is also defined for y₁ = y₂ = 0, because 0 acts as its own additive inverse. This special case of the negation formula is equivalent to the fourth case of the formula from above. The negation rule is summarized in the following theorem.

Theorem 2.11. Given a point P = (x, y), the inverse P⁰ of that point is P⁰ = (x,−y) Notice that this formula only works for the short Weierstrass equation, for curves with other curve equations, negation of a point is handled differently.

2.5.3 Additon and Subtraction of a Point

In some situations, as shown later, it is desirable to calculate both the addition of two points P₁+P₂ and the subtraction P₁ −P₂ at the same time. Naively, this is possible by two point additions, one whereP1+P2 as with point 1 in theorem in 2.10, and one equivalent addition only withP₂ negated. However, the negation process of a point only changes the y-coordinate. Thus, some of the intermediate calculations could be reused.

In Miracl, the following formula saves one inversion:

Addition and Subtraction P₁+P₂, P₁−P₂

Let(x1, y1) + (x2, y2) = (x3, y3) and(x1, y1)−(x2, y2) = (x⁰₃, y⁰₃) Thent1 =y2−y1, t2= _x ¹

2−x1, m=t1·t2

x₃ =m²−x₁−x₂, y₃ =m(x₁−x₃)−y₁ t⁰₁=y2+y1, m⁰=t⁰₁·t2

x⁰₃ = (m⁰)²−x₁−x₂, y⁰₃=m⁰(x₁−x⁰₃) +y₁

2.5.4 Counting Points on an Elliptic Curve

After choosing parameters and finding a field to define the EC for, the number of points on that curve need to be counted. This number is usually written #E(F). Hasse’s theorem(thm. 4.2 in [17]) gives an rough interval on#E(F).

Theorem 2.12. Hasse’s theorem

Let E be an elliptic curve over a finite field Fq. Then the order ofE(Fq) satisfies

|q+ 1−#E(Fq)| ≤2√ q

(35)

The expanded equation becomes:

q+ 1−2√

q ≤#E(Fq)≤q+ 1 + 2√ q

This interval only gives a rough guideline and the exact number of points can be calculated by an deterministic polynomial-time algorithm known as Schoof’s algorithm [18]. The reason for counting the number of points is that the curve should have prime order or close to prime order. If the order of the group is prime, then no subgroups can exist, making the small subgroup attack impossible, see section 2.12.

Describing the advanced and time consuming process of curve parameter generation is beyond the scope of this thesis. For more on this topic, see some of the most used curve recommendations: NIST-curves [10], Brainpool-curves [19] and “Nothing Up My Sleeve” (NUMS) curves [20].

2.5.5 Cofactor

For some curve representations it is impossible to find a curve which has#E(K) prime.

Still, these curves are used in practice, but#E(K) is then restricted to being a product of a large prime and a small factor that is named the cofactor:

Definition 2.12. The cofactor(h) is given by h = ^#E(K)_n , where n is a prime and the order of the base point P = (x_p, y_p).

Note that a base point is the same as a generator as defined in definition 2.5. This way of presenting the curve parameters can be found in many works, e.g. [21]. Table 2.1 shows the minimal cofactor of the following curve representations.

Curve Representation Cofactor(h) short Weierstrass 1

Hessian 3

Edwards 4

Table 2.1: Minimal cofactor

For more on the cofactor in a specific curve representation, see their respective subsections. A further discussion on how the cofactor affects security and efficiency, is given in section 3.1.2.

2.5.6 Twists

Given a curve with carefully selected parameters and a counted number of points that are prime or a product of the cofactor and a prime, the curve is usually safe to use. However, this curve could be highly inefficient. In some curve representations, a few operations can be saved if some of the parameters are small or constant. To achieve this, take the safe curve E(Fq) and find its quadratic, or sometimes even quartic twist, denoted E⁰(Fq).

(36)

When calculating the twist some of its parameters can be set to optimize performance in the doubling and addition formulas, and then simply calculate the rest.

After the twist of a curve is calculated, a recount of the number of points on the twist is not necessary. Given#E(Fq) =q+ 1−a, the number of points on the twist will be

#E⁰(Fq) = q+ 1 +a. Thus, given the number of points on one curve, the number of points on the twist can easily be calculated, see p. 108 in [17].

NIST [10] and NUMS [20] among others, have exploited this property to find a short Weierstrass curve with a twist whereA=−3, as this saves a few operations when adding points. There are also many security notions tied to the twist of a curve. For more on this topic, see the Twist Security section of [22].

2.6 Coordinate Systems

There are many ways to present elliptic curves and the arithmetic on them. Section 2.5 showed a classic approach to the construction of an elliptic curve. Further on, section 2.5.1, presented how to add two points together with the group operation, the coordinates used in these formulas are often called affine coordinates. This section presents an alternative coordinate system for representing the points on the curve, and how the group operation changes with respect to this coordinate system.

2.6.1 Projective Coordinates

Earlier, the point at infinity was introduced as an addition to the elements in F_q, but with projective coordinates this can be defined as an actual point. Projective coordinates are lines through the origin of a two-dimensional vector space, this space is called the projective space.

Definition 2.13. A line in a projective space is given as a triple of(x, y, z), not all zero, where x, y, z ∈ Fq. Two lines (x1, y1, z1) and (x2, y2, z2) are equivalent if there exists a nonzero element a∈Fq such that (x₁, y₁, z₁) = (ax₂, ay₂, az₂).

Because the projective coordinates represent lines and not points, the notation (x:y:z)is commonly used, although they are still referred to as points.

To go from affine coordinates (x, y) to projective coordinates (x:y:z), let z= 1so that(x, y)→(x:y : 1). Equivalently, projective coordinates can be translated to affine coordinates: (x:y: 1) → (x, y). These points are the finite points in the projective plane. In the cases where z 6= 1 and z 6= 0, the projective point can be normalized by dividing by z: (x:y:z) = (x/z :y/z : 1). Note that the inverse of z will exist for all nonzero z∈Fq. The projective points(x:y: 0) are called the points at infinity. These points map to the affine point∞. In this way, the point at infinity(∞) have clearly been defined as a point in the projective plane. For a more thorough description we refer to section 2.3 of [17].

(37)

2.6.2 Homogeneous Polynomials

In order to use projective coordinates for points on the EC, the curve needs to be a polynomial F(x, y, z). Additionally, to ensure the equivalence definition of two points, the polynomialF(x, y, z) needs to be homogeneous.

Definition 2.14. A polynomial is homogeneous of degree nif it is a sum of terms on the form bxⁱy^jz^k with b∈Fq andi+j+k=n. A polynomial can be made homogeneous by inserting appropriate powers of z.

Take for example the short Weierstrass equation form above, this can be written as a polynomial f(x, y) =y²−x³−Ax−B. The homogeneous version of this polynomial would be F(x, y, z) =y²z−x³−Axz²−Bz³.

2.6.3 Double and Add Formula for Projective Coordinates

The formula for adding and doubling a point in projective coordinates can be obtained by inserting x= ^x_z andy = ^y_z into the affine formula. This clears the denominators and cancels out the computational expensive inversion, p. 42 [17].

There exists a huge amount of formulas for addition and doubling in projective coordinates. Below the thesis gives the addition and doubling formulas for what is called Jacobian projective coordinates for the curve: y² =x³+axz⁴+bz⁶. The point(x:y:z) on this curve corresponds to the affine point x/z², y/z³

, p. 90-91 [23]. These are the formulas that will be used further on in this thesis.

Doubling

If input point is ∞then this point is ∞. A= 3 x1−z²₁

x1+z₁²

, B = 2y1,

z₃=B·z₁, C=B², D=C·x₁, x₃ =A²−2D, y₃ = (D−x₃)A−^C₂²

Addition (Note: these are the full formulas, if one point is normalized they can easily be simplified.)

If one input point is ∞then this point is ∞.

A1 =z₁², B1=z1·A1, C1=x2·A1, D1 =y2·B1, A2=z₂², B2 =z2·A2, C₂=x₁·A₂, D₂ =y₁·B₂, E =C₁−C₂, F =D₁−D₂

IfE = 0 then:

if F = 0 then use the doubling formula above.

else return∞.

z3=z1·z2·E, G=E², H=E³, I =C2·G, x3=F²−(H+ 2I), y3 =F(I−x3)−D2·H

Addition and Subtraction P1+P2, P1−P2

Miracl uses the same addition-subtraction formula as affine coordinates, but with normalized points. The normalization process adds one inversion, one squaring and three

(38)

multiplications per point. As a result, the cost of the addition-subtraction operation may be higher than two separate additions, depending on the scale of the field operations.

2.7 Curve Representations Over F

^p

Until now the thesis have only considered the Weierstrass equation, but there are many equations which are birationally equivalent to this equation. This section will present the curve equations and their doubling and addition formulas which will be implemented further on. For these equations, only the projective versions of the formulas are presented.

2.7.1 Types of Formulas

Before this section gives addition and doubling formulas for different curve representations, this subsection defines two important concepts that explains how the formulas can be used and which input they can handle. Both of the following definitions are taken from the abstract of [24].

Definition 2.15. Complete Formula

A formula iscomplete if the formula works for all inputs without change.

Definition 2.16. Unified Formula

An addition formula is unified if the addition formula can be used to double a point without changing the formula.

The formulas for addition and doubling in subsection 2.5.1 and 2.6.3 are complete, as they handle all types of inputs. On the contrary, the formulas are not unified. E.g.

using the affine addition formula for doubling would cause division by zero.

2.7.2 Edwards Curves

Edwards curves is named after Harold Edwards after his developments in [25]. These curves have later been used in ECC and many performance and security studies have followed. One such study is the Inverted Edwards form introduced by Bernstein et al.

in [24]. Later theTwisted Edwards form was introduced, this form includes more curves than the original Edwards curves [26]. The same work also shows that Twisted Edwards curves are birationally equivalent to Montgomery curves. As a limitation, the twisted Edwards curve needs to have a point of order 4, i.e. minimal cofactor equal 4, and characteristic 6= 2, for more details see [26]. The same source also gives the projective inverted twisted Edwards curve equation used in Miracl:

x²+ay²

z² =x²y²+dz⁴ Negation of a point on this curve is found in section 2:

Given a point(x:y:z), withz6= 0 the inverse of that point is defined: (−x:y:z:). If z= 0then this is the point at infinity.

(39)

Note that the point(x:y:z:)on a twisted Edwards curve corresponds to the affine point (z/x, z/y) on the twisted inverted Edwards curve as shown above. This is useful when transforming a point on a Twisted Edwards curve to a point on twisted inverted Edwards curve.

2.7.3 Double and Add Formula for Twisted Inverted Edwards Curves Below are the formulas for unified addition, and doubling on an inverted twisted Edwards curve from section 6 in [26]. The addition-subtraction formulas is directly from Miracl [1].

Addition

A=z1·z2, B =d·A², C =x1·x2, D=y1·y2, E=C·D, H =C−a·D, I = (x₁+y₁)·(x₂+y₂)−C−D,

x3= (E+B)·H, y3= (E−B)·I, z3 =A·H·I.

Doubling

A=x²₁, B =y₁², U =a·B, C=A+U, D=A−U, E = (x1+y1)²−A−B, x3=C·D, y3=E· C−2d·z₁²

, z3 =D·E.

Addition and Subtraction P1+P2, P1−P2

LetA, B, C, D, E, H be as in the addition formula. Additionally, letF =x1·y2, G= x₂·y₁. ThenP₁+P₂ = (x₃:y₃ :z₃) is given by:

x₃= (E+B)·H, y₃= (E−B) (F+G), z₃=A·H·(F+G). P1−P2 = (x⁰₃ :y⁰₃:z₃⁰) is given by:

H₁=C+a·D

x⁰₃= (E−B)·H₁, y₃⁰ = (E+B) (F −G), z₃⁰ =A·H₁·(F −G).

2.7.4 Hessian Curves

Hessian curves origin from Otto Hesse in 1844, p. 90 in [27]. In recent time, twisted Hessian curves have been suggested as a curve representation for ECC by Bernstein et al. in [28]. Assuming there is a point of order 3, i.e. cofactor 3, Weierstrass curves and Hessian curves are birationally equivalent, for a detailed explaination of this we refer to section 3 of [29]. In this thesis we will use the formulas from Bernstein et al. and the following projective representation of the curve:

ax³+y³+z³ =dxyz

Equivalently as for Weierstrass curves, Hessian curves have the discriminant requirement:

a 27a−d³ 6= 0

The point at infinity in this curve representation will be(0 :−1 : 1). Hence, the algorithm for normalizing a point will be shifted to the following:

All points with x= 0 will be points at infinity. If not, the point can be normalized by dividing with x: (1 :y/x:z/x).

Implementation and Performance Testing of Curve Representations

Elliptic Curve Cryptography