Contents | Announcements | Exams | Literature | Pictures, videos, 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 Chloe Martindale.
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 October 31, 2017, 13:30 - 16:30. The retake exam will take place January 23, 2018, 18:00 - 21:00. Rooms will be announced. For Mastermath the exam will take place on January 8, 2018, 14:00 - 17:00. We plan to merge the retake with the 2MMC10 retake, this means that you need to come to TU/e on Jan 23.
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:
Gustavo Banegas and
Manos Doulgerakis 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.
05 Sep 2017
General introduction to cryptography; concepts public key,
symmetric key cryptography, and hash functions.
Pictures of blackboards are here.
Videos will come as soon as I have better internet.
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.
07 Sep 2017
Recap on Fermat's little theorem, Euler phi function and its computation,
Lagrange's theorem,
Chinese Remainder Theorem (CRT).
RSA encryption (KeyGen, Encrypt, Decrypt), exponentiation via square
and multiply, use of RSA in hybrid encryption (use RSA to encrypt a
key for symmetric crypto, use the latter to encrypt the message.
choolbook RSA is homomorphic, avoid this structure
by using a padding scheme; we covered
RSA OAEP.
RSA signatures (KeyGen, Sign, Verify).
Note that RSA is exceptional in that signing and encrypting are
so closely related.
Faster decryption/signing via CRT-RSA incl. estimates on
improvement (look up Karatsuba multiplication).
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 14 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, 28 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.
12 Sep 2017
Factorization techniques for integers: trial division, Pollard's
rho method including explanation why it works when it works and
Floyd's cycle-finding algorithm; Pollard's p-1 method including
why it works.
Start of explanation of how to factore RSA numbers; e.g. how to
factor if p and q ar too close.
Pictures of blackboards and videos are here.
14 Sep 2017
Factorization using Dixon's method/method of random squares.
The initial example didn't work as well as I expected and I
couldn't connect with my laptop. Thanks for helping out
with laptop and typing!
We used the computer algebra system Pari-gp for the examples
and I wrote some of the commands on the board (also at the
beginning of the second lecture). See the beginning of the
second lecture (= 4th picture)
for a working example of factoring 323.
Q-sieve, quadratic sieve, some comments about the number-field
sieve and running times.
You can find examples and code snippets for these methods and
those from the previous lecture on http://facthacks.cr.yp.to.
The slides I used are here.
Primality testing methods: Fermat test and Carmichael numbers;
Miller-Rabin test. These tests 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. Read up on Pocklington's test.
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 21 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, 12 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.
Note that you do not need to write anything for exercise 6.
19 Sep 2017
Lecture given by Chloe Martindale.
Finite fields. Recap on basic group theory and building up knowledge about finite fields from axioms.
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 p^{n} for
some prime p and positive integer n. Multiplicative
group is cyclic,
example of F_{4}, additive structure is vector space.
Chloe was so nice to write up lecture notes for this
class.
Pictures of blackboards and videos are here.
21 Sep 2017
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 AES, modes, and padding;
that means up to (and including) page 43 of the slides. I
will cover MACs later.
Links:
For 2MMC0, homework is due next Thursday, 28 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, 26 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 3rd exercise sheet is here.
26 Sep 2017
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 was so nice to make his slides available:
[part1-pdf],
[part1-pptx],
[part2-pdf],
[part2-pptx]
Videos are here.
28 Sep 2017
Lecture given by Chloe Martindale.
More background on finite fields:
example of building F_{8}, representation via polynomials,
irreducible polynomials
irreducible polynomials,
Rabin's test for irreducibility.
Crypto protocols relying on hardness of DLP (Diffie-Hellman, ElGamal encryption,
ElGamal signatures, DSA), and attacks on DLP (PlayStation3 disaster,
Pohlig-Hellman attack, Baby-step giant-step).
Chloe was so nice to write up lecture notes for this
class. Note, Section 5, point 4 in the
Pohlig-Hellman attack there were some incorrect indices (now fixed).
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 05 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, 09 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. The 4th exercise sheet is here.
Note that I updated the sheet to fix the statement of Rabin's test.
This didn't matter for the exercise.
I also updated exercise 2a to change the requirements on h.
03 Oct 2017
Lecture given by Chloe Martindale.
Examples of finite fields, including a field with 32
elemnets. Computational and decisional Diffie-Hellman problem with
examples. Example of the Baby-Step Giant-Step algorithm and Pollard's
rho method for discrete logs. Start of index calculus attacks for finite fields.
Pictures of blackboards and videos are here.
05 Oct 2017
Lecture given by Chloe Martindale.
The slides for Pollard's rho method are
here.
Explanation and example of index calculus attack, 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. 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.
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.
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 12 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, 23 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.
WIth this you might overlook one mathematically interesting attack in logjam:
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.
10 Oct 2017
Lecture given by Chloe Martindale.
Representation of integers modulo p; repetition of addition on circle;
Edwards curves, picture for d&tl; 0, addition law;
no division by 0 if d is not a square (which matches d< 0 over
the reals) with proof over the reals and over any finite field;
group properties apart from associativity.
Doubling, projective coordinates, explicit formulas for doublings with
operation count.
For many more (and computer verified!) formulas see the
EFD.
Chloe keeps on totally spoiling you and wrote up
lecture notes for this class.
Pictures of blackboards and videos are here.
12 Oct 2017
Lecture given by Chloe Martindale.
Twisted Edwards curves, 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.
Chloe keeps on totally spoiling you and wrote up
lecture notes for this class.
Note, bottom of p6 there was a
sign error (now fixed)
Pictures of blackboards and videos 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.
Last year 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!
For 2MMC0, homework is due next Thursday, 19 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, 07 Dec, 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.
17 Oct 2017 Different curve shapes; 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.
Some details on Curve25519 and the selection criteria for it; number of points on curve plus the number of points on the (quadratic) twist is 2p+2 for a curve over F_p; 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. The Elliptic-Curve Method (ECM) of factorization is a generalization of the p-1 method to using and elliptic curve modulo n to factor n. If you combine ECM with Edwards curves you get EECM
Message Authentication Codes (MACs) ensure authenticity and integrity of the message between communicating parties. Unlike signatures they cannot convince a third party of the authenticity. Warning on length extension attacks for Merkle-Damgaard schemes with dummy MAC H(k||m) (don't ever do that!), and length extension in CBC-MAC. Quick statements of better MACs: HMAC and Poly1305. Note that the addition of AES_k(n) mod 2^128 is an integer addition mod 2^128 and not an XOR (wouldn't make sense mod 2^128). I briefy mentioned the CAESAR competition for authenticated ciphers, those are combining encryption and authentication in one design. An older design is AES-GCM which uses AES in CTR mode to encrypt and polynomial authenticator like in Poly1305.
Pictures of blackboards and videos are here.
19 Oct 2017 Comparison of keylengths. I gave something close to NIST's recommendation, which are easy to remember because they use numbers that are powers of 2, with an occasional 3 in there. Note, these can be off. For an overview of recommended keylengths see https://www.keylength.com/. Of course, just choosing the correct sizes does not make the system secure. I discussed the logjam attack in a bit more detail, including a lesser knownn part that only appears in the paper in which the authors attack DSA implementations that messed up the order of parameters and use q as generator instead of g. In combination with choosing nonces k of restricted size these systems were often solvable by an adaptation of Pohlig-Hellman: compute k modulo small primes dividing the order of q in F_p until the solution is unique within the range of k. Then use that knowing one nonce allows you to recover the long-term signing key.
Things can also go wrong for RSA: in 2012 two teams found that RSA keys on the Internet shared primes, i.e. n1=p*q1 and n2=p*q2, which made them breakable by simply computing gcds. There are too many keys to compute pairwise gcds, so the authors did something smarter (see https://factorable.net/ for more details from one of the teams). Normally this could not happen -- the prime-number theorem says that there are x/log_e(x) primes up to x and randomly chosen primes will not repeat. But, these RSA keys were generated by small linux boxes that did not get enough randomness. The year after we had some fun breaking RSA keys on certified smartcards. We noticed patterns in the repeating keys and used a technique due to Coppersmith to find more factors. I have some slides online about our attack.
Finally I mentioned Post-Quantum Cryptography and that there is a huge need to investigate alternatives to ECC and RSA.
Pictures of blackboards and videos are here.
What's next? Here are a few courses that you might find interesting:
24 Oct 2017
I offered a question and answers session. The TAs were so nice to finish
grading the homeworks already. If you didn't get yours, find them or me
in the office the next days.
I explained a bit about Edwards curves and did an example of Pohlig-Hellman.
Pictures of blackboards and videos are here.
You will notice that the last exercise is going beyond the exact material covered
in class, to see whether you understand what you learned (rather than just being
able to follow an algorithm).
26 Oct 2017 No class
Old exams by me: