| 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.
08 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.
Thanks to a student for taking the pictures.
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
This lecture was given by Jonathan Levin because I was sick.
Jonathan recapped that Montgomery curves
and twisted Edwards curves are birationally equivalent by giving the explicit
maps. He showed where these maps have exceptional cases and where those from
the twisted Edwards curve should land – (0,1) at infinity, as the neutral
element should map to the neutral element, and (0,-1) to (0,0) on the
Montgomery curve, because both have order 2 and (0,0) is not reached otherwise
(u=0 corresponds to y = -1 but then v is not defined as 0/0). Mapping from
Montgomery to twisted Edwards may have more exceptional cases,
Jonathan showed that on a Montgomery curve over a finite field at least one of the
following holds: there are 3 points of order 2 or 2 points of order 4. This
implies that the
group order is always divisible by 4. The proof needed that in a finite field
the product of two non-squares is a square. Jonathan used
that the multiplicative group of a finite field is cyclic (can be written as
powers of a single element, called a generator) so that each element can be
written as g^j for some j. Then note that g^2i is a square while g^(2i+1) is not,
and that when you multiply two non-square g^(2i+1)*g^(2j+1) = g^(2(i+j+1)) you
get a square. Note that that also means that there are as many squares as
non-squares among the non-zero elements. He also repeated the theorem of
Lagrange, that the order of an element in a finite group divides the group
order, where group order means the number of elements in the group.
The proof itself used the points of order 2 that you found on Tuesday in the
lecture, the points of order 4 that are part of the exercise sheet 2, and then
a third case that can help you if you got stuck with the exercise sheet.
See the blackboard pictures for details.
Projective coordinates are a useful trick to speed up computations as
inversions are computationally expensive, so for efficient implementations we
like to work with fractions and clear denominators only at the end of the
computation.
For more addition formulas in projective coordinates and optimized operation
counts in multiplications etc. see https://hyperelliptic.org/EFD/.
Projective coordinates also
help understand the point at infinity on the Weierstrass and Montgomery form of
elliptic curves. This is also how Sage represents points (see below).
Geometrically, this means working with projective coordinates (the
normal coordinates that we've looked at are called affine coordinates) and
instead of using just two coordinates (x,y) we work with three (X:Y:Z) with the
understanding that x=X/Z and y=Y/Z; this requires Z non-zero and means that we
do not have a unique representation (the : in (X:Y:Z) are used by convention to
indicate the redundancy of the representation; note (X:Y:Z)=(cX:cY:cZ) for nonzero
c).
Jonathan gave a short show-and-tell of how Sage works, showing how to construct
an elliptic curve over a finite field, how to get the number of points, and how
to pick a random point. You can also try E.points() to see all points
on the curve (this example is small enough). For a transcript of what he typed
and what the output was see here.
Note that Sage uses
(0:1:0) to denote the point at infinity.
In 2021 I recorded a
video to
demonstrate how to use Sage https://www.sagemath.org/, covering basics of finite fields and
elliptic curves.
I also wrote a short ``cheat sheet'' with commands for Sage,
see here
Finally, Jonathan explained the baby-step giant-step (BSGS) algorithm and
showed an example of using it to solve the DLP on a small curve in Sage.
For a transcript of what he typed
and what the output was see here.
In the DLP we want to find a with P_A = aP and a should be less than the number
of points l.
The Baby-Step-Giant-Step (BSGS) attack computes a = i + jm mod l for m=√
l and 0≤ i < m, 0 ≤ j ≤ m.
Hence, the DLP in a group is no harder than the square root of the group order.
BSGS has storage costs of m which might be prohibitive and thus choosing less
optimal ratio of BS and GS might be better.
Pictures of blackboards are here.
Thanks to a student for taking the pictures.
15 Sep 2026
We covered the double-and-add method (You have seen this already from Jonathan
for computing aP) and the double-and-always-add method (using dummy operations to
hide the pattern if we're worried about side-channel attacks) as the simplest
cases of scalar multiplication. These need one doubling per bit and maybe or
always one addition per bit Windowing methods lead to a speedup for
scalar multiplications as they need fewer additions and they also need fewer dummy
operations if doing one addition per step.
This matters as
an attacker might be able to obtain side channel information, such as timing
(at different levels of precision), electromagnetic radiation, or power consumption
and from this infer information on the secret scalar that was being used.
I showed the timing distribution from some TPMs (Trusted Platform modules) from
TPM-Fail where you can clearly see the influence
of length of a and Hamming weight of a. In several cases this leaks 12 bits; for
Diffie-Hellman that's not a big problem, but for the signature system that they
were attacking it was -- and you don't know where your scalar multiplication will
be used.
I showed one slide for side-channel attacks. You can find more about scalar
multiplication and two SCA pictures in these
slides.
If you want to see more ways to implement
things securely, take our new "Cryptographic Engineering" course, see below
under Follow-up courses.
Montgomery curves are interesting because they offer efficient differential additions
in which we compute only the first coordinate of a point (u-coordinate in how
we write them), a dADD operations adds points of known difference and uses the
u-coordinate of the difference to do that. We developed u-only doubling and I
asserted that dADD would work with u only as well. To see this, let
P2 and P3 be the input points and let P1 be their
difference. Then the u-coordinate of their sum P5 satisfies that
u1 u5 = (u2u3 -)^2/(u3 -
u2)^2. You can find the projective version of this computation
on these slides. I also showed the
definition of Curve25519, a Montgomery curve used in practice for
Diffie-Hellman computations.
The Montgomery ladder computes scalar multiplication aP by using two
intermediate points of difference P and one DBL and one dADD per bit of a.
I showed ladder computations for computing 31P and 33P.
The Montgomery ladder is also interesting because it hides the exact operations
we are doing.
The slides also show how to do swaps in the Montgomery ladder so that the sequence
of operations becomes 1 dADD, 1DBL, independent of the bits of the scalar
a.
If you want to see a lot more on side-channel attacks and countermeasures, check
out the CHES conference series.
Talks are available on YouTube on the "The IACR" channel.
Here is the
sheet for the instruction session (block 7 & 8).
The next homework is due on 22 September at 13:30 via Canvas. Here is the homework sheet. Note that I'll cover Pollard rho only on Thursday.
Pictures of blackboards are here.17 Sep 2026
BSGS takes √l to find the discrete log of Q=aP for base point P of order
l. Our topic today is to reduce the storage requirement and we'll see a method
called Pollard's rho method. First we consider how big l is for a curve over a
finite field with p elements.
By Hasse's theorem, the number of points on the curve over F_p is in
[p+1-2√ p, p+1+ 2 &radc; p] and we discussed why it makes sense that this
is an interval centered around p+1. I used the big-O notation to describe the
complexity and got some puzzled looks, so I briefly defined what that is.
Then I motivated the approach in Pollard rho by showing that if we had a random
walk on the multiples of P and for each point would know some representation
W_i = b_iP + c_iQ and would get to the same point with two different ways,
i.e. W_i = W_j, then we could use that compute the discrete log a as
a \equiv (b_j - b_i)/(a_i - a_j) mod l.
After the break I showed some pictures from these
slides,
explaining collisions of random walks on a finite
set and that the resulting graph (once I shortened all arrows to having the
same length) looks like the Greek letter ρ. The reason
we see collisions after about √l steps is the birthday paradox. The time
to collision splits about evenly over the tail and the cycle part.
I explained Floyd's cycle-finding method which permits to identify collisions
without requiring to store all visited points while requiring about twice as
much computation.
Pollard's rho method with Floyd's cycle-finding method runs in O(√l) in a
group of size l and only uses two
points. The method does a fast (two basic steps per fast step) and a slow walk and
only compares the current points, not past points.
The birthday paradox guarantees that each walk collides with itself and the
pseudorandom nature of the walk means that it enters a cycle after a collision,
which we can find using cycle finding.
On the boards the green walk is the fast walk, doing two of
the steps at once, and the red walk is the slow walk, doing just one step each
time. We only compare F_i and S_i for the same i. By the time that they meet,
the fast walk has run around the cycle once and then caught up again to the
slow walk; both have walked the tail part. On average this needs twice the
tail, plus 1.5 the cycle for the fast and 0.5 the cycle for the slow walk,
i.e., twice the tail and twice the cycle in total. Note that we'd have to do
each once in the best case to find a collision but finding it right away would
require a lot of storage.
This method is called Pollard's rho method
I first showed that at two scalar multiplications per step we can have a random
walk, but that's kind of expensive. I then showed the schoolbook version as the
simplest case of defining steps that need just one ADD or one DBL per step and
that achieves some OK randomness, but that that then requires doing some
book-keeping to remember and update after each step the values for b_i and c_i.
We can get better randomness by precomputing some 8 or 16 points R_k with
properly random d_k and e_k giving R_k = d_kP + e_kQ, and then selecting the
which precomputed step to add based on the last 3 or 4 bits of the current
point as
W_i = W_{i-1} + R_k, where x_{i-1} \equiv k mod 8 (or mod 16, depending on the
number of precomputed points). The walk is more random with more precomputed
points. I didn't show this but
there is still some loss in randomness:
doing a pseudo-random walk with 2^k different precomputed R_i leads to a
slowdown factor of 1/√(1-1/2^k), so we need to choose k large enough.
Note: for these walks, as well as for BSGS,
we work with unique representatives of points, so we need to use
affine coordinates rather than projective ones, and there Weierstrass curves are faster.
We can use the birational equivalence to move our attack targets to Weierstrass
form in case it is given on a twisted Edwards curve.
I showed the graph for the parallel attack due to van Oorschot and Wiener
from these slides,
In these graphs each
walk ends when it hits a 'distinguished point' (a point marked by some
properties in its coordinates, e.g., a large number of 0 bits in the
x-coordinate of the point).
Instead of waiting for walks to close a cycle we then hope for walks to join
paths and reach the same distinguished point. This uses M computers
efficiently, giving a factor of M speedup.
The attack designer
can choose the frequency of distinguished points to control the lengths of the
walks, storage (and communication) costs,
The same approach is also taken in finding collisions in hash functions using
many computers. There it is important to find the first collision, for DLPs any
collision is good as long as c_i is not c_j mod n.
Pictures of blackboards are here.
22 Sep 2026
I recapped the different options for the step functions for Pollard rho.
For k precomputed steps in the additive walk the walk takes longer by a factor
of 1/√(1 - 1/k).
Please also see the
slides which also calculates the formula.
Then I explained in more detail how the parallel version due to van Oorschot
and Wiener works. See the slides linked for last week.
We then analyzed ways to break the decisional Diffie-Hellman problem if we can
compute orders of points. In particular, we checked whether a, b, and c
matched modulo small divisors of l (the order of P).
The Pohlig-Hellman attack turns this information into an attack to compute
the full DLP, if all factors of l are small enough then
a modulo the divisors is efficiently computable and we can recover
ausing CRT.'
Important For l = Π qi ei the attack
solves ei DLPs in a group of size qi, not one DLP
in a group of size qi ei, but I didn't get to
around to showing how to do that, yet. We will cover that on Thursday. For now
you only know how to reduce solving the DLP mod l to solving it in groups of size
qi ei. Still faster than the full, but we can
do better!
Pictures of blackboards are here.
Here is the
sheet for the instruction session (block 7 & 8).
Homework is optional. If you want feedback, please submit by next Tue (03 Oct)
before 13:30 through Canvas. Please submit in groups of 2-3 people; we do not have
capacity to grade everybody individually.
Here is the homework sheet.
24 Sep 2026
I redid the explanations of Pohlig-Hellman, incl the detours to see what is not
the correct way of doing the computation. See the blackboard pictures and then
the two slide sets for
DLP VI
DLP VII
to give a numerical example. The slides highlight the different costs of what
you might try to do in sort of following this attack idea. These costs state
the costs of the DLPs because the scalar multiplications
don't matter asymptotically, and the CRT computation is very fast.
The slides also contain a systematic statement of how to run the Pohlig-Hellman
attack which you should look at and understand.
If you don't remember how the CRT computation works, take a looks at this
YouTube video I
made for 2WF80 and the corresponding
slides.
The lesson of the Pohlig-Hellman attack is that the DLP is no harder than the
DLP in the largest prime-order subgroup, so we try to choose points P with prime
order l; there might be some cofactor c so that the curve has c*P points.
Further reading on DLP:
I showed the required properties and generic hardness of preimage attacks, second preimage attacks, and collision finding for cryptographic hash functions using these slides. Search for hash to find the correct segment. I highlighted how Pollard rho and parallel collision search work to recover two different colliding inputs.
Pictures of blackboards are here.
Old exams by me: