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
To prepare for the exam:
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
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.
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
2^{k}-ary
method for k=2; try to use bigger numbers and m
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:
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
F_{p} one sees that a finite field has
p^{n} 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
α_{i}*α_{j} for 0<=i,j
< n or (g^{i}+1) for 0<i<
p^{n}-1.
Pictures are here.
Homework: Assume that F_{8} exists. Write group tables
for addition and multiplication - if possible.
06 Oct 2011
Long example to construct F_{8}. Can construct field by
using basis 1,a,a^{2},a^{3}, ...,
a^{n-1}. Need to represent a^{n} 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)=
(a^{2}+5b^{2})*(c^{2}+5d^{2}).
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 F_{p} of degree n splits completely
over F_{pn}, construction of
F_{pn} using an irreducible
polynomial of degree n over F_{p}; number
of irreducible polynomials of degree n over
F_{p}.
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
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: