| 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 2MMC10 - Cryptology. This course is offered at TU/e and is also part of the TRU/e security master study program. The official page is here. If you are a student from Nijmegen following this course, please register with TU/e (you'll need a proof that you're registered at your home university) and then register for the course on http://oase.tue.nl/. You also need a TU/e login to access the video recordings of the lectures and to register for the exam. I cannot let you participate in the exam without registration.
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.
A freely downloadable textbook is
Henk van Tilborg's "Fundamentals of Cryptology", Kluwer academic
Publishers, Boston, 2000.
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; 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 or 3. 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 Vreede and
Henry de Valence are
the teaching assistants for this course. You can reach them
at crypto15 (at) tue.nl.
Do not send me your homework but submit it
on paper before the Thursday lectures. If there is a programming
component to the exercises contact the TAs.
The first exam will take place October 27, 2015, 13:30 - 16:30, in Matrix atelier 3. The retake exam will take place January 19, 2016, 13:30 - 16:30. Rooms will be announced on the oase and owinfo pages.
01 Sep 2015
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.
03 Sep 2015
Recap on modular arithmetic, Euclidean
algorithm, exponentiation via square and multiply, multiplicative
group mod n, Euler phi function and its computation, Lagrange's
theorem, RSA, efficient decryption via CRT-RSA incl. estimates on
improvement (look up Karatsuba multiplication).
Pictures of blackboards are here.
Homework is due next Thursday 10:45. Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. To submit, please bring your homework on paper to the
lecture on Thursday and hand it before the lecture to the
lecturer. The exercise sheet is here.
08 Sep 2015
Lecture given by Ruben Niederhagen.
Background on finite fields: reminder of fields and subfields,
integers modulo 2 as example,
extension degree,
characteristic, characteristic must be prime; prime field,
structure of the additive group is a vector space over the prime
field; 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.
10 Sep 2015
Lecture given by Ruben Niederhagen.
More background on finite fields.
example of F4(=GF(4)), additive structure is vector space,
same for F8, representation via polynomials,
irreducible polynomial, inversion of elements using XGCD or
exponentitaion, Rabin's test for irreducibility.
Ruben took pictures of all black boards
before erasing them. They are here.
He also typed up some more classnotes for this lecture.
Homework is due next Thursday 10:45. Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. To submit, please bring your homework on paper to the
lecture on Thursday and hand it before the lecture to the
lecturer. The exercise sheet is here.
15 Sep 2015
Recap of cyclic groups, primiitive element, order of group elements
divides order of group n, for every divsisor l of n there exist
ϕ(l) elements of that order, get these as gin/l
for i coprime to l.
Diffie-Hellman key exchange; Decisional DH Problem (DDHP),
Computational DH Problem (CDHP), Discrete Logarithm Problem (DLP).
Brief mention of hash functions and AES (more later) to show how DH is
usesd in practice. Check your browser to see uses of DHE (ephemeral DH)
and maybe DH.
ElGamal encryption and signatures.
Pictures of blackboards are here.
17 Sep 2015
Explanation why ElGamal signatures work. Pitfalls for signatures.
We can solve the DDHP if the generator generates all of Fp
by checking whether the parity of ab and c matches; to do that compute
the (p-1)/2-th power of the elements. If this is =1 then the element
is a square. If at least one of ha and hb is a
square then their DH share is also a square, so we can detect radom c
if the parity doesn't match. The same works for other divisors of
p-1.
We turned this distinguishing attack into a discrete logarithm attack
by computing a modulo the prime divisors of p-1; in the end we
reinvented the Pohlig-Hellman attack which solves the DLP in a big
group by solving it in subgroups.
The examples were done using Pari/GP. Under linux it is
available as Debian package pari-gp.
Pictures of blackboards are here.
Homework is due next Thursday 10:45. Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. To submit, please bring your homework on paper to the
lecture on Thursday and hand it before the lecture to the
lecturer. The exercise sheet is here.
22 Sep 2015
Lesson from last lecture: work in prime-order subgroup. How to attack
DLP there? Brute force, multi-target, birthday paradox, Baby-Step
Giant-Step algorithm and runtime analysis; Pollard-rho attack
incl. parallel version.
Here
are the pictures from the slides in condensated form.
Pictures of blackboards are here.
24 Sep 2015
Explanation and example of index calculus attack, 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. For fields of small characteristic stronger attacks exist. The
logjam attack makes use of
precomputation to attack individual DLPs very quickly. Check out the
page for details. Parameters for DSA, see http://www.keylength.org/ for
more.
Pictures of blackboards are here.
Homework is due next Thursday 10:45. Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. To submit, please bring your homework on paper to the
lecture on Thursday and hand it before the lecture to the
lecturer. The exercise sheet is here. Also, please read the
logjam paper for the index calculus attack details; you'll see the
part on TLS in Applied Crypto.
29 Sep 2015
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:
01 Oct 2015
Mathematically interesting attack in logjam: some implementations messed
up the parsing of generator and order of generator in the DSA setting. You should
really read the paper and take a look at Nadia Heninger's slides.
Clock group and arithmetic: lots of points on the unit circle; how to add them
using their angles, translation using trigonometric formulas, addition law using
regular carthesian (x,y) coordinates, (0,1) is the neutral element,
-(x,y) =(-x,y), addition is obviously commutative. Some special points and their
orders; clocks modulo p, finding points on the clock modulo 17.
Edwards curves, picture for d&tl; 0, special points, addition law;
no division by 0 if d is not a square (which matches d< 0 over
the reals.
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, Oct 08 10:45. The exercise sheet is here.
06 Oct 2015
Lecture given by Ruben Niederhagen.
Symmetric cryptography;
background on stream ciphers and block ciphers.
Details on modes of operaton, DES and 3DES,
and on the Advanced Encryption Standard (AES).
Ruben's slides
are here.
8 Oct 2015
First part of the lecture given by
Tung (Tony) Chou.
Message authentication codes: differences between MACs and signatures,
general constructions, HMAC, Poly1305, Auth256.
Tony made his slides available:
here
The second (smaller) part was about elliptic curves: twisted Edwards curves,
explicit formulas, Montgomery's trick for simultaneous
inversion, projective coordinates.
For many more (and computer verified!) formulas see the
EFD.
We took pictures of the board before I erased
them. They are here.
Homework is due next Thursday 10:45. The exercise sheet is here.
13 Oct 2015
Weierstrass curves, singularities (cusp, node) and how they are
characterized and what they look like over the reals, short
Weierstrass form odd characteristic and for characterisitc 2;
geometric addition law; lots of cases for addition law; formulas for
ADD and DBL; Montgomery curves and addition on them, quick note on
Curve25519; 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 an overview of suggested curves and their security properties
see http://safecurves.cr.yp.to/,
where we check security properties of curves agains mathematical and
implementation-based attacks.
Some people asked after the lecture about secure ways of choosing
curves. We actually did some work on figuring out how much freedom
sombody has to sneak in a backdoored curve (not that we know of any
way of backdooring curves). Our results are
online. Have fun!
I took pictures of all black boards before I erased
them. They are here.
15 Oct 2015
ECDH, use double and add for computation of aP; look up (signed)
windowing methods for more efficient ways. Montgomery ladder.
Montgomery ladder and integrated fomulas for computing the
x coordinate of aP on Curve25519 (or any Montgomery curve; just
update the a24 and loop length). Namedropping of EdDSA.
If you want to see the Curve25519 standard grow, take a look at the GitHub page and the
resulting Internet Draft. EdDSA is currently being turned into an Internet
Draft; for more references see the 'References' part of that
document.
Factorization methods: Dixon's method to generate a and b with a^2 =
b^2 mod n. Namedropping of quadratic sieve and number field
sieve. Methods to factor resulting numbers (the right-hand side in the
relations): trial division, Pollard rho. Pollard p-1, namedropping of
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 mentioned timings for factorizations of 512-bit numbers by Nadia
Heninger. Turns out they just put their paper online.
I took pictures of all black boards before I erased
them. They are here.
20 Oct 2015
I offered a session on the old exams; see the
picture for a few
general announcements.
Old exams by me: