Cryptology - Fall 2016

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

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 November 01, 2016, 13:30 - 16:30, in rooms PAV SH2 A and B. The retake exam will take place January 24, 2017, 13:30 - 16:30, in room PAV L10.
For Mastermath the exam will take place on December 14, 13:30 - 16:30. We will merge the retake with the 2MMC10 retake, this means that you need to come to TU/e on Jan 24 13:30 - 16:30. The Paviljoen building is some hike accross campus, make sure to budge time for that. You can find a map of campus here; Paviljoen is building 62 in quadrant E2 on that map. .

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. 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 Leon Groot Bruinderink 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

06 Sep 2016
Lecture given by Andreas Hülsing.
General introduction to cryptography; concepts public key and symmetric key cryptography.
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.
Andreas made his slides available:
Slides in pdf format.
If you want to try your skills at some cryptosystems visit
http://www.mysterytwisterc3.org/.

08 Sep 2016
Recap on modular arithmetic, multiplicative group mod n, Euler phi function and its computation, Lagrange's theorem, exponentiation via square and multiply, RSA, efficient decryption via CRT-RSA incl. quick estimates on improvement (look up Karatsuba multiplication).
Pictures of blackboards are here.
For 2MMC0, homework is due next Thursday, 15 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, 22 Sep, at 10:45 by email. Details will follow.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. The exercise sheet is here. I've updated the RSA exercise to state that you can assume a caclulator with very large precision, i.e. you should use the square-and-multiply method.

13 Sep 2016
Background on finite fields: 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, same for F8, representation via polynomials, irreducible polynomial.
We took pictures of all black boards before erasing them. They are here.

15 Sep 2016
More properties of finite fields; irreducible polynomials, fundamental equation of finite fields xpn-x; Frobenius map, conjugate elements, Rabin's test for irreducibility. Diffie-Hellman key exchange.
We took pictures of all black boards before erasing them. They are here.
The cartoon I mentioned is here.
For 2MMC10, homework is due next Thursday 10:45, for mastermath later (if we can correct at all). 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.

20 Sep 2016
Diffie-Hellman key exchange; Decisional DH Problem (DDHP), Computational DH Problem (CDHP). Showing how to solve DDH for an example in F19* by checking for even or odd exponents. In general, we can solve the DDHP if the generator generates all of Fp* by checking whether the parity of ab and c matches; to do that compute the (p-1)/2-th power of the elements. If this is =1 then the element is a square. If at least one of ha and hb is a square then their DH share is also a square, so we can detect radom c if the parity doesn't match. The same works for other divisors of p-1.
Brief mention of hash functions and AES (more next week) to show how DH is usesd in practice. Check your browser to see uses of DHE (ephemeral DH) and maybe DH.
ElGamal encryption, relation of IND-CPA for ElGamal and DDH.
Digital signatures, RSA signatures, ElGamal signatures and pitfalls.
Pictures of blackboards are here.

22 Sep 2016
We turned the distinguishing attack into a discrete logarithm attack by computing a modulo the prime divisors of p-1; in the end we reinvented the Pohlig-Hellman attack which solves the DLP in a big group by solving it in subgroups.
The examples were done using Pari/GP. Under linux it is available as Debian package pari-gp.
Lesson from first part: work in prime-order subgroup. Definition of Discrete Logarithm (DL); DSA uses subgroups for lower bandwidth.
Quick run of Baby-Step Giant-Step algorithm (see homeworks for more) and about random walks using these slides.
Pictures of blackboards are here.
Homework is due next Thursday 10:45 (for 2MMC10) and Oct 20 (for Mastemath). 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: There is a reason that I don't state the generator or Alic'e public key; you're not supposed to compute the DL. ElGamal in the subgroup works the same as described in the lecture; the only difference is that s is computed modulo the order of the subgroup (which is prime here, so that everything is nicely invertible).

27 Sep 2016
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 modes and padding; that means up to (and including) page 43 of the slides. I will cover MACs next week.
Links:

29 Sep 2016
Lecture given by Andreas Hülsing.
Hash function, desired security properties, formal reductions between collision resistance, preimage resistance, and second preimage resistance. Attacks on hash functions using brute force and Pollard rho. Compression functions and length extension modes, Merkle-Damgaard construction, sponges, constructions using permutations. Attacks against deployed hash functions with details on MD5 and the rogue-CA attack.
Andreas made his slides available:

Homework is due next Thursday 10:45 (for 2MMC10) and Nov 03 (for Mastemath). Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons.
The exercise sheet is here.

04 Oct 2016
Message authentication codes: differences between MACs and signatures, security notions, general constructions, HMAC, CBC-MAC, CMAC, Poly1305.
Pollard-rho attack against the DLP. Birthday bound, how to recover DLP from collision, Floyd's cycle finding method. Two ways of getting a random walk -- with very differnt costs. Additive walk requires a few precomputed points but it much cheaper.
Pictures of blackboards are here.

06 Oct 2016
Full step function for Pollard rho attack, parallel version, optimization of steps depending purely on g (reusable) and input points depending on h. You can find the parallel rho picture in higher resolution here.
Generic attacks, random self reducibility of DL
Explanation and examples of index calculus attack, factor base, complexity is exp(c(log q)1/3(log log q)2/3), 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.
Pictures of blackboards are here.
Homework is due next Thursday 10:45 (for 2MMC10) and Nov 17 (for Mastermath). Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons.
The exercise sheet is here. Also, please read the logjam paper for the index calculus attack details; you'll see the part on TLS in Applied Crypto.

11 Oct 2016
Key sizes for DL in finite fields and groups. For more recommendations of key sizes see https://www.keylength.com/.
We didn't cover this in class, but there are some speedups that depend on the prime. Joshua Fried, Pierrick Gaudry, Nadia Heninger, and Emmanuel Thomé just published Cryptanalysis of 1024-bit trapdoored primes, which shows that such weak primes need not be obvious. And cooked up one such prime with 1024 bits and computed DLs for it! That's a lot larger than anything done so far.
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 in finite fields.
Edwards curves, picture for d< 0, special points, addition law; no division by 0 if d is not a square (which matches d< 0 over the reals, pictures for other cases for d.
We took pictures of all black boards before I erased them. They are here.

13 Oct 2016
Twisted Edwards curves, (signed) window method for scalar multiplication; (signed) sliding window method for scalar multiplication, Montgomery's trick for simultaneous inversion, projective coordinates; compute Edwards DBL in 3M+4S+1 mult by a. For many more (and computer verified!) formulas see the EFD.
Weierstrass curves, singularities (cusp, node) and how they are characterized and what they look like over the reals, short Weierstrass form characteristic not equal to 2; point at infinity; lots of cases for addition law; formulas for ADD and DBL.
We took pictures of the board before I erased them. They are here.
Homework is due next Thursday 10:45. The exercise sheet is here.

18 Oct 2016
Chord-and-tangent method of addition on Weierstrass curves. Negation if a1 or a3 is nozero. Montgomery curves and addition on them, can do arithmetic on u-coordinates without ever needing the v coordinate. For adding P2 and P3 one needs to have their u coordinates and the u coordinate of their difference P3-P2; map between twisted Edwards curves and Montgomery curves.
Elliptic curves in the wild, NIST curves, Brainpool curves, Curve25519, Curve448, Curve41417. The recent RFC I mentioned is RFC7748. The signature proposal EdDSA is still in the state of Internet Draft at draft-josefsson-eddsa-ed25519-03.
We 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 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 took pictures of all black boards before I erased them. They are here.

20 Oct 2016
Montgomery ladder and how to avoid implementer mistakes.
Factorization methods: Problems if p and q are too close, Dixon's method to generate a and b with a^2 = b^2 mod n, quadratic sieve. Namedropping of number field sieve. Methods to factor resulting numbers (the right-hand side in the relations): trial division/sieving, Pollard rho. Pollard p-1, namedropping of ECM.
You can find examples and code snippets for these methods on http://facthacks.cr.yp.to. In 2013 we broke some smartcards which were not generating their primes in a proper way. For some disasters on RSA see http://smartfacts.cr.yp.to.
No exercises this week because there is no more lecture to submit them. If you want to practice Edwards and Montgomery curves, take a look at the first exercise of exercise sheet 11 from 2014.
I took pictures of all black boards before I erased them. They are here.

25 and 27 Oct 2015
I will be there, you can ask questions. Use the time to practice on some old exams.
On the 27th I need to leave around 12:00.
Some people asked what an affine point is; that is a point of the form (x,y) as opposed to a projective point (X:Y:Z).

Old exams

Old exams by me:

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