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

Exam from Jan 28 posted: here.

Exam from Jan 21 posted: here.

Practice exam posted: here.
Changed exercise 3.d) to define d_p and d_q correctly.
To prepare for the exam:

• go through your homeworks and class notes
• do some old exams for practice without a computer
• 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.

• September 10, 17: potentiaal 2.19
• September 24: Matrix 1.43
• October 1: LaPlace -1.19
• October 8: Matrix 1.43
• October 15: LaPlace -1.19
• November 12: auditorium 11
• November 19: auditorium 1
• November 26: auditorium 7
• December 3: auditorium 1
• December 17: auditorium 1
• January 7: auditorium 7
• January 14: auditorium 1

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. This book is available as reprint with Anita Klooster, HG 9.93. You can also 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.
• 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 takes place Friday January 21, 2011, 14:00- 17:00. Please register by January 9, 2011. The resit exam takes place April 11, 2011; registration is open till March 27, 2011.

Class notes

03 Sep 2010
General introduction to cryptography; concepts public key and symmetric key cryptography. We took pictures of all black boards before erasing them. They are here.
I mentioned http://www.mystery-twister.com/ and http://www.mysterytwisterc3.org/ for some fun pages to train one's cryptanalysis skills. Note that the second site is not advertised, yet. Comments are welcome.
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.

10 Sep 2010
Summary of background material on groups. 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. I changed the second exercise to state that you do not need to prove associativity.

17 Sep 2010
Cyclic groups, lots of examples, Diffie-Hellman (DH) key exchange, discrete logarithm problem, several examples of totally insecure groups for DH, one more secure group; m-RSA. Note: the extended Euclidean algorithm is important!
Pictures are here.
Homework is due next Friday 10:45. The exercise sheet is here. To repeat, do not send your homework to me!

24 Sep 2010
Lagrange's theorem, multiplicative group modulo n, Euler phi-function and computation, Fermat's little theorem, Euler's theorem, RSA cryptosystem (schoolbook version).
I mentioned a script by me. It can be downloaded here.
Pictures are here.
Homework is due next Friday (01 Oct) 10:45. The exercise sheet is here.

01 Oct 2010
RSA as signature scheme, homomorphic property, small public keys for efficient encryption/signature verification, CRT-RSA for efficient decryption/signature generation, 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.
Pictures are here.
Homework is due next Friday (08 Oct) 10:45. The exercise sheet is here.

08 Oct 2010
Atacks using homomorphic properties of RSA, RSA-OAEP to avoid these problems and others; zero-divisors in rings; domains; fields; finite fields; characteristic. Vector spaces and polynomials will be handled as part of the homework.
Pictures are here.
Homework is due next Friday (15 Oct) 10:45. The exercise sheet is here. At the moment Ruben corrects the homeworks.

15 Oct 2010
An excursion into finite fields with explorations of the additive and multiplicative structure. The characteristic of a finite field is prime. By considering the field as a vectorspace over F_p one sees that a finite field has pⁿ elements for some prime n and positive integer n. The multiplicative group is cyclic. Each of these representations facilitates one of the field operations but not both. One needs to store tables of α_i*α_j for 0<=i,j < n or (gⁱ+1) for 0<i< pⁿ-1. A way out is to use a polynomial basis: start with 1 and η use η², η³, ..., η^n-1 as further basis elements: need to know how to represent ηⁿ in the basis but then everything else follows.
Pictures are here.
Homework is due in 4 weeks on Friday, November 12 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. For this round he prefers submissions by email.

12 Nov 2010
Recap on finite fields; 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. Pictures are here.
Homework is due Friday, November 19 at 10:45. The exercise sheet is here. Note that the last 2 exercises are about polynomials over F₂ (stated now on the sheet).
At the moment Ruben corrects the homeworks.

19 Nov 2010
Lecture given by Peter Schwabe.
Background on block ciphers and modes of operaton; details of the Advanced Encryption Standard (AES).
Scans of the lecture notes and some blackboard pictures are posted here.
Homework is due Friday, November 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
• http://www-math.uni-paderborn.de/~aggathen/rijndael/2001/flussvisualisierung/

26 Nov 2010
Little bits on AES keyscheduling; good software is provided on Peter's page, including a bitsliced version which avoids cache timing attacks. In library form it is provided as part of NaCl.
Attacks on the discrete logarithm problem: BSGS and Pollard rho. The page with keysize recommendations is http://www.keylength.com/. Pictures are here.
Homework is due Friday, December 03 at 10:45. The exercise sheet is here.
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?

03 Dec 2010
You can still submit homework 9 till midnight on December 3, 2010. The new exercise sheet will apear only after that. Parallel Pollard rho, distinguished points, pictures; L to express complexities between exponential and polynomial; index calculus attacks on finite fields. Pictures are here.
No lectures on December 10. Homework is due Friday, December 17 at 10:45. At the moment Sebastiaan corrects the homeworks. The exercise sheet is here.
Sorry if you're receiving very short messages from me right now; I'm travelling and do not have good internet connections.

13 Dec 2010
Lecture given by Sebastiaan de Hoogh.
Hash functions are used 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.

07 Jan 2011
Lecture given by Peter Schwabe.
The clock group, Edwards curves and twisted Edwards curves, arithmetic, completeness of the group law, Montgomery curves, birational maps; statements on bit sizes for security.
Scans of the lecture notes and some blackboard pictures are posted here.
Homework is due Friday, January 14 at 10:45. The exercise sheet is here.
In the section on groups we defined [n]P to mean the n-fold of P; here P is a point on an Edwards curve and so the group operation is point addition. [2]P means P+P. Peter showed that for some curve parameters one does not need to worry about vanishing denominators. If these conditions do not hold then one needs to be alert and watch out for vanishing denominators - but for most input pairs things are fine.
Note that the transformation from twisted Edwards curves to Montgomery curves maps (x,y) to (u,v)=( (1+y)/(1-y), (1+y)/(x*(1-y))). There was also a 'typo' in the doubling formulas on p.4; these have been fixed now. Many more (computer verified) formulas are available at the Explicit Formulas Database.
At the moment Sebastiaan corrects the homeworks.

14 Jan 2011
Twisted Edwards curves, projective coordinates, Montgomery's trick, explicit formulas for addition and doubling, points at infinity. Factorization: p-1 method, elliptic-curve method.
Blackboard pictures are posted here.

Old exams

Exams from 2009 can be found on the 2WC12 page from 2009.
Henk van Tilborg has agreed that I put up his old exams for you to practice:

• 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