| 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
The crypto lectures of this course are shared with 2WC12. Some of the crypto lectures will be given by Ruben Niederhagen and some of the coding theory lectures by Ruud Pellikaan.
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
The lectures take place Wednesdays 15:45 - 17:30 (Matrix 1.50) and
Thursdays 10:45 - 12:30 (Auditorium 15). 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 20 - 24 and Jan 12- 16.
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.
Niels de Vreede is
the teaching assistants for the crypto part of your course. To submit
your homework, email it as a pdf file to crypto14 (at) tue.nl.
Do not send me your homework but contact
the TA.
Please team up with another 1-2 students 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
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 a laptop to display
pdf files if you send me the files beforehand. The laptop will have
access to the course page incl. blackboard pictures and scripts, but
you may not use it to surf the internet. There will be a termnal
to run GP-Pari and one to run Python; sage is not allowed.
You may use a programmable calculator and I expect you to be able
to use it for modular exponentiation and inversion.
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.
Niels de Vreedeis
the teaching assistants for this course. To submit your homework,
email it as a pdf file to crypto14 (at) tue.nl.
Do not send me your homework but contact
the TA.
The first exam took place January 27, 2015, 13:30 - 16:30
in Auditorium 11.
The second exam will take place April 14, 2015, 13:30 - 16:30.
Please make sure to register on time! Deadlines for registering are
January 11, 2015 for the first exam and March 29, 2015 for the second one.
03 Sep 2014
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.
Pictures of the whiteboards are here.
05 Sep 2013
General introduction to cryptography; concepts public key and
symmetric key cryptography. Caesar cipher, Viginere, one-time
pad, skytale.
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.
To submit your homework please send it as a pdf file to
crypto14 (at) tue.nl
The exercise sheet is here.
10 Sep 2014
Covering radius, perfect codes,
Sphere-Packing Bound, Gilbert-Varshamov bound, linear codes,
equivalence of codes, generator matrix, parity-check matrix, dual
code, selfdual code, selforthogonal code, syndrome. For most of the
results the repetition code and the even weight code were used as
examples.
Clarification: If you fix a code (rather than go for equivalent codes)
the systematic form of the generator matrix is unique, else, there are
permutations in P.
We took pictures of the blackboard. They are here.
11 Sep 2014
Symmetric-key crypto, public-key crypto,
recap on modular arithmetic, Euclidean algorithm, multiplicative group
mod n, Euler phi function and its computation, Euler's theorem, RSA,
exponentiation via square and multiply, efficient decryption via
CRT-RSA incl. estimates on improvement (schoolbook and Karatsuba
multiplication), pitfalls of schoolbook RSA (same message to three
parties all using exponent 3, oracle assisted decryption).
Pictures of blackboards are here.
Homework is due next Thursday 10:45.
Please email your solutions to crypto14 (at) tue.nl
in pdf format.
The exercise sheet is here.
17 Sep 2014
Lecture given by Ruud Pellikaan
Notation:
F_q instead of GF(q) for a finite field with q elements, and F_q^n
instead of V_n(q) for the n-dimensional vector space over F_q.
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).
Parity check matrix of a code, standard inner product, dual code.
New:
If G is generator matrix of code, then G is a parity check matrix of
the dual code.
If G is generator matrix of code of the form (I_k |A), then
(-A^T|I_{n-k}) is a parity check matrix of the 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.
Singleton bound both linear and nonlinear.
Encoders and decoders. There are efficient encoders with complexity
O(n^2). Closest codeword decoders, this decoding can be done
efficiently for special codes but is in general NP-hard.
Syndrome decoding and cosetleaders, worked-out example (as in the
book). Estimated the probability of correct decoding of the example.
18 Sep 2014
Lecture given by Ruben Niederhagen.
Background on block ciphers and modes of operaton; details on DES and
3DES and on the Advanced Encryption Standard (AES).
Ruben's slides
are here.
Homework is due Thursday, September 25 at 10:45.
The exercise sheet
is here.
Links:
24 Sep 2014
Lecture given by Ruud Pellikaan.
A Closest Codeword Decoder is a Maximum likelihood decoder;
example of a repetition code and the probability of correct
decoding;
dual of binary repetition code is even weight code;
code constructions: extended, punctured and shortened code and
their parameters;
residual code, the nonexistence of a binary [13,6,5] code and
Griesmer's bound;
(u|u+v) construction and concatenated code and their parameters
Homework (no submission, solve these for yourself):
Read section 2.4 Unequal error protection codes and do exercises 2.5.5 and 2.5.6
We took pictures of the blackboard. They are here.
25 Sep 2014
Lecture given by Andreas Hülsing.
Desired properties of hash functions: preimage
resistance, 2nd preimage resistance, and collision
resistance...; attacks on hash functions: brute force,
birthday, Pollard rho; Merkle-Damgaard construction;
attacks on MD5 incl hashclash,
classification of hash functions (provably secure ones
based on public key primitives or block ciphers and dedicated
constructions).
Andreas made his slides available:
1 Oct 2014
Lecture given by Ruud Pellikaan.
- Projective space over a finite field, principal representation
of a projective point, number of points of P^{r-1}(F_q), the projective
space over a finite field
- Hamming code H_r(q) with parity check matrix where the columns
are principal representations of projective points of P^{r-1}(F_q)
- Parameters of a Hamming code, it is a perfect code, syndrome
decoding for this code
- Notion of generalized equivalence of codes C and D, by
permutations and multiplications of coordinates by nonzero scalars
- A code with the parameters of a Hamming code is generalized
equivalent with that Hamming code
- Dual of the Hamming code H_r(q) is the simplex code S_r(q) ,
its parameters and it is a constant weight code
- A code with the parameters of a simplex code is generalized
equivalent with that simplex code
- Weight enumerator polynomial A(z) of a code C and its two
variable homogeneous version W_C(x,y)
- Weight enumerators of trivial codes, n-fold repetition code,
even weight code, simplex code
- Recurrence relation for the weights of the binary Hamming code
H_r(2)
- Mac Williams identity (advantage to use the homogenous
version), checked it in the examples treated
- Weight enumerators of the Hamming code H_r(q) using the Mac
Williams identity
2 Oct 2014
Lecture given by Ruben Niederhagen.
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 pn for
some prime p and positive integer n. Multiplicative
group is cyclic.
Ruben took pictures of all black boards
before erasing them. They are here.
He also typed up some classnotes for this lecture.
Homework is due next Thursday 10:45. The exercise sheet is here.
8 Oct 2014
Lecture given by Ruud Pellikaan.
- Preparations for proof of Mac Williams identity: characters and Hadamard transform
- Full proof of Mac Williams identity
- q-ary symmetric channel with cross-over probability p
- Probability of undetected error for detection only: W_C(1-p,p/(q-1))-(1-p)^n
- Correct decoding, decoding failure, decoding error
- Formulas (no proof) of probability of correct decoding and
probability of decoding error are given in case of bounded distance
decoding up to t errors with t at most (d-1)/2
9 Oct 2014
Lecture given by
Tung (Tony) Chou.
Message authentication codes: general constructions, HMAC, Poly1305, Auth256.
Diffie-Hellman key exchange; use of DH in public-key authenticated
encryption.
Tony made his slides available:
here
Homework is due next Thursday 10:45. The exercise sheet is here.
15 Oct 2014
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. Please read the proof concerning the
dual of RM(r,m) in the lecture notes.
We took pictures of the blackboard. They are here.
16 Oct 2014
Lecture given by Ruben Niederhagen.
ElGamal encryption and signatures;
problems with signatures; Pohlig-Hellman attack; Baby-Step Giant-Step
algorithm and runtime analysis; Pollard-rho attack.
Ruben took pictures of the black boards
before erasing them. They are here.
He also typed up some classnotes for this lecture.
The slides he showed are here.
Homework is due November 13 at 10:45. The exercise sheet is here.
12 Nov 2014
Cyclic codes: binary Hamming code of length 7 and corresponding
simplex code are cyclic; interpretation of code words as polynomials
mod xn-1; generator polynomial and its degree, generator
matrix, encoding for G=(PI), parity check polynomial, convolution,
parity check matrix. Short excursion to finite fields: roots of
irreducible polynomials in extension fields, conjugates,
(a+b)q=qq+bq.
We took pictures of the blackboard. They are here. Note that the binomial
on the last blackboard is not correct.
Please check out Exercise 4.7.8; we'll take some time at the beginning
of the next lecture to deal with it.
13 Nov 2014
Courtesy of the Dutch railways and some truck
company I didn't make it to class until about 12:00. Andreas Hülsing was so
nice to step in spontaenously.
Notions of security for signatures, hash-based signatures,
Lamport-Diffie one-time signatures and security proof,
Merkle tree to get few-time signatures.
Parameters for DSA, short explanation and example of index calculus
attack.
We took pictures of the black boards
before erasing them. They are here.
Homework is due November 20 at 10:45. The exercise sheet is here.
19 Nov 2014
Background on finite fields: primitive element, primitive n-th roots
of unitiy, minimal polynomial, factorization pattern, orbits under
q-th powers = cyclotomic coset, several examples.
Cyclic codes: roots of generator polynomial are also roots of every
code word,
writing the paritiy check matrix as powers of an n-th
root, this corresponds to evaluating the codewords at that root
relation to cyclotomic cosets, every binary Hamming code
is cyclic. Solution to exercise 4.7.8.
We took pictures of the blackboard. They are here.
20 Nov 2014
Some ideas how to choose the factor base,
L-notation for complexity of index calculus,
complexity of basic index calculus is Lq(1/2,c), with
several improvements it's Lq(1/3,c), where the constant c
depends on the field type. Index calculus for fields of small characteristic.
The table I showed last time about the relative security of DLP in group
and finite field is a small part of
http://www.keylength.org/.
Clock group and arithmetic.
We took pictures of all black boards before I erased
them. They are here.
Homework is due Thursday, Nov 27 10:45. The exercise sheet is here.
26 Nov 2014
Cyclic codes are ideals in Fq[x]/(xn-1).
I defining set, cyclotomic coset, minimal polynomial, examples of I={1}
and I={1,3} over F2, where n=q^m-1, including decoding
algorithm; BCH codes (definitions and properties), examples of n=7, d=3;
n=15, d=7; n=23, d=?.
Proof that BCH codes have minimum distance at least equal to their
designed minimum distance.
Reed-Solomon code.
We took pictures of the blackboard. They are here.
27 Nov 2014
Edwards curves, picutres, special points,
addition and doubling formulas, Montgomery's trick for simultaneous
inversion, Projective coordinates, operation count for doubling on
Edwards curves, quick note on Curve25519 and Curve41417 as curves and
fields with nice properties.
A proof that addition on Edwards curves with d<0 over R is complete
can be found p47 onwards on these
slides.
We took pictures of all black boards before I erased
them. They are here.
Homework is due Thursday, Dec 4 10:45. The exercise sheet is here.
03 Dec 2014
In a field the sum of the n-th roots of unitiy, for n>1, is 0.
Details on RS codes; minimum distance equals desgined distance,
RS codes are MDS, also their shortened version,
also their extended version. Binary Golay code [23,12,7] and how
to find these parameters.
We took pictures of the blackboard. They are here.
04 Dec 2014
Weierstrass curves, short Weierstrass form for characterisitc 2
and odd characteristic; singularities (cusp, node) and how they
are characterized and what they look like over the reals, geometric
addition law; lots of cases for addition law; formulas for ADD and
DBL; Montgomery curves and addition on them; map between twisted
Edwards curves 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.
For many more (and computer verified!) formulas see the
EFD.
We took pictures of all black boards before I erased
them. They are here.
Homework is due Thursday, Dec 11 10:45. The exercise sheet is here.
There was an error in the second exercise that has been fixed now.
The expresssion should be 4a^3+27b^2.
10 Dec 2014
Lecture given by Ruud Pellikaan
Ternary Golay codes. The rest of the lecture was based on the book by
Ruud Pellikaan.
Reed-Solomon codes and generalized Reed-Solomon codes, including
extended codes, BCH versions not starting with α but powers of
it; subfield subcodes, super codes. This covers pages 157-162 in teh
pdf file; please work through the examples yourself.
Alternant codes (p 174) are subfield subcodes the duals of
generalized Reed-Solomon codes; parameters.
11 Dec 2014
Lecture given by Andreas Hülsing.
Proofs and reductions; random oracle model, reasons why padding alone
is not enough; proof for RSA signatures with PSS.
Andreas made his slides available ROM_Signatures.pdf
No homeworks for this week; there will be another sheet next week.
17 Dec 2014
Quick recap of GRS codes, including
systematic form and links to BCH codes; alternant codes, please read
the examples in Ruud's book.
Alternative view on BCH codes, leading to Goppa codes; Goppa codes,
sorry for the confusion of switching between the notation of both
books: we take the ai and the polynomial g from the same field, which
is an extension field of Fq; the code we consider
has codewords in Fq. Relation between Γ(L,g1)
and Γ(L,g2) if g1 divides g2; parameters, typical choice has g
irreducible.
McEliece cryptosystem: uses binary Goppa codes; minimum distance is
almost twice as large (no proof given yet); encryption and decryption,
use of easy to decode code G, permuation matrix P, and
invertible matrix A to generate public key generator matrix
G=AGP; decryption = decoding works because P only permutes the
error positions but does not change the number of them. Decode for
message mA, then apply inverse of A. Parameters of original McEliece
system were n=1024, k=524, degree of g=50, and extension field
10. When we broke these paramters in 2008 it was good enough for a press
release and a paper about this.
We took pictures of the blackboard. They are here.
18 Dec 2014
Hasse's theorem. Compositeness tests:
Fermat and Miller-Rabin. Namedropping of primality tests: Pocklington
and ECPP. Factorization methods: trial division, Pollard rho. Dixon's
method to generate a and b with a^2 = b^2 mod n. Namedropping of
quadratic sieve and number field sieve. namedropping of Pollard p-1,
p+1 and ECM.
You can find examples and code snippets for these methods on http://facthacks.cr.yp.to. In
2013 we broke some smartcards which were not generating their primes
in a proper way. For some disasters on RSA see http://smartfacts.cr.yp.to.
I forgot my camera, Arjen Zijlstra and Simon Voorberg were so nice
to send me their blackboard pictures.
Homework is due Thursday, Jan 8 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.
07 Jan 2014
Lecture given by Ruud Pellikaan
The following numbers refer to the book by Pellikaan.
- decoding complexity, brute force and syndrome decoding, complexity exponent p.
105-106
- decoding erasures, p. 106-108
- information and covering set and decoding (just mentioned, they can read p. 109-115
- algebraic decoding, error-correcting pairs, p. 179-182 (work out example on page 183)
Homework:
Exercises 4.1:1,2,3,4 on p. 116.
exercise 7.1.1 on page 184
08 Jan 2015
Lecture given by Thijs Laarhoven.
Constructive applications of lattices in lattice-based crypto and
algorithms for computing shortest vectors. These can be used to break
some RSA instances and against lattice-based crypto.
Thijs has put the slides from his lecture online. Slides for the
first hour and the
second hour.