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

This page belongs to course 2WC09 - Coding Theory and Cryptology I. This course is part of the masters program offered at TU/e. The official page is here.

Contents
Cryptology

• Classical systems
• Symmetric systems
• Stream ciphers
• Block ciphers, in particular AES/Rijndael
• Basic idea of asymmetric cryptography
• Diffie-Hellman, the discrete logarithm problem and attacks on the DLP
• Cryptosystems based on elliptic curves
• RSA with primality tests and factorization algorithms
• Code-based Cryptography

• Linear codes
• Some constructions (Hamming codes, Reed-Muller codes)
• Cyclic codes
• BCH codes
• Goppa codes
• Code-based cryptography

Announcements

The lectures take place Tuesdays 15:45 - 17:30 (Auditorium 16) and Thursdays 10:45 - 12:30 (Auditorium 15 in first quarter and 14 in 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.
There will be no lectures in the weeks Oct 21 - 25 and Jan 13- 17.

Make sure to register for this course; in the new system (OASE) you shouldn't wait till registering for the exam becomes necessary. On the bright side, this makes it possible for me to send email to all of you - that is, to those of you who are registered.
Thijs Laarhoven and Jan-Jaap Oosterwijk are the teaching assistants for the crypto part of your course. To submit your homework, email them at crypto13 (at) tue.nl.
Do not send me your homework but contact the TAs.
Please team up with another student from this course. We do not have the manpower to correct homeworks for all students separately.

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, and Henk van Tilborg, "Coding Theory, a first course", Kluwer academic as basis. You can find the pdfs online Cryptology and Coding Theory. The Cryptology book is also available as a mathematica worksheet here.
Other books you might find useful

• Johannes Buchmann "Introduction to Cryptography", Springer 2004 (2nd edition).
• William Cary Huffman and Vera Pless "Fundamentals of error-correcting codes", Springer.
• Antoine Joux "Algorithmic Cryptanalysis", CRC Press 2009.
• 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.
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

03 Sep 2013
Chapters 1 and part of 2 of Henk van Tilborg, "Coding Theory, a first course", in particular binary symmetric channel, inary symmetric error and erasure channel, Gaussian channel, rate, Shannon's entropy function, channel capacity, Hamming distance, Hamming bound.
Homework (due next Tuesday) is Section 1.4 (Exercises)
Pictures of the blackboards are here.

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. To submit your homework, email it to crypto13 (at) tue.nl.

10 Sep 2013
Class given by Christiane Peters.
Maximum-likelihood decoding, covering radius, perfect codes, Sphere-Packing Bound, Gilbert-Varshamov bound, linear codes, minimum distance of a code, generator matrix. For most of the results repetition codes were used as examples.
Christiane was so nice to make her notes available.
No real home work this time. We'll go through 1.4 at the beginning of lectures on Sep 17. Please also work though the proof of the GV bound again.

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 Friday 10:45. The exercise sheet is here.

17 Sep 2012
Lecture given by Ruud Pellikaan as a last minute replacement because Hertz failed their contract with me and didn't provide me a rental car, even though I waited for 1.5h.

Repetition from last week: linear codes, minimum distance = minimum weight, generator matrix of a linear code. There are many of them for a given code. Linear algebra over a field: Gaussian elimination, elementary row operations, a code has a unique generator matrix in reduced row echelon form, every code has after a permutation of the coordinates a generator matrix of the form G = (I_k |A). New material:

• parity check matrix of a code,
• standard inner product: bilinear, symmetric, but positive definiteness makes no sense in char p, nondegenerate.
• dual code, double dual of code is the code itself, a code can be self dual (in contrast to the reals)
• if G is generator matrix of code, then G is a parity check matrix of the dual code
• If H is a parity check matrix of a code, then the minimal number of dependent columns of C is the minimum distance of C

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

24 Sep 2013
Dual codes (parity check code and repetition code are dual). Syndrome decoding with examples, ways to generate new codes from given ones: extended code, punctured code.
Homework (please be prepared to present this at the beginning of the next lecture): 2.5.5 and 2.5.6.
Richard Both was so nice to take pictures of the blackboard. They are here.

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.

01 Oct 2013
Presentation of homework: 2.5.5 and 2.5.6.
Punctured code, residual code, Griesmer bound, lots of bounds for one example; (u,u+v) construction, concatenated code.
Hamming codes.
In the u+v construction the min distance is equal to min{2d1,d2}, the less-than-or-equal-to symbol is incorrect there.
Homework for next Tuesday: 2.5.8 (first part); 2.5.11 also include Griesmer bound. We took pictures of the blackboard. They are 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.

08 Oct 2013
Presentation of homework: 2.5.8 (part 1) and 2.5.11 (incl. Griesmer bound).
Hamming codes, examples H_r(q) for r=3 and q=2 and q=3; syndrome decoding for Hamming codes; Hamming codes are perfect; weight enumerator; weight enumerator for repetition code and Hamming code (long example); statement of MacWilliams identity and application to repetition code, giving weight enumerator of binary parity check code.
Homework for next Tuesday: 2.5.8 second part. We took pictures of the blackboard. They are here.

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.

15 Oct 2013
Homework was 2.8.5; we did every single step, see the pictures
Weight enumerator, characters in finite fields, trace, simple character sum, proof of MacWilliams identity. Homework: Read and understand Pr_e and the part about Simplex codes and their weight enumerators. We took pictures of the blackboard. They are here.

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.

12 Nov 2013
Weight enumerator and use for estimating probability of correcting to wrong codeword, Simplex code as dual of Hamming code and weight enumerators of both.
Basics of Reed-Muller codes and examples. We took pictures of the blackboard. They are 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.

19 Nov 2013
Details of Reed-Muller codes and examples: dimension, minimum distance, dual of RM(r,m) is RM(m-r-1,m), RM(0,m) is repetition code, RM(m-1,m) is even-weight code. We took pictures of the blackboard. They are 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.

26 Nov 2013
RM(1,m) is extended simplex code, as it's dual RM(m-2,m) is the extended Hamming code. Automorphisms of codes, for RM(r,m) alll invertible affine transformations are included (since f(xA+b) has the same degree as f). Decoding of Reed-Muller codes (it's painful but works).
Cyclic codes: binary Hamming code of length 7 and corresponding simplex code are cyclic; interpretation of code words as polynomials mod xⁿ-1; cyclic codes are ideals in F_q[x]/(xⁿ-1).
Details of Reed-Muller codes and examples: dimension, minimum distance, dual of RM(r,m) is RM(m-r-1,m), RM(0,m) is repetition code, RM(m-1,m) is even-weight code. We took pictures of the blackboard. They are here.
Home work is due Dec 10, please prepare 3.4.4 and 3.4.8.

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.

03 Dec 2013 Lecture given by Boris Skoric on use of coding theory in traitor tracing.
Boris was so nice to make his slides available, they are here.

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.

10 Dec 2013
Cyclic codes are ideals in F_q[x]/(xⁿ-1), generator polynomial, roots of irreducible polynomial are conjugate (over extension field defined by the irreducible polynomial), generator polynomials are factors of (xⁿ-1), this polynomial splits completely over F_q^m, when n divides q^m-1. [7,4,3] Hamming code has m=3, g=x³+x+1, with roots a, a², and a⁴; equivalent code has a³, a⁵, and a⁶, representation by cosets. Equivalence of f divides c and c(a)=0, where is a root of f over F_q[x]/f and f is irreducible over F_q.
We took pictures of the blackboard. They are here.
Home work is due Dec 17, please prepare 4.7.2 and 4.7.8 (without the 'vice versa' in c).

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.

17 Dec 2013
gh=xⁿ-1, g generator polynomial, h parity check polynomial, I defining set, cyclotomic coset, minimal polynomial, examples of I={1} and I={1,3} over F₂, where n=q^m-1, including decoding algorithm; BCH codes (definitions and properties), example of n=15, d=7; Reed-Solomon codes (definition and some properties). We took pictures of the blackboard. They are here.
No homework.

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