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

• Classical systems like Caesar and Vigenère, some simple cryptanalysis.
• The general structure of block ciphers, Feistel ciphers like DES, AES, the most suitable modes-of-use, e.g. CBC or OFB.
• Shift register sequences (linear and non-linear), the linear complexity of a periodic sequence, the Berlekamp-Massey algorithm.
• The principle of public key cryptography.
• Basics of finite fields and their arithmetic.
• Diffie-Hellman key exchange, El Gamal, several methods to take discrete logarithms (baby-step giant-step method, the Pohlig-Hellman method, Pollard-rho and the index calculus method).
• Elliptic curve cryptosystems.
• The RSA system for encryption and signing, generating prime numbers by means of probabilistic primality tests, several factorization algorithms (Pollard-(p-1), Pollard-rho, the random square method, the quadratic sieve method), and some insecure modes of RSA.
• Hash functions, Message Authentication Codes

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.

• All lectures take place Thursdays 10:45 - 12:30 in Auditorium 15 in the first quarter and Auditorium 14 in the second quarter. At TU/e the semester is interrupted by an exam break at the end of October; since this course does not have intermediate exams there won't be any program during this time (but some homework to keep you entertained).
  There will be no lectures in the weeks Oct 21 - 25 and Jan 13- 17.
• Make sure to register with TU/e, otherwise you will not be able to register for the exam.
  

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

• Neal Koblitz "A course in Number Theory and Cryptography", Springer, 1994.
• Tanja Lange "Number Theory and Algebra" ( Chapter of draft book "Discrete Mathematics")
• Tanja Lange "Finite Fields" (Chapter of draft book "Discrete Mathematics")
• Christof Paar and Jan Pelzl "Understanding Cryptography", Springer, 2010
• Bruce Schneier "Applied Cryptography", John Wiley & Sons, 1994.
• Doug Stinson "Cryptography: Theory and Practice", CRC Press, 1995

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:

• http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
• http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf

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 pⁿ 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 2¹³⁰-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 x⁴+x+1 as the irreducible polynomial. If you used x⁴+x³+1 it's also OK. Also the decryption in exercise 3 uses c, not m.

10 Oct 2013
Finite fields; example of F_2², and of F_2⁴; a^(pn-1) = 1 for all a in K^*. Construction of F_pⁿ using an irreducible polynomial of degree n over F_p; examples of F_2², and of F_2⁴; number of irreducible polynomials of degree n over F_p; Rabin irreduciblity test; irreducible binomials of degreee n over F_q 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, N₃(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 F_q 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 L_q(1/2,c), with several improvements it's L_q(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.

Old exams

Old exams by me:

• Exam from Jan 28 2014, here.
  
• Exam from Apr 13 2012, here.
  
• Exam from Jan 27 2012, here.
  
• Exam from Apr 28 2011, here.
  
• Exam from Jan 28 2011, here.
  Note that in exercise 5 the definition of P_A should be [a]P.
  
• Exam from Jan 21 2011: here.
  
• Practice exam 2010/2011: here.
  
• Exam from Apr 15 2010, here.
  
• Exam from Jan 29 2010: here.
  
• Practice exam 2009/2010: here.
  

• 2WC00_2003_Nov.pdf
• 2WC00_2004_Jan.pdf
• 2WC00_2004_Nov.pdf
• 2WC00_2005_Jan.pdf
• 2WC00_2005_Nov.pdf
• 2WC00_2006_Febr.pdf
• 2WC00_2007_Maart.pdf