2MMC10 Cryptology - Fall 2017

Contents Announcements Exams Literature Pictures, videos, 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

Some of the lectures will be given by Chloe Martindale.

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 a laptop 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 31, 2017, 13:30 - 16:30. The retake exam will take place January 23, 2018, 18:00 - 21:00. Rooms will be announced. For Mastermath the exam will take place on January 8, 2018, 14:00 - 17:00. We plan to merge the retake with the 2MMC10 retake, this means that you need to come to TU/e on Jan 23.

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: Gustavo Banegas and Manos Doulgerakis 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.

05 Sep 2017
General introduction to cryptography; concepts public key, symmetric key cryptography, and hash functions. Pictures of blackboards are here.
Videos will come as soon as I have better internet.
If you want to try your skills at some cryptosystems visit http://www.mysterytwisterc3.org/.
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.

07 Sep 2017
Recap on Fermat's little theorem, Euler phi function and its computation, Lagrange's theorem, Chinese Remainder Theorem (CRT).
RSA encryption (KeyGen, Encrypt, Decrypt), exponentiation via square and multiply, use of RSA in hybrid encryption (use RSA to encrypt a key for symmetric crypto, use the latter to encrypt the message. choolbook RSA is homomorphic, avoid this structure by using a padding scheme; we covered RSA OAEP.
RSA signatures (KeyGen, Sign, Verify). Note that RSA is exceptional in that signing and encrypting are so closely related.
Faster decryption/signing via CRT-RSA incl. estimates on improvement (look up Karatsuba multiplication).
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 14 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, 28 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.

12 Sep 2017
Factorization techniques for integers: trial division, Pollard's rho method including explanation why it works when it works and Floyd's cycle-finding algorithm; Pollard's p-1 method including why it works.
Start of explanation of how to factore RSA numbers; e.g. how to factor if p and q ar too close.
Pictures of blackboards and videos are here.

14 Sep 2017
Factorization using Dixon's method/method of random squares. The initial example didn't work as well as I expected and I couldn't connect with my laptop. Thanks for helping out with laptop and typing!
We used the computer algebra system Pari-gp for the examples and I wrote some of the commands on the board (also at the beginning of the second lecture). See the beginning of the second lecture (= 4th picture) for a working example of factoring 323.
Q-sieve, quadratic sieve, some comments about the number-field sieve and running times. You can find examples and code snippets for these methods and those from the previous lecture on http://facthacks.cr.yp.to. The slides I used are here.
Primality testing methods: Fermat test and Carmichael numbers; Miller-Rabin test. These tests 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. Read up on Pocklington's test.
Pictures of blackboards and videos are here.

For 2MMC0, homework is due next Thursday, 21 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, 12 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. Note that you do not need to write anything for exercise 6.

19 Sep 2017 Lecture given by Chloe Martindale.
Finite fields. Recap on basic group theory and building up knowledge about finite fields from axioms.
characteristic, characteristic must be prime; prime field, structure of the additive group is a vector space over the prime field; number of field elements is pn for some prime p and positive integer n. Multiplicative group is cyclic, example of F4, additive structure is vector space.
Chloe was so nice to write up lecture notes for this class.
Pictures of blackboards and videos are here.

21 Sep 2017
Lecture given by Joan Daemen.
One-time pad. Stream ciphers: (DECT, RC4), Block ciphers: security notions, Feistel ciphers, DES, weaknesses of DES. AES/Rijndael: Design principles, S-box, shift rows, mix columns, key schedule. Implementation and security aspects. Block cipher modes.
Joan was so nice to make is slides available. Please read the slides (or literature above) to learn about AES, modes, and padding; that means up to (and including) page 43 of the slides. I will cover MACs later.
Links:

Videos are here.

For 2MMC0, homework is due next Thursday, 28 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, 26 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 3rd exercise sheet is here.

26 Sep 2017
Lecture given by Andreas Hülsing.
Desired properties of hash functions: preimage resistance, 2nd preimage resistance, and collision resistance...; attacks on hash functions: brute force, birthday, Pollard rho; Merkle-Damgaard construction; attacks on MD5 incl hashclash, classification of hash functions (provably secure ones based on public key primitives or block ciphers and dedicated constructions).
Andreas was so nice to make his slides available:
[part1-pdf], [part1-pptx], [part2-pdf], [part2-pptx]

Videos are here.

28 Sep 2017 Lecture given by Chloe Martindale.
More background on finite fields: example of building F8, representation via polynomials, irreducible polynomials irreducible polynomials, Rabin's test for irreducibility.
Crypto protocols relying on hardness of DLP (Diffie-Hellman, ElGamal encryption, ElGamal signatures, DSA), and attacks on DLP (PlayStation3 disaster, Pohlig-Hellman attack, Baby-step giant-step).
Chloe was so nice to write up lecture notes for this class. Note, Section 5, point 4 in the Pohlig-Hellman attack there were some incorrect indices (now fixed).
Pictures of blackboards and videos are here.

For 2MMC0, homework is due next Thursday, 05 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, 09 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 4th exercise sheet is here.
Note that I updated the sheet to fix the statement of Rabin's test. This didn't matter for the exercise. I also updated exercise 2a to change the requirements on h.

03 Oct 2017 Lecture given by Chloe Martindale.
Examples of finite fields, including a field with 32 elemnets. Computational and decisional Diffie-Hellman problem with examples. Example of the Baby-Step Giant-Step algorithm and Pollard's rho method for discrete logs. Start of index calculus attacks for finite fields.

Chloe is totally spoiling you and wrote up lecture notes for this class.

Pictures of blackboards and videos are here.

05 Oct 2017 Lecture given by Chloe Martindale.
The slides for Pollard's rho method are here.
Explanation and example of index calculus attack, factor base, L-notation for complexity of index calculus, 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. Parameters for DSA, see http://www.keylength.org/ for more.
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, finding points on the clock modulo 17.

Chloe is totally spoiling you and wrote up lecture notes for this class.

Pictures of blackboards and videos are here.

For 2MMC0, homework is due next Thursday, 12 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, 23 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. WIth this you might overlook one mathematically interesting attack in logjam: 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.

10 Oct 2017 Lecture given by Chloe Martindale.
Representation of integers modulo p; repetition of addition on circle; 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 the reals and over any finite field; group properties apart from associativity.
Doubling, projective coordinates, explicit formulas for doublings with operation count. For many more (and computer verified!) formulas see the EFD. Chloe keeps on totally spoiling you and wrote up lecture notes for this class.

Pictures of blackboards and videos are here.

12 Oct 2017 Lecture given by Chloe Martindale.
Twisted Edwards curves, 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. Chloe keeps on totally spoiling you and wrote up lecture notes for this class. Note, bottom of p6 there was a sign error (now fixed)

Pictures of blackboards and videos 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.
Last year some people asked after the lecture about secure ways of choosing curves. 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, 19 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, 07 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. 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.

17 Oct 2017 Different curve shapes; 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.

Some details on Curve25519 and the selection criteria for it; number of points on curve plus the number of points on the (quadratic) twist is 2p+2 for a curve over F_p; 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. The Elliptic-Curve Method (ECM) of factorization is a generalization of the p-1 method to using and elliptic curve modulo n to factor n. If you combine ECM with Edwards curves you get EECM

Message Authentication Codes (MACs) ensure authenticity and integrity of the message between communicating parties. Unlike signatures they cannot convince a third party of the authenticity. Warning on length extension attacks for Merkle-Damgaard schemes with dummy MAC H(k||m) (don't ever do that!), and length extension in CBC-MAC. Quick statements of better MACs: HMAC and Poly1305. Note that the addition of AES_k(n) mod 2^128 is an integer addition mod 2^128 and not an XOR (wouldn't make sense mod 2^128). I briefy mentioned the CAESAR competition for authenticated ciphers, those are combining encryption and authentication in one design. An older design is AES-GCM which uses AES in CTR mode to encrypt and polynomial authenticator like in Poly1305.

Pictures of blackboards and videos are here.

19 Oct 2017 Comparison of keylengths. I gave something close to NIST's recommendation, which are easy to remember because they use numbers that are powers of 2, with an occasional 3 in there. Note, these can be off. For an overview of recommended keylengths see https://www.keylength.com/. Of course, just choosing the correct sizes does not make the system secure. I discussed the logjam attack in a bit more detail, including a lesser knownn part that only appears in the paper in which the authors attack DSA implementations that messed up the order of parameters and use q as generator instead of g. In combination with choosing nonces k of restricted size these systems were often solvable by an adaptation of Pohlig-Hellman: compute k modulo small primes dividing the order of q in F_p until the solution is unique within the range of k. Then use that knowing one nonce allows you to recover the long-term signing key.

Things can also go wrong for RSA: in 2012 two teams found that RSA keys on the Internet shared primes, i.e. n1=p*q1 and n2=p*q2, which made them breakable by simply computing gcds. There are too many keys to compute pairwise gcds, so the authors did something smarter (see https://factorable.net/ for more details from one of the teams). Normally this could not happen -- the prime-number theorem says that there are x/log_e(x) primes up to x and randomly chosen primes will not repeat. But, these RSA keys were generated by small linux boxes that did not get enough randomness. The year after we had some fun breaking RSA keys on certified smartcards. We noticed patterns in the repeating keys and used a technique due to Coppersmith to find more factors. I have some slides online about our attack.

Finally I mentioned Post-Quantum Cryptography and that there is a huge need to investigate alternatives to ECC and RSA.

Pictures of blackboards and videos are here.

What's next? Here are a few courses that you might find interesting:

24 Oct 2017 I offered a question and answers session. The TAs were so nice to finish grading the homeworks already. If you didn't get yours, find them or me in the office the next days.
I explained a bit about Edwards curves and did an example of Pohlig-Hellman. Pictures of blackboards and videos are here.
You will notice that the last exercise is going beyond the exact material covered in class, to see whether you understand what you learned (rather than just being able to follow an algorithm).

26 Oct 2017 No class

Old exams

Old exams by me:

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