2MMC10 Cryptology - Fall 2022

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

Announcements

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.

Literature

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):

You can also find a lot of information (though not written as a textbook) in the Handbook of Applied Cryptography. Note that the authors were so nice to offer chapters of HAC online for download.

Examination

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.

Videos

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.

Class notes & exercises

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.


What's next?

Here are a few courses that you might find interesting:

Old exams

Old exams by me:

Andreas Hülsing gave the course in 2018. His exams are available online Henk van Tilborg has agreed that I put up his old exams for you to practice: