## Elliptic Curve Cryptography and the Weil pairing

Goal:

An elliptic curve is an algebraic curve equipped with an abelian group law. Elliptic curves are very important objects in current number theory. Apart from this, they are also used in cryptography (e.g. in the German identity card and the German passport). For this application, one uses elliptic curves defined over big' finite fields. The abelian group is then a big' finite abelian group. If one chooses the curve well, this group can be cyclic, generated by a point P. Any other point Q is then of the form Q = mP for some m \in Z. Given Q and P, it seems to be very hard to compute m. This is called the Discrete Logarithm Problem for elliptic curves. Let us denote the elliptic curve by E and the neutral element O (it is also natural to call it \infty) and let n \in N. The n-torsion points are defined to be the set of points of order a divisor of n. André Weil defined a pairing on E[n]. This pairing has many very nice features.

This subject has several components:

• Expose the essentials of elliptic curves.
• Define the Weil pairing.
• Expose how to compute with elliptic curves (e.g. the group law) and how to compute the Weil pairing.
• Implement elliptic curves and the Weil pairing.
• Expose and implement a cryptographic scheme using elliptic curves. It is possible, but not necessary, to use a pairing based scheme.

A short summary:

1. A short description of some basic ideas about elliptic curves and their properties. Essentially, about the group law and the computation of the addition inside an elliptic curve, which will later be used in different ways.
2. Definition of torsion points and divisors, which will be necessary for the most important part of the thesis: the Weil pairing and its application in cryptography. It follows a presentation of two different possible definitions of the Weil pairing. The first one is easier to proof, but slower to compute when trying to implement. The second one is much faster for computations, but needs a little bit more work to be proven, which is why it will be shown that both Weil Pairing definitions are equivalent. Afterwards, it will follow an introduction of the Miller algorithm, which will be necessary for the implementation and calculation of the Weil Pairing.
3. Presentation of some applications of the Weil Pairing and elliptic curves. There are some possible attack methods to break cryptographic applications, which are using elliptic curves, but on the other side, one can guarantee a high security level by applying the right methods and pairings to a system. The MOV attack and the Boneh-Franklin scheme will be presented.
4. A python implementation of elliptic curves, finite prime fields, the Weil pairing and the Boneh-Franklin scheme. Of course, there are still possible improvements to be done, this why the reader is invited to analyze the implementations before using them for some real applications.

A tutorial and examples on how to use the different scripts:

1. ModP(integer,prime)

ModP(3,7)
Creates the element 3 mod 7.

2. Polynomial([list of coefficients],prime)

Polynomial([ModP(1,p),ModP(0,p),ModP(1,p),ModP(2,p)],p)
Creates the polynomial 1+0*x+1*x^2+2*x^3 with coefficients in the field F_{p}.

3. FiniteField(p,1)

Creates the finite field F_{p}.

4. FiniteField(prime,power of prime, polynomial)

FiniteField(p,2, Polynomial([ModP(1,p),ModP(1,p),ModP(1,p)],p))
Creates the finite field F_{p^2} modulus the polynomial 1+1*x+1*x^2 with coefficients in F_{p}.

5. Fp2([list of coefficients])

Fp2([0,1])
Creates the element 0+1*x of the finite field Fp2, defined by the previous example.

6. EllipticCurve(ModP(a,p),ModP(b,p))

Creates the elliptic curve of the form y^2 = x^3 + a*x + b with coefficients in the field F_{p}.

7. Point(ellipticCurve, first coefficient, second coefficient)

Point(E, , ModP(a,p),ModP(b,p))
Creates the point (a mod p, b mod p) on the elliptic curve E.

8. EllipticCurve(a,b, finiteField)

EllipticCurve( Fp2([0]),Fp2([1]), Fp2)
Creates the elliptic curve of the form y^2 = x^3 + 0*x + 1 with coefficients in the finite field Fp2.

9. Point(ellipticCurve, first coefficient, second coefficient)

Point(E, , Fp2([0]),Fp2([1])) Creates the point on the elliptic curve E with coefficients in Fp2.

10. Infinity(EllipticCurve)

Infinity(E)
Creates the element infinity on the elliptic curve E.

11. WeilPairing(Point, Point, integer)

WeilPairing(Q,P,m)
Calculates the Weil Pairing of the Point P and Q of order m.

A tutorial and an example on how to use the python implementation of the Boneh-Franklin scheme:

1. Open the file boneh-chiff.py
2. Fix the parameters, which you want to use:
• l = int(56453) ----- is the basic prime number
• p = int(int(6) * l - int(1)) ----- is calculated by the script; the prime number over which we will work. It is important that p is a prime number as well
• Fp2 = FiniteField(p,2, Polynomial([ModP(1,p),ModP(1,p),ModP(1,p)],p)) ----- creates the field F_{p^2} with irreducible polynomial 1+x+x^2
• b = Fp2([0,1]) ----- define a third root of unity of F_{p^2}, in this case it is 0+x
• s = int(13) ----- in F*_{x}; choosen by the authority
• r = int(7) ----- in F*_{x}; choosen by the party, which want to encrypt the message
• One could fix the base point P. By default, it is calculated by an algorithm
3. Run the script boneh-chiff.py
• Enter an ID. This ID will generate a point DID on the elliptic curve. These coordinates need to be passed to the third party for the decryption.
• Enter the message, which you want to encrypt.
4. An output file has been created by the previous run of the script. It contains some necessary information for the decryption.
5. Open the file boneh-dechiff.py
6. Adapt the parameters to the changes done in the file boneh-chiff.py
• l = int(56453) ----- is the basic prime number
• p = int(int(6) * l - int(1))
• Fp2 = FiniteField(p,2, Polynomial([ModP(1,p),ModP(1,p),ModP(1,p)],p)) ----- use the same irreducible polynomial
• b = Fp2([0,1]) ----- define the same third root of unity of F_{p^2}
• cypherACordX = 240099 ----- depends on the base point choosen in the first script. check the created output file
• cypherACordY = 283222 ----- depends on the base point choosen in the first script. check the created output file
7. Run the script boneh-dechiff.py
• Enter the coordinates of the point DID
• Enter the encrypted message
• The script will output the decrypted message

Literature:

• Lawrence Washington: Elliptic curves, number theory and cryptography, CRC Press. This is the main reference; one only needs some small parts of it.
• Hankerson, Menezes, Vanstone: Guide to Elliptic Curve Cryptography, Springer. This book may be useful for practical aspects.
• Wikipedia etc. There's a wealth of useful information on the web, which may be used, if properly accredited.

Participants: Steve Dias da Cruz.

Supervisors: Gabor Wiese.

Difficulty level: Bachelor Thesis.

Results: Bachelor Thesis
Code