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 6.104B
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.
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 exam will take place 1 Nov 09:00 - 12:00.
The resit for 2MMC10 is planned for 24 Jan 2023 18:00 – 21:00.
The videos from this course appear on
this page of videocollege,tue.nl. You can find
older editions of this course
here.
Note that this page shows lectures
from multiple years and that there are some differences between the
course versions; I taught the course in 2019 and my colleague Andreas
Hülsing taught 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.
For even fewer cookies, you can find the
videos on surfdrive. File names match the file names of the slides.
This section is extended through the course with notes of what happened in class and links to blackboard pictures.
06 Sep 2022
This lecture was given by Florian Weber.
General introduction to cryptography; concepts public key,
symmetric key cryptography, and hash functions.
Spoiler alert! Don't follow the upcoming link if you sill
want to solve exercise 1 yourself.
As an example we attacked the
"Perfect Code Public Key System" by Fellows and Koblitz. Attention,
this was never proposed for cryptography but only as a teaching tool.
I don't have the slides from Florian, yet, here are the slides from last
year
pdf for the perfect code
system. Other hints:
08 Sep 2022
We covered Diffie-Hellman key exchange and related problems (computational Diffie-Hellman
problem, decisional Diffie-Hellman problem, and discrete logarithm problem) abstractly,.
Then we covered the clock group over the reals (or rational numbers) as a bad example
where the attacker can easily solve the discrete logarithm problem, 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. This is an example of a cryptosystem
against which the best attacks have subexponential (but superpolynomial) complexity; we
will get to this attack much later.
Finally we saw Edwards curves and the addition law and how much it resembles addition
on the clock.
If you're following this course with the short videos from last year you should watch
the first three videos on elliptic curves. It's not a 1-to-1 match (some missing, some
extra) but covers the core.
Homework is optional. If you want feedback, please submit by next Thu (15 Sep)
before 10:30 through Canvas. Please submit in groups of 2-3 people; we do not have
capacity to grade everybody individually.
Here is the first homework sheet.
The pdf file has been updated to fix exerice 1 (1 missing on right side of the equation)
and 2 (the point of order 2 is (0,-1)).
Pictures of blackboards are here.
13 Sep 2022
Recap of Edwards curves; proof that denominators are never 0 over the reals if d is
negative. For the proof that there are no exceptions over F_p for p>2 and d a non-square
please watch ECC from the
YouTube Channel.
We showed that the points on Edwards curves form a group under this addition with
neutral element (0,1) (see homework) and -(x,y)=(-x,y). The group is commutative.
The number of points on the curve over F_p is in [p+1-2√ p, p+1+ 2 &rad; p].
Twisted Edwards curves are a generalization of Edwards curves but the number of points
over any finite field remains divisible by 4. This will be shown once we cover Montgomery
curves.
FInally we covered Weierstrass curves and showed how isomorphisms let us take the long
Weierstrass form and (for characteristic not equal to 2 or 3) move to the short Weierstrass
form. I finished with showing pictures of the addition law but haven't written out the
formulas, yet.
If you're following this course with the short videos from last year you should watch
ECC IV and V. It's not a 1-to-1 match (some missing, some
extra) but covers the core.
Pictures of blackboards are here.
15 Sep 2022
Recap of Weierstrass curve addition. We developed the addition formulas incl.
proving that there is exactly one 3rd. point on the curve for a line of the
form v= λ u + μ 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 resutls and in crypto that's often enough
for an attacker to get in.
Montgomery curves are another special curve shape; we covered the addition law
(to the extent that it differs from the Weierstrass case); showed that over a
finite field that are 3 points of order 2 or points of order 4 (meaning that the
group order is always divisible by 4); and then showed that Montgomery curves
and twisted Edwards curves are birationally equivalent.
Inversions are computationally expensive, so for efficient implementations we
like to work with fractions and clear denominators only at the end of the
computation. 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 nonzero 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). I showed how the Edwards curve addition law looks using projective coordiantes
and then showed Curve25519 as a real-world example of what you use in Signal,
WhatsApp, and https for doing a key exchange. I used
slides to show these latter items.
Homework is optional. If you want feedback, please submit by next Thu (22 Sep)
before 10:30 through Canvas. Please submit in groups of 2-3 people; we do not have
capacity to grade everybody individually.
Here is the 2nd homework sheet.
Pictures of blackboards are here.
If you're following this course with the short videos from last year you should watch
ECC V, VI, and IX. It's not a 1-to-1 match (some missing, some
extra) but covers the core.
20 Sep 2022
We covered the double-and-add method and its speedup in the windowing method.
An attacker might be able to obtain side channel information, such as timing
(at different levels of precision), electomagnetic 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 Hanning weight of a. In several cases this leakes 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. In terms of defenses, we covered the double-and-always add menthod and
the Montgomery ladder; the latter is interesting for efficient implementations as
it ensures that each addition is an addition of points with known, fixed difference
P. On Montgomery curves, such differential additions can be efficiently commputed
using only the u-coordinates of the points and their difference. I showed the
projective version of this computation.
All of this is covered in these
slides, I also scribbled a small example of
computing 42P on the board.
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.
For the second half we covered attacks on the discrete logarithm problem, starting
from the naive search through all multiples of P to randomizing the target, turning
one target into many, and more, how many targets are useful at most, and how to
systematize this. This led us to (a transposed version of) the Baby-Step-Giant-Step
(BSGS) attack, which computes a = i - jm mod N for m=√ N and 0≤ i,j ≤ m.
Hence, the DLP in a group is no harder than the square root of the group order.
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - IX and DLP I - II.
22 Sep 2022
Complexity estimates for BSGS, big-O notation, worst-case and average-case cost
for BSGS for computation and storage.
Birthday paradox and how we can use this to develop a probabilistic algorithm
that also runs in time √N but does not require storage. Pollard's rho
method with Floyd's cycle-finding method runs in O(√N) and only uses two
points. The pseudorandom function f can just be some hash of the coordinates
of W which produces b and c (we'll see a cheaper way next week). Getting the
DL a from the collision is just computing a=(bj-bi)/(ai-aj) modulo N.
Finally we looked at van Oorschot and Wiener's parallel collision search to
use T computers efficiently to solve the DLP T times faster. The attack designer
can choose the frequency of distinguished points to control the lengths of the
walks, storage (and communicaion) costs, For solving DLs we recompute the whole
walk up to the DP to get the coefficients; when we see this method again in
breaking hash functions it's important to find the first collision.
I used
slides to show what the resulting graphs look
like.
Homework is optional. If you want feedback, please submit by next Thu (29 Sep)
before 10: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.
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - IX and DLP I - V, apart for the additive walks.
You should now be able to solve the exercises from the presence exercise sheets
from 2021 up to and including exercise 5 on sheet 3. Solve those for checking
your progress.
Old exams by me: