Cryptography I

2WC12 Cryptography I - Fall 2009

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 where ever 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

The course takes place in the fall term on Fridays 10:45 - 11:30 and 11:45 - 12:30. Please note that I have to leave instantly after the lecture. If you want to meet me for discussions please come BEFORE the lectures.
In the first quarter the lectures took place in paviljoen k10. For the second quarter we are in HG 6.09. Note that several Fridays there are other events at TU/e.
Dates for the lectures: Sep 04, Sep 11, Sep 18, Sep 25, Oct 02, Oct 09, Oct 23, Nov 13, Nov 20, Nov 27, Dec 04, Dec 18, Jan 08, Jan 15.
Homework is due the Friday after it is posed. Homework should reach me in person by the beginning of Friday's session or my mailbox in HG before that. You can also contact Peter Schwabe (the student in charge of corrections) directly.

Literature

Henk van Tilborg, Fundamentals of Cryptology, Kluwer academic Publishers, Boston, 2000.

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.
In case of doubt the numbers for the homework relate to the mathematica version.
Some extra reading on more recent topics (text written by Henk van Tilborg).

Examination

You can earn up to 1P for the final mark through the homework. You may hand in your solutions in groups of 2-3. 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.
The exams take place Jan 29 and Apr 15. The Jan 29 exam takes place 14:00 - 17:00 in HG 10.30 f.

Class notes

04 Sep 2009
General introduction to cryptography; concepts public key and symmetric key cryptography. 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 ps and in pdf for the perfect code system.
No homework for this week.

11 Sep 2008
Summary of background material on groups, rings and fields to refresh it. We took pictures of all black boards before erasing them. They are here.
Homework is to read Sections 3.1, 3.2, 3.3 on linear feedback shift registers and to do excercise 3.1, 3.2 and A3. Homework should reach me in person by the beginning of Friday's session or my mailbox in HG before that.

18 Sep 2009
Summary of LSFRs. Modes of operation for block ciphers, DES, triple DES. Pictures are here; the order does not match the order they were written in.
Homework is to do exercises 3.8 d), 4.1, and 4.2. To do the exercises you need to read the section on cipher feedback mode.
Attention: Some people misunderstood the assignment as mostly reading. 4.1 and 4.2 are the exercises you should do.

25 Sep 2009
Lecture given by Michael Naehrig.
Overview and details of the Advanced Encryption Standard (AES). Pictures of the boards are here.
Homework for this week pdf file.
Links:

02 Oct 2009
Summary of finite fields, Diffie Hellman key exchange, DLP, CDHP, DDHP, ElGamal encryption, Pohlig-Hellman attack. Pictures are here.
Homework is to solve 8.1, 8.2, 8.3.

10 Oct 2008
Baby-step giant step algorithm to solve DLPs, exploration of the parameter space between storage/precomputation and total computation time; Pollard's rho method including parallelized versions. For pictures on how the parallel version looks like see pages 7 and 8 of ePrint 2009/466. Pictures of the blackboards are here.
Homework is to solve 8.6 and 8.7. Please note the remarks on homework submission on imgp1734.jpg. Homework is due at the next lesson, i.e. October 23rd.

23 Oct 2009
Short summary of generic attacks; index calculus attack background; example: index calculus attack in F_p with p=4007. The computer algebra system we used was GP/PARI. The values for g and h were chosen at random by Mod(random(4006)^2,4007). I should have used lift to move things back to the integers.
As preparation for understanding RSA we did Kid-RSA (due to Koblitz and Fellows). The slides for Kid-RSA are here Pictures of all blackboards are here.
Homework is to solve 8.9 and 8.10; these require reading section 8.3.4.

13 Nov 2009
RSA: basic schoolbook version, pitfalls (homomorphic property), problem with small exponents and bulk encryption, RSA OAEP, computing square roots mod n is as hard as factoring.
Pictures of all blackboards are here.
Homework is to solve 9.2 and 9.10.

20 Nov 2009
Lecture given by Christiane Peters.
Clock group; Edwards curves.
Edwards curves, completeness of addition law, explicit projective formulas for addition and doubling.
Pictures of all blackboards are here.
Homework is to solve the following two exercises:
1. Let E_d be an Edwards curve over Q with d \neq 0,1. a) Find a point (x1,y1) of order 2. b) Find points doubling to this point of order 2. c) Sudy points on E_d that double to (1,0) or (-1,0) and give intervals for d for there to exist 0, 4 or 8 such points.
2. The point P=(2,5) is on E₃: x² +y²= 1+3x²y² over F₁₇. Compute [2]P and [3]P.
Attention, this is the correct point!!

27 Nov 2009
Factorization methods: trial division, Pollard's rho method, Dixon's method/random squares, quadratic sieve, Pollard's p-1 method, ECM (elliptic curve method). Hasse-Weil theorem. Primality tests: Fermat.
Pictures of all blackboards are here.
Homework: 9.6, 9.12, 9.13 (the latter require reading the section on Rabin's variant)

04 Dec 2009
Attention: no classes next week, homework is due December 18.
Compositness tests: Fermat, Miller-Rabin; primality tests: Pocklington, ECPP. Elliptic curves in Weierstrass form, short Weierstrass form, birational equivalence to twisted Edwards curves, addition law in short Weierstrass form.
The birational equivalence from the Edwards curve ax²+y²=1+dx²y² to the Weierstrass curve v²=u³+(A/B)u² +(1/B²)u uses A=2(a+d)/(a-d), B=4/(a-d) and u=(1+y)/((1-y)B), v=(1+y)/((1-y)xB) to get from Edwards to Weierstrass and a=(A+2)/B, d=(A-2)/B, x=u/v, y=(Bu-1)/(Bu+1) to get from Weierstrass to Edwards.
Pictures of all blackboards are here.
Homework: Do the Pocklington test to show that 709 is prime. You may assume that 7 is prime. Excercises 10.1 and 10.3.

18 Dec 2009
Lecture given by Henk van Tilborg
Chapter 11: introduction to coding theory, McEliece cryptosystem.
No homework; enjoy the break!

08 Jan 2010
Zero knowledge proofs of knowledge: Fiat-Shamir and Schnorr. Secret sharing schemes: Shamir.
Pictures of all blackboards are here.
Homework: 14.1, 15.1., 15.3

15 Jan 2010
Hash functions and message authentication codes (MACs): properties of hash functions; news; MACs based on keyed hash functions; Poly1305-AES as an example of a Wegman-Carter-based hash function
Pictures of all blackboards are here.
A practice exam pdf file. Note that the real exam will not have a math exercise like exercise 1 but you should know your tools. There will be at least one exercise which requires a bit more thinking/understanding than the ones in the practice exam.
Attention: the Edwards exercise was incorrectly posed and has been chenged in the version that is now online.
Check out the formulas for the transformations on this page; this section has been extended.

Exam

Henk van Tilborg has agreed that I put up his old exams for you to practice:

Here are the exams which were given for this course (posted June 10, 2010).