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

Exam from Jan 28 posted: here.

Exam from Jan 21 posted: here.

Practice exam posted: here.

Changed exercise 3.d) to define *d _{p}* and

To prepare for the exam:

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

The first meeting took place September 3, 2010, in potentiaal 13.03 10:45 - 12:30.

The following meetings will take place in a variety of rooms:

- September 10, 17: potentiaal 2.19
- September 24: Matrix 1.43
- October 1: LaPlace -1.19
- October 8: Matrix 1.43
- October 15: LaPlace -1.19
- November 12: auditorium 11
- November 19: auditorium 1
- November 26: auditorium 7
- December 3: auditorium 1
- December 17: auditorium 1
- January 7: auditorium 7
- January 14: auditorium 1

There are no classes on October 22 and on December 10, 2010.

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

Other books you might find useful

- Neal Koblitz "A course in Number Theory and Cryptography", Springer, 1994.
- 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

You can earn up to 1P for the final mark through the homework. You may
hand in your solutions in groups of 2. 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.

Sebastiaan de Hoogh will take care of correcting the first rounds of
homework. Starting October also Ruben Niederhagen is in charge of this class; in December Sebastiaan takes over again.
Do not send me your homework but contact the correcting student. At the moment this is Sebastiaan `S.J.A.d.Hoogh@tue.nl`.

The first exam takes place Friday January 21, 2011, 14:00- 17:00. Please
register by January 9, 2011. The resit exam takes place April 11,
2011; registration is open till March 27, 2011.

**03 Sep 2010**

General introduction to cryptography; concepts public key and
symmetric key cryptography. We took pictures of all black boards
before erasing them. They are here.

I mentioned http://www.mystery-twister.com/
and http://www.mysterytwisterc3.org/
for some fun pages to train one's cryptanalysis skills. Note that the
second site is not advertised, yet. Comments are welcome.

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.

No homework for this week.

**10 Sep 2010**

Summary of background material on groups.
We took pictures of all black boards
before erasing them. They are here.

Homework is due next Friday 10:45. The exercise sheet is here. I changed the
second exercise to state that you do not need to prove associativity.

**17 Sep 2010**

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; m-RSA. Note: the extended Euclidean
algorithm is important!

Pictures are here.

Homework is due next Friday 10:45. The exercise sheet is here. To repeat, do not send
your homework to me!

**24 Sep 2010**

Lagrange's theorem, multiplicative group modulo *n*, Euler
phi-function and computation, Fermat's little theorem, Euler's
theorem, RSA cryptosystem (schoolbook version).

I mentioned a script by me. It can be downloaded here.

Pictures are here.

Homework is due next Friday (01 Oct) 10:45. The exercise sheet is here.

**01 Oct 2010**

RSA as signature scheme, homomorphic property, small public keys for
efficient encryption/signature verification, CRT-RSA for efficient
decryption/signature generation, 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.

Pictures are here.

Homework is due next Friday (08 Oct) 10:45. The exercise sheet is here.

**08 Oct 2010**

Atacks using homomorphic properties of RSA, RSA-OAEP to avoid these
problems and others; zero-divisors in rings; domains; fields; finite
fields; characteristic. Vector spaces and polynomials will be handled
as part of the homework.

Pictures are here.

Homework is due next Friday (15 Oct) 10:45. The exercise sheet is here. At the moment Ruben
corrects the homeworks.

**15 Oct 2010**

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

Pictures are here.

Homework is due in 4 weeks on Friday, November 12 at 10:45. The exercise sheet is here. Note that

At the moment Ruben corrects the homeworks. For this round he prefers submissions by email.

**12 Nov 2010**

Recap on finite fields; construction of
**F*** _{pn}* using an irreducible
polynomial of degree

Homework is due Friday, November 19 at 10:45. The exercise sheet is here. Note that the last 2 exercises are about polynomials over

At the moment Ruben corrects the homeworks.

**19 Nov 2010**

Lecture given by Peter Schwabe.

Background on block ciphers and modes of operaton; details of the
Advanced Encryption Standard (AES).

Scans of the lecture notes and some blackboard pictures are posted
here.

Homework is due Friday, November 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
- http://www-math.uni-paderborn.de/~aggathen/rijndael/2001/flussvisualisierung/

**26 Nov 2010**

Little bits on AES keyscheduling; good software is provided on Peter's page, including a
bitsliced version which avoids cache timing attacks. In library form
it is provided as part of NaCl.

Attacks on the discrete logarithm problem: BSGS and Pollard rho. The
page with keysize recommendations is http://www.keylength.com/.
Pictures are
here.

Homework is due Friday, December 03 at 10:45.
The exercise sheet
is here.

If you run into problems inverting modulo the group order, find the
result modulo 253 first and then find the result. Make sure to
verify your result. Why does this work?

**03 Dec 2010**

You can still submit homework 9 till
midnight on December 3, 2010. The new exercise sheet will apear only
after that.
Parallel Pollard rho, distinguished points,
pictures; L to express complexities between exponential and
polynomial; index calculus attacks on finite fields.
Pictures are
here.

No lectures on December 10.
Homework is due Friday, December 17 at 10:45. At the moment
Sebastiaan corrects the homeworks.
The exercise sheet
is here.

Sorry if you're receiving very short messages from me right now;
I'm travelling and do not have good internet connections.

**13 Dec 2010**

Lecture given by
Sebastiaan de Hoogh.

Hash functions are used 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 was so friendly to make his notes available

- p1
- p2
- p3
- powerpoint slides for the X 509 collision.

Homework is due Friday, January 07 at 10:45. The exercise sheet is here.

At the moment Sebastiaan corrects the homeworks.

**07 Jan 2011**

Lecture given by Peter Schwabe.

The clock group, Edwards curves and twisted Edwards curves,
arithmetic, completeness of the group law, Montgomery curves,
birational maps; statements on bit sizes for security.

Scans of the lecture notes and some blackboard pictures are posted
here.

Homework is due Friday, January 14 at 10:45.
The exercise sheet
is here.

In the section on groups we defined [n]P to mean the n-fold of P;
here P is a point on an Edwards curve and so the group operation is
point addition. [2]P means P+P. Peter showed that for some curve
parameters one does not need to worry about vanishing denominators.
If these conditions do not hold then one needs to be alert and watch
out for vanishing denominators - but for most input pairs things are
fine.

Note that the transformation from twisted Edwards curves to Montgomery
curves maps *(x,y)* to *(u,v)=( (1+y)/(1-y),
(1+y)/(x*(1-y)))*. There was also a 'typo' in the doubling formulas
on p.4; these have been fixed now.
Many more (computer verified) formulas are
available at the Explicit
Formulas Database.

At the moment Sebastiaan corrects the homeworks.

**14 Jan 2011**

Twisted Edwards curves, projective coordinates, Montgomery's trick,
explicit formulas for addition and doubling, points at infinity.
Factorization: p-1 method, elliptic-curve method.

Blackboard pictures are posted
here.

Exams from 2009 can be found on the 2WC12 page from 2009.

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