Advanced topics in cryptology
Tanja Lange
Department of Mathematics
Technical University of Denmark
Matematiktorvet  Building 303
DK2800 Kgs. Lyngby
Denmark
Room 152
Phone: +45 4525 3007
Voice mail: +45 3696 7248
Fax.: +45 4588 1399
email: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 sidechannel 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 highlightening 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

T. Høholdt and J. Justesen, "A Course In ErrorCorrecting
Codes", Springer Verlag. Contains details for binary fields.
 R. Lidl/H. Niederreiter, "Finite Fields, Encyclopedia of
Mathematics and its Applications 20", AddisonWesley.
 R. Lidl/H. Niederreiter, "Introduction to finite fields and their
applications", Cambridge University Press.
 A. Menezes, "Applications of Finite Fields", Kluwer.
 T. Murphy, "Finite Fields",
online.
 V. Shoup, "A Computational Introduction to Number Theory and
Algebra", Cambridge University Press. This book is also available online.
Elliptic curves (does often contain some material on finite
fields, too).

R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F.
Vercauteren, "Handbook of Elliptic and Hyperelliptic Curve
Cryptography", CRC Press.

I. F. Blake, G. Seroussi and N. P. Smart, "Elliptic curves in
cryptography", Cambridge University Press.

I. F. Blake, G. Seroussi and N. P. Smart, "Advances in Elliptic Curve
Cryptography", Cambridge University Press.

D. Hankerson, A. J. Menezes and S. A. Vanstone, "Guide to elliptic
curve cryptography", Springer Verlag.

J. Silverman, "The Arithmetic of Elliptic Curves", Springer Verlag.
 J. Silverman, "Advanced topics in the arithmetic of elliptic
curves", Springer Verlag.
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 F_{p}.
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=p^{n}.
This describes the additive structure of finite fields. Now we
consider the multiplicative structure.
Th. 3.7 Let K=p^{n}, 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, g^{2}, g^{3} ...})
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
 K[x]/(f(x)) field
 f is irreducible.
Examples:
f=x, f=x^2+1, f=x^2+x+1, f=x^4+x^2+1 over
F_{2}. 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), F_{2}(&alpha) with (&alpha) root of x^{2}+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:
 K(θ)≅ K[x]/(g(x)).
 dim_{K}F=n, basis given by {1,θ, θ^{2}, ...,θ^{n1}}.
 α ∈ K(θ) has minimal polynomial m_{θ} with degm_{θ}n .
Le. 3.16 α, β ∈ F roots of f∈ K[x], f irreducible over K then K(α)≅ K(β).
Th. 3.17 F finite field with q=p^{n}. Then
x^{q}x=Π_{a ∈F} (xa).
F is the splitting field of x^{q}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 p^{n}.
Notation: F_{pn}.
Example:
Why is F_{4} not contained in
F_{8}? Try to find an element a satisfying
a^{2}+a+1 (such an element exists in
F_{4}) in the field F_{8}. This
fails.
Le. 3.19 f ∈ F_{q}[x] irreducible, α
root of f in splitting field. Let h∈ F_{q}[x]. Then one has h(&alpha)=0 if and only if fh.
Le. 3.20 f ∈ F_{q}[x] irreducible of deg(f)=m.
Then fx^{qn} if and only if mn.
Cor. 3.21 f ∈ F_{q}[x] irreducible of deg(f)=m.
Then F_{qm} is splitting field of f. x^{qn}x is defining equation of F_{qn}.
Examples:
Find the splitting fields of x^{2}+x+1,
x^{3}+x+1 and x^{3}+x+1 over
F_{2}.
Cor. 3.22 f, g irreducible, deg(f)=deg(g) then their splitting fields are isomorphic.
Th. 3.23 x^{qn} is product of all irreducible polynomials over F_{q} whose degree divides n.
Cor. 3.24 Let N_{}(d) be the number of irreducible polynomials over F_{q} of degree d. Then q^{n}=
Σ _{dn}dN_{q}(d). In particular for all d, q
we have
N_{}(d) >0.
Th. 3.25 f ∈ F_{q}[x] irreducible of deg(f)=m.
If α is root of f over F_{qm} then all roots of f are given by α α^{q}, α^{q2}, α^{q3}, ...
, α^{qm1}.
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 F_{qn} over F_{q}.
Th. 3.28 All automorphisms of F_{qn} over F_{q} are given by the maps σ_{0}, σ_{1}, ...,σ_{n1}, where σ_{i}(α)=α^{qi}.
Def. 3.29 Trace Tr_{qn:Fq}.
Le 3.30 Tr_{qn:Fq}
maps to F_{q}. Relation with coefficients of minimal
polynomial of α.
Le. 3.31 Properties of trace map (additivity, scalars from ground field).
Def. 3.32 Norm N_{qn:Fq}.
Le. 3.33 Properties of norm.
Excurs: How to check that a polynomial is irreducible? Rabin test
f ∈ F_{q}[x] of deg(f)=n irreducible if and only if

fx^{qn}x
 for all divisors dn one has gcd(f,x^{qd})=1.
Example:
Find an irreducible polynomial of the form x^{3}a over F_{7}. 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 builtin in function IsIrreducible).
Let n be prime. An irreducible binomial of degree n over
F_{q} exists if and only if nq1 (proof via
existence of nth roots of unity).
4. Background on curves
Def. 4.1 A^{n}/K affine space of dimension n.
Def. 4.2 A^{n}(L) for L extension field
of K contained in algebraic closure.
Def. 4.3 P^{n}/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[x_{1},x_{2},...,x_{n}]. Define
topology by using D_{f}={P ∈
A^{n}  f(P)≠ 0} as basic open sets.
Def. 4.5 Consider an ideal I⊆
K[x_{1},x_{2},...,x_{n}]. The sets V_{I}={P ∈
A^{n}  f(P)=0 for all f ∈ I}
are closed sets.
A set S is closed if there exists an ideal
I⊆ K[x_{1},x_{2},...,x_{n}]
with S=V_{I}.
This topology is called the Zariski Topology.
Example:
A^{n} 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[x_{0},x_{1},...,x_{n}] is called homogeneous of degree d if and only if
f(λx_{0},λx_{1},...,λx_{n})=
λ
λ^{d}f(x_{0},x_{1},...,x_{n}).
Def 4.7 Let f ∈
K[x_{0},x_{1},...,x_{n}] be a homogeneous
polynomial. Then D_{f}={P\in P^{n}f(P) ≠ 0} is well defined (since f is homogeneous). Use D_{f} 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≠ <x_{0}, x_{1}, ... ,x_{n} >. Let V_{I}={P\in P^{n}f(P) = 0 for all f ∈ I }.
A set S ⊂P^{n} is closed if it is
the set of simultaneous zeros of homogeneous polynomials in
K[x_{0},x_{1},...,x_{n}].
Example:
Let U_{i}=D_{xi}, i.e.
U_{i}={(x_{0}:x_{1}:.... :x_{n}) in
P^{n}x_{i}≠ 0} and
W_{i}=V_{(xi)}, i.e.
W_{i}={(x_{0}:x_{1}:.... :x_{n}) in
P^{n}x_{i}= 0}.
The sets U_{i} are open, W_{i} 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=S_{1}⊃S_{2} of two proper closed affine
(projective) sets.
Th. 4.11 V_{I} is an affine (projective) variety if and
only if I is a (homogeneous) prime ideal in
K[x_{1},x_{2},...,x_{n}]
(K[X_{0},X_{1},...,X_{n}])
Example:
n=2, I=<x_{1}>
V_{I}={(0,a)}, where a is in the algebraic
closure of K, is a variety. The corresponding projective
variety must consist of the points
(X_{0}:0:X_{2}) for which not both
X_{0}, X_{2} are
zero. E.g. I=<X_{1} 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=S_{0}⊃S_{1}⊃ ... ⊃S_{n}
of distinct irreducible nonempty closed subspaces S_{i} of
V.
Example:
A^{n}, P^{n} have
dimension n.
E.g. A^{1} has dimension 1 since the only
subsets are points, so A^{1}⊂P.
n=2,
f(x_{1},x_{2})=x_{1}x_{2}1 leads
to V_{I}={(a,1/a)}, where a is in the algebraic
closure of K. For K=R the points form a circle.
V_{I} is a variety. Its dimension is one.
Let F ∈ K[X_{0},X_{1},..., X_{n}]
be a homogeneous polynomial of degree d the polynomial
F_{i}=F(x_{1},x_{2},...,x_{i},1,
x_{i+1},...,x_{n}) ∈
K[x_{1},...,x_{n}]
is called the dehomogenization of F with respect to
X_{i}. It has as points the intersection of
V_{I} with W_{i} 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
f_{i}=X_{i}^{d}f(X_{0}/X_{d},
X_{1}/X_{d},...,X_{i1}/X_{d},X_{i+1}/X_{d},...,X_{n}/X_{d})
∈ K[X_{0},X_{1}, ...,X_{n}]
is homogeneous of degree d. This process adds some points 
new points are those with X_{i}=0 and are called
"points at infinity".
Examples:
f(x_{1},x_{2})=x_{1}x_{2}1⇒
f_{0}(X_{0},X_{1},X_{2})=X_{0}^{2}(X_{1}X_{2}/X_{0}^{2}1)=X_{1}X_{2}X_{0}^{2}.
.
E: y^{2}=x^{3}+Ax+B in
A^{2} corresponds to the projective equation
Y^{2}Z=X^{3}+AXZ^{2}+BZ^{3} in
P^{2}.
Def. 4.13 A variety of dimension one is called a curve.
Example:
Open sets U_{i}=D_{Xi} are
mapped to A^{n} by dehomogenizing with respect to
X_{i}. The inverse mapping is given by
ΦA^{n} →U_{i},
(x_{1},...,x_{n}) maps to
(x_{1}:x_{1}:...:x_{i}:1:x_{i+1}:...:x_{n})
This defines a canonical bijection between a U_{i} and
A^{n} which maps closed sets in
U_{i} to closed sets in A^{n}
("inclusion of A^{n} in
P^{n}). U_{0},
U_{1} ,...,U_{n} cover
P^{n}l this covering is called the standard
covering.
Def. 4.14 Let V be an affine variety and I so that
V=V_{I}.
K[V]=K[x_{1},x_{2},...,x_{n}]/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]/(y^{2}x^{3}AxB) means
that y^{2} is replaced by x^{3}+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
A^{2} 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:
 F(P)=0,
 F_{x}(P)=0,
 F_{y}(P)=0.
Otherwise C is called nonsingular. Note that the points are
taken from the algebraic closure of K.
Def. 4.16 A nonsingular curve is also called smooth.
Examples:
Consider F(x,y)=y^{2}x^{3}AxB over a field
of characteristic not two. The partial derivatives are
F_{x}=(3x2+A) and
F_{y}=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)=x^{3}AxB must be zero and
thus that x is a simultaneous root of
f:=x^{3}+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 4A^{3}+27B^{3}=0. The last expression is
called the discriminant of the curve.
The corresponding projective curve is
Y^{2}ZX^{3}AXZ^{2}BZ^{3},
there is exactly one point at infinity given by
(0:1:0). Dehomogenizing the projective curve with respect to Y
one obtains zx^{3}Axz^{2}Bz^{3}
which has partial derivative 1 with respect to z, so the point
at infinity is nonsingular.
Let
y^{2}=^{3}2x^{2}+x=x(x1)^{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∈C}n_{P}P, n ∈Z
and all but finitely many n_{P} are zero. Apparently
the divisors form a group, the group of divisors
Div_{C}.
Def. 4.18 We define a degree function
deg: Div_{C} → Z
by
deg(Σ_{P∈C}n_{P}P)=Σ_{P∈C}n_{P}.
Le. 4.19 Div_{C}^{0} (the divisors of degree
zero) is a subgroup of Div_{C}.
Def. 4.20 Let f ∈ K(C). We can associate a divisor with the
function using valuations v_{P} 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
Princ_{C}. It is a subgroup of the group of degree zero
divisors.
Def. 4.22 The divisor class group of C is the factor group
Div_{C}^{0} /Princ_{C} = Pic_{C}^{0}.
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
PP_{∞}. 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:y^{2}+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
Σ^{ r}_{n=1}P_{i}rP_{∞},
r≤g and P_{i}≠P_{j} 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 Krational point.
Down to earth: if
E:y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+_{6}, a_{i} ∈K
is nonsingular (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=F_{q}. Then the number of Krational points is
also finite (obviously there is only a limited choice for pairs
(x,y)). For chosen a∈F_{q} 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(
F_{q}).
Th. 5.2 Weil's Theorem
E(F_{q})=q+1t,
where
t<2^{1/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
F_{q}. (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 a^{3}=c^{2},
i.e. a=m^{2}, c=m^{3} for some m since
then both sides can be made monic.
Choosing m=1, b=0, d=a_{1}/2,e=a_{3}/2 we get
in the new coordinates a curve of the form
y^{2}=x^{3}+b_{2}x^{2}+
b_{4}x+b_{6}. If the characteristic is not 3 then
b_{2}/3 exists and we can additionally change x
to xb_{2}/3 and obtain y^{2}=x^{3}+
_{4}x+c_{6}. 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:
x_{R}=λ^{2}x_{P}x_{Q},
y_{R}=λ(x_{P}x_{R}), where
λ=(y_{P}y_{Q})/(x_{P}x_{Q})
for P≠Q and λ=(x_{P}^{3}+c_{4})/2y_{P} 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 inversionfree coordinates are
interesting. We present projective coordinates and refer to the
literature for Jacobian coordinates.
Let the curve be given by Y^{2}Z=X^{3}+
c_{4}XZ^{2}+c_{6}Z^{3} and put
P=X_{1}:Y_{1}:Z_{1}),
Q=(X_{2}:Y_{2}:Z_{2})
Addition: P≠ ±Q
A=Y_{2}Z_{1}Y_{1}Z_{2};
B=X_{2}Z_{1}X_{1}Z_{2};
C=A^{2}Z_{1}Z_{2}B^{3}
2B^{2}X_{1}Z_{2};
X_{3}=BC;
Y_{3}=A(B^{2}X_{1}Z_{2}C)
B^{3}Y_{1}Z_{2};
Z_{3}=B^{3}Z_{1}Z_{2}.
Doubling:
A=a_{4}Z_{1}^{2}+3X_{1}^{2};
B=Y_{1}Z_{1}; C=X_{1}Y_{1}B;
D=A^{2}8C; X_{3}2BD;
Y_{3}A(4CD)8Y_{1}^{2}B^{2};
Z_{3}=8B^{3}
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
By^{2}=x3+Ax^{2}+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, babystep giantstep) which run in
O(G^{1/2}). So EC have shorter parameters.
E.g. if q∼160 then an EC over F_{q} is
assumed to have the same security as the DL in finite fields of size
1024 bits and the gap widens (ECC192 corresponds to FF2048).
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
Sidechannel 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}=a^{pn}+b^{pn}
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
y^{2}=x^{5}+f_{4}x^{4}+... (assuming
this is a nonsingular curve). And how if the right hand side has
degree 6. (Hint: count the number of points at infinity)