| 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
If you're a student in the TRU/e master you should subscribe to the mailing list for getting updates.
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
For 2MMC10, the exam will take place on 27 Oct. There will be a 3h exam online followed by 30 min during which you need to record a video of you explaining your solution.
The online exam will take place 13:30 - 16:;30 using Ans Delft. Log in with your TU/e student credentials to find the exam for 2MMC10 called "2MMC10_Cryptology_Q1_20/21_Final Exam". You can also find a practice exam there to see how Ans Delft works. This practice exam is available now till 27 Oct 12:00. You can use the arrows in the bottom row to jump between exercises or click on the boxes in the middle to naviagate between exercise parts. Note that each exercse stars with some defintions that you need to read before you can do the exercise parts.
There are two question types: numerical questions that take a single number as answer and open-answer questions that give you a text editor to enter your answer. You must enter your answer by typing. Do not write on paper and send photos. You may use latex formatting to make your answer look better but this is not a rrequirement. Latex mode is started and ended by typing two dollar signs next to each other. The text will render nicely once you have clicked outside the text field. Check out the practice ezam on Ans Delft to experiment with how to enter text and formiulas.
17:00 - 17:30 you will get access to the exercises and your answers
through Ans Delft. You then have 30 min to record a video of you. The
video should start with you presenting your student ID and saying your
name. Then you explain your solution to 3 exercise parts. You may
choose these parts yourself among the exercise parts that are not
numerical questionsbut those that required some text in the answer field.
An exercise part is any piece that has it's own answer field, so I don't
expct all parts of exercise 3 for example and you an pick parts of different
exercises to explain. Aim for 5 min, but up to 10 min
is OK. This videos will be used only to establish that you are the
person who wrote those exercises, it does not influence your grade.
Name the file as
ID_{student ID]_[Last name].[file format]
filling in your TU/e student ID, your last name, and the file format (mp4, webm)
instead of the brackets
and upload your file to Surfdrive (file drop only).
You need to upload your video by 17:30. If Surfdrive fails, the backup is to
uploadt the video on Canvas, I have created an assignment there.
If your connection is too weak, store the video on your computer and compute the SHA-256 checksum of it and mail that to Tanja Lange.
If you want to practice file upload, use the surfdrive test site
The cover sheet states all information on permitted materials.
Here is the cover sheet you'll encounter for
this exam.
I should also warn you that when I click on "Start the test" I do see "Just a moment, we're preparing your test" for longer than what I would consider a moment. You're all getting your very personal exams with numbers generated just for you, so I think it's doing that while you're waiting. Don't panic when that happens. I has worked out for me each time.
The resit for 2MMC10, which is equal to the first exam for the
MasterMath students is planned for 19 Jan 2021. The format will b
the same as for the first exam. The cover sheet
is slightly updated to reflect questions I received .
Students who do not have a TU/e account
need to contact Tanja so that she can make accounts for Ans Delft.
Please regiser by 5 Jan 2021 for this. See also the email from
22 Dec 2020..
One lesson learned from the first exam is that you should set up
your coputer so that you can copy numbers using copy-and-pste.
Do not retype the numbers.
You can test file upload toSurfDrie with
this link.
For the exam we will use
this link.
Do not use this one for practicin
.
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: Your teaching assistants this year are
01 Sep 2020
I expect you to have watched the videos of the first lecture (1a and 1b) from
the 2019 set. The second one is short and you can stop after the explanations
about the hash functions. I will use the perfect-code system during the
BBB session.
If the board is hard to read, click on the window with it to magnify. I
also have
pictures of blackboards here.
If you have problems finding the right lecture, choose to sort from old to new
and limit the date range to 2019.
For this week I'm nice and post the direct links here
Please prepare questions on the topics covered in that lecture, namely:
General introduction to cryptography; concepts public key,
symmetric key cryptography, and basics of hash functions.
In the live session I did a quick recap of these topics, I will not do this for the other lectures. I also went through a bunch of the admin things that in priciple are mentioned there already, but there were a lot of questions. Some people where helpful in typing things in the shared notes. here are the combined notes.
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
03 Sep 2020
If you're a student in the TRU/e master you should subscribe to
mailing list
for getting updates.
There seems to be some confusion regarding the lecture slot. I expect
the Thrusday lectures to be in block 3 and 4, so 10:45 – 12:30.
The topics covered in the video are:
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 are here.
Please prepare questions for the live session.
In the live session I computed some example of RSA KeyGen, Enc,
and Dec (with and without CRT). I used the ocomuter algebra system Pari for this.
We also looked at the components of a PGP key and saw that it stores p, q, and u
as part of the private key, i.e., it uses the CRT method. For details on the
PGP key format see
RFC 4880.
Note that in RSA-CRT you should reduce c prior to computing the small
exponentiations, I didn't put the notation on the boards, but there
should be c_p and c_q, to ensure that the operands have smaller size.
Some people where helpful in typing things in the shared
notes. here are the combined notes.
08 Sep 2020
Please watch the video before the live session and prepare questions.
The topics covered in the video are:
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 are here.
For the live session we split into three breakout rooms.
One student asked for a more detailed explanation of the runtime of Pollard-rho using Floyd's cycle finding method. See Random mapping statistics by Flajolet and Odlyzko for average estimates of the tail length √ π p /8 and cycle length √ π p /8 leadng to an average rho length of √ π p /2, see section 3.2 of that paper. The best case happens if tail and cycle have exacly the same length, meaning that the fast walk meets the slow walk exactly at the entrance. If the cycle is sonewhat longer then it will take only a few steps for the fast walk to catch up. In the worst case the cycle is just a tad shoter,meaning that the fast walk has just passed the entry point and will need another two rounds till it meets the slow walk near the entry point. At that point the slow walk has done roughly √ π p /2. while the fast walk has done roughly 3 √ π p /2 leading to the factor of 4 I said in the lecture, but I was sloppy there in ignoring the π/2 factor and I was wronga about where the (tight) miss can happen.
There were also some questions regarding why Pocklington works and when to use it. I will try to write up some more and post here.
10 Sep 2020
Please prepare questions on the topics of lectue 4a and 4b.
It would be great if you could post them on Zulip before
the lecture. The topics are
In the live sessions I explained more about exponentiation, see this slide set and Dixon's method of random squares, see this slide set. I also highlighted the essential parts of the p-1 method so far this has had it only to a whiteboard picture. It would be great if you could ask questions in advance on Zulip so that I can prepare slides in advance.
The notes ind chat ncluded some questions, which I answered on Zulip.
Here for posterity and the definition of order:
ordn(a) means the order of a modulo n, which is the smallest number
o > 0 such that a^o equiv 1 (mod n).
For 2MMC0, homework is due next Thursday, 17 Sep, at 10:45.
For MasterMath, homework is due Thursday, 01 Oct, at 10:45.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
15 Sep 2020
The topics covered in this lecture are:
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.
In the live session we covered the Q-sieve and basics of LLL/Coppersmith using the slides linked above. here are the notes from the session, thanks to the people who helped type.
17 Sep 2020
The lectue in 2019 was given by Andreas Hülsing.
He covered
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.
In the live session I explained a bit more about the dataflow of sponge
functions and the relevance of the parameters r and c.
Florian Weber explained a bit more
about reductions; he will update his writeup from last year which I
will then link from here.
In the second hour I explained the basics behind hash-based signatures
using these slides; you can also download the
code snippets from the slides. If you missed this lecture and want to see a similar one,
the original summer school talk on this topic was recorded.
For 2MMC0, homework is due next Thursday, 24 Sep, at 10:45.
For MasterMath, homework is due Thursday, 15 Oct, at 10:45
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
22 Sep 2020
The topics covered in the videos as
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 from last year are here.
In the live session I covered again that for normal encryption you will want to use
DH for getting a shared key and then use symmetric crypto in authenticated encryption
to send the actual message. ElGamal is only used if you really want the homoorphic
properties.
Situations where key erasure matters are A and B communicating and not keeping copies
of the plaintext, but an attacker recording all encrypted traffic and then later getting
access to A's or B's device.; if that device still contains the keys used for the
session, the attacker can decrypt the recording.
As a major topic I covered LLL and Coppersmith / Howgrave-Graham attacks to explain how one sets up the matrices and why that makes sense. I made slides for that, see here.
Florian Weber wrote some background information on reductions to give more details and an example from the Diffie-Hellman world. The (updated) 2020 version is here.
24 Sep 2020
Please prepare questions on the following topics
In the live session we did two detailed examples of Pohlig-Hellman, details of why it works, and a comparison of three appraoches to handling prime powers (to explain why I insist on updating the target h). Then we briefly discussed how to rewrite protocols to work in a subgroup of prime order inside the multiplicative group of the finite field. All of this is captured in the notes.
For 2MMC0, homework is due next Thursday, 01 Oct, at 10:45.
For MasterMath, homework is due Thursday, 29 Oct, at 10:45.
Submission is by email for both groups.
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.
29 Sep 2020
Please prepare questions for the following topics:
Summary of what happens in the videos
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 from 2019 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
I wanted to show some nice slides in the live session and messed up in combining them
so that I was left with none (well, some old ones). Here are the now-fixed slides.
I explained BSGS, Pollard rho, and briefly index calculus attacks. We did
example computations for each of them. I copied the Pari-GP history and annotated
the commands so that you can catch up on what we did.
Here are these notes.
01 Oct 2020 Please prepare questions on symmetric crypto. I might get some more material to post.
In 2019 the 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 the live session Tomer Ashur presented on symmetric cryptography (general, stream ciphers, block ciphers) and answered a lot of questions. See the Zulip chat for links.
For 2MMC0, homework is due next Thursday, 08 Oct, at 10:45.
For MasterMath, homework is due Thursday, 12 Nov, at 10:45
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 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.
06 Oct 2020
These are the topics of the lecture, please prepare questions
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 from 2019 are here.
In the live session we first discussed questions regarding the homework.
For exercise 1: if you're stuck trying to invert something which doesn't have
gcd 1 with p-1, take a look at the handling of the DL of 3 in exercise 2.
If you're stuck in exercise 2 at the matrix step, similar comments apply, i.e.
solve everything modulo factors of p-1 where things are invertible, then
figure out the unknown parts of each of the DLs of the small primes.
Then we showed that (0,-1) has order 2, (\pm 1,0) have order 4 and points of the
form (\pm x, \pm x) have order 8, if they exist. The group order is always a
multiple of 4. These results hold for any shape of Edwards curve, not just for
d not a square. We also looked at 0 < d < so see that it has the same points
of small order. The drawing does not have all points – there are points at
infitiny that are missing. To study them, we looked at the homogenous equation of
the Edwards curve Z^2(X^2+Y^2) = Z^4 + dX^2y^2 and found (1:0:0) and (0:1:0) as
points with Z=0. For the "experts" I added that those points are singular and
that the blow-up is defined over a field where d is a square -- which is another
way to see the completeness of the addition law for d a non-square. Embedding
the curve int P^1 x P^1 is nicer as the points at infinity are naturally
non-singular. The Z coordinate will come back on Thu, maybe then this will look
more natural.
The drawings didn't come out too well, but anyways, here they are
whiteoard 1 and whiteboard 2.
08 Oct 2020 Trigger warning: I had a pretty bad cold last year and am coughing a lot in the video. I should have stayed home or at least worn a mask, but last fall was much more carefree.
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 from 2019 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!
In the live session we discussed the general definition of elliptic curves,
long and short Weierstrass equations, definitions of singularity and how
to find singular points (depending on the curve equataion),
birational equivalences between curves, and Montgomery curves.
The slides from the live session are here.
Test your understanding of singularities by proving that Montgomery
curves are nonsingular for
A not 2 or -2. B must be nonzero. For twisted Edwards curves the
conditions are that a is not the same as d and that they are both
non-zero. I mentioned already on Tuesdays that there are singularties
at infinity in the usual projective embedding into P^2 and that you
should use P x P instead (ignnore the part about infinity if these
concepts don't mean anything to you).
For 2MMC0, homework is due next Thursday, 15 Oct, at 10:45.
For MasterMath, homework is due Thursday, 26 Nov, at 10:45.
The exercise sheet is here.
13 Oct 2020
In 2019 this lecture was 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 from 2019 are here.
In the live lecture we went through some of the slides linked above. The takeaway
is that there are some small speedups to Pollard rho and that actually doing a
full attack computation requires a lot of optimizations – but we're doing a
lot of work for not even a factor-2 speedup. So elliptic curves are pretty strong.
Finally I showed some code to demonstrate how ECM, the elliptic-curve method
of factorization, works. Sadly, screensharing and sage managed to crash my laptop
and even before that it was pretty unhappy performance wise. The script just runs
trhough the primes between 2 and 10 000 and outputs whether the prime would have
been found for p-1 with base 2 and exponent 60, with ECM on Bv^2=u^3+8u^2+u with
base point (2,v8) and s=60,, or with ECM on Bv^2=u^3+9u^2+u with
base point (2,v9) and s=60. The B, v8, v9 are chosen so that the point is on
the curve (pick the v-value, compute B) but they don't matter as the formulas
use only the u-coordinate (see the link to RFC 7748 above for instructions on
how these formulas work). I got myself totally confused during this part and
forgot about the B. If you want to play with the script, e.g. to vary the
curves or the s, you can find it here.
15 Oct 2020 This session will be held on BigBlueButton/Canvas Conference. This system is accessible to students outside TU/e and I will post a link on this page when I have it (it only remains valid for a few hours and I need to start the session to get it).
In 2019 this lecture was given by
Andreas Hülsing.
The topics he covered are
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.
We did a live Q&A session; see th Zulip chat for screenshots. Good luck with the exam.
05 Ja 2021
What's next?
Here are a few courses that you might find interesting:
Old exams by me:
