2MMC10 Cryptology - Fall 2021

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 online exam will take place 2 Nov 13:30 - 16:30 using Ans Delft. After the exam you have 30 min during which you need to record a video of you explaining your solution.

Videos

This part has no-cookie links to the YouTube videos. Watch them from here 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.

You can also go to the YouTube Channel for the course and get notifications there.

Introduction

This video sets the context for the course and introduces the concepts of public-key cryptography and symmetric-key cryptography.

See also the slides.

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

Elliptic-curve cryptography

This video explains the Diffie-Hellman key exchange and shows one example of a group in which to use it, namely the clock.

See also the slides.

This video covers clock arithmetic over finite fields and shows the double-and-add method. It also has some important warnings.

See also the slides.
If you have never seen the square-and-multiply method (or just want a recap) and thus had problems with the double-and-add method, take a look at this video which I recorded for 2WF80 Introduction to Cryptology. The slides are here.

This video introduces Edwards curves and proves that the addition law does not have any exceptional cases.

See also the slides.

This video covers Edwards curves modulo a prime p. Do not be deterred by this video being somewhat longer. This is partially due to a proof which is not particularly illuminating, so you can skip it if you want, but I wanted to make sure to show everything for Edwards curves, and partially due to me giving some historical perspective at the end, which should be easy listening.

See also the slides.

This video goes back to the dark ages and shows how we used to explain elliptic curves. You will need the content starting page 5.

See also the slides.
The typos on the last slide are now fixed.

This video covers Montgomery curves, the concept of birational equivalence, and a proof that Montgomery curves have group order divisible by 4 over a finite field. The video also shows that Montgomery curves and twisted Edwards curves are birationally equivalent, thus proving the claim from part 4 that the group order on twisted Edwards curves over finite fields is divisible by 4.

See also the slides.

This video covers improvements of the double-and-add method using windows to save point additions and information on timing attacks.

See also the slides.

This video covers the double-and-always add method as well as the Montgomery ladder to compute scalar multiples in a constant-time manner. Note, this still requires your operations in the finite field not to show what the inputs are.

See also the slides.

This video covers projective coordinates, an explanation of points at infinity, and explicit formulas for addition on Edwards curves and differential addition and doubling on Montgomery curves.

See also the slides.

This video states the properties we want to achieve with signatures as well as the security notions and powers the attacker may be given.

See also the slides.

This video presents the Schnorr identification system, Schnorr signatures, EdDSA and ECDSA.

See also the slides

This video discusses a small speedup to the Pollard rho method that uses symmetries of the elliptic curve. In particular, identifying a point and its negative means that the search space for finding a collision has half as many elements, promising a speedup by a factor of √2 if the walk is defined to work on classes of points modulo negation. The talk shows pitfalls with this approach and how to circumvent them.
Yes, I did a whole video for a factor of √2 – I even wrote a paper about this once.

See also the slides

Further reading:

Discrete logarithm problem

This video sets up our targets. It covers hardness assumptions for Diffie-Hellman and related systems and also shows how to use it in practice and what issues can arise.

See also the slides.

This video goes through how to mount brute force attacks for a single target, multiple targets, and how to use random self reduction to turn one target into many and solve them faster. Optimizing and systematizing this approach we obtain the Baby-Step Giant-Step (BSGS) algorithm.

See also the slides.

This video covers random walk and cycle finding. This is relevant background for the Pollard-rho method, the subject of the next video. We also get a glimpse at how finding collisions in well-designed walks allows us to compute the discrete logarithm of a target.

See also the slides.

This video explains two ways to instantiate the pseudo-random walk in Pollard's rho method. Attacks use the second one, additive walks, as they are significantly faster. The video also discusses a small slowdown caused by these walks being not fully random.

See also the slides.

This video investigates how to use more than one computer to solve the DLP faster. The overall cost remains the same at n^(1/2) but using t computers gives a speedup of a factor t. To achieve this, the way of finding collisions has to be changed.

See also the slides.

This video uses a running example to find how to use subgroups to speed up attacks against the DLP. Systematic treatment happens in the following video.

See also the slides.

This video presents the Pohlig-Hellman attack. For an example see the previous video. Pohig-Hellman solves a DLP in an order-n group by solving it in the prime order subgroups. If a prime p divides n with multiplicity e, i.e. if p^e divides n, then Pohlig-Hellman solves e DLP in the subgroup of order p. The most interesting part is how to ensure that one lands in this subgroup and that the results are meaningful for the DLP computation. After all these partial DLPs are computed they are combined using the Chinese remainder theorem.

See also the slides.
If you don't know that theorem, watch this short video.

This video gives a summary of the generic attacks seen so far and studies the effect of subgroups on the hardness of the DDHP (decisional Diffie-Hellman problem).
Note: When Eve gets a challenge (aP,bP,cP) in DHHP then cP=abP with 50% probability, that's how the challenge is set up. So, guessing valid or not has a 50% probability of being correct.

See also the slides.

See ECC XII for attack optimizations for elliptic curves and the DL in finite field lectures below for improvements specific to ECC and finite fields.

Further reading

Hash functions

This video introduces hash functions as used in practice and covers the estimates for the generic hardness. Note that these are best-case estimates, i.e., a hash function cannot be stronger than this, but designs can be weaker.

See also the slides.

This video goes into details on attacking hash collisions using the Pollard rho method and what to consider for creating meaningful collisions. The attack page, also linked from the slides is Predicting the winner of the 2008 US Presidential Elections using a Sony PlayStation 3

See also the slides.

This video formalizes the security properties we want to achieve with a hash function. To make this work, we even have to change the definition of a hash function, which makes it less useful for describing properties of actual hash functions. However, it is possible to turn a given hash function into a keyed hash function, so this approach is not fully futile.

See also the slides.

This video covers reductions between hardness assumptions, both as a general concept and applied to the properties of hash functions.

See also the slides.

This video shows the sponge construction as a modern example of how hash functions are built. Some details for the NIST standard SHA-3 are given which is based on the sponge construction. Note that SHA-3 was called Keccak before being standardized.

See also the slides.

Symmetric cryptography

Tomer Ashur recorded 4 videos on symmetric-key cryptography, his area of research, for this course. He sure ups the game on video recording!

This first video sets the scene and puts symmetric crypto into a historical context. We use symmetric-key cryptography for encrypting data.

Stream ciphers use a key to deterministically produce a sequence of output bits (or bytes) that appear random and are unpredictable to an observer who obtains prior output but does not know the key. Alice can encrypt a message (written as a sequence of bits = vector in F2) by computing the xor = vector addition modulo 2 of the message with an output piece of the same length. Bob computes the same output and xors it with the ciphertext to get the message. Of course, both need to know where to start; to simplify this and avoid having to skip ahead by many steps stream ciphers use an extra input, the initialization vector, which is sent along with the ciphertext. With that, encryption and decryption start with the beginning of the output stream.

A block cipher encrypts a fixed-length message into a ciphertext of the same length using a key. To encrypt longer messages, modes of operation are used, see the next video. A block cipher is an invertible function from n bits to n bits, i.e., a permutation on {0,1}^n. Tomer covers general design strategies and speaks in more detail about AES.

To encrypt longer messages with a block cipher the message is split into pieces of n bits, possibly adding some padding if the length is not a multiple of n. If these blocks were encrypted individually, basic frequency analysis would weaken or break the system (this mode is called ECB = electronic code-book mode and the ECB penguin is the negative example you should keep in mind). Tomer covers the formal definition of modes and presents the modes CBC, CFB, OFB and CTR.

This video shows the Tiny Encryption Algorithm as an example of a block cipher and discusses the importance of cryptanalysis.

See also the slides.

In this video 4 variations on TEA are shown and broken. Each of these illustrates a technique used in symmetric-key cryptanalysis.

See also the slides.
The slides have been updated to clarify the meaning of high and low bits and that the first output bit is b_0.

This video introduces message authentication codes (MACs) and shows the Wegman–Carter construction, first for a small example and then for Poly1305, a MAC used in the real world.

See also the slides.

Further reading:

RSA, primes, and factorization

This video states the components of public-key cryptosystems as well as the security notions. It then explains the RSA cryptosystem and shows that schoolbook RSA is not IND-CPA or OW-CCA-II secure. Finally it presents RSA-OAEP as a solution to this problem, the padding randomizes the encryption process and destroys the homomorphic properties.

See also the slides.

This video shows RSA signatures and then investigates how RSA is used in GPG. For faster decryption it uses RSA-CRT which saves a factor 2-4.

See also the slides.

This video analyzes the first step in RSA KeyGen, namely how primes are picked – or rather how one determines that a given number is prime. It shows the Fermat primality test, the Miller–Rabin primality test and the Pocklington primality proof.

See also the slides.

This video gives and overview of factorization methods and explains Pollard's rho method for factorization.

See also the slides.

This video explains the p-1 method and its generalizations to the p+1 method and the elliptic-curve-method of factorization (ECM).

See also the slides.

This video shows the blue print of all the sieving methods: a hard to factor number n is factored by finding a and b with a^2 \equiv b^2 mod n and computing gcd(a-b,n). The methods differ in how these a and b are computed. This video shows Dixon's method of equivalences of squares.

See also the slides.

This video covers the Q-sieve as a stepping stone to the more general, and faster, number-field sieve. All computations here are simple integer computations. The only non-trivial part is in the analysis using the approximation u^{-1} of the Dickman function.

See also the slides.

A number field is an algebraic extension of Q, so the Q-sieve is a special case of the number field sieve. This video first covers the sieve for Q(√14) and then shows which parts generalize in the number field sieve.

See also the slides.

This video is easy listening for some disaster stories about RSA with bad randomness.

See also the slides.

This video introduces Coppersmith's method to factor integers with known bits. We actually found examples of where this worked in the wild and broke a bunch of keys. In general, Coppersmith's method is a way to find small roots of polynomials modulo RSA numbers using LLL.

See also the slides.

This video has all the details to understand Coppersmith's attack: showing the LLL algorithm and proving a theorem by Howgrave-Graham which explains how we build the matrices. Finally, the video also shows how to attack stereotyped messages, i.e., messages where only some small part is unknown, if RSA with small exponent is used.

See also the slides.

Further reading:

DL systems over finite fields

This video revisits the Diffie-Hellman system over finite fields and frames semi-static DH in the KEM-DEM framework, which is also introduced. ElGamal encryption is a randomized encryption system for DL system. We show that IND-CPA security is equivalent to DDHP.

See also the slides.

This video shows the schoolbook version of index calculus attacks. Optimized attacks differ in the details, but this gives you the gist of how they work. This is at the same level as Dixon's method of equivalences of squares compared to the number-field sieve for factoring.

See also the slides.

This video starts by showing the ECRYPT key-size recommendations. By now we know almost all systems appearing in that table. For finite-field DL systems there is a big difference between the needed group size and the needed field size; DSA is a signature system for which signatures are compressed to two elements modulo the group order, which is shorter than the corresponding ElGamal signatures would be. The video closes with an overview of what we have seen so far and gives the state of the art for crypto used on the Internet.

See also the slides.

Further reading:

Advanced systems and PQC

This video introduces pairings and shows how they can be used to attack ECC (in cases where efficient pairings can be computed).

See also the slides.

Class notes & exercises

This session is extended through the course. I will announce here which topics we cover which weeks and which videos you should watch to prepare for the live sessions. See here for the videos.

07 Sep 2021
In preparation for class, please watch the interaction video and the first two videos in elliptic-curve cryptography.
In the live session I explained the perfect-code system. Here are the slides perfect-code.pdf The exercise sheet for the live session is here.
Hints I gave for exercise 1

Spoiler alert! Don't follow the upcoming link if you sill want to solve exercise 1 yourself.
The "Perfect Code Public Key System" was designed by by Fellows and Koblitz. Attention, this was never proposed for cryptography but only as a teaching tool. I like using it because the public key looks very different from the private key.

09 Sep 2021
Please bring your questions. I've also added 3 more videos on ECC which you should watch. I understand that I was late in doing so, so I don't expect you to get this done by the lecture, but if you do and if you do have questions I'll be there to answer them.
We went through most slides sets of videos. To see the case for (x2-y2) being nonzero in the proof for Edwards curves over finite fields, start with (x1-y1\epsilon) and trace the sign change through the formulas.

14 Sep 2021
Please watch the remaining 4 videos on ECC (part 6 - 9) before the session. We will meet in the wonder.me room, I will post an exercise sheet before the session starts.
The first homework is due on 21 Sep at 13:15 via Canvas. Note that homeworks exercises are different from the exercises for the live sessions and I am allergic to answering questions about the homeworks in the Tuesday sessions. I will normally post the homework sheet only after the Tuesday session, but this one has been long announced.
The homework sheet has been updated to specify that exercise 2 is for Edwards curves, i.e. a=1.
The exercise sheet for the live session is here.

16 Sep 2021
This is a Q &A session on BBB, you have gotten an invitation already. Please bring your questions! Topics can be the first 9 ECC videos or the first 3 DLP videos. Also please ping me if you have problems signing up for Zulip.
We discussed exercise 2c from sheet 1, exercise 7 from sheet 2, what isomorphisms mean, and why it is enough for DH to use only the u-coordinate on Montgomery curves..Here are the notes that I was typing in the shared document. I had made an error in copying within the calculation for the isomorphism an fixed that after the end of the session. I've also done some minor cleanup for the rest.

21 Sep 2021
Please watch the next 4 videos on DLP (part 4 - 7) before the session. If you have not used Sage I recommend you watch the introductory video I recorded, see second video under Introduction.
We will meet in our wonder.me room, see Canvas or Zulip for the URL. The exercise sheet for the live session is here.

The second homework is due on 28 Sep at 13:15 via Canvas.

23 Sep 2021
This is a Q &A session on BBB, you have gotten an invitation already. Please bring your questions! Topics can be the first 9 ECC videos, the first 8 DLP videos, the first 2 hash videos and Sage. Also please ping me if you have problems signing up for Zulip.
We discussed what random self reduction does, how and why Pollard rho works, and why Pohlig–Hellman works.

28 Sep 2021
Please watch the remaining videos on hash functions and on ECC before this session. There are now 5 hash videos and 11 ECC videos.
We will meet in our wonder.me room, see Canvas or Zulip for the URL. The exercise sheet for the live session is here.

The third homework is due on 05 Oct at 13:15 via Canvas.
There was a typo in 2b: k_i was supposed to be r_i. This is now fixed.

30 Sep 2021
This is a Q &A session on BBB, you have gotten an invitation already. Please bring your questions! Topics can be anything we covered up to now, but I would like to focus on questions regarding the most recent videos, so hash functions, signatures, and symmetric cryptography.
We covered in detail why the verification equation of EdDSA / Ed25519 includes a multiplication by 8. You can find the slides for it here.

05 Oct 2021
Please watch the remaining videos on symmetric-key cryptography (up to VI) before this session.
We will meet in our wonder.me room, see Canvas or Zulip for the URL. The exercise sheet for the live session will be posted before the session. is here.

The fourth homework is due on 12 Oct at 13:15 via Canvas.

07 Oct 2021
This is a Q &A session on BBB, you have gotten an invitation already. Please bring your questions! Topics can be anything we covered up to now, but I would like to focus on questions regarding the most recent videos, so symmetric-key cryptography and RSA.
I would appreciate getting some questions in advance on Zulip so that I can prepare some extra material.

12 Oct 2021
Please watch the new videos on RSA (up to VIII, up to VI is needed) before this session.
We will meet in our wonder.me room, see Canvas or Zulip for the URL. The exercise sheet for the live session is here.

The fifth homework is due on 19 Oct at 13:15 via Canvas.

14 Oct 2021
This is a Q &A session on BBB, you have gotten an invitation already. Please bring your questions! Topics can be anything we covered up to now, but I would like to focus on questions regarding the most recent videos, so RSA and finite-field DLP.
I would appreciate getting some questions in advance on Zulip so that I can prepare some extra material.

19 Oct 2021
Please watch the new videos on DLs in finite fields (up to III), ECC XII, and Pairings I before this session.
We will meet in our wonder.me room, see Canvas or Zulip for the URL. The exercise sheet for the live session will be posted before the session.

21 Oct 2021
This is a Q &A session on BBB, you have gotten an invitation already. Please bring your questions! We have reached the end of the course with ECC I-XIII, DLP I-VIII, hash I-V, symmetric crypto I-VII, RSA I-IX, DLs in FF I-III, Pairings I-III, and single lectures on Paillier encryption and post-quantum cryptography.
Topics can be anything we covered up to now, but I would like to focus on questions regarding the most recent videos, so everything after RSA.
I would appreciate getting some questions in advance on Zulip so that I can prepare some extra material.


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: