Advanced topics in cryptology

-----------




Announcements Literature CourseProjectHomework









Tanja Lange

Department of Mathematics

Technical University of Denmark

Matematiktorvet - Building 303

DK-2800 Kgs. Lyngby

Denmark

Room 152

Phone: +45 4525 3007

Voice mail: +45 3696 7248

Fax.: +45 4588 1399

e-mail:tanja@hyperelliptic.org

This is an overview of the topics taught in the course 01427 - Advanced topics in cryptology at DTU. Details are filled in as time permits.

The topics of this course are related to elliptic curves in cryptography. Since the curves are defined over finite fields and for applications not only prime fields are considered we start with background on finite fields and their implementation. We then consider curves over arbitrary fields and define the divisor class group. Examples are elliptic and hyperelliptic curves. The most efficient implementations of the group arithmetic depend on the type of curve and characteristic of the field. For elliptic curves over finite fields we present different coordinate systems in even and odd characteristic. A topic which gained a lot of attention recently is pairings on elliptic curves. We introduce the Tate pairing and show its use in protocols together with implementation details. Finally we introduce side-channel attacks and present countermeasures against simple and differential attacks.

Announcements

03. April

This meeting takes place in the computer room of building 303. It is entirely devoted to the questions on th project on elliptic curves over optimal extension fields.

09. May

This Tuesday is a Monday! Little bits left out before - this lecture is not relevant for the exam. However, this lecture is the ideal time to ask your questions.

10. May

Exam. The first candidate starts at 08:00.

Literature

There is not a single textbook which presents all this material. Clearly I cannot resist high-lightening the Handbook of Elliptic and Hyperelliptic Curve Cryptography (CRC Press, 2005) which contains basically all material covered in this course - and much more. So buying this book is definitely overkill unless you would like to work more in this topic. The same holds true for all the literature presented below - except for the free online resources.

Finite fields Elliptic curves (does often contain some material on finite fields, too). Lecture notes (in German)on a course on Discrete Mathematics II which I held in Bochum, 2003 are available here. They cover most of what we did on finite fields and a bit of elliptic curves.

I organized two summer schools on elliptic curve cryptography, lecture notes are available here.

Project

Implementation of elliptic curves over optimal extension fields. The deadline has been extended to Thursday, April 27th.

Exam

The oral exam takes place on May 10th, starting early in the morning.

Class notes

General overview of course. Reminder of groups, rings, fields and vector spaces. For cryptography finite groups are most interesting. Highlights: Theorem of Lagrange, possible orders of elements giving the group order, how to find an element of given prime order.

3.Finite fields

Def. 3.1 Characteristic.

Lem. 3.2 K field with Char(K)>0 then Char(K)=p for some prime p.

Def. 3.3 Prime field (or prime subfield).

Th. 3.4 K finite field then there exists a prime p so that K has subfield isomorphic to Fp.

Cor. 3.5 There is (up to isomorphism) only one field with p elements.

Th. 3.6 K finite field then there exists a prime p and an integer n so that |K|=pn.

This describes the additive structure of finite fields. Now we consider the multiplicative structure.

Th. 3.7 Let |K|=pn, for K finite field. The multiplicative group K* is cyclic. (Proof via roots and exponent of the group).

Def. 3.8 Generator of K* is called primitive element. (Does always exist, leads to representation K={0, g, g2, g3 ...})

Def. 3.9 Irreducible polynomial.

Th. 3.10 K finite field, K[x] abelian ring with 1, Euclidean algorithm works; is even ring with unique factorization.

Th. 3.11 K finite field. Then the following two are equivalent

Examples:
f=x, f=x^2+1, f=x^2+x+1, f=x^4+x^2+1 over F2. Attention: the last polynomial does not have a root but is not irreducible.

Def. 3.12 α in K root of f ∈ K[x] then (x-α)|f(x)

Def. 3.13 Splitting field of a polynomial (is unique up to isomorphism).

Def 3.14 Adjoint K(&theta), minimal polynomial mθ(x).

Examples:
R(i), F2(&alpha) with (&alpha) root of x2+x+1.

Th. 3.15 θ ∈ F for F an extension field of K. Let g(x) be the minimal polynomial of θ over K and deg(g)=n. Then: Le. 3.16 α, β ∈ F roots of f∈ K[x], f irreducible over K then K(α)≅ K(β).

Th. 3.17 F finite field with q=pn. Then
xq-x=Πa ∈F (x-a).
F is the splitting field of xq-x.

Th. 3.18 Existence and uniqueness of finite fields: for each prime p and each integer n there exists up to isomorphism exactly one finite field of order pn.

Notation: Fpn.

Example:
Why is F4 not contained in F8? Try to find an element a satisfying a2+a+1 (such an element exists in F4) in the field F8. This fails.

Le. 3.19 f ∈ Fq[x] irreducible, α root of f in splitting field. Let h∈ Fq[x]. Then one has h(&alpha)=0 if and only if f|h.

Le. 3.20 f ∈ Fq[x] irreducible of deg(f)=m. Then f|xqn if and only if m|n.

Cor. 3.21 f ∈ Fq[x] irreducible of deg(f)=m. Then Fqm is splitting field of f. xqn-x is defining equation of Fqn.

Examples:
Find the splitting fields of x2+x+1, x3+x+1 and x3+x+1 over F2.

Cor. 3.22 f, g irreducible, deg(f)=deg(g) then their splitting fields are isomorphic.

Th. 3.23 xqn is product of all irreducible polynomials over Fq whose degree divides n.

Cor. 3.24 Let N(d) be the number of irreducible polynomials over Fq of degree d. Then qn= Σ d|ndNq(d). In particular for all d, q we have N(d) >0.

Th. 3.25 f ∈ Fq[x] irreducible of deg(f)=m. If α is root of f over Fqm then all roots of f are given by α αq, αq2, αq3, ... , αqm-1.

Def. 3.26 Conjugates

Examples:
R(i)≅R(-i).

Each of the powers of &alpha in 3.25 generates the same field.

Def. 3.27 Automorphism of Fqn over Fq.

Th. 3.28 All automorphisms of Fqn over Fq are given by the maps σ0, σ1, ...,σn-1, where σi(α)=αqi.

Def. 3.29 Trace Trqn:Fq.

Le 3.30 Trqn:Fq maps to Fq. Relation with coefficients of minimal polynomial of α.

Le. 3.31 Properties of trace map (additivity, scalars from ground field).

Def. 3.32 Norm Nqn:Fq.

Le. 3.33 Properties of norm.

Excurs: How to check that a polynomial is irreducible? Rabin test f ∈ Fq[x] of deg(f)=n irreducible if and only if Example:
Find an irreducible polynomial of the form x3-a over F7. This can still be done by a naive approach since a polynomial of degree 3 is irreducible if and only if it does not have a root, i.e. if a≠ 0,1,-1.

Use of Magma online calculator makes it easy to implement the Rabin test (and even comes with a built-in in function IsIrreducible).

Let n be prime. An irreducible binomial of degree n over Fq exists if and only if n|q-1 (proof via existence of n-th roots of unity).

4. Background on curves

Def. 4.1 An/K affine space of dimension n.

Def. 4.2 An(L) for L extension field of K contained in algebraic closure.

Def. 4.3 Pn/K projective space of dimension n. Relation, pictorial description.

Last was definition of projective n space. Still open: topology.

Def. 4.4 Let f ∈K[x1,x2,...,xn]. Define topology by using Df={P ∈ An | f(P)≠ 0} as basic open sets.

Def. 4.5 Consider an ideal I⊆ K[x1,x2,...,xn]. The sets VI={P ∈ An | f(P)=0 for all f ∈ I} are closed sets.

A set S is closed if there exists an ideal I⊆ K[x1,x2,...,xn] with S=VI.

This topology is called the Zariski Topology.

Example:
An and the empty set are both - open and closed - as they are the roots of the polynomials 0 and 1.

In the projective space we cannot work with general polynomials/ideals since a point is an equivalence class.

Def. 4.6 A polynomial f ∈ K[x0,x1,...,xn] is called homogeneous of degree d if and only if f(λx0,λx1,...,λxn)= λ λdf(x0,x1,...,xn).

Def 4.7 Let f ∈ K[x0,x1,...,xn] be a homogeneous polynomial. Then Df={P\in Pn|f(P) ≠ 0} is well defined (since f is homogeneous). Use Df as basic open sets.

Def 4.8 An ideal is homogeneous if it is generated by homogeneous polynomials, i.e. it contains only homogeneous polynomials.

Def 4.9 Let I be a homogeneous ideal and I≠ <x0, x1, ... ,xn >. Let VI={P\in Pn|f(P) = 0 for all f ∈ I }.

A set S ⊂Pn is closed if it is the set of simultaneous zeros of homogeneous polynomials in K[x0,x1,...,xn].



Example:
Let Ui=Dxi, i.e. Ui={(x0:x1:.... :xn) in Pn|xi≠ 0} and Wi=V(xi), i.e. Wi={(x0:x1:.... :xn) in Pn|xi= 0}.

The sets Ui are open, Wi are closed.

Def. 4.10 We look at varieties, that are affine (projective) closed sets S that are irreducible, i.e. cannot be expressed as union S=S1⊃S2 of two proper closed affine (projective) sets.

Th. 4.11 VI is an affine (projective) variety if and only if I is a (homogeneous) prime ideal in K[x1,x2,...,xn] (K[X0,X1,...,Xn])

Example:
n=2, I=<x1>

VI={(0,a)}, where a is in the algebraic closure of K, is a variety. The corresponding projective variety must consist of the points (X0:0:X2) for which not both X0, X2 are zero. E.g. I=<X1 does the job since it is a homogeneous ideal which contains exactly these points.

Def. 4.12 Let V be an affine (projective) variety. The dimension is defined to be the supremum on the length n of all chains
V=S0⊃S1⊃ ... ⊃Sn
of distinct irreducible nonempty closed subspaces Si of V.

Example:
An, Pn have dimension n.

E.g. A1 has dimension 1 since the only subsets are points, so A1⊂P.

n=2, f(x1,x2)=x1x2-1 leads to VI={(a,1/a)}, where a is in the algebraic closure of K. For K=R the points form a circle. VI is a variety. Its dimension is one.

Let F ∈ K[X0,X1,..., Xn] be a homogeneous polynomial of degree d the polynomial
Fi=F(x1,x2,...,xi,1, xi+1,...,xn) ∈ K[x1,...,xn]
is called the dehomogenization of F with respect to Xi. It has as points the intersection of VI with Wi which are embedded into the affine space.

The reverse process starts with a polynomial f of total degree d (this is the highest degree of any monomial). The polynomial
fi=Xidf(X0/Xd, X1/Xd,...,Xi-1/Xd,Xi+1/Xd,...,Xn/Xd) ∈ K[X0,X1, ...,Xn]
is homogeneous of degree d. This process adds some points -- new points are those with Xi=0 and are called "points at infinity".

Examples:
f(x1,x2)=x1x2-1⇒ f0(X0,X1,X2)=X02(X1X2/X02-1)=X1X2-X02. .

E: y2=x3+Ax+B in A2 corresponds to the projective equation Y2Z=X3+AXZ2+BZ3 in P2.

Def. 4.13 A variety of dimension one is called a curve.

Example:
Open sets Ui=DXi are mapped to An by dehomogenizing with respect to Xi. The inverse mapping is given by
ΦAn →Ui, (x1,...,xn) maps to (x1:x1:...:xi:1:xi+1:...:xn)
This defines a canonical bijection between a Ui and An which maps closed sets in Ui to closed sets in An ("inclusion of An in Pn). U0, U1 ,...,Un cover Pnl this covering is called the standard covering.

Def. 4.14 Let V be an affine variety and I so that V=VI.
K[V]=K[x1,x2,...,xn]/I
is called the coordinate ring of V. The quotient field K(V)=Quot(K[V]) is called the function field of V.

Example:
K[E]=K[x,y]/(y2-x3-Ax-B) means that y2 is replaced by x3+Ax+B, i.e. the highest power of y appearing in a reduced element from K(E) is 1.

We work with affine plane curves, i.e. dimension 1 varieties in A2 given by one equation and with their projective closure, obtained by including the points at infinity.

Th. 4.15 Jacobi Criterion
Let C=V(F) be a plane curve with F∈K[x,y]. P is a singular point of C if and only if the following three equations are satisfied: Otherwise C is called non-singular. Note that the points are taken from the algebraic closure of K.

Def. 4.16 A non-singular curve is also called smooth.

Examples:
Consider F(x,y)=y2-x3-Ax-B over a field of characteristic not two. The partial derivatives are Fx=-(3x2+A) and Fy=2y. A singular point must satisfy all these 3 equations, i.e. 2y=0 ⇐ y=0. Since the point must be on the curve we get that F(x,0)=-x3-Ax-B must be zero and thus that x is a simultaneous root of f:=x3+Ax+B and its derivative 3x2+A. So we get that the curve is singular if there exists a point (a,0) such that a is simultaneous root of f and f' which is possible if and only if f has multiple roots. Direct calculation shows that this holds if and only if 4A3+27B3=0. The last expression is called the discriminant of the curve.

The corresponding projective curve is Y2Z-X3-AXZ2-BZ3, there is exactly one point at infinity given by (0:1:0). Dehomogenizing the projective curve with respect to Y one obtains z-x3-Axz2-Bz3 which has partial derivative 1 with respect to z, so the point at infinity is non-singular.

Let y2=3-2x2+x=x(x-1)2. In the point (1,0) the tangent cannot be defined uniquely so the curve has a singularity there. Such a singularity is called a node.

Def. 4.17 Let C be a curve. A divisor D is an element of the free abelian group over the points of C.
D=ΣP∈CnPP, n ∈Z
and all but finitely many nP are zero. Apparently the divisors form a group, the group of divisors DivC.

Def. 4.18 We define a degree function
deg: DivC → Z
by
deg(ΣP∈CnPP)=ΣP∈CnP.
Le. 4.19 DivC0 (the divisors of degree zero) is a subgroup of DivC.

Def. 4.20 Let f ∈ K(C). We can associate a divisor with the function using valuations vP which returns the order of the zero or pole of f at P. Such a divisor is called a principal divisor.

Le. 4.21 The principal divisors form a group PrincC. It is a subgroup of the group of degree zero divisors.

Def. 4.22 The divisor class group of C is the factor group
DivC0 /PrincC = PicC0.
It is also called the Picard group.

Pictures and formulas for elliptic curves, in particular showing that on an elliptic curve each divisor class is uniquely represented by P-P∞. This shows that the group of points indeed forms a group. Formulas for group operations see below.

Th. 4.23 Let C be given by C:y2+h(x)y=f(x), where deg(f)=2g+1, deg(h)≤g, f is monic and C is smooth. Such a curve is called a hyperelliptic curve of genus g.

Then each divisor class can be represented by Σ rn=1Pi-rP∞, r≤g and Pi≠Pj for i≠j.

5. Efficient arithmetic on elliptic curves

Def. 5.1 An elliptic curve E/K is a smooth projective curve of genus 1 with at least one K-rational point.

Down to earth: if

E:y2+a1xy+a3y=x3+a2x2+a4x+6, ai ∈K
is non-singular (cf. Th. 4.15) then E is an elliptic curve over K (and this is the most general equation).

In cryptography we work with curves over finite fields K=Fq. Then the number of K-rational points is also finite (obviously there is only a limited choice for pairs (x,y)). For chosen a∈Fq we obtain a quadratic equation in y which has two solutions in about 50% of the values a, so we can expect about q points in E( Fq).

Th. 5.2 Weil's Theorem
|E(Fq)|=q+1-t,
where |t|<21/2 and t is called the trace of the Frobenius endomorphism.

So to get a group with l elements one chooses a prime power q∼ and checks random curves over Fq. (There is a lot of literature about Schoof's point counting algorithm).

To obtain the most efficient arithmetic one needs to specify whether the characteristic is even or odd. We consider odd characteristic fields in the following and show which isomorphic transformations are possible. By an isomorphic transformation we mean replacing x by ax+b and y by cy+dx+e. These maps do not change the highest powers occurring. The shape of the curve is unchanged if a3=c2, i.e. a=m2, c=m3 for some m since then both sides can be made monic.

Choosing m=1, b=0, d=-a1/2,e=-a3/2 we get in the new coordinates a curve of the form y2=x3+b2x2+ b4x+b6. If the characteristic is not 3 then b2/3 exists and we can additionally change x to x-b2/3 and obtain y2=x3+ 4x+c6. So the curve we considered before was the most general case in odd characteristic larger than 3.

We obtained the following formulas to add P+Q=R for P≠-Q:

xR=λ2-xP-xQ, yR=λ(xP-xR), where λ=(yP-yQ)/(xP-xQ) for P≠Q and λ=(xP3+c4)/2yP for P=Q.

This means that an addition takes 1I (inversion), 2M (multiplication), 1S (squaring) while a doubling needs 1I, 2M, 2S.

For most platforms inversions are much more expensive than multiplications and thus inversion-free coordinates are interesting. We present projective coordinates and refer to the literature for Jacobian coordinates. Let the curve be given by Y2Z=X3+ c4XZ2+c6Z3 and put P=X1:Y1:Z1), Q=(X2:Y2:Z2)

Addition: P≠ ±Q

A=Y2Z1-Y1Z2; B=X2Z1-X1Z2; C=A2Z1Z2-B3- 2B2X1Z2;

X3=BC; Y3=A(B2X1Z2-C)- B3Y1Z2; Z3=B3Z1Z2.

Doubling:

A=a4Z12+3X12; B=Y1Z1; C=X1Y1B; D=A2-8C; X32BD; Y3A(4C-D)-8Y12B2; Z3=8B3

One addition needs 12M, 2S while a doubling needs 7M, 5S.

Using mixed coordinates (one input point to the addition is in affine coordinates - usually the base point in a scalar multiplication is in affine and just the intermediate points are in projective coordinates) takes less operations.

Another interesting coordinate system are Montgomery coordinates. This works on curves of the form
By2=x3+Ax2+x.
Formulas and the Montgomery ladder were stated in class.

Elliptic curves are used in cryptography mainly for DL systems. One chooses groups in which the DLP (given Q=[a}P and find a) is hard. Particularly the group should have finite order. Due to the Pohlig Hellman attack one chooses even only prime order groups.

Reasons for choosing ECC over DL in finite fields (FF):
Finite fields have subexponential attacks on the DLP. These index calculus attacks run much faster than the generic attacks (Pollard rho and Pollard lambda, baby-step giant-step) which run in O(|G|1/2). So EC have shorter parameters. E.g. if q∼160 then an EC over Fq is assumed to have the same security as the DL in finite fields of size 1024 bits and the gap widens (ECC-192 corresponds to FF-2048).
This is critical for restricted devices but in addition, EC are much faster than FF due to the size difference.
New advantage of elliptic curves is that special elliptic curve give rise to efficiently computable pairings.

24. April

Introduction to pairings, ID based crypto, tripartite key exchange, computation of pairings.

01. May

No teaching! Labor day!

08. May

Side-channel attacks and countermeasures.

Homework

Find out how a field with 4 elements could look like by using group tables.

Let R be a ring of characteristic p, where p is prime. Show that for any integer n one has
(a+b)pn=apn+bpn
for all a, b ∈R.

Show:

If αis a multiple root of f then (x-α)|gcd(f,f').

gcd(f,f')=1 if and only if f has only simple roots over its splitting field.

Prove Theorem 3.25.

Prove Lemma 3.33.

The example after Def. 4.16. was actually a homework.

How do the divisor classes look like on y2=x5+f4x4+... (assuming this is a non-singular curve). And how if the right hand side has degree 6. (Hint: count the number of points at infinity)