| 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 some laptops 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 October 29, 2019, 13:30 - 16:30 in GEM-Z 3A08, 3A10, 3A12, and 3A13, that's in the Gemini building at the south side.
The retake exam will take place January 21, 2020, 13:30 - 16:30
in Atlas 4.215 and Atlas 4.225. Take a look at the
campus map to find the building.
.
For Mastermath the exam will take place on January 21, 2020,
in Eindhoven together with the retake for 2MMC10.
this means that you need to come to TU/e on Jan 21. The retake still
needs to be scheduled but will either be 25 February 2020 in the
afternoon or replaced by oral exams.
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.
The bonus point only counts if the grade for the exam is at least
5.0, so even if you score a full bonus point in the homework but
only a 4.5 in the test you do not pass. 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: Manos Doulgerakis and
Florian Weber 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.
03 Sep 2019
General introduction to cryptography; concepts public key,
symmetric key cryptography, and hash functions.
Pictures of blackboards are here.
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. The other hints I gave are
05 Sep 2019
Recap on Fermat's little theorem, Euler phi function and its computation,
Chinese Remainder Theorem (CRT).
RSA encryption (KeyGen, Encrypt, Decrypt), exponentiation via square
and multiply method.
Faster decryption/signing via CRT-RSA incl. estimates on
improvement (look up Karatsuba multiplication).
Fermat's primality test.
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 12 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, 19 Sep, at 10:45 by email.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
For the RSA exercise you can assume a
caclulator with very large precision, i.e. you should use the
square-and-multiply method.
10 Sep 2019
RSA signatures; note the use of the hash function.
Miller-Rabin primality test. Fermat and Miller-Rabin are 100% correct
when they output 'not prime'; otherwise they say 'maybe prime'. If you
want to be sure that a number is prime, you need to use a primality
proof. We covered Pocklington's test which does not work for all
primes (in the way I presented it). I'll get back to this later..
Factorization techniques for integers: trial division, Pollard's
rho method including explanation why it works when it works and
Floyd's cycle-finding algorithm. In practice you would batch the
gcd computation, doing one only every l steps and computing the
gcd over the product of the steps. Each step then costs 3 squarings
(two for the fast walk and one for the slow walk) and 1 multiplication
(for the product in the gcd). Note that all of these are done modulo n.
Furthermore, l steps together incur one gcd computation.
Pictures of blackboards and videos are here.
12 Sep 2019
Pollard's p-1 method including
why it works
Factorization using Dixon's method/method of random squares.
We used the computer algebra system Pari-gp for the examples
and I wrote some of the commands on the board.
You can find examples and code snippets for these methods and
those from the previous lecture on http://facthacks.cr.yp.to.
Pictures of blackboards are here.
For 2MMC0, homework is due next Thursday, 19 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, 03 Oct, at 10:45 by email.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
17 Sep 2019 General factorization methods: Dixon, quadratic sieve, Q-sieve, number field sieve. To reduce the size of the inputs and thus to increase the chance of smoothness and to use sieving we showed how the quadratic sieve works. As a step towards the general number-field sieve we covered the Q-sieve with slides, of which we covered the first pages. To see the asymptotic analysis, read on.
If schoolbook RSA is used many things can go wrong, in particular if
the public exponent is small. We covered the basic case that the
message has less than 1/e of the bitlength of n and thus no reduction
took place and then covered stereotyped messages. For those we could
try to brute force the missing pieces but an attack using lattices is
much faster. Take a look at page 29 onwards of
these slides to see how we can set up a lattice and then use LLL to solve for
the varying part of the stereotyped message. We used
sage for the live computations and the
slides.
To avoid such issues use a large modulus and modify the message before
encryption. We covered OAEP, see also the next homework sheet.
Note that there was an error in the lecture. I confused the positions
of H and G. I have now fixed the jpgs.
Coppersmith's method is a way to find small roots of polynomials
modulo RSA numbers using LLL. As a second example we showed how to set
up a system to break RSA if all but the bottom 86 bits of p are known,
for n=p*q. This is explained with examples on page 14 onwards of these
slides (same as above). For a practical example that it can
really happen that parts of the secret RSA primes become known I showed
an explanation of the
ROCA results using my own
slides
(see page 72 onwards; this is the same slide deck as for the Q-sieve).
We wrote a longer blog post on this
here.
The slides before that (page 56 onwards) cover another real-world example
of bad randomness and attacks using Coppersmith' method. For the full
story check out http://smartfacts.cr.yp.to/.
Pictures of blackboards are here.
19 Sep 2019
Lecture given by Andreas Hülsing on
cryptographic hash functions.
Desired properties of hash functions: preimage
resistance, 2nd preimage resistance, and collision
resistance; attacks on hash functions: brute force,
birthday, Pollard rho; length extension constructions:
Merkle-Damgaard, sponges; compression function design: MMO;
provable security and reductions: relations between hash function properties;
brief intro to hash-based signatures: Lamport-Diffie OTS, Merkle signature scheme.
Andreas was so nice to make his slides available:
[part1-pdf],
[part1-pptx],
[part2-pdf],
[part2-pptx]
Pictures of blackboards are here.
For 2MMC0, homework is due next Thursday, 26 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, 17 Oct, at 10:45 by email.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
24 Sep 2019
Some more background on Coppersmith's method, including a bound on the
length of the shortest vector output by LLL and a theorem by
Howgrave-Graham. If you want to learn more about this take a look at
the overview article by Alexander May (you need to be on a university network to
download it). Exercises based on this method appear fairly often in
crypto challenges and CTFs – and as we found out also in real-life
scenarios such as the Taiwanese Citizencards
and ROCA, so it's a good tool to know
Diffie-Hellman key exchange, related problems (DDH, CDH, DLP) and their relations. ElGamal encryption (why it works, that it is homomorphic, and that you can break the IND-CPA security if if you can solve DDH).
Pictures of blackboards are here.
26 Sep 2019
ElGamal signatures, DSA), and attacks on DLP: brute force,
Pohlig-Hellman attack,
Pictures of blackboards are here.
For 2MMC0, homework is due next Thursday, 03 Oct, 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, 31 Oc, at 10:45 by email.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The 4th exercise sheet is here.
Note: I corrected h to h' in step 2; this does not affect the
homework as there the highest power of a p_i was 2.
01 Oct 2019
DSA (how and why it works, some paramters). For more on
parameters for DSA, see http://www.keylength.org/.
Generic attacks on the DLP: baby-step giant-step, Pollard's rho method.
Explanation of index calculus attack, factor base,
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.
Pictures of blackboards are here.
The second part of the lecture was given by
Daniel J. Bernstein
on symmetric cryptography. He explained the general history and
functionality and then MACs (Message Authentication Codes), which
are used to authenticate messages. In particular he explained
Wegman–Carter MACs which are information-theoretically secure.
He has posted his slides
03 Oct 2019
Lecture was given by
Daniel J. Bernstein.
He presented the concepts of pseudo-random functions (PRFs) and
pseudo-random permutations (PRPs), block ciphers, and modes.
He explained cipher design and attack avenues on the example of the
Tiny Encryption Algorithm (TEA) by doing minimal changes to the
algorithm and then showing how to break the tweaked version.
He has posted his slides
For 2MMC0, homework is due next Thursday, 10 Oct, 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, 14 Nov, at 10:45 by email.
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 or take a look at
Nadia Heninger's slides.
Make sure not to overlook one mathematically interesting attack in the logjam paper:
some implementations messed
up the parsing of generator and order of generator in the DSA setting;
you'll see the
part on TLS in Applied Crypto.
08 Oct 2019
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.
The video I mentioned at the end of the lecture showing geometric addition laws for the 0 < d <1 is here (YouTube link)
Pictures of blackboards are here.
Florian Weber wrote up an extra document on reduction proofs for your information. This includes a coments on the grading for exercise shee 3 for students of 2MMC10. You can find the sheet here.
10 Oct 2019 Twisted Edwards curves as a generalization of Edwards curves. Doubling, projective coordinates, explicit formulas for doublings with operation count. For many more (and computer verified!) formulas see the EFD.
Weierstrass curves incl. pictures over the reals;
addition on Weierstrass curves and partial proof that this is a group law;
Explanation of point at infinity via projective coordinates;
derivation of addition formulas on Weierstrass curves.
Montgomery curves as a special form of Weierstrass curves; easy to map
between Montgomery curves and Edwards curves, so they have the same security.
Montgomery curves are not just interesting as yet another curve shape.
Montgomery curves have efficient scalar multiplication using
one DBL and one DADD per bit of the scalar using the Montgomery ladder; see RFC 7748 for details on Curve25519 and Curve 448 and how to implement them
correctly and efficiently.
Pictures of blackboards are here.
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 mentioned that the deigner of the system can choose the parmeters, of course within
the limits of making secure choices. However, there is also some risk in this
flexibility, namely that somebody might make malicious choices.
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!
For 2MMC0, homework is due next Thursday, 17 Oct, 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, 28 Nov, at 10:45 by email.
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 Oct 2019
Lecture given by Lorenz Panny.
Quick repetition of projective coordinates.
Elliptic Curve Method (ECM) for factoring as generalization of p-1 method
using elliptic curves modulo n to factor n.
Hasse's theorem says that the number of points on a curve over F_q is away from q+1 by at most
twice the squareroot of q.
Pollard rho method as an attack on the ECDLP; parallel rho method in order
to use multiple computers and have shorter walks, this uses distinghuished
points. How to choose the step function? Quick repetition of the schoolbook
version. Real attacks use additive walks with many precomputed steps, for
sufficiently many steps, this is close to random and for r different steps
the probability of success is reduced by √1/(1-1/r).
For ECDLP we can group P and -P in the walk to gain a factor √2 in
speed, however this requires us to deal with fruitless cycles, i.e. walks
that get stuck in a very small loop, colliding with itself without solving
the ECDLP, but we know how to escape them.
The slides for Pollard's rho method are here.
If you want to learn more about solving the ECDLP or care about attacks in interval, take a look at slides from a summer school talk. Spoiler alert: cute kangaroo pictures!
Pictures of blackboards are here.
17 Oct 2019
Lecture given by Andreas Hülsing.
Formal treatment of secret key cryptography. Secret key encryption: Perfect secrecy, IND, SEM, IND-CPA, IND-CCA. PRGs, PRFs, PRPs and how to use them to build (secure) encryption. Message authentication: EU-CMA, PRF is a secure MAC, CBC-MAC, how to securely combine SKE & MAC.
Andy was so nice to make his slides available.
What's next? Here are a few courses that you might find interesting:
Old exams by me: