Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room HG 9.92
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

• To prepare for the exam:
  • go through your homeworks and class notes;
  • know your tools: you will likely need to compute modular inverses or so, so practice doing the extended Euclidean algorithm; for small fields get used to inverting 'by hand'; another important tool is the Chinese Remainder Theorem.
  • get used to your pocket calculator.
  • do some old exams for practice without a computer, those from last year match what we did this year.
  You should be able to do all exercises in the practice exam from last year; the real exams contain one exercise (the last one) which goes beyond what we did in class.
• All lectures take place Fridays 10:45 - 12:30. 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).
• Change of room
  In the first quarter (09-09-2011 till 21-10-2011) the lectures take place in Paviljoen U46; in the second quarter (18-11-2011 till 23-12-2011 and on 13-01-2012) the lectures take place in matrix 1.46.
• Make sure to register with TU/e, otherwise you will not be able to register for the exam.
  There will be one exam on January 27 and one on April 13.

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

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.
Sebastiaan de Hoogh will take care of correcting the first rounds of homework. Starting October also Ruben Niederhagen is in charge of this class; in December Sebastiaan takes over again. Do not send me your homework but contact the correcting student. At the moment this is Sebastiaan S.J.A.d.Hoogh@tue.nl.

The first exam took place January 27, 2012, 14:00 - 17:00.
Exercise sheet from the first exam.

The second exam will take place April 13, 2012, 14:00 - 17:00, Auditorium 12.
Please make sure to register on time!

Class notes

09 Sep 2011
General introduction to cryptography; concepts public key and symmetric key cryptography. We took pictures of all black boards before erasing them. They 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.
No homework for this week.

16 Sep 2011
Summary of background material on groups, cyclic groups, lots of examples, Diffie-Hellman (DH) key exchange. We took pictures of all black boards before erasing them. They are here.
Homework is due next Friday 10:45. The exercise sheet is here.

23 Sep 2011
Lecture given by Michael Naehrig.
Lots of examples of easily breakable Diffie-Hellman (DH) key exchange, modular reduction, one more secure group, discrete logarithm problem, and Diffie-Hellman problem, m-RSA. We took pictures of all black boards before erasing them. They are here.
Homework is due next Friday 10:45. The exercise sheet is here.

30 Sep 2011
Extended Euclidean algorithm, computation of modular inverses, gcd(a,b) divides any linear combination of a and b; order of an element divides group order, integers mod n form a group with respect to addition for any n; multiplication tables modulo 5 and modulo 6, multiplicative group modulo n
Pictures are here.
Homework is due next Friday (07 Oct) 10:45. The exercise sheet is here. At the moment Ruben corrects the homeworks.

07 Oct 2011
Lecture given by Michael Naehrig.
Rings, examples of rings, Z/nZ, Euler phi-function and computation, Fermat's little theorem, Euler's theorem, RSA cryptosystem (schoolbook version), square-&-multiply, example and analysis of costs.
Pictures are here.
Homework is due next Friday (14 Oct) 10:45. The exercise sheet is here.

14 Oct 2011
RSA: homomorphic property, small public keys for efficient encryption,problems with small public exponents if the same message is sent to multiple users or if there is a linear (or more general) dependence between messages, CRT-RSA for efficient decryption, attacks using homomorphic properties of RSA, RSA-OAEP to avoid these problems and others.
Pictures are here.
Attention, there was a typo in the definition of vectorspace; this has been fixed in the linked pdf file. Homework is due next Friday (21 Oct) 10:45. The exercise sheet is here. At the moment Ruben corrects the homeworks.

21 Oct 2011
Lecture given by Michael Naehrig.
Zero-divisors in rings; domains; fields; subfield as a vector space, with extension degree = dimension; characteristic of a field, it is 0 or prime; finite fields; characteristic of finite field is prime p; definition of prime field; finite field has pⁿ elements: addition and multiplication; a^(pn-1) = 1 for all a in K^*.
Pictures are here.
Homework is due in 4 weeks on Friday, November 18 at 10:45. The exercise sheet is here. Note that F_p^* denotes the multiplicative group of F_p, so the operation used in exercise 2 is multiplication.
At the moment Ruben corrects the homeworks.

18 Nov 2011
Lecture given by Michael Naehrig.
Recap on finite field: characteristic, prime field, order; K^* is cyclic; primitive element; examples: fields with 4 and 8 elements; polynomial ring over a field, irreducible polynomial, examples; polynomial ring over finite field modulo monic irreducible polynomial.
Pictures are here.
Homework is due Friday, November 25 at 10:45. The exercise sheet is here. At the moment Ruben corrects the homeworks.

25 Nov 2011
Construction of F_pⁿ using an irreducible polynomial of degree n over F_p; 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.
Pictures are here.
Homework is due Friday, December 02 at 10:45. The exercise sheet is here. At the moment Sebastiaan corrects the homeworks.

02 Dec 2011
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 Friday, December 09 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
• http://www-math.uni-paderborn.de/~aggathen/rijndael/2001/flussvisualisierung/

09 Dec 2011
ElGamal encryption, embedding of messages into finite fields, ElGamal signatures, important properties of hash functions used in signatures, pitfalls in using nonces, breaking DLP by breaking it in subgroups (Pohlig-Hellman attack).
Pictures are here.
Homework is due Friday, December 16 at 10:45. The exercise sheet is here. At the moment Sebastiaan corrects the homeworks.

16 Dec 2011
DSA signatures, Pollard's rho method (incl. parallel version), distinguished points. The slides I used for Pollard rho are available here. L to express complexities between exponential and polynomial; index calculus attacks on finite fields.
The page with keysize recommendations is http://www.keylength.com/.
Pictures are here.
Homework is due Friday, December 23 at 10:45. The exercise sheet is here. At the moment Sebastiaan corrects the homeworks.
If you run into problems inverting modulo the group order, find the result modulo 253 first and then find the result. Make sure to verify your result. Why does this work?

23 Dec 2011
The clock group, Edwards curves and twisted Edwards curves, arithmetic, projective coordinates, explicit formulas for doubling, Weierstrass curves, addition law, exceptional cases.
Blackboard pictures are posted here.
Many more (computer verified) formulas are available at the Explicit Formulas Database.
For more material on elliptic curves check out the tutorial at Indocrypt 2011 that I just gave.
Homework is due Friday, January 13 at 10:45. The exercise sheet is here.
Attention, a 2 was missing in the formula for A, that's fixed now on the current version of the exercise sheet.
At the moment Sebastiaan corrects the homeworks.

13 Jan 2012
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 was so friendly to make his notes available

• p1
• p2
• p3
• powerpoint slides for the X 509 collision.

Old exams

Old exams by me:

• Exam from Apr 28 2011, here.
  Exam from Jan 28 2011, here.
  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