2WC12 Cryptography I - Fall 2013

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
Fax.: +31 (0)40 243 5810

The easiest ways to reach me wherever I am:
e-mail:tanja@hyperelliptic.org

This page belongs to course 2WC12 - Cryptography I. This course is offered at TU/e and is also part of the Kerckhoff study program. The official page is here.

Contents

Announcements

Note that one of the course requirements is algebra, this year I will not repeat basic background on groups, rings and fields. 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. For the past years this course used Henk van Tilborg, "Fundamentals of Cryptology", Kluwer academic Publishers, Boston, 2000, as basis. You can find the pdf here and the book 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. I will bring some laptops to display pdf files if you send me the files beforehand. We're still figuring out what type of calculators will be allowed. Please contact me if you cannot get one of the more powerful programmable calculators.
You can earn up to 1P for the final mark through the homework. You may hand in your solutions in groups of 2. Please make sure to register for the exam in time. Students from other universities need to have a TU/e student ID in order to register.
Thijs Laarhoven and Jan-Jaap Oosterwijk are the teaching assistants for this course. To submit your homework, email them at crypto13 (at) tue.nl.
Do not send me your homework but contact the TAs.

The first exam will take place January 28, 2014, 14:00 - 17:00.
The second exam will take place April 15, 2014, 14:00 - 17:00.
Please make sure to register on time! Deadlines for registering are January 12, 2014 for the first exam and March 30, 2014 for the second one.

Class notes

05 Sep 2013
General introduction to cryptography; concepts public key and symmetric key cryptography. Pictures of blackboards are here.
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.
Homework is due next Thursday 10:45. The exercise sheet is here.

12 Sep 2013
Lecture given by Sebastiaan de Hoogh.
Hash functions are used in message authentication codes in symmetric-key cryptography and in signatures to map to fixed length and to protect against builing new signatures from a given one. Desired properties of hash functions are preimage resistance, 2nd preimage resistance, and collision resistance. Classification of hash functions (provably secure ones based on public key primitives or block ciphers and dedicated constructions). Merkle-Damgaard construction. MACs and HMACs.
Sebastiaan made his slides available.
Homework is due next Thursday 10:45. The exercise sheet is here.

19 Sep 2013
Lecture given by Ruben Niederhagen.
Background on block ciphers and modes of operaton; details of the Advanced Encryption Standard (AES).
Ruben's slides are here.
Homework is due Thursday, September 26 at 10:45. The exercise sheet is here.
Links:

26 Sep 2013
Background on finite fields: computing modulo n, characteristic, must be prime; structure of the additive group is a vector space; number of field elements is pn for some prime p and positive integer n. Multiplicative group is cyclic, generator is called primitive element. Poly1305-AES as an example of a Wegman-Carter-based MAC (using reduction mod 2130-5 and AES in its construction). Any two messages have negligible chance of producing any particular difference in Poly1305 outputs; chance measured over random choices of key We took pictures of all black boards before erasing them. They are here.
Homework is due next Thursday 10:45. The exercise sheet is here.

03 Oct 2013
Diffie-Hellman (DH) key exchange, discrete logarithm problem, and Diffie-Hellman problems (computational, decisional). Lots of examples of easily breakable Diffie-Hellman (DH) key exchange, one more secure group. How to find a generator of the full group and of subgroups. We took pictures of all black boards before erasing them. They are here.
Homework is due next Thursday 10:45. The exercise sheet is here. Note, exercise 2 got updated to include the field representation. Please use x4+x+1 as the irreducible polynomial. If you used x4+x3+1 it's also OK. Also the decryption in exercise 3 uses c, not m.

10 Oct 2013
Finite fields; example of F22, and of F24; a(pn-1) = 1 for all a in K*. Construction of Fpn using an irreducible polynomial of degree n over Fp; examples of F22, and of F24; number of irreducible polynomials of degree n over Fp; Rabin irreduciblity test; irreducible binomials of degreee n over Fq exist if and only if n divides q-1. We took pictures of all black boards before erasing them. They are here.
Homework is due next Thursday 10:45. The exercise sheet is here. Note that the description has been fixed to match the numbers, N3(4) should be computed as stated. In exercise 1 consider only n>1.

17 Oct 2013
Full proof of: irreducible binomials of degreee n over Fq exist if and only if n divides q-1; example construction of finite fields; ElGamal; homomorphic encryption and pitfalls if unintended; Baby-Step Giant-Step algorithm and runtime analysis. We took pictures of all black boards before erasing them. They are here.
More pictures by others: http://ubuntuone.com/5O4wE9nbTUX6FmmpDgN4Yz and http://ubuntuone.com/4uLS29nHYVxO74TCo4Jqak. Homework is due Thursday, Nov 14 10:45. The exercise sheet is here.

14 Nov 2013
Pollard's rho method (incl. parallel version), distinguished points. The slides I used for Pollard rho are available here. Index calculus attacks on finite fields with example p=107.
We (a student with a nice camera and I) took pictures of all black boards before erasing them. They are here.
Homework is due Thursday, Nov 21 10:45. The exercise sheet is here.

21 Nov 2013
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.
Relative security of DLP in group and finite field, see also http://www.keylength.org/.
Clock group and arithmetic. Edwards curves and arithmetic.
On the Edwards curve x^2+y^2=1-30x^2y^2 the points with x=y have x=±((-1+sqrt(31))/30)^1/2, about 4.5677643.
Eran Lambooij took pictures of all black boards before I erased them. They are here.
Homework is due Thursday, Nov 28 10:45. The exercise sheet is here.

28 Nov 2013
Operation count for addition on Edwards curves, Montgomery's trick, Projective coordinates, faster doubling, NAF has weight 1/3, Weierstrass curves, Montgomery curves, map bewteen Edwards and Montgomery.
Note that the formula for doubling on Montgomery curves has lambda=(3xP^2+2AxP+1)/(2ByP). The picture has been updated.
Eran Lambooij took pictures of all black boards before I erased them. They are here.
Homework is due Thursday, Dec 5 10:45. The exercise sheet is here. The exercise sheet has been updated to state that the map can go to a twisted Edwards curve.

05 Dec 2013 Lecture given by Ruben Niederhagen on multivariate systems in cryptography.
Ruben was so nice to make his slides available, they are here.
Homework is due Thursday, Dec 12 10:45. The exercise sheet is here.

12 Dec 2013 Comments on index calculus (factor base is chosen independently of target h), and exceptional points for maps between Edwards and Montgomery curves.
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.
Z/m, Euler phi-function and computation, Euler's theorem, RSA cryptosystem (schoolbook version), small public keys for efficient encryption, CRT-RSA for efficient decryption, problems with small public exponents if the same message is sent to multiple users, homomorphic property, taking squareroots modulo n is as hard as factoring, attacks using homomorphic properties of RSA, RSA-OAEP to avoid these problems and others.
Eran Lambooij took pictures of all black boards before I erased them. They are here.
Homework is due Thursday, Dec 19 10:45. The exercise sheet is here.

19 Dec 2013 Compositeness tests: Fermat and Miller Rabin. Namedropping of primality tests: Pocklington and ECPP. Factorization methods: trial division, Pollard rho, Pollard p-1, namedropping of p+1 and ECM. With ECM definition of "strong primes" does not make any sense. Dixon's method to generate a and b with a^2 = b^2 mod n. Namedropping of quadratic sieve and number field sieve.
Note that the description of Pollard's rho method was wrong in the gcd step; the picture is updated. You can find examples and code snippets for these methods on http://facthacks.cr.yp.to. We recently broke some smartcards which were not generating their primes in a proper way. For some disasters on RSA see http://smartfacts.cr.yp.to.
Eran Lambooij took pictures of all black boards before I erased them. They are here.
Homework is due Thursday, Jan 9 10:45. The exercise sheet is here. Use the holiday time to take a look at the exams; feel free to email me with questions and what you think might be solutions and ask for corrections.

Old exams

Old exams by me:

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