| Contents | Announcements | Exams | Literature | Videos | Course notes & exercise sheets | Follow-up courses | Old Exams |
Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room MF 5.062
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands
Phone: +31 (0) 40 247 4764
The easiest ways to reach me wherever I am:
e-mail:tanja@hyperelliptic.org
Contents
Note that one of the course requirements is algebra. I will not repeat basic background on groups, rings and fields in class. If you don't have the necessary background, take the summer and work through the "Number Theory and Algebra" script or more from my draft book Discrete Mathematics.
It is not necessary to purchase a book to follow the course.
Previous versions of this course used
Henk van Tilborg's "Fundamentals of Cryptology", Kluwer academic
Publishers, Boston, 2000. But the book is out of print.
A preliminary author's copy by Henk can be downloaded in pdf form
here
and as a mathematica worksheet here.
Other books you might find useful (in alphabetical order):
The first exam is on 27 Oct 12:30 - 16:30. The retake is on 26 Jan 18:00 - 21:00.
The videos from this course appear on
TU/e's
Yuja page.
Note that this page requires a TU/e account to log in and shows lectures
from multiple years and that there are some differences between the
course versions; I taught the course with recordings in 2022 and 2019 and my colleague Andreas
Hülsing taught it in 2018, so you can get different explanations.
For the 2021 edition of the course I recorded a lot of short videos
which you can find on the YouTube Channel.
The
course page for 2021 has short descriptions of all videos, slides,
and no-cookie links to the YouTube videos. Watch them
from there if you're on a low-cookie diet.
This section is extended through the course with notes of what happened in class and links to blackboard pictures.
01 Sep 2026
This lecture was covered by Jonathan Levin because I was sick.
General introduction to cryptography; concepts public key
and symmetric key cryptography.
Jonathan covered Diffie-Hellman key exchange with some generic P and showed that A
and B both compute abP while E sees P, aP, and bP.
Then he covered the clock group over the reals (or rational numbers) as a bad example
where the attacker can easily solve the discrete logarithm problem by observing
how large the power of 5 grows when using P=(3/5,4/5), but this study
also gave us the addition formulas for the clock group which we then used to consider
the clock group over the integers modulo a prime.
He showed that the addition law has (0,1) as neutral element, -(x,y) = (-x,y)
and that the law is commutative. In the instruction you'll show that the
resulting point is on the clock. He skipped associativity as it is not
particularly illuminating.
Clocks modulo primes are an example of cryptosystems
against which the best attacks have subexponential (but superpolynomial) complexity; we
will get to this attack much later. If possible, we would like to have systems
where the best attacks are exponential.
Pictures of blackboards are here. Thanks to a student for taking the pictures.
Here is the sheet for the instruction session (block 7 & 8).
Submitting homework is optional. If you want feedback, please submit by next
Tue (08 Sep)
before 13:30 through Canvas. Please submit in groups of 2-3 people; we do not have
capacity to grade everybody individually.
To explain the 'optional':
I do expect that you look at the exercises (homework and instructions, in
particular if they cover pieces we leave out in the lectures. In general it's a
good idea to engage with the material.
Here is the first homework sheet.
03 Sep 2026
This lecture was covered by Jonathan Levin because I was sick.
Jonathan showed Edwards curves and the addition law and how much it resembles addition
on the clock.
He started with a recap of the Diffie–Hellman key exchange and cleanly
defined the related problems of computational Diffie–Hellman problem,
decisional Diffie–Hellman problem, and discrete logarithm problem.
For computing aP he explained the double-and-add method with examples 5P and
23P. If this went too fast§, watch ECC II from the
YouTube
Channel
Consideration of what points are bad starting points for the clock; you'll have
a similar proof for Edwards curves in the homework,but remember that you cannot
argue about angles there, so you need to use the formulas.
Definition of order of a group element (this should be a recap for you.
He covered the following "interesting" points on the clock: points (0,1) has order 1,
(0,-1) has order 2, and (-1,0) and (1,0) have order 4 and are thus bad starting
points for clock-group Diffie–Hellman.
Then he showed the Edwards addition law and what Edwards curve look like over the
reals.
The addition law is similar to that on the circle but has denominators.
He showed that -(x,y) = (-x,y) continues to hold on
Edwards curves and that (0,1) remains the neutral element.
He showed that denominators are never 0 over the reals if d is negative.
These arguments do not make sense over a finite
field, as we cannot argue about sizes there. The matching properties are that
negative d means that it's not a square and that a positive d is a square.
Being a square or not is a property that makes sense over a finite field.
We'll pick that up next week.
For the proof that there are no exceptions over F_p for p>2 and d a non-square
please watch ECC III from the
YouTube
Channel. I will not show this in proof in class.
.
To prove that the Edwards addition law is a group law we still miss showing
that addition is associative and that the sum of two points
is on the curve, but given that there are no exceptions to the addition law
this is something you can ask your computer to check. Taken together, these
show that the points on Edwards curves form a group under this addition.
The group is commutative.'
From the pictures and the addition formula it is clear that the number of
points on an Edwards curve are a multiple of 4, because for every point (x,y)
also the points (-x,y),(x,-y) and (-x,-y) are on the curve and they are
distinct if x and y are nonzero. There are also the above-mentioned 4 points of
order 1,2,4, and 4 which have one of their coordinates equal to zero.
A different way to see that the group order is divisible by 4 is by Lagrange
because we have points of order 4 (the hands of the starfish)
and Lagrange says that the order of a group element divides the group order.
Jonathan showed the additional symmetry that with (x,y) also (y,x) is on the
curve, along with it's 3 mirror images.
Pictures of blackboards are here.
Thanks to a student for taking the pictures.
If anybody is looking for more intuition on the Edwards addition law. There is no
adding of angles or pizza pieces to explain it, but here is a link to a
blog
post describing a unified way of addition on circles and Edwards curves by
Thomas Hales. I prefer the simple and intuitive addition law on the circle
which we've seen to be a special case of the Edwards addition law for d = 0.
He goes the other way around – starting with a geometric interpretation
of the addition law that I worked out with Arene, Naehrig, and Ritzenthaler,
and then showing that that can also be used for the circle. But tastes differ,
so you might like his presentation better.
For our paper, Michael Naehrig recorded a video about it together with his kids
which you can find
here.
8 Sep 2026
This lecture was given by Jonathan Levin because I was sick.
Jonathan recapped the addition law on Edwards curves and gave an example of
which numbers are squares in the finite field F_7. He then introduced twisted
Edwards curves as a generalization and showed how the addition law changes.
Twisted Edwards curves are a generalization of Edwards curves which, depending
on the choice of a, do not have a point of order 4. But we will show later,
when we cover more on Montgomery curves,
that the number of points over any finite field remains divisible by 4.
The complete case, i.e., the one that avoids divisions by 0 in the addition
law, is for a a square and d a non-square.
Jonathan covered Weierstrass curves as the most general form of elliptic
curves, stated the Jacobi criterion (check that there is no point on the curve
in which both partial derivatives vanish to conclude that the curve is non
singular), and showed what singularities (cusp and node) look like.
Over fields in which 6 is not 0, so fields that do not have characteristic 2 or
3, we can transform the curve with an isomorphism to short Weierstrass
form y^2 = x^3 +a_4 x + a_6, which is non-singular if 4a_4^3 + 27 a_6^2 is not
0. A curve isomorphism is an invertible map that is compatible with the group
operation.
Starting from the addition law that points on a line add up to 0, Jonathan
developed the addition formulas incl.
proving that there is exactly one 3rd. point on the curve for a line of the
form v= λ u + μ going through two input points (or being the tangent
to one input point, in the case of doubling)
and then showed that there are 5 cases to consider for
the inputs for addition. The Weierstrass form is the most general curve equation
for elliptic curves but also the most annoying to implement – missing one
of the special cases can cause wrong results and in crypto that's often enough
for an attacker to get in.
The geometric addition law is called the
chord-and-tangent method. See the blackboard pictures for drawings over the
reals to show the cases of addition and doubling. Jonathan showed that for
doubling a point of the form (x,0) or adding (x,y) to (x,-y) we encounter a
vertical line with no obvious 3rd point of intersection. The result then in the
point at infinity, an additional point that can be thought of as infinitely far
out on the y-axis. This point forms the neutral element of the group of points
on Weierstrass curves and -(x,y) = (x,-y).
Montgomery curves are another useful shape of elliptic curves. Jonathan covered
that the curve is non-singular if A is not 2 or -2 and B is not 0, where he used
the Jacobi criterion, giving an example of how to apply it.
Jonathan wished to clarify that in the explanation for when the Montgomery
curve equation is not singular, he first explained that A = +/- 2 gives a
singular curve, and thus curves with other values of A are not singular.
He then covered the addition law on Montgomery curves, which is very close to
that of Weierstrass curves, but note the extra B and A in the formulas.
A relaxation of isomorphisms are birational equivalences
which are also invertible maps between curves which are compatible with
addition, but permit a finite number of exceptions; as the name
suggests, these are given by fractions of polynomials.
Jonathan stated that Montgomery curves are birationally equivalent to Edwards
curves and gave the formulas to map from one curve shape to the other and back.
Pictures of blackboards are here.
Here is the sheet for the instruction session (block 7 & 8).
The next homework is due on 15 September at 13:30 via Canvas. Here is the homework sheet.
10 Sep 2026
Old exams by me: