2WC09 Coding Theory and Cryptology I - Fall 2011

Contents Announcements Exams Literature Pictures and slides

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

Coding theory

Announcements

To prepare for the exam:

The lectures take place Tuesdays 10:45 - 12:30 (matrix 1.41) and Thursdays 08:45 - 10:30 (HG 6.09). There are no lessons on September 20 and 22. 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. Note that there will be classes on October 27 at the regular time and location; there won't be lessons on the 25th.

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

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 2k-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)=x5 + 3x3 + x2 + 2x + 1 and g(x)=x4 - 5x3 - 5x2 - 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 Fp one sees that a finite field has pn 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 αij for 0<=i,j < n or (gi+1) for 0<i< pn-1. Pictures are here.
Homework: Assume that F8 exists. Write group tables for addition and multiplication - if possible.

06 Oct 2011
Long example to construct F8. Can construct field by using basis 1,a,a2,a3, ..., an-1. Need to represent an 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)= (a2+5b2)*(c2+5d2). Because squares are positive this means that 4=(ac)2, (bd)2=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 Fp of degree n splits completely over Fpn, construction of Fpn using an irreducible polynomial of degree n over Fp; number of irreducible polynomials of degree n over Fp. Pictures are here.
Homework:

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)

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

Classical Systems Caesar Henk was so nice to provide two pdf files with his lecture Henk_1.pdf and Henk_2.pdf.

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:

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

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:

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

Old exams

For exams for a similar course targeted at computer scientists see 2WC12.