| Contents | Announcements | Exams | Literature | Videos | Course notes & exercise sheets | Follow-up courses | Old Exams |
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 (in alphabetical order):
The online exam will take place 2 Nov 13:30 - 16:30 using Ans Delft. After the exam you have 30 min during which you need to record a video of you explaining your solution.
I have made a practice exam available for testing the interface. That exam is not for testing knowledge, just to see how Ans works. As soon as the study admin people have added you to the course in Ans Delft you can log in with your TU/e student credentials to find the exams for 2MMC10. The real exam is called "2MMC10_Cryptology_Q1_21/22_Final Exam". That's not available, yest, of course. You can also find the practice exam there to see how Ans Delft works. This practice exam is available now till 01 Nov 12:00. You can use the arrows in the bottom row to jump between exercises or click on the boxes in the middle to navigate between exercise parts. Note that each exercise stars with some definitions 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 requirement. 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 exam on Ans Delft to experiment with how to enter text and formulas.
16:30 - 18:00 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 questions but 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
expect 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, this implies that you cannot see your
own file after upload, but you can ask Tanja to check).
You should upload your video by 17:00 for regular time, 17:30 if you
got extra time.
If your connection is too slow, store the video on your computer and compute the SHA-256 checksum of it and mail that to Tanja Lange before the deadline
you can continue to upload your video after the deadline.
If you want to practice file upload, use the Surfdrive test site (file drop only, this implies that you cannot see your own file after upload, but you can ask Tanja to check).
If you want to opt out of recording a video, please contact me (Tanja) at the latest on 31 Oct, but preferrably earlier, to schedule a short online interview right after the exam. The interview covers the same as the video, so you will need a camera, show your student ID and say how you solved the exercises, but it will not be recorded. We do not have capacity to offer this to all 100 of you but by experience we have enough capacity to handle everybody who is concerned about having their video on surfdrive. Note that in any case I will delete all videos after the grades are announced.
The cover sheet states all information on permitted materials.
Here is the cover sheet you'll encounter for
this exam (up to changes in the dates).
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 is planned for 25 Jan 2022 18:00 – 21:00. The format will be the same as for the first exam. The URL for uploading the video after the exam is https://surfdrive.surf.nl/files/index.php/s/nn9BxdmBv58YNdF.
This part has no-cookie links to the YouTube videos. Watch them from here if you're on a low-cookie diet. For even fewer cookies, you can find the videos on surfdrive. File names match the file names of the slides.
You can also go to the YouTube Channel for the course and get notifications there.
This video sets the context for the course and introduces the
concepts of public-key cryptography and symmetric-key cryptography.
See also the slides.
I recorded a video to demonstrate how to use Sage https://www.sagemath.org/, covering basics of finite fields and
elliptic curves.
I also wrote a short ``cheat sheet'' with commands for Sage,
see here
This video explains the Diffie-Hellman key exchange and shows one
example of a group in which to use it, namely the clock.
See also the slides.
This video covers clock arithmetic over finite fields and shows the
double-and-add method. It also has some important warnings.
See also the slides.
If you have never seen the square-and-multiply method (or just
want a recap) and thus had problems with the double-and-add method,
take a look at this video which I recorded for 2WF80 Introduction to Cryptology. The
slides are here.
This video introduces Edwards curves and proves that the addition
law does not have any exceptional cases.
See also the slides.
This video covers Edwards curves modulo a prime p. Do not be deterred
by this video being somewhat longer. This is partially due to a proof
which is not particularly illuminating, so you can skip it if you want,
but I wanted to make sure to show everything for Edwards curves, and
partially due to me giving some historical perspective at the end, which
should be easy listening.
See also the slides.
This video goes back to the dark ages and shows how we used to explain
elliptic curves. You will need the content starting page 5.
See also the slides.
The typos on the last slide are now fixed.
This video covers Montgomery curves, the concept of birational
equivalence, and a proof that Montgomery curves have group order
divisible by 4 over a finite field. The video also shows that
Montgomery curves and twisted Edwards curves are birationally
equivalent, thus proving the claim from part 4 that the group
order on twisted Edwards curves over finite fields is divisible
by 4.
See also the slides.
This video covers improvements of the double-and-add method
using windows to save point additions and information on
timing attacks.
See also the slides.
This video covers the double-and-always add method as well as the
Montgomery ladder to compute scalar multiples in a constant-time
manner. Note, this still requires your operations in the finite
field not to show what the inputs are.
See also the slides.
This video covers projective coordinates, an explanation of points
at infinity, and explicit formulas for addition on Edwards curves and
differential addition and doubling on Montgomery curves.
See also the slides.
This video states the properties we want to achieve with signatures
as well as the security notions and powers the attacker may be given.
See also the slides.
This video presents the Schnorr identification system, Schnorr signatures,
EdDSA and ECDSA.
See also the slides
This video discusses a small speedup to the Pollard rho
method that uses symmetries of the elliptic curve. In
particular, identifying a point and its negative means
that the search space for finding a collision has half
as many elements, promising a speedup by a factor
of √2 if the walk is defined to work on classes
of points modulo negation. The talk shows pitfalls with
this approach and how to circumvent them.
Yes, I did a whole video for a factor of √2 –
I even wrote a paper about this once.
See also the slides
This video rounds off the unit on elliptic curves by briefly
summarizing what other attacks exist and then summarizing
how to choose good elliptic curves for cryptography.
Note, Pairings I also discusses attacks on the
ECDLP and should
be watched before this video.
See also the slides
Further reading:
This video sets up our targets. It covers hardness assumptions for
Diffie-Hellman and related systems and also shows how to use it in
practice and what issues can arise.
See also the slides.
This video goes through how to mount brute force attacks for a single
target, multiple targets, and how to use random self reduction to turn
one target into many and solve them faster. Optimizing and systematizing
this approach we obtain the Baby-Step Giant-Step (BSGS) algorithm.
See also the slides.
This video covers random walk and cycle finding. This is relevant
background for the Pollard-rho method, the subject of the next
video. We also get a glimpse at how finding collisions in well-designed
walks allows us to compute the discrete logarithm of a target.
See also the slides.
This video explains two ways to instantiate the pseudo-random
walk in Pollard's rho method. Attacks use the second one,
additive walks, as they are significantly faster. The video also
discusses a small slowdown caused by these walks being not
fully random.
See also the slides.
This video investigates how to use more than one computer to
solve the DLP faster. The overall cost remains the same at
n^(1/2) but using t computers gives a speedup of a factor t.
To achieve this, the way of finding collisions has to be
changed.
See also the slides.
This video uses a running example to find how to use subgroups
to speed up attacks against the DLP. Systematic treatment
happens in the following video.
See also the slides.
This video presents the Pohlig-Hellman attack. For an example
see the previous video. Pohig-Hellman solves a DLP in an
order-n group by solving it in the prime order subgroups. If
a prime p divides n with multiplicity e, i.e. if p^e divides n,
then Pohlig-Hellman solves e DLP in the subgroup of order p.
The most interesting part is how to ensure that one lands in this
subgroup and that the results are meaningful for the DLP computation.
After all these partial DLPs are computed they are combined using
the Chinese remainder theorem.
See also the slides.
If you don't know that theorem,
watch this
short video.
This video gives a summary of the generic attacks seen so far and
studies the effect of subgroups on the hardness of the DDHP
(decisional Diffie-Hellman problem).
Note: When Eve gets a challenge (aP,bP,cP) in DHHP
then cP=abP with 50% probability, that's how the challenge is set up.
So, guessing valid or not has a 50% probability of being correct.
See also the slides.
See ECC XII for attack optimizations for elliptic curves and the DL in finite field lectures below for improvements specific to ECC and finite fields.
Further reading
This video introduces hash functions as used in practice and covers
the estimates for the generic hardness. Note that these are
best-case estimates, i.e., a hash function cannot be stronger than
this, but designs can be weaker.
See also the slides.
This video goes into details on attacking hash collisions using
the Pollard rho method and what to consider for creating meaningful
collisions. The attack page, also linked from the slides is
Predicting the winner of the 2008 US Presidential Elections using a Sony PlayStation 3
See also the slides.
This video formalizes the security properties we want to achieve
with a hash function. To make this work, we even have to change
the definition of a hash function, which makes it less useful for
describing properties of actual hash functions. However, it is possible
to turn a given hash function into a keyed hash function, so this
approach is not fully futile.
See also the slides.
This video covers reductions between hardness assumptions, both
as a general concept and applied to the properties of hash
functions.
See also the slides.
This video shows the sponge construction as a modern example of how
hash functions are built. Some details for the NIST standard SHA-3
are given which is based on the sponge construction. Note that SHA-3
was called Keccak before being standardized.
See also the slides.
Further reading
Tomer Ashur recorded 4 videos on symmetric-key cryptography, his area of research, for this course. He sure ups the game on video recording!
This first video sets the scene and puts symmetric crypto into a
historical context. We use symmetric-key cryptography for encrypting
data.
Stream ciphers use a key to deterministically produce a sequence of
output bits (or bytes) that appear random and are unpredictable to an
observer who obtains prior output but does not know the key. Alice
can encrypt a message (written as a sequence of bits = vector in
F2) by computing the xor = vector addition modulo 2
of the message with an output piece of the same length. Bob computes
the same output and xors it with the ciphertext to get the message.
Of course, both need to know where to start; to simplify this and
avoid having to skip ahead by many steps stream ciphers use an extra
input, the initialization vector, which is sent along with the
ciphertext. With that, encryption and decryption start with the
beginning of the output stream.
A block cipher encrypts a fixed-length message into a ciphertext
of the same length using a key. To encrypt longer messages,
modes of operation are used, see the next video. A block cipher
is an invertible function from n bits to n bits, i.e., a permutation
on {0,1}^n. Tomer covers general design strategies and speaks in
more detail about AES.
To encrypt longer messages with a block cipher the message is
split into pieces of n bits, possibly adding some padding if
the length is not a multiple of n. If these blocks were encrypted
individually, basic frequency analysis would weaken or break the
system (this mode is called ECB = electronic code-book mode and the
ECB penguin is the negative example you should keep in mind). Tomer
covers the formal definition of modes and presents the modes CBC, CFB,
OFB and CTR.
This video shows the Tiny Encryption Algorithm as an example of a block
cipher and discusses the importance of cryptanalysis.
See also the slides.
In this video 4 variations on TEA are shown and broken. Each of these
illustrates a technique used in symmetric-key cryptanalysis.
See also the slides.
The slides have been updated to clarify the meaning of high and low
bits and that the first output bit is b_0.
This video introduces message authentication codes (MACs) and
shows the Wegman–Carter construction, first for a small
example and then for Poly1305, a MAC used in the real world.
See also the slides.
Further reading:
This video states the components of public-key cryptosystems
as well as the security notions. It then explains the RSA
cryptosystem and shows that schoolbook RSA is not
IND-CPA or OW-CCA-II secure. Finally it presents RSA-OAEP
as a solution to this problem, the padding randomizes
the encryption process and destroys the homomorphic properties.
See also the slides.
This video shows RSA signatures and then investigates how RSA
is used in GPG. For faster decryption it uses RSA-CRT which
saves a factor 2-4.
See also the slides.
This video analyzes the first step in RSA KeyGen, namely how primes
are picked – or rather how one determines that a given number is
prime. It shows the Fermat primality test, the Miller–Rabin primality
test and the Pocklington primality proof.
See also the slides.
This video gives and overview of factorization methods and explains
Pollard's rho method for factorization.
See also the slides.
This video explains the p-1 method and its generalizations to the p+1
method and the elliptic-curve-method of factorization (ECM).
See also the slides.
This video shows the blue print of all the sieving methods:
a hard to factor number n is factored by finding a and b with
a^2 \equiv b^2 mod n and computing gcd(a-b,n). The methods
differ in how these a and b are computed. This video shows
Dixon's method of equivalences of squares.
See also the slides.
This video covers the Q-sieve as a stepping stone to the more general,
and faster, number-field sieve. All computations here are simple
integer computations. The only non-trivial part is in the analysis
using the approximation u^{-1} of the Dickman function.
See also the slides.
A number field is an algebraic extension of Q, so the Q-sieve
is a special case of the number field sieve. This video first covers
the sieve for Q(√14) and then shows which parts generalize
in the number field sieve.
See also the slides.
This video is easy listening for some disaster stories
about RSA with bad randomness.
See also the slides.
This video introduces Coppersmith's method to factor integers with
known bits. We actually found examples of where this worked in
the wild and broke a bunch of keys.
In general, Coppersmith's method is a way to find small roots of polynomials
modulo RSA numbers using LLL.
See also the slides.
This video has all the details to understand Coppersmith's
attack: showing the LLL algorithm and proving a theorem by
Howgrave-Graham which explains how we build the matrices.
Finally, the video also shows how to attack stereotyped
messages, i.e., messages where only some small part is
unknown, if RSA with small exponent is used.
See also the slides.
Further reading:
This video revisits the Diffie-Hellman system over finite fields
and frames semi-static DH in the KEM-DEM framework, which is also
introduced.
ElGamal encryption is a randomized encryption system for DL system.
We show that IND-CPA security is equivalent to DDHP.
See also the slides.
This video shows the schoolbook version of index calculus attacks.
Optimized attacks differ in the details, but this gives you the
gist of how they work. This is at the same level as Dixon's method
of equivalences of squares compared to the number-field sieve for
factoring.
See also the slides.
This video starts by showing the ECRYPT key-size recommendations.
By now we know almost all systems appearing in that table.
For finite-field DL systems there is a big difference between the
needed group size and the needed field size; DSA is a signature
system for which signatures are compressed to two elements modulo
the group order, which is shorter than the corresponding ElGamal
signatures would be. The video closes with an overview of what
we have seen so far and gives the state of the art for crypto used
on the Internet.
See also the slides.
This video presents a small example for the schoolbook version
of index calculus.
See also the slides.
Further reading:
This video introduces pairings and shows how they can be used to
attack ECC (in cases where efficient pairings can be computed).
See also the slides.
This video covers constructive aspects of pairings by showing how to
use them to do tripartite key exchange, construct an ID-based encryption
system, and how to get short signatures from pairings.
In the context of the latter I also introduce distortion maps.
See also the slides.
This video defines supersingular curves and shows that
these curves have very small embedding degrees and
offer distortion maps (for the designer as well as for
the attacker).
See also the slides.
This video covers Paillier's cryptosystem, an additively
homomorphic system. The video shows how the homomorphism works and
that decryption correctly recovers the message.
See also the slides.
This video gives an introduction to post-quantum cryptography, showing
what the threats are, and why this matters already today.
See under What's next? for a course I will be teaching spring 2022 on post-quantum
crypto in MasterMath; the video and slides for links to the 2021
edition of that course with lots of exercises and videos. The last slide
has more links.
See also the slides.
Further reading
This session is extended through the course. I will announce here which topics we cover which weeks and which videos you should watch to prepare for the live sessions. See here for the videos.
07 Sep 2021
In preparation for class, please watch the interaction video and the
first two videos in elliptic-curve cryptography.
In the live session I explained the perfect-code system.
Here are the slides perfect-code.pdf
The exercise sheet for the live session is here.
Hints I gave for exercise 1
Spoiler alert! Don't follow the upcoming link if you sill
want to solve exercise 1 yourself.
The
"Perfect Code Public Key System" was designed by by Fellows and
Koblitz. Attention, this was never proposed for cryptography but only
as a teaching tool. I like using it because the public key looks very
different from the private key.
09 Sep 2021
Please bring your questions. I've also added 3 more videos on ECC
which you should watch. I understand that I was late in doing so,
so I don't expect you to get this done by the lecture, but if you
do and if you do have questions I'll be there to answer them.
We went through most slides sets of videos. To see the case for
(x2-y2) being nonzero in the proof for Edwards curves over finite
fields, start with (x1-y1\epsilon) and trace the sign change through
the formulas.
14 Sep 2021
Please watch the remaining 4 videos on ECC (part 6 - 9) before
the session. We will meet in the wonder.me room, I will post an
exercise sheet before the session starts.
The first homework is due on
21 Sep at 13:15 via Canvas. Note that homeworks exercises are
different from the exercises for the live sessions and I am
allergic to answering questions about the homeworks in the
Tuesday sessions. I will normally post the homework sheet only
after the Tuesday session, but this one has been long announced.
The homework sheet has been updated to specify that exercise 2
is for Edwards curves, i.e. a=1.
The exercise sheet for the live session is here.
16 Sep 2021
This is a Q &A session on BBB, you have gotten an invitation
already. Please bring your questions! Topics can be the first 9 ECC
videos or the first 3 DLP videos. Also please ping me if you have
problems signing up for Zulip.
We discussed exercise 2c from sheet 1, exercise 7 from sheet 2,
what isomorphisms mean, and why it is enough for DH to use only
the u-coordinate on Montgomery curves..Here are the
notes that I was typing in the
shared document. I had made an error in copying within the
calculation for the isomorphism an fixed that after the end of the
session. I've also done some minor cleanup for the rest.
21 Sep 2021
Please watch the next 4 videos on DLP (part 4 - 7) before
the session. If you have not used Sage I recommend you watch
the introductory video I recorded, see second video
under Introduction.
We will meet in our wonder.me room, see Canvas or Zulip for the URL.
The exercise sheet for the live session is here.
The second homework is due on
28 Sep at 13:15 via Canvas.
23 Sep 2021
This is a Q &A session on BBB, you have gotten an invitation
already. Please bring your questions! Topics can be the first 9 ECC
videos, the first 8 DLP videos, the first 2 hash videos and Sage.
Also please ping me if you have
problems signing up for Zulip.
We discussed what random self reduction does, how and why Pollard rho works,
and why Pohlig–Hellman works.
28 Sep 2021
Please watch the remaining videos on hash functions and on ECC before
this session. There are now 5 hash videos and 11 ECC videos.
We will meet in our wonder.me room, see Canvas or Zulip for the URL.
The exercise sheet for the live session
is here.
The third homework is due on
05 Oct at 13:15 via Canvas.
There was a typo in 2b: k_i was supposed to be r_i. This is
now fixed.
30 Sep 2021
This is a Q &A session on BBB, you have gotten an invitation
already. Please bring your questions! Topics can be anything we
covered up to now, but I would like to focus on questions regarding
the most recent videos, so hash functions, signatures, and
symmetric cryptography.
We covered in detail why the verification equation of
EdDSA / Ed25519 includes a multiplication by 8. You
can find the slides for it here.
05 Oct 2021
Please watch the remaining videos on symmetric-key cryptography
(up to VI) before this session.
We will meet in our wonder.me room, see Canvas or Zulip for the URL.
The exercise sheet for the live session
will be posted before the session.
is here.
The fourth homework is due on
12 Oct at 13:15 via Canvas.
07 Oct 2021
This is a Q &A session on BBB, you have gotten an invitation
already. Please bring your questions! Topics can be anything we
covered up to now, but I would like to focus on questions regarding
the most recent videos, so symmetric-key cryptography and RSA.
I would appreciate getting some questions in advance on Zulip so
that I can prepare some extra material.
12 Oct 2021
Please watch the new videos on RSA
(up to VIII, up to VI is needed) before this session.
We will meet in our wonder.me room, see Canvas or Zulip for the URL.
The exercise sheet for the live session
is here.
The fifth homework is due on
19 Oct at 13:15 via Canvas.
14 Oct 2021
This is a Q &A session on BBB, you have gotten an invitation
already. Please bring your questions! Topics can be anything we
covered up to now, but I would like to focus on questions regarding
the most recent videos, so RSA and finite-field DLP.
I would appreciate getting some questions in advance on Zulip so
that I can prepare some extra material.
In the end there were no questions on Zulip, but during the live
session we covered Miller-Rabin vs. Fermat for primality test
and what you need to know about the Coppersmith method. I took
screenshots of what I typed; sorry for formatting and typos.
screenshot for Miller-Rabin vs. Fermat,
screenshot for Coppersmith method.
19 Oct 2021
Please watch the new videos on DLs in finite fields
(up to III), ECC XII, and Pairings I before this session.
We will meet in our wonder.me room, see Canvas or Zulip for the URL.
The exercise sheet for the live session
is here.
The sixth homework is due on
26 Oct at 13:15 via Canvas.
21 Oct 2021
This is a Q &A session on BBB, you have gotten an invitation
already. Please bring your questions! We have reached the end of
the course with ECC I-XIII, DLP I-VIII, hash I-V, symmetric crypto I-VII,
RSA I-IX, DLs in FF I-III, Pairings I-III, and single lectures on
Paillier encryption and post-quantum cryptography.
Topics can be anything we
covered up to now, but I would like to focus on questions regarding
the most recent videos, so everything after RSA.
I would appreciate getting some questions in advance on Zulip so
that I can prepare some extra material.
During the first hour I covered an example for index calculus. The
slides are
here. I'm considering recording a video
with them but haven't gotten the time, yet.
In the second hour we discussed elliptic-curve questions.
I took
screenshots of what I typed; sorry for formatting and typos.
screenshot for a warning regarding invalid-point attacks,
see also safecurves.cr.yp.to,
and
screenshot regarding the point at infinity.
I also showed some drawing and a graphic to visualize the point at infinity.
This file is an updated version of the graphic adding
more perspective. You can see the affine curve in projective space as the
intersection with the plane where z equals 1. A projective point is a line
through the origin. In the pictures you can see that far out in the y
direction the slope of the line has less and less increase in the z
direction, asymptotically reaching z being 0, which corresponds to (0:1:0).
26 Oct 2021
We will meet in our wonder.me room, see Canvas or Zulip for the URL.
The exercise sheet for the live session
is the first exam from last year.
Please take a look at the sheet before the session so that you
can focus your time on questions you find difficult or unclear. The
exam is meant for 3 hours and the exercise session is only 1.5h.
28 Oct 2021
This is a Q &A session on BBB, you have gotten an invitation
already. Please bring your questions! We have reached the end of
the course with ECC I-XIII, DLP I-VIII, hash I-V, symmetric crypto I-VII,
RSA I-IX, DLs in FF I-III, Pairings I-III, and single lectures on
Paillier encryption and post-quantum cryptography.
Of course you can also ask about the old exams.
Again, I appreciate receiving questions in advance.
In the end the questions covered the Pohlig-Hellman attack and
Coppersmith attack.
I took
screenshots of what I typed; sorry for formatting and typos.
Old exams by me:
