| 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 (29 Sep)
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.
29 Sep 2026
We covered schoolbook RSA encryption, how KeyGen, Encrypt, and Decrypt
work and that m'=m, even when gcd(m,n) is not 1. This uses Euler's
theorem and in the special case that p or q divides m we needed the Chinese
Remainder Theorem (CRT).
I mentioned that one
can speed up encryption by choosing small e which have only very few non-zero
bits in the binary expansion such as e=65537. For decryption we cannot make
special choices of d as that's part of the secret key and we shouldn't restrict
the number of choices there. The CRT method (named after the Chinese Remainder
Theorem) gives a speed-up by a factor of 3 - 4 (depending on whether the
modular arithmetic uses quadratic-time schoolbook multiplication of Karatsuba
multiplication). To get this speedup you need to reduce c (to get half-length
operands) and reduce d (to get half-length exponents). Do not forget to do
either of those, else we'll remove your points. So, you need to compute and
document c_p, c_q, d_p, and d_q. As you'll see on the HW sheet below, it's also
common to precompute u, the inverse of p modulo q, as that's needed in the CRT
reconstruction of m for each decryption.
As a second topic we covered attacks on RSA and how to factor general numbers
(not products of two big prime numbers as in RSA). Trial division is good for
removing small prime factors from general numbers, but has no chance at
factoring RSA numbers, as there are p/ln(p) primes up to p, which is a very
large number for cryptographically sized primes, e.g. there are roughly
1.1377 10613 primes with 2048 bits.
We then covered Pollard's rho method of
factorization and that it takes time about √p to find p.
I showed the last few pages from these
slides for
our third (and last) usage of Pollard rho in attacks and showed on board how we
would execute and document this method in hand calculations vs. how we do it in
implementations on a computer. In the latter case we don't do gcd computations
after each step but combine b of them into one single gcd computation which
takes the product of all b differences. Then each iteration takes only
a step in the fast and the slow walk and a multiplication of their difference
with the intermediate batch value. Note that all parts here are computed modulo
m, the number we want to factor.
If we've done trial division with all small primes up to 2^10 we might want to
do Pollard rho to find all primes up to 20 bits, which on average takes 2^10
rho steps to find a collision. Our batches will be smaller than that as we'll
encounter some primes of just 11 or 12 bits.
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 (06 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.
01 Oct 2026
I showed what RSA keys look like in PGP. The command to inspect the key is
called pgpdump. The private key includes p and q and additionally a
value u which is the inverse of p modulo q, so that the CRT computation is a
simple m \equiv m_p + pu(m_q-m_p) mod n.
In the (p-1)-method we pick exponents s that are very smooth (have many small
prime factors) and hope that 1 < gcd(a^s-1,n) < n gives us a proper
factor of n. We did a detailed analysis of when that happened.
While the basic explanation is that p and q are split by computing the gcd if
p-1 divides s and q-1 does not divide s, the actual story is more nuanced.
The main insight is that only the order of a modulo p and modulo q matters
rather than p-1 and q-1 (which are the maximum orders that can appear for any
a). We discussed how a large prime l > b in q-1 means that with chance
(l-1)/l the gcd will not be divisible by q and that if a small prime l' is
needed to have s*l' be a multiple of p-1 we have a 1/l' chance of picking an a
so that p divides the gcd. The explanation uses that the multiplicative group
modulo a prime is cyclic. See the blackboard pictures for details. The
statistics on how many primes divide 2^s -1 for s the lcm of all numbers up to
20 are on these slides.
I had mentioned that the schoolbook method is not how RSA is used. To explain
why this is a problem I did an excursion into security notions and reductions.
I defined the attack goals of breaking one-wayness (OW) and of breaking
indistinguishability (IND) and the attack powers of chosen plaintext attacks
(CPA) and chosen ciphertext attack (CCA). The former is always possible for
public-key crypto, the latter models a very powerful attacker. We showed that
schoolbook RSA is not IND-CPA because it is deterministic and that it is not
OW-CCA-II secure because it is homomorphic. Take a look at these
slides for the statements and the
definition of RSA-OAEP, which is a way to work around these problems and is
used in practice.
I mentioned that the IND-CPA attack is a general problem with deterministic
encryption and that this is a meaningful concern because n real-world
situations we often have just a small set of answers (yes/no) that an attacker
could test the ciphertext against. It's a problem if the dictionary (the set of
possible plaintexts) can be exhaustively checked.
Homomorphic encryption is always a problem with OW-CCA-II but also offers some
features for advanced cryptographic applications, which may be worthwhile to
achieve only CCA-I security.
06 Oct 2026
Coppersmith's method finds small integer solutions to (systems of) modular
equations. We looked into factoring RSA numbers when a part of one of the
primes is known. For most of the lecture I covered the case that we know the
top 2/3 bits of p but I commented on how we can extend this so that we need to
know fewer bits of p.
In this lecture I showed Coppersmith's approach in that he sets up a system of
equation that are 0 modulo some b^k, in our case modulo p, and that one can
combine such equations to get new ones that are also 0 modulo b^k. A
theorem of Howgrave-Graham gives a bound on how large the root may be so that
the resulting polynomial has an integer root (instead of just a root modulo
some b^k). In our example we have b^k equal p and X is the bound on the unknown
part of p (the top part is assumed to be known as in the example of the TW
citizen cards. We
first treated LLL as black box algorithm which provides short integer linear
combinations. Then I explained what LLL does and what
guarantees it gives on the shortness of the output vectors.
Coppersmith's attack uses LLL to find a polynomial with bounded coefficients.
We did an example with Sage where I randomly picked 150-bit primes p and q and
"leaked" the top 102 bits of p. We set up the matrix as explained on the board
and we recovered the missing part of p. Then I showed a negative example were
we know only the top 82 bits of p, missing the bottom 68 bits. In this case the
polynomial from the first row does not have an integer root and we get an
error. We also tried the polynomial from the second row, but that also didn't
work.
Howgrave-Graham gives us an easy criterion to check when we can expect to get a
solution. LLL promises that the first vector is shorter than det(M)^1/d, where
d is the dimension of the matrix and I'm dropping some small constant. HG
promises success if this is smaller than b^k, which in our case was p. The 3x3
matrix that we constructed works for bounds X up to p^1/3. The 2 x 2 matrix
can't work at all. We looked at a 4 x4 matrix that covers a system of
equations modulo p, but that didn't get a better bound either.
To make progress and deal with fewer known bits of p, we need to use the
flexibility in the b^k and instead of considering equations modulo p, consider
equations modulo p^2. This means that we need an n^2 and n(x+a), so the
determinant gets a contribution of n^3, but we have a d-th root of the
determinant and once we get to a 5x5 matrix we improve the bound from n^1/6 to
n^1/5. [I messed up on my first trial but fixed the board before taking
pictures.]. The slides I showed are
here.
The next step would be to make a system modulo p^3, starting with n^3, n^2*f,
n*f^2, f^3, including also X*f^3, X^2*f^3, X^3*f^3. This reaches X < p^(3/7) (which
is larger than p^(2/5)). As you can see we're getting closer to p^(1/2) which
is the asymptotic limit of this method.
I showed
on the example of our attack on the Taiwanese citizen cards https://smartfacts.cr.yp.to that we did
find a case in practice where we had known parts of primes. See
the slides linked above for the story I told.
Generalizations exist to
bottom bits and bits in two chunks.
As an example of something totally different to do with this method I briefly
showed stereotyped, which will be the first topic on Thursday.
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 (13 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.
08 Oct 2026
After a recap of Coppersmith's method for factorization, we covered how to use
it for recovering the variable parts of a stereotyped message. This only works
for small public exponent e and does not work if padding is used (see OAEP
linked above) but is another easy application. We showed that for e = 3 we can
recover the missing part if it is no longer than 1/6 of the message.
I repeated Fermat's compositeness test and the (p-1)–method and that it works if one of the primes has that p-1 is smooth. This might prompt users to pick primes of the form p = 2p'+1 and q=2q'+1 with p' and q' primes, as this is maximally hard for this method. However, the (p+1)–method looks at smoothness of p+1 instead. With the Elliptic Curve Method (ECM) we have that p is found if the order of a point P on an elliptic curve E modulo p is a divisor of s. We know that any order in the Hasse interval is assumed and thus there is no way of escaping ECM.
A student was so nice to let me use their laptop to show Thijs Laarhoven's slides with a visualization of LLL, so I did a short show and tell with the slides. You can use LLL as a blackbox, but the illustration is great to see how the sizes of entries peculate through and average out.
Then we went back to factorization and covered that for ECM we start with a point and then construct a curve, and I stated the steps that ECM takes. During this I asserted that computing square roots modulo a composite number is hard. To show that I showed how we could turn an oracle that returns square roots into a factorization attack that succeeds with 50% probability.13 Oct 2026
To finish off the integer-factorization topic,
I showed the numerical example for Dixon from RSA-VI.
An idea for keeping the sizes of the auxiliary numbers small is to start with
the square root of n (round up) and then count up from there. This gives the
quadratic sieve (I think I said rational sieve and one student even checked
back with me, oops). The relevant part is that the numbers are much smaller
(around the square root of n) and that we can use sieving instead of trial
division to divide out the small primes.
I then showed some
slides
to show the Q-sieve. This slide set goes beyond what I had in the slides for
the YouTube talks for the other two RSA talks and are from a summer school
lecture that I gave for young researchers in Columbia. There is no need for you
to go through these, but you can find a lot more details than what I covered
today.
I only summarized the complexity of the Number Field Sieve attacks, for which I
introduced the L-notation
as a way to express complexities between exponential and polynomial
and how those are covered as L_n(1,c) and L_n(0,c).
Due to some recent news I stated the complexities of the General NFS with c =
(64/9)^{1/3} and of the Special NFS with c = (32/9)^{1/3} and commented on some
recent factorization records. Reasons for these comments are
In the break I answered some questions regarding the exam. The exam is scheduled to be held in person and your answers will be written on paper. You should teach your calculator to do
As a second topic we covered symmetric crypto. The assumption in
symmetric crypto is that A and B share a key k. They then use it to encrypt and
authenticate their messages. I mentioned block ciphers and drew the CBC and CTR
modes to show how to avoid that identical plaintext blocks encrypt to identical
ciphertext blocks.
You should watch Tomer Ashur's awesome videos
symmetric crypto,
stream ciphers,
block ciphers, and
modes of operation.
for a more detailed introduction.
What we covered in more detail is how to authenticate and protect integrity of
messages with a Message-Authentication Code (MAC), We assume that the users
share a key. The authentication tag should be such
that an attacker has only negligible chance of forging a valid message. We
apply the MAC to the ciphertext so that the decryption key gets used only on
ciphertexts that are valid. Always use a MAC when encrypting, we want
authenticated encryption.
Note that a MAC, as part of symmetric crypto, cannot be used to
prove authenticity to a third party. I mentioned HMAC as a standard hash-based
MAC and then went on to show how Wegman-Carter MACs work. These are used in
AES-GCM and in Poly1305.
For AES-GCM- see
NIST's
SP800-38D for the official standard and Dan Bernstein's
dummy submission
for the Caesar competition which used AES-GCM as an example of what a
submission should look like.
I then wrote out Poly1305 where we form a polynomial by taking the ciphertext
blocks as coefficient and evaluating it at the secret shared
value r. This computation is done modulo p = 2^{130} - 5. There is a second
part that is shared between the users and must be fresh for each new tag. I
tried to be smart and show how to avoid having (r,{s_j}) with many s_j as
preshared set, but we can just put s_j = AES_k(j) (no dependency on the
argument of the MAC, only on another shared key k). I also swapped the order
in which the ciphertext blocks are used as coefficients.
See the last
slide of sym-7.pdf for full details of Poly1305.
Here is the sheet for the instruction session (block 7 & 8).
Pictures of blackboards are here.
15 Oct 2026
I repeated the definition of Wegman-Carter MACs and highlighted that the s_j
must be used only once. In cryptography, a number that is used only once is
referred to as nonce.
You have seen in HW 4 that the ElGamal signature scheme is very sensitive to
nonce reuse, Exercise 2c) showed how an attacker can recover the private key
if Alice reuses a nonce.
We looked at another DLP-based signature scheme.
As a step towards the signature scheme we covered Schnorr's identification scheme which
is a zero-knowledge proof of knowledge of the discrete log of PA. We
showed why this is zero knowledge and why it proves that the prover knows a with Pa
=aP. The latter part also showed that if one signs two messages with the same
randomness R then an attacker can compute the private key, see also the fourth
homework.
In Schnorr signatures the random challenge picked by the verifier is replaced
by the output of a hash function which is computed over the message and the commitment.
Ed25519 and Ed448 are defined in
RFC 8032.
EdDSA is a direct instatiation of Schnorr
signatures with some improvements and handling that the basepoint P has order n/8
(where n is the total number of points on the curve and n/8 is prime). ECDSA is
slightly different in the order of how the operands are combined and is more
annoying in the verification because we need to compute inverses modulo the order
of P -- which is a good reason in addition to Pohlig-Hellman to choose groups of
prime order.
The Sony PlayStation
disaster (see 27C3 talk
PS3 Epic Fail)
gives a real-world example where Sony failed to update the random r. As you
have seen in the homework, this means you can compute a from just two signatures.
To avoid this fragility, EdDSA picks r peudorandomly, by generating the private
key as (a,b), with a the usual DL of the public key and b a seed for generating
r = hash(b,m), so ensure that different messages lead to different r.
We then covered ElGamal encryption. I skipped the proof that it is IND-CPA secure
with security closely related to the DDHP as I had enough to rant about. On exercise
sheet 7 you have an exercise to show that it is homomorphic, so cannot be OW-CCA II
secure.
I commented on the tension that to avoid
Pohlig-Hellman attacks one needs to work in a prime-order subgroup while for
ElGamal one needs to have that the messages are part of the group – or
the attacker can learn something about the message. I gave the Moscow voting
system as an example where the encryption leaked information on m. I used that
as inspiration for the last exercise on the exam on 21 Jan 2020. For the full
story see Pierrick Gaudry's talk at
ECC2019.
Finite-field DLP has lower security per bit than ECC.
Index calculus attacks have many similarities with the number-field sieve
attack: again we replace one hard computation with many easier ones. Here we
solve the DLPs for many small primes by setting up a system of linear equations
(to get there we again need to factor). Note that these attacks require fixing
a factor base for which it is easy to see whether a given element factors over
it. We have this for finite fields (including extension fields) using
factorization into integers (or irreducible polynomials) but not for
elliptic curves over finite fields. That's why we can safely use elliptic
curves over fields of size 256 bits while the DLP in finite-field needs to have
3072 bits to be equally hard. I showed an example using the slides
ff-dl-4.pdf for a small example of
index calculus attacks. For keysize recommendations.see e.g. the
ECRYPT-CSA
Algorithms, Key Size and Protocols Report. This report is from 2018 and an
update from 2020 exists but is locked up with ENISA. If you just want the
summary (which hasn't changed) see the first slide of
ff-dl-3.pdf.
These attacks also run in time L(1/3,c).
Interestingly, one can backdoor the prime selection to have an easier DLP, see
A kilobit hidden SNFS discrete
logarithm computation. This attack uses that the hardness of the DLP
depends on features of p and that one needs to know them in order to actually
break the system.
Pictures of blackboards are here.
21 Oct
I will offer an AMA online during 12:30 - 13:30. It would be nice if you could
send questions before the session so that I can prepare a bit.
Old exams by me: