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 MF 6.104B

Technische Universiteit Eindhoven

P.O. Box 513

5600 MB Eindhoven

Netherlands

Phone: +31 (0) 40 247 4764

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

- Linear codes
- Some constructions (Hamming codes, Reed-Muller codes)
- Cyclic codes
- BCH codes
- Goppa codes
- Code-based cryptography

The lectures take place Tuesdays 15:45 - 17:30 (Auditorium 16) and
Thursdays 10:45 - 12:30 (Auditorium 15 in first quarter and 14 in
second quarter). 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.

There will be no lectures in the weeks Oct 21 - 25 and Jan 13- 17.

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.

Thijs Laarhoven and Jan-Jaap Oosterwijk are
the teaching assistants for the crypto part of your course. To submit
your homework, email them at `crypto13 (at) tue.nl`.

Do not send me your homework but contact
the TAs.

Please team up with another student from this course. We do not have the
manpower to correct homeworks for all students separately.

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

The exam will be an open-book exam, meaning that you can use any book
or notes that you have on paper. I will bring some laptops to display
pdf files if you send me the files beforehand. We're still figuring
out what type of calculators will be allowed. Please contact me if you
cannot get one of the more powerful programmable calculators.

The first exam will take place January 28, 2014, 14:00 - 17:00.

The second exam will take place April 15, 2014, 14:00 - 17:00.

Please make sure to register on time! Deadlines for registering are
January 12, 2014 for the first exam and March 30, 2014 for the second one.

**03 Sep 2013**

Chapters 1 and part of 2 of Henk van
Tilborg, "Coding Theory, a first course", in particular binary
symmetric channel, inary symmetric error and erasure channel, Gaussian
channel, rate, Shannon's entropy function, channel capacity, Hamming
distance, Hamming bound.

Homework (due next Tuesday) is Section 1.4 (Exercises)

Pictures of the blackboards are here.

**05 Sep 2013**

General introduction to cryptography; concepts public key and
symmetric key cryptography.
Pictures of blackboards are here.

If you want to try your skills at some cryptosystems visit http://www.mysterytwisterc3.org/.

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.

Homework is due next Thursday 10:45. The exercise sheet is here.
To submit your homework, email it to `crypto13 (at) tue.nl`.

**10 Sep 2013**

Class given by Christiane Peters.

Maximum-likelihood decoding, covering radius, perfect codes,
Sphere-Packing Bound, Gilbert-Varshamov bound, linear codes,
minimum distance of a code, generator matrix. For most of the
results repetition codes were used as examples.

Christiane was so nice to make her notes
available.

No real home work this time. We'll go through 1.4 at the beginning of
lectures on Sep 17. Please also work though the proof of the GV bound
again.

**12 Sep 2013**

Lecture given by
Sebastiaan de Hoogh.

Hash functions are used in message
authentication codes in symmetric-key cryptography and 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 made his slides
available.

Homework is due next Friday 10:45. The exercise sheet is here.

**17 Sep 2012**

Lecture given by Ruud Pellikaan as a last
minute replacement because Hertz failed their contract with me and
didn't provide me a rental car, even though I waited for 1.5h.

Repetition from last week: linear codes, minimum distance = minimum
weight, generator matrix of a linear code. There are many of them for
a given code.
Linear algebra over a field: Gaussian elimination, elementary row
operations, a code has a unique generator matrix in reduced row
echelon form, every code has after a permutation of the coordinates a
generator matrix of the form G = (I_k |A).
New material:

- parity check matrix of a code,
- standard inner product: bilinear, symmetric, but positive definiteness makes no sense in char p, nondegenerate.
- dual code, double dual of code is the code itself, a code can be self dual (in contrast to the reals)
- if G is generator matrix of code, then G is a parity check matrix of the dual code
- If H is a parity check matrix of a code, then the minimal number of dependent columns of C is the minimum distance of C

**19 Sep 2013**

Lecture given by Ruben Niederhagen.

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

Ruben's slides
are here.

Homework is due Thursday, September 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

**24 Sep 2013**

Dual codes (parity check code and repetition code are dual).
Syndrome decoding with examples, ways to generate new codes from given
ones: extended code, punctured code.

Homework (please be prepared to present this at the beginning of the
next lecture): 2.5.5 and 2.5.6.

Richard Both was so nice to take pictures of the blackboard. They are here.

**26 Sep 2013**

Background on finite fields: computing modulo *n*,
characteristic, must be prime; structure of the additive group is a
vector space; number of field elements is *p ^{n}* for
some prime

Homework is due next Thursday 10:45. The exercise sheet is here.

**01 Oct 2013**

Presentation of homework: 2.5.5 and 2.5.6.

Punctured code, residual code, Griesmer bound, lots of bounds for one
example; (u,u+v) construction, concatenated code.

Hamming codes.

In the u+v construction the min distance is equal
to min{2d1,d2}, the less-than-or-equal-to symbol is incorrect there.

Homework for next Tuesday:
2.5.8 (first part);
2.5.11 also include Griesmer bound.
We took pictures of the blackboard. They are here.

**03 Oct 2013**

Diffie-Hellman (DH) key exchange, discrete logarithm problem, and
Diffie-Hellman problems (computational, decisional). Lots of examples
of easily breakable Diffie-Hellman (DH) key exchange, one more secure
group. How to find a generator of the full group and of subgroups.
We took pictures of all black boards before erasing them. They are here.

Homework is due next Thursday 10:45. The exercise sheet is here. Note, exercise 2 got updated
to include the field representation. Please use *x ^{4}+x+1*
as the irreducible polynomial.
If you used

**08 Oct 2013**

Presentation of homework: 2.5.8 (part 1) and 2.5.11 (incl. Griesmer
bound).

Hamming codes, examples H* _{r}(q)* for

Homework for next Tuesday: 2.5.8 second part. We took pictures of the blackboard. They are here.

**10 Oct 2013**

Finite fields; example of F_{22}, and of
F_{24};
*
a ^{(pn-1)} = 1* for all

Homework is due next Thursday 10:45. The exercise sheet is here. Note that the description has been fixed to match the numbers, N

**15 Oct 2013**

Homework was 2.8.5; we did every single step, see the pictures

Weight enumerator, characters in finite fields, trace, simple
character sum, proof of MacWilliams identity.
Homework: Read and understand Pr_{e} and the part about
Simplex codes and their weight enumerators.
We took pictures of the blackboard. They are here.

**17 Oct 2013**

Full proof of: irreducible binomials of degreee *n* over
**F**_{q} exist if and only if *n* divides
*q-1*; example construction of finite fields; ElGamal;
homomorphic encryption and pitfalls if unintended; Baby-Step Giant-Step
algorithm and runtime analysis.
We took pictures of all black boards before erasing them. They are here.

More pictures by others:
http://ubuntuone.com/5O4wE9nbTUX6FmmpDgN4Yz and http://ubuntuone.com/4uLS29nHYVxO74TCo4Jqak.
Homework is due Thursday, Nov 14 10:45. The exercise sheet is here.

**12 Nov 2013**

Weight enumerator and use for estimating probability of correcting to
wrong codeword, Simplex code as dual of Hamming code and weight
enumerators of both.

Basics of Reed-Muller codes and examples.
We took pictures of the blackboard. They are here.

**14 Nov 2013**

Pollard's rho method (incl. parallel version), distinguished
points. The slides I used for Pollard rho are available here. Index calculus attacks on finite
fields with example p=107.

We (a student with a nice camera and I) took pictures of all black
boards before erasing them. They are here.

Homework is due Thursday, Nov 21 10:45. The exercise sheet is here.

**19 Nov 2013**

Details of Reed-Muller codes and examples: dimension, minimum
distance, dual of RM(r,m) is RM(m-r-1,m), RM(0,m) is repetition code,
RM(m-1,m) is even-weight code.
We took pictures of the blackboard. They are here.

**21 Nov 2013**

L-notation for complexity of index calculus,
complexity of basic index calculus is L_{q}(1/2,c), with
several improvements it's L_{q}(1/3,c), where the constant c
depends on the field type.

Relative security of DLP in group and finite field, see also
http://www.keylength.org/.

Clock group and arithmetic. Edwards curves and arithmetic.

On the Edwards curve x^2+y^2=1-30x^2y^2 the points with x=y have
x=±((-1+sqrt(31))/30)^1/2, about 4.5677643.

Eran Lambooij took pictures of all black boards before I erased
them. They are here.

Homework is due Thursday, Nov 28 10:45. The exercise sheet is here.

**26 Nov 2013**

RM(1,m) is extended simplex code, as it's dual RM(m-2,m) is the
extended Hamming code. Automorphisms of codes, for RM(r,m) alll
invertible affine transformations are included (since f(xA+b) has the
same degree as f). Decoding of Reed-Muller codes (it's painful but
works).

Cyclic codes: binary Hamming code of length 7 and corresponding
simplex code are cyclic; interpretation of code words as polynomials
mod x^{n}-1; cyclic codes are ideals in
**F**_{q}[x]/(x^{n}-1).

Details of Reed-Muller codes and examples: dimension, minimum
distance, dual of RM(r,m) is RM(m-r-1,m), RM(0,m) is repetition code,
RM(m-1,m) is even-weight code.
We took pictures of the blackboard. They are here.

Home work is due Dec 10, please prepare 3.4.4 and 3.4.8.

**28 Nov 2013**

Operation count for addition on Edwards curves,
Montgomery's trick,
Projective coordinates,
faster doubling, NAF has weight 1/3,
Weierstrass curves, Montgomery curves, map bewteen Edwards and
Montgomery.

Note that the formula for doubling on Montgomery curves has
lambda=(3xP^2+2AxP+1)/(2ByP). The picture has been updated.

Eran Lambooij took pictures of all black boards before I erased
them. They are here.

Homework is due Thursday, Dec 5 10:45. The exercise sheet is here. The exercise sheet
has been updated to state that the map can go to a *twisted*
Edwards curve.

**03 Dec 2013**
Lecture given by Boris Skoric on use of coding theory in traitor tracing.

Boris was so nice to make his slides available, they are
here.

**05 Dec 2013**
Lecture given by Ruben Niederhagen
on multivariate systems in cryptography.

Ruben was so nice to make his slides available, they are
here.

Homework is due Thursday, Dec 12 10:45. The exercise sheet is here.

**10 Dec 2013**

Cyclic codes are ideals in **F**_{q}[x]/(x^{n}-1),
generator polynomial, roots of irreducible polynomial are conjugate
(over extension field defined by the irreducible polynomial),
generator polynomials are factors of (x^{n}-1), this
polynomial splits completely over **F**_{qm},
when n divides q^{m}-1. [7,4,3] Hamming code has m=3,
g=x^{3}+x+1, with roots a, a^{2}, and a^{4};
equivalent code has a^{3}, a^{5}, and a^{6},
representation by cosets. Equivalence of f divides c and c(a)=0, where
is a root of f over **F**_{q}[x]/f and f is irreducible
over **F**_{q}.

We took pictures of the blackboard. They are here.

Home work is due Dec 17, please prepare 4.7.2 and 4.7.8 (without the
'vice versa' in c).

**12 Dec 2013** Comments on index calculus (factor base is chosen
independently of target h), and exceptional points for maps between
Edwards and Montgomery curves.

For more material on elliptic
curves check out the tutorial
I gave at Indocrypt 2011. There even exist some videos of it part I and part II.

**Z**/*m*, Euler phi-function and computation, Euler's
theorem, RSA cryptosystem (schoolbook version), small public keys for
efficient encryption, CRT-RSA for efficient decryption, problems with
small public exponents if the same message is sent to multiple users,
homomorphic property, taking squareroots modulo n is as hard as
factoring, attacks using homomorphic properties of RSA, RSA-OAEP to
avoid these problems and others.

Eran Lambooij took pictures of all black boards before I erased
them. They are here.

Homework is due Thursday, Dec 19 10:45. The exercise sheet is here.

**17 Dec 2013**

gh=x^{n}-1, g generator polynomial, h parity check polynomial,
I defining set, cyclotomic coset, minimal polynomial, examples of I={1}
and I={1,3} over **F**_{2}, where n=q^m-1, including decoding
algorithm; BCH codes (definitions and properties), example of n=15, d=7;
Reed-Solomon codes (definition and some properties).
We took pictures of the blackboard. They are here.

No homework.

**19 Dec 2013**
Compositeness tests: Fermat and Miller Rabin. Namedropping of
primality tests: Pocklington and ECPP. Factorization methods: trial
division, Pollard rho, Pollard p-1, namedropping of p+1 and ECM.
With ECM definition of "strong primes" does not make any sense.
Dixon's method to generate a and b with a^2 = b^2 mod n. Namedropping
of quadratic sieve and number field sieve.

Note that the description of Pollard's rho method was wrong in the gcd
step; the picture is updated.
You can find examples and code snippets for these methods on
http://facthacks.cr.yp.to.
We recently broke some smartcards which were not generating their
primes in a proper way. For some disasters on RSA see
http://smartfacts.cr.yp.to.

Eran Lambooij took pictures of all black boards before I erased
them. They are here.

Homework is due Thursday, Jan 9 10:45. The exercise sheet is here. Use the holiday time
to take a look at the exams; feel free to email me with questions
and what you think might be solutions and ask for corrections.

Exam from Apr 13 2012, here.

Exam from Jan 27 2012, here.

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