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
Some of the lectures will be given by Ruben Niederhagen.
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. I will not repeat basic background on groups, rings and fields in class. 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 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 and 12.
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.
04 Sep 2014
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.
Please email your solutions to crypto14 (at) tue.nl
in pdf format.
The exercise sheet is 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.
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:
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:
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 p^{n} 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.
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.
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.
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.
20 Nov 2014
Some ideas how to choose the factor base,
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. 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.
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.
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.
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.
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. Note that the comment about the calculator does not
mean that you're supposed to do 3 & 4 with a calculator --
for once those are not primes.
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.
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.
Old exams by me: