| 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
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.
Previous versions of this course used
Henk van Tilborg's "Fundamentals of Cryptology", Kluwer academic
Publishers, Boston, 2000. But the book is out of print.
A preliminary author's copy by Henk can be downloaded in pdf form
here
and 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.
You may use a programmable calculator and I expect you to be able
to use it for modular exponentiation and inversion.
I will also bring a laptop with
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 available on the laptop.
For 2MMC10,
the first exam will take place November 01, 2016, 13:30 - 16:30,
in rooms PAV SH2 A and B.
The retake exam will take place January 24, 2017, 13:30 - 16:30,
in room PAV L10.
For Mastermath the exam will take place on December 14,
13:30 - 16:30.
We will merge the retake with the 2MMC10 retake,
this means that you need to come to TU/e on Jan 24 13:30 - 16:30.
The Paviljoen building is some hike accross campus, make sure to
budge time for that. You can find a map of campus here; Paviljoen is building 62 in quadrant E2 on that map.
.
For 2MMC10 you can earn up to 1P for the final mark through the homework. Please hand in your solutions in groups of 2 or 3, we do not have the capacity for individual corrections. Please make sure to register for the exam in time. For TRU/e students from Nijmegen, this means that you need to register at TU/e as well and get a student number etc.
For students from Mastermath, please register on their site.
You can earn up to 1P for the final mark through the homework. Please
hand in your solutions in groups of 2 or 3, we do not have the
capacity for individual corrections. Please submit your solution
on time by email to the address below.
For all students:
Gustavo Banegas and
Leon Groot Bruinderink are
the teaching assistants for this course. You can reach them
at crypto.course (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 email the solution to the TAs.
If an assignment is unclear and you have questions about the
homeworks, contact me in class or by email.
06 Sep 2016
Lecture given by Andreas Hülsing.
General introduction to cryptography; concepts public key and
symmetric key cryptography.
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.
Andreas made his slides available:
Slides in pdf format.
If you want to try your skills at some cryptosystems visit http://www.mysterytwisterc3.org/.
08 Sep 2016
Recap on modular arithmetic,
multiplicative
group mod n, Euler phi function and its computation, Lagrange's
theorem, exponentiation via square and multiply,
RSA, efficient decryption via CRT-RSA incl. quick estimates on
improvement (look up Karatsuba multiplication).
Pictures of blackboards are here.
For 2MMC0, homework is due next Thursday, 15 Sep, at 10:45.
To submit, please bring your homework on paper to the
lecture on Thursday and hand it before the lecture to the
lecturer.
For MasterMath, homework is due Thursday, 22 Sep, at 10:45 by email.
Details will follow.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
I've updated the RSA exercise to state that you can assume a
caclulator with very large precision, i.e. you should use the
square-and-multiply method.
13 Sep 2016
Background on finite fields:
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,
example of F4, additive structure is vector space,
same for F8, representation via polynomials,
irreducible polynomial.
We took pictures of all black boards
before erasing them. They are here.
15 Sep 2016
More properties of finite fields; irreducible polynomials,
fundamental equation of finite fields xpn-x;
Frobenius map, conjugate elements, Rabin's test for irreducibility.
Diffie-Hellman key exchange.
We took pictures of all black boards
before erasing them. They are here.
The cartoon I mentioned is here.
For 2MMC10, homework is due next Thursday 10:45, for mastermath later
(if we can correct at all). 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.
20 Sep 2016
Diffie-Hellman key exchange; Decisional DH Problem (DDHP),
Computational DH Problem (CDHP).
Showing how to solve DDH for an example in F19*
by checking for even or odd exponents.
In general, 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.
Brief mention of hash functions and AES (more next week) to show how DH is
usesd in practice. Check your browser to see uses of DHE (ephemeral DH)
and maybe DH.
ElGamal encryption, relation of IND-CPA for ElGamal and DDH.
Digital signatures, RSA signatures, ElGamal signatures and pitfalls.
Pictures of blackboards are here.
22 Sep 2016
We turned the 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.
Lesson from first part: work in prime-order subgroup.
Definition of Discrete Logarithm (DL); DSA uses subgroups for lower
bandwidth.
Quick run of Baby-Step Giant-Step algorithm (see homeworks for more) and
about random walks using these slides.
Pictures of blackboards are here.
Homework is due next Thursday 10:45 (for 2MMC10) and Oct 20 (for Mastemath).
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons.
The exercise sheet is here.
Hint: There is a reason that I don't state the generator or Alic'e public key;
you're not supposed to compute the DL. ElGamal in the subgroup works
the same as described in the lecture; the only difference is that
s is computed modulo the order of the subgroup (which is prime
here, so that everything is nicely invertible).
27 Sep 2016
Lecture given by Joan Daemen.
One-time pad.
Stream ciphers: (DECT, RC4),
Block ciphers: security notions, Feistel ciphers, DES,
weaknesses of DES.
AES/Rijndael: Design principles, S-box, shift rows, mix columns,
key schedule. Implementation and security aspects.
Block cipher modes.
Joan was so nice to make is slides available. Please
read the slides (or literature above) to learn about modes and padding;
that means up to (and including) page 43 of the slides. I
will cover MACs next week.
Links:
29 Sep 2016
Lecture given by Andreas Hülsing.
Hash function, desired security properties, formal reductions between collision
resistance, preimage resistance, and second preimage resistance.
Attacks on hash functions using brute force and Pollard rho.
Compression functions and length extension modes, Merkle-Damgaard construction,
sponges, constructions using permutations.
Attacks against deployed hash functions with details on MD5 and the rogue-CA
attack.
Andreas made his slides available:
04 Oct 2016
Message authentication codes: differences between MACs and signatures,
security notions,
general constructions, HMAC, CBC-MAC, CMAC, Poly1305.
Pollard-rho attack against the DLP. Birthday bound, how to recover
DLP from collision, Floyd's cycle finding method. Two ways of
getting a random walk -- with very differnt costs. Additive walk
requires a few precomputed points but it much cheaper.
Pictures of blackboards are here.
06 Oct 2016
Full step function for Pollard rho attack, parallel version,
optimization of steps depending purely on g (reusable) and
input points depending on h.
You can find the parallel rho picture in higher resolution
here.
Generic attacks, random self reducibility of DL
Explanation and examples of index calculus attack, factor base,
complexity is exp(c(log q)1/3(log log q)2/3),
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 (for 2MMC10) and Nov 17 (for Mastermath).
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons.
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.
11 Oct 2016
Key sizes for DL in finite fields and groups. For more recommendations
of key sizes see https://www.keylength.com/.
We didn't cover this in class, but there are some speedups that depend
on the prime. Joshua Fried, Pierrick Gaudry, Nadia Heninger, and Emmanuel
Thomé just published
Cryptanalysis of 1024-bit trapdoored primes,
which shows that such weak primes need not be obvious. And cooked up
one such prime with 1024 bits and computed DLs for it! That's a lot
larger than anything done so far.
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 in finite fields.
Edwards curves, picture for d< 0, special points, addition law;
no division by 0 if d is not a square (which matches d< 0 over
the reals, pictures for other cases for d.
We took pictures of all black boards before I erased
them. They are here.
13 Oct 2016
Twisted Edwards curves, (signed) window method for scalar multiplication;
(signed) sliding window method for scalar multiplication, Montgomery's trick
for simultaneous inversion, projective coordinates; compute Edwards DBL in
3M+4S+1 mult by a.
For many more (and computer verified!) formulas see the
EFD.
Weierstrass curves, singularities (cusp, node) and how they are
characterized and what they look like over the reals, short
Weierstrass form characteristic not equal to 2;
point at infinity; lots of cases for addition law; formulas for
ADD and DBL.
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.
18 Oct 2016
Chord-and-tangent method of addition on Weierstrass curves.
Negation if a1 or a3 is nozero.
Montgomery curves and addition on them, can do arithmetic on
u-coordinates without ever needing the v coordinate. For adding
P2 and P3 one needs to have their u coordinates and the u coordinate
of their difference P3-P2; map between twisted Edwards curves and Montgomery
curves.
Elliptic curves in the wild, NIST curves, Brainpool curves,
Curve25519, Curve448, Curve41417. The recent RFC I mentioned is
RFC7748. The signature
proposal EdDSA is still in the state of Internet Draft at
draft-josefsson-eddsa-ed25519-03.
We 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!
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.
I took pictures of all black boards before I erased
them. They are here.
20 Oct 2016
Montgomery ladder and how to avoid implementer mistakes.
Factorization methods: Problems if p and q are too close,
Dixon's method to generate a and b with a^2 =
b^2 mod n, quadratic sieve. Namedropping of number field
sieve. Methods to factor resulting numbers (the right-hand side in the
relations): trial division/sieving, 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.
No exercises this week because there is no more lecture to submit
them. If you want to practice Edwards and Montgomery curves, take a
look at the first exercise of
exercise sheet
11 from 2014.
I took pictures of all black boards before I erased
them. They are here.
25 and 27 Oct 2015
I will be there, you can ask questions. Use the time to practice on some
old exams.
On the 27th I need to leave around 12:00.
Some people asked what an affine point is; that is a point of the form
(x,y) as opposed to a projective point (X:Y:Z).
Old exams by me:
