2MMC10 Cryptology - Fall 2019

Contents Announcements Exams Literature Pictures and slides

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

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 be an open-book exam, meaning that you can use any book or notes that you have on paper. You may use a programmable calculator and I expect you to be able to use it for modular exponentiation and inversion.
I will also bring some laptops with access to the course page incl. blackboard pictures and scripts, but you may not use it to surf the internet. There will be a termnal to run GP-Pari; sage is not available on the laptop.

For 2MMC10, the first exam will take place October 29, 2019, 13:30 - 16:30 in GEM-Z 3A08, 3A10, 3A12, and 3A13, that's in the Gemini building at the south side. The retake exam will take place January 21, 2020, 13:30 - 16:30 in Atlas 4.215 and Atlas 4.225. Take a look at the campus map to find the building. .
For Mastermath the exam will take place on January 21, 2020, in Eindhoven together with the retake for 2MMC10. this means that you need to come to TU/e on Jan 21. The retake still needs to be scheduled but will either be 25 February 2020 in the afternoon or replaced by oral exams.

For 2MMC10 you can earn up to 1P for the final mark through the homework. Please hand in your solutions in groups of 2 or 3, we do not have the capacity for individual corrections. Please make sure to register for the exam in time. For TRU/e students from Nijmegen, this means that you need to register at TU/e as well and get a student number etc.

For students from Mastermath, please register on their site.
You can earn up to 1P for the final mark through the homework. The bonus point only counts if the grade for the exam is at least 5.0, so even if you score a full bonus point in the homework but only a 4.5 in the test you do not pass. Please hand in your solutions in groups of 2 or 3, we do not have the capacity for individual corrections. Please submit your solution on time by email to the address below.

For all students: Manos Doulgerakis and Florian Weber are the teaching assistants for this course. You can reach them at crypto.course (at) tue.nl.
Do not send me your homework but submit it on paper before the Thursday lectures. If there is a programming component to the exercises email the solution to the TAs.
If an assignment is unclear and you have questions about the homeworks, contact me in class or by email.

Class notes

The course notes will be filled in after each lecture. You will find a summary of the content of the lecture, links to further reading or slides, and pictures of the blackboard. The homework sheets will be posted along with the notes.

03 Sep 2019
General introduction to cryptography; concepts public key, symmetric key cryptography, and hash functions. Pictures of blackboards are here.

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.
Here are the slides in pdf for the perfect code system. The other hints I gave are


05 Sep 2019
Recap on Fermat's little theorem, Euler phi function and its computation, Chinese Remainder Theorem (CRT).
RSA encryption (KeyGen, Encrypt, Decrypt), exponentiation via square and multiply method.
Faster decryption/signing via CRT-RSA incl. estimates on improvement (look up Karatsuba multiplication).
Fermat's primality test.
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 12 Sep, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 19 Sep, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. The exercise sheet is here. For the RSA exercise you can assume a caclulator with very large precision, i.e. you should use the square-and-multiply method.

10 Sep 2019
RSA signatures; note the use of the hash function.
Miller-Rabin primality test. Fermat and Miller-Rabin are 100% correct when they output 'not prime'; otherwise they say 'maybe prime'. If you want to be sure that a number is prime, you need to use a primality proof. We covered Pocklington's test which does not work for all primes (in the way I presented it). I'll get back to this later..
Factorization techniques for integers: trial division, Pollard's rho method including explanation why it works when it works and Floyd's cycle-finding algorithm. In practice you would batch the gcd computation, doing one only every l steps and computing the gcd over the product of the steps. Each step then costs 3 squarings (two for the fast walk and one for the slow walk) and 1 multiplication (for the product in the gcd). Note that all of these are done modulo n. Furthermore, l steps together incur one gcd computation.
Pictures of blackboards and videos are here.

12 Sep 2019
Pollard's p-1 method including why it works
Factorization using Dixon's method/method of random squares. We used the computer algebra system Pari-gp for the examples and I wrote some of the commands on the board.
You can find examples and code snippets for these methods and those from the previous lecture on http://facthacks.cr.yp.to.
Pictures of blackboards are here.

For 2MMC0, homework is due next Thursday, 19 Sep, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 03 Oct, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. The exercise sheet is here.

17 Sep 2019 General factorization methods: Dixon, quadratic sieve, Q-sieve, number field sieve. To reduce the size of the inputs and thus to increase the chance of smoothness and to use sieving we showed how the quadratic sieve works. As a step towards the general number-field sieve we covered the Q-sieve with slides, of which we covered the first pages. To see the asymptotic analysis, read on.

If schoolbook RSA is used many things can go wrong, in particular if the public exponent is small. We covered the basic case that the message has less than 1/e of the bitlength of n and thus no reduction took place and then covered stereotyped messages. For those we could try to brute force the missing pieces but an attack using lattices is much faster. Take a look at page 29 onwards of these slides to see how we can set up a lattice and then use LLL to solve for the varying part of the stereotyped message. We used sage for the live computations and the slides.
To avoid such issues use a large modulus and modify the message before encryption. We covered OAEP, see also the next homework sheet. Note that there was an error in the lecture. I confused the positions of H and G. I have now fixed the jpgs.
Coppersmith's method is a way to find small roots of polynomials modulo RSA numbers using LLL. As a second example we showed how to set up a system to break RSA if all but the bottom 86 bits of p are known, for n=p*q. This is explained with examples on page 14 onwards of these slides (same as above). For a practical example that it can really happen that parts of the secret RSA primes become known I showed an explanation of the ROCA results using my own slides (see page 72 onwards; this is the same slide deck as for the Q-sieve). We wrote a longer blog post on this here.
The slides before that (page 56 onwards) cover another real-world example of bad randomness and attacks using Coppersmith' method. For the full story check out http://smartfacts.cr.yp.to/.
Pictures of blackboards are here.

19 Sep 2019
Lecture given by Andreas Hülsing on cryptographic hash functions.
Desired properties of hash functions: preimage resistance, 2nd preimage resistance, and collision resistance; attacks on hash functions: brute force, birthday, Pollard rho; length extension constructions: Merkle-Damgaard, sponges; compression function design: MMO; provable security and reductions: relations between hash function properties; brief intro to hash-based signatures: Lamport-Diffie OTS, Merkle signature scheme.
Andreas was so nice to make his slides available:
[part1-pdf], [part1-pptx], [part2-pdf], [part2-pptx]

Pictures of blackboards are here.

For 2MMC0, homework is due next Thursday, 26 Sep, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 17 Oct, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. The exercise sheet is here.

24 Sep 2019
Some more background on Coppersmith's method, including a bound on the length of the shortest vector output by LLL and a theorem by Howgrave-Graham. If you want to learn more about this take a look at the overview article by Alexander May (you need to be on a university network to download it). Exercises based on this method appear fairly often in crypto challenges and CTFs – and as we found out also in real-life scenarios such as the Taiwanese Citizencards and ROCA, so it's a good tool to know

Diffie-Hellman key exchange, related problems (DDH, CDH, DLP) and their relations. ElGamal encryption (why it works, that it is homomorphic, and that you can break the IND-CPA security if if you can solve DDH).

Pictures of blackboards are here.

26 Sep 2019
ElGamal signatures, DSA), and attacks on DLP: brute force, Pohlig-Hellman attack,
Pictures of blackboards are here.

For 2MMC0, homework is due next Thursday, 03 Oct, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 31 Oc, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. The 4th exercise sheet is here. Note: I corrected h to h' in step 2; this does not affect the homework as there the highest power of a p_i was 2.

01 Oct 2019 DSA (how and why it works, some paramters). For more on parameters for DSA, see http://www.keylength.org/.
Generic attacks on the DLP: baby-step giant-step, Pollard's rho method.
Explanation of index calculus attack, factor base, complexity of basic index calculus is Lq(1/2,c), with several improvements it's Lq(1/3,c), where the constant c depends on the field type. For fields of small characteristic stronger attacks exist. The logjam attack makes use of precomputation to attack individual DLPs very quickly. Check out the page for details.

Pictures of blackboards are here.

The second part of the lecture was given by Daniel J. Bernstein on symmetric cryptography. He explained the general history and functionality and then MACs (Message Authentication Codes), which are used to authenticate messages. In particular he explained Wegman–Carter MACs which are information-theoretically secure.
He has posted his slides

03 Oct 2019 Lecture was given by Daniel J. Bernstein.
He presented the concepts of pseudo-random functions (PRFs) and pseudo-random permutations (PRPs), block ciphers, and modes. He explained cipher design and attack avenues on the example of the Tiny Encryption Algorithm (TEA) by doing minimal changes to the algorithm and then showing how to break the tweaked version.
He has posted his slides

For 2MMC0, homework is due next Thursday, 10 Oct, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 14 Nov, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer. The exercise sheet is here.
Also, please read the logjam paper for the index calculus attack details or take a look at Nadia Heninger's slides. Make sure not to overlook one mathematically interesting attack in the logjam paper: some implementations messed up the parsing of generator and order of generator in the DSA setting; you'll see the part on TLS in Applied Crypto.

08 Oct 2019
Clock group and arithmetic: lots of points on the unit circle; how to add them using their angles, translation using trigonometric formulas, addition law using regular carthesian (x,y) coordinates, (0,1) is the neutral element, -(x,y) =(-x,y), addition is obviously commutative. Some special points and their orders; clocks modulo p.

Edwards curves, picture for d&tl; 0, addition law; no division by 0 if d is not a square (which matches d< 0 over the reals) with proof over any field, finding points on an Edwards curve modulo 5, pictures for d >0 and 0 < d <1.

The video I mentioned at the end of the lecture showing geometric addition laws for the 0 < d <1 is here (YouTube link)

Pictures of blackboards are here.

Florian Weber wrote up an extra document on reduction proofs for your information. This includes a coments on the grading for exercise shee 3 for students of 2MMC10. You can find the sheet here.

10 Oct 2019 Twisted Edwards curves as a generalization of Edwards curves. Doubling, projective coordinates, explicit formulas for doublings with operation count. For many more (and computer verified!) formulas see the EFD.

Weierstrass curves incl. pictures over the reals; addition on Weierstrass curves and partial proof that this is a group law; Explanation of point at infinity via projective coordinates; derivation of addition formulas on Weierstrass curves.
Montgomery curves as a special form of Weierstrass curves; easy to map between Montgomery curves and Edwards curves, so they have the same security. Montgomery curves are not just interesting as yet another curve shape. Montgomery curves have efficient scalar multiplication using one DBL and one DADD per bit of the scalar using the Montgomery ladder; see RFC 7748 for details on Curve25519 and Curve 448 and how to implement them correctly and efficiently.

Pictures of blackboards are here.

For more material on elliptic curves check out the tutorial I gave at Indocrypt 2011. There even exist some videos of it part I and part II.
For an overview of suggested curves and their security properties see http://safecurves.cr.yp.to/, where we check security properties of curves agains mathematical and implementation-based attacks.
I mentioned that the deigner of the system can choose the parmeters, of course within the limits of making secure choices. However, there is also some risk in this flexibility, namely that somebody might make malicious choices. We actually did some work on figuring out how much freedom sombody has to sneak in a backdoored curve (not that we know of any way of backdooring curves). Our results are online. Have fun!

For 2MMC0, homework is due next Thursday, 17 Oct, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 28 Nov, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer. The exercise sheet is here.

15 Oct 2019 Lecture given by Lorenz Panny.
Quick repetition of projective coordinates. Elliptic Curve Method (ECM) for factoring as generalization of p-1 method using elliptic curves modulo n to factor n. Hasse's theorem says that the number of points on a curve over F_q is away from q+1 by at most twice the squareroot of q.

Pollard rho method as an attack on the ECDLP; parallel rho method in order to use multiple computers and have shorter walks, this uses distinghuished points. How to choose the step function? Quick repetition of the schoolbook version. Real attacks use additive walks with many precomputed steps, for sufficiently many steps, this is close to random and for r different steps the probability of success is reduced by √1/(1-1/r).
For ECDLP we can group P and -P in the walk to gain a factor √2 in speed, however this requires us to deal with fruitless cycles, i.e. walks that get stuck in a very small loop, colliding with itself without solving the ECDLP, but we know how to escape them.

The slides for Pollard's rho method are here.

If you want to learn more about solving the ECDLP or care about attacks in interval, take a look at slides from a summer school talk. Spoiler alert: cute kangaroo pictures!

Pictures of blackboards are here.

17 Oct 2019 Lecture given by Andreas Hülsing.
Formal treatment of secret key cryptography. Secret key encryption: Perfect secrecy, IND, SEM, IND-CPA, IND-CCA. PRGs, PRFs, PRPs and how to use them to build (secure) encryption. Message authentication: EU-CMA, PRF is a secure MAC, CBC-MAC, how to securely combine SKE & MAC.
Andy was so nice to make his slides available.

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: