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
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
Note that one of the course requirements is algebra, this year I will not repeat basic background on groups, rings and fields. If you don't have the necessary background, take the summer and work through the "Number Theory and Algebra" script.
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.
You can find the pdf here
and the book 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 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.
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.
Thijs Laarhoven and Jan-Jaap Oosterwijk are
the teaching assistants for this course. To submit your homework,
email them at crypto13 (at) tue.nl.
Do not send me your homework but contact
the TAs.
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.
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.
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 Thursday 10:45. The exercise sheet is here.
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:
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 p and positive integer n. Multiplicative
group is cyclic, generator is called primitive element.
Poly1305-AES as an example of a Wegman-Carter-based MAC (using
reduction mod 2^{130}-5 and AES in its construction).
Any two messages have negligible chance of producing any particular difference in Poly1305 outputs; chance measured over random choices of key
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.
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 x^{4}+x^{3}+1 it's also OK.
Also the decryption in exercise 3 uses c, not m.
10 Oct 2013
Finite fields; example of F_{22}, and of
F_{24};
a^{(pn-1)} = 1 for all a in
K^{*}. Construction of
F_{pn} using an irreducible
polynomial of degree n over F_{p};
examples of F_{22}, and of
F_{24}; number of irreducible polynomials of degree
n over F_{p}; Rabin irreduciblity test;
irreducible binomials of degreee n over
F_{q} exist if and only if n divides
q-1.
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 that the description
has been fixed to match the numbers, N_{3}(4) should be
computed as stated. In exercise 1 consider only n>1.
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.
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.
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.
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.
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.
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.
Old exams by me: