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:

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:
  3. Run the script boneh-chiff.py
  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
  7. Run the script boneh-dechiff.py

Literature:

Participants: Steve Dias da Cruz.

Supervisors: Gabor Wiese.

Difficulty level: Bachelor Thesis.

Results: Bachelor Thesis
Code

FSCT -- University of Luxembourg