2MMC10 Cryptology - Fall 2018

Contents Announcements Exams Literature Class notes

Andreas Hülsing
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room MF 6.097a
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands

Phone: +31 (0) 40 247 6088

The easiest ways to reach me wherever I am:
e-mail: andreas (put_at_here) huelsing.net

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. The first part of the course is based on Katz and Lindell's "Introduction to Modern Cryptography", CRC Press, 2014.
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 literature 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

Please note that the date for the Eindhoven resit / MasterMath exam changed to Friday, January 25th, 2019, 13:30 - 16:30. Sorry for the late note but there were some scheduling issues with MasterMath.

The exam will be an open-book exam, meaning that you can use any book or notes that you have on paper. However, I strongly suggest that instead of bringing a whole bunch of books, you bring one handwritten A4 sheet with all formulas that you consider relevant. The preparation of this sheet is typically the best preparation for an exam. You may use a programmable calculator and I expect you to be able to use it for modular exponentiation and inversion. To clarify: You are not allowed to use your personal laptop!
We will also bring laptops with access to the course page incl. blackboard pictures and scripts, but you may not use it to surf the internet (this also means that externally hosted materials like old exams are inaccessible). There will be a terminal to run GP-Pari; sage is not available on the laptop.

For 2MMC10, the first exam will take place October 30, 2018, 13:30 - 16:30. The retake exam will take place January 25, 2019, 13:30 - 16:30.
For Mastermath the exam will take place on January 29, 2019, in Eindhoven together with the retake for 2MMC10. This means that you need to come to TU/e on Jan 29. The retake still needs to be scheduled.

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.
Do not send me your homework but hand it in on paper before the Thursday lectures. If and only if there is a programming component to the exercises email the solution to the TAs using the email address below.

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: Leon Groot Bruinderink and Manos Doulgerakis are the teaching assistants for this course. You can reach them at crypto.course (at) tue.nl.
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. Videos can be found on https://videocollege.tue.nl/Mediasite/Catalog/catalogs/Cryptology shortly after the lecture (typically within a day).

04 Sep 2018
General introduction to cryptography; symmetric key cryptography: symmetric key encryption, attacker abilities / attack types, paradigm of modern cryptography, attack goals. On the way we used a reductionist proof in an example. Pictures of blackboards are here.

If you want to try your skills at breaking some cryptosystems visit http://www.cryptopals.com/ and look into the first set of challenges.

06 Sep 2018
Perfect secrecy: different definitions, one-time pad, limitations of perfect secrecy. Pictures of blackboards are here.

For 2MMC0, homework is due next Thursday, 13 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, 27 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.
Hint: For exercise 3, one of the directions is easier to prove using a forward proof (not towards a contradiction). A key thought is that the adversary is a deterministic algorithm.

11 Sep 2018
Computational security: Concrete security, asymptotic security. Pseudorandom generators, PRG Encrypt. Pictures of blackboards are here.

13 Sep 2018
IND-CPA security, pseudorandom functions (PRF), IND-CPA secure secret-key encryption using a PRF, pseudorandom permutations (PRP). Pictures of blackboards are here.
The blackboards contain a mistake which is corrected in this "Cryptology: Errata and additional content for lecture on Thursday September 13" file. The file also covers modes of operation for block ciphers and more generally PRPs which we did not manage to cover in todays lecture. Please read this file before the next lecture.
For 2MMC0, homework is due next Thursday, 20 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, 11 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.

18 Sep 2018
Lecture by Daniel J. Bernstein on symmetric primitives. Covered TEA block cipher, TEA-CTR, TEA-XCBC-MAC, Feistel Networks, overview over other symmetric primitives. The slides are available on Dan's homepage.

20 Sep 2018
Message authentication codes and hash functions: formal definition of MAC and EU-CMA; PRFs are good MACs; CBC-MAC; how to combine ENC and MAC; hash functions; OW, SPR, CR; relations among notions; generic attacks; birthdaying, Pollard-roh + Floyds cycle finding; length extension modes: Merkle-Damgard and Sponges.
Slides are here: MAC, Hash part 1 [pdf], Hash part 1 [pptx], Hash part 2 [pdf], and Hash part 2 [pptx].
Pictures of blackboards are here.

For 2MMC0, homework is due next Thursday, 27 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, 25 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.

25 Sep 2018
Hash function constructions: Recap on length extension, MD4 family and attacks on MD5. Public key cryptography: Public key encryption and digital signatures. IND-CCA and EU-CMA. Hybrid encryption.
Slides on hash functions were already included in Hash part 2 [pptx] from last week.
Pictures of blackboards for the PKC part are here.

27 Sep 2018
Short recap on what digital signature schemes are used for; KEMs; RSA: Schoolbook RSA and why it is insecure, Recap on math background, (Schoolbook) RSA Encrypt, RSA problem, homomorphic property. Secure RSA encryption: RSA-OAEP.
Pictures of blackboards are here.

For 2MMC0, homework is due next Thursday, 04 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, 08 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. The exercise sheet is here.

02 Oct 2018
Fast exponentiation using Square & Multiply; RSA Signatures: Schoolbook, why it is insecure, and FDH / RSA-PSS. RSA-CRT for efficent secret exponentiation. We started to look into factoring. We covered trial division and Pollard's roh.
Pictures of blackboards are here.

04 Oct 2018
Tanja covered the following: A quick wrap-up of Pollard's rho method, highlighting the space savings when implementing this on a computer vs. the minor slowdown of not finding the first collision in Floyd. Pollard's p-1 method: how it works and why it works. Bad RSA numbers have p and q very close. This is easy to see by inspecting √n: if this has one or even many 9s after the decimal, will be very close to the squarroot. Just do a brute-force search; e.g. 323=17*19. If a^2 ≡ b^2 mod n we have at least 50% chance of factoring n using gcd(a-b,n) -- all but a = ± b will give a nontrivial factor of n. Dixon's method/method of random squares builds such squares. Tanja used the computer algebra system PARI/GP for the examples. The main command was factor(lift(Mod(a^2,n))) to try to get one relation for Dixon. A relation is of the form a^2 = Πpiei where the left side is first reduced modulo n and the resulting integer is factored. The pi are primes. A relation is kept if all the primes are in the factorbase. Once enough relations are collected a linear combination of them is computed that turns the right side into a square by taking the product of the relations. Tanja mentioned the quadratic sieve and the number-field sieve as further improvements and briefly showed the Q-sieve using slides from a course she taught on factorization. You can find examples and code snippets for these methods and those from the previous lecture on http://facthacks.cr.yp.to. The slides Tanja used are here.
Pictures of blackboards are here.

For 2MMC0, homework is due next Thursday, 11 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, 22 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. The exercise sheet is here. In the first version of this sheet there was a little mistake in exercise 5. Namely, at two places I forgot to add that F is applied. Please check the new sheet!

09 Oct 2018
Primality testing: Fermat and Miller-Rabin primality tests; Rabin Encryption scheme: We showed that being able to compute squares mod N is equivalent to factoring N (actually I omitted the proof that you can compute square roots if you can factor, read up on this on Wikipedia where it is explained in the context of decryption for Rabin-PKE). We showed that this gives a one-way function from factoring and that this function becomes a trapdoor one-way permutation over QRN if N is a Blum integer. Then I introduced textbook Rabin PKE and we left a proof for its OW-CPA security as exercise.
Pictures of blackboards are here.

11 Oct 2018
Cryptography in cyclic groups. I first introduced some hard problems in cyclic groups: DLog, CDH, and DDH. Then we looked at the definition of key exchange protocols and saw DH (Diffie-Hellman key exchange). Afterwards we did ElGamal encryption and proved it IND-CPA secure.
Pictures of blackboards are here.
I commented in the beginning of the lecture that in the last lecture we only stated that Rabin PKE is OW-CPA but that we can turn it into a IND-CCA secure KEM. This is described in Section 8 of this paper.

For 2MMC0, homework is due next Thursday, 18 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, 06 Dec, 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.

16 Oct 2018
ElGamal Signatures, and their "issues". I did not say this in class, but the reason I did not get into any security proof for this scheme is that the proof requires techniques that go beyond the scope of the lecture. For those interested: The underlying concept is to start from an identification scheme which is an interactive protocol in which a prover proves to a verifier that it knows a matching secret key for a public key (without leaking the secret key). This protocol is then made non-interactive using the so-called Fiat-Shamir transform.
Then we went on to generic algorithms to solve DLog over cyclic groups. We covered Brute-Force Search, Baby-step/Giant-step, Pollard-roh, and most of Pohlig-Hellman (I owe you the part where we turn a DLog in a prime-power order group into DLogs in a group of order of the respective prime). All these algorithms are generic and have runtime exponential in the largest prime factor of the group order. I did not have the time to touch upon index-calculus methods which have sub-exponential runtime. However, they only apply to certain groups (but these "certain groups" include finite fields which were / are used in crypto). You can read up on Index-Calculus in the Katz & Lindell book or watch last years lecture on it which you find here.
Pictures of blackboards are here.

18 Oct 2018
We finished the Pohlig-Hellman algorithm, showing how to turn a DLog in a prime-power order group into several DLogs in a group of the order of the prime. Afterwards we did clock based crypto and afterwards elliptic curves (mostly Edwards curves). I did a really short primer for this. A talk on this topic for a more general audience was given by Daniel J Bernstein and Tanja Lange at 31C3. The talk was recorded. The slides and code-snippets used can be found here (note, there is a broken video link on this page, but the above link works). Finally, Chloe who gave the lectures on elliptic curve crypto last year published lecture notes which you can find here and here. The lecture notes contain for example a full proof that Edwards curves form a group with the addition we defined.
Pictures of blackboards are here.

Here is a last exercise sheet. This sheet will not be graded anymore and is just for you to practice.

Old exams

Old exams by Tanja:

Henk van Tilborg has agreed that I put up his old exams for you to practice: