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 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 en factorization algorithms
• Code-based Cryptography

• Linear codes
• Some constructions (Hamming codes, Reed-Muller codes)
• Cyclic codes
• BCH codes

Announcements

To prepare for the exam:

• go through your 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.

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 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.

Class notes

06 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 on some interactive Caesar cipher challenges visit http://www.mysterytwisterc3.org/ and select MysteryTwister I from the taks bar. There are also lots of other nice challenges which even come with a hall of fame (but are less interactive).
Here are the slides in pdf for the perfect code system. The homework is to figure out how and why this worked and to break the system.

08 Sep 2011
Discussion of why the perfect-code system works and how to break it. This system was propsed as an educational tool by Fellows and Koblitz. Attention, this was never proposed for cryptography but only as a teaching tool.
You can read more about it and a few other systems in their Cryptologia article.
Quick revamp of algebra: groups, order, cyclic groups. Diffie-Hellman key exchange in general cyclic group.
We took pictures of all black boards before erasing them. They are here.

13 Sep 2011
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. Lagrange theorem. Extended Euclidean Algorithm.
We took pictures of all black boards before erasing them. They are here.
If you're not familiar with the extended Euclidean algorithms and efficient ways to compute it, now is a good moment to start training!

15 Sep 2011
Rings, polynomials, matrices, groups tables for Z/nZ, multiplicative group modulo n, Euler phi-function, RSA.
Pictures are here.

Homework (no lessons next week):
1. Show that ((Z/nZ)^×,*) is a group.
2. Compute the phi function for n=37800 by hand/pocket calculator and for n=1939201349958859167498240 with some computer algebra system.
3. Prove that m=m' in the RSA example.
4. Read Section 9.1 of Henk van Tilborg's book to understand RSA for encryption and signatures. Compute an example with primes larger than 1000 using mathematica or your favorite computer algebra system. The textbook uses the powermod function, this uses the 2^k-ary method for k=2; try to use bigger numbers and me mod n to see why this is necessary.
Check yourself by solving exercise 5 of an old exam using only a pocket clculator.
Note: this is not how RSA is used in practice, check out Optimal asymmetric encryption padding and the papers linked from there for proper ways of using it.

27 Sep 2011
RSA cryptosystem, 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 in combination with schoolbook version, therefore use RSA-OAEP. Sometimes the homomorphic property is wanted: RSA gives encryption of products of messages, Paillier gives addition.
Pictures are here.
Homework:

1. Use the extended Euclidean algorithm to compute the gcd of f(x)=x⁵ + 3x³ + x² + 2x + 1 and g(x)=x⁴ - 5x³ - 5x² - 5x - 6 in Q[x].
2. Find a solution of the following system of congruences:
   x≡ 1 mod 2, x≡ 4 mod 5, x≡ 3 mod 9.
   
   
3. Does the following system have solutions? If so, modulo which number are they unique? x≡ 3 mod 4, x≡ 6 mod 12.
4. Does the following system have solutions? If so, modulo which number are they unique? x≡ 4 mod 9, x≡ 10 mod 12.

29 Sep 2011
Solutions to homework; zero divisors, fields, finite fields, subfields, extension fields, characteristic.
Pictures are here.

04 Oct 2011
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. Pictures are here.
Homework: Assume that F₈ exists. Write group tables for addition and multiplication - if possible.

06 Oct 2011
Long example to construct F₈. Can construct field by using basis 1,a,a²,a³, ..., a^n-1. Need to represent aⁿ in the basis and then everything else follows. This construction fails if the resulting polynomial is reducible (zero divisors); it works if it is irreducible (can use XGCD to compute inverses). Note: in general irreducible is a weaker condition than prime.
Here is the proof that 2 is irreducible in Z[√-5]: If 2=(a+b√-5)*(c+d√-5) then 2=ac-5bd+(ad+bc)√-5 which implies that ad+bc=0. Then also (a-b√-5)*(c-d√-5)=ac-5bd+(ad+bc)√-5=ac-5bd=2 and we get 4=(a+b√-5)*(c+d√-5)*(a-b√-5)*(c-d√-5)= (a²+5b²)*(c²+5d²). Because squares are positive this means that 4=(ac)², (bd)²=0 and together with ad+bc=0 we get a=± 2, c=±1, b=0,d=0 (up to swapping of a and c).
Pictures are here.

11 Oct 2011
Recap on finite fields; irreducible polynomials, irreducibility depends on field, irreducible polynomial over F_p of degree n splits completely over F_pⁿ, construction of F_pⁿ using an irreducible polynomial of degree n over F_p; number of irreducible polynomials of degree n over F_p. Pictures are here.
Homework:

• Compute the product of all irreducible polynomials of degree 4 over F₂.
• How many irreducible polynomials of degree 6 exist over F₅?

13 Oct 2011
Existence of finite fields; conjugate elements; norm, trace, and their properties; Frobenius automorphism; Rabin irreducibility test.
If you're looking for more details on finite fields, check out the chapter linked above.
Pictures are here.
Homework (due October 27)

• Let α in F_qⁿ and c F_q. Show that Tr(α)=Tr(α_q) and Tr(c)=nc.
• Prove the following statement:
  Let n be prime. An irreducible binomial xⁿ-a of degree n over F_q exists if and only if n divides (q-1).

18 Oct 2011
Lecture given by Henk van Tilborg.
Block ciphers

• Introduction
• Cipher block chaining (also MAC)
• Cipher feedback
• An identity verification protocol
• AES

• Simple substitution (weaknesses, method of a probable word)
• Vigenere (and Kasiski's method)

18 Oct 2011
Lecture given by Benne de Weger.
Design and analysis of hash functions. Benne was so nice to provide his presentation as pdf file. It can be found here.

27 Oct 2011
ElGamal encryption, ElGamal signatures, pitfalls in using nonces, important properties of hash functions used in signatures, breaking DLP by breaking it in subgroups; this attack is known as the Pohlig-Hellman attack.
Check out exercises 8.1, 8.2, 8.3 on p.145 of Henk van Tilborg's script. Exercise 8.3 uses the same idea we used to compute DLPs mdoulo 37 by working modulo 2,3,4, and 9.
The pictures are here.

15 Nov 2011
Attacks on the discrete logarithm problem: Pohlig-Hellman, BSGS, Pollard rho, parallel Pollard rho, and index calculus attacks. Please read section 8.3 in Henk van Tilborg's book and test your understanding solving Problem 8.8. The slides I used for Pollard rho are available here
For keysize recommendations see http://www.keylength.com/.
Pictures are here.

17 Nov 2011
Lecture given by Henk van Tilborg.
Henk covered chapters 1 and part of 2 of his book on coding theory; the last thing he covered was the Sphere packing bound.

22 Nov 2011
Codes, alphabets, distance, rate, bounds: Sphere packing bound, singleton bound, GV bound; perfect codes. Linear codes over finite fields: weight, bounds, minimum distance = lowest weight of non-zero codeword.
The pictures are here.

24 Nov 2011
Generator matrix, parity check matrix, syndrome decoding, weight enumerator polynomial; several examples. The pictures are here.

29 Nov 2011
Lecture given by Ruud Pellikaan.
Here is what Ruud wrote to me afterwards:
I have treated the following subjects:

• the definition of the weight enumerator again, also in its homogenous form.
• example of the zero code and its dual
• example of the all one repetition code and its dual in the binary case
• statement of the MacWilliams identity and showed that the examples satisfy it
• characters on a finite abelian group, e.g. and its properties
• example of characters on F_p and F_q
• shown that Trace is a non-trivial F_p linear map, giving rise to a non-principal character on F_q
• the Hadamard transform \hat(F) of a map f from F_q^n to a complex vector space V
• property of the Hadamard transform: \sum _{c in C}\hat(f(c)) = |C| \sum_{v in C^\perp } f(v)
• applied this to the map f(v)=X^{n-wt(v)}Y^{wt(v)} to get a proof of the MacWilliams identity. So I treated the proof via the Hadamard transform, that is in greater generality than what is happening in Henk's book.

01 Dec 2011
Lecture given by Relinde Jurrius.
Here is what Relinde wrote to me afterwards:

• Re-stated the definition of weight enumerator and MacWilliams relations.
• Weight enumerator of repetition code
• Weight enumerator of dual of repetition code: I first showed them how to set up a recurrence relation to determine it directly, and after that used the MacWilliams relation.
• For q=2, showed this indeed gives the binary even weight code.
• Skipped the estimation of the probability of decoding error using the weight enumerator.
• Introduction to the Hamming code: projective codes.
• Relation between dependencies in columns of the parity check matrix and the minimum distance (exercise 2.5.9).
• Definition of the Hamming codes, and the two examples from the book. Some words on equivalent codes (permute columns or multiply them by a nonzero constant).
• Showed the Hamming codes are perfect.
• Decoding the Hamming codes using syndrome decoding.
• Didn't mention the direct calculation of the weight enumerator.
• Definition Simplex code.
• Weight enumerator of simplex code and therefor weight enumerator of the Hamming codes.

06 Dec 2011
Construction of codes from given codes: extension, puncturing, shortening, residual code, Griesmer boung, (u,u+v), concatenation. Reed-Muller codes: definition.
The pictures are here.

08 Dec 2011
Reed-Muller codes: definition, details, examples, properties. Homework is to read the remainder of the chapter on RM codes. Code-based cryptography: the McEliece cryptosystem.
The pictures are here.

13 Dec 2011
Lecture given by Michael Naehrig.
Key size recommendations for 128-bit security level; Circle/clock group, circle over F_7, clock group is just arithmetic in F_p^2; Edwards curve, group law; if d is not a square, formulas are complete (with proof); some efficiency discussion, special doubling formulas; projective formulas to delay divisions. The pictures are here.

15 Dec 2011
Lecture given by Benne de Weger.
Classical Weierstrass equations, discriminant, addition law (geometric & formulas), projective coordinates, Montgomery curve, map from Edwards to Weierstass, including the statement (no proof) that this map preserves the addition law / group structure (a lot of literature seems to forget mentioning this essential fact), statement of ECDLP,how to do crypto on these curves.
Benne didn't take pictures, so I post my notes here which I think he used for preparation. ECC-notes.

20 Dec 2011
Most general Weierstrass curves, addition formulas, Hasse's theorem, some curves with easy point counting (some supersingular curves and some Koblitz curves; make sure not to use supersingular curves when you only need a DLP.
The pictures are here.

22 Dec 2011
Factoring: Dixon's method (random squares), quadratic sieve, Pollard's rho method for factoring, Pollard's (p-1) method, elliptic curve method of factorization. The pictures are here.

10 Jan 2012
Lecture given by Ruud Pellikaan.
Here is what Ruud wrote to me afterwards (with some changes in notation):
Topics treated:

• Definition of a cyclic code
• A code is cyclic if and only if the cyclic shift of the rows of a generator matrix of the code are code words
• The dual of a cyclic code is cyclic
• A clear distinction is made between capital X and polynomials c(X) in F_q[X] and small x (coset of X) and the elements c(x) in the factorring F_q[X]/(X^n-1)F_q[X]
• F_q-linear isomorphism between F_q^n and F_q[X]/(X^n-1)F_q[X]
• (linear) cyclic codes in F_q^n correspond one-to one with ideals in F_q[X]/(X^n-1)F_q[X]
• Division with rest in F_q[X]
• F_q[X] is an Euclidean domain, and therefore a PID (principal ideal domain)
• F_q[X]/(X^n-1)F_q[X] is a PID and for every ideal I there is a unique monic polynomial g(X) of minimal degree such that g(x) generates I
• The generator polynomial of a cyclic code, it divides X^n-1
• Examples of two [7,4,3] binary Hamming codes, one that is cyclic and the other that is not
• The description of the generator matrix of a cyclic code by the coefficients of the generator polynomial and its cyclic shifts
• Reversion of a code the (monic) reciprocal of a polynomial
• The parity check polynomial h(X) of a cyclic code
• The generator polynomial of the dual of a cyclic code C is the monic reciprocal of the parity check polynomial of C
• g(X)=1+X+X^3 and h(X) = 1+X+X^2+X^4 for the cyclic [7,4,3] binary Hamming code
• If gcd(n,q)=1, then there is an element in an extension of F_q that has order n
• The zeros of a cyclic code

12 Jan 2012
Lecture given by Relinde Jurrius.
Here is what Relinde covered:

• Recalled the definitions of cyclic codes, in particular zeros of cyclic codes, example 4.1.5.
• Skipped the first part of 4.2 on BCH codes, with the decoding algorithm. (So there was no decoding at all.)
• Definition of BCH codes (4.2.4)
• BCH bound (4.2.5) and the proof as is in the book.
• Examples 4.2.6 and 4.2.7. As hints for more practice with BCH codes, I mentioned exercises 4.7.3, 4.7.4, 4.7.5 and 4.7.10.
• Definition Reed Solomon code (4.2.8) and proof that they are MDS (4.2.9).
• Wrote down theorem 4.4.1 on the alternative definition of a BCH code, no proof because there was no time left.
• Mentioned something about generalizations to Goppa codes.

Old exams