Pictures and slides | Announcements | Literature | Course | Exam |

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

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.

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

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

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.

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

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

**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:

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

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

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

2. The point

Attention, this is the correct point!!

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)

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

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.