## 2MMC10 Cryptology - Fall 2021

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

• This page belongs to course 2MMC10 - Cryptology. This course is offered at TU/e and aimed at students of mathematics and computer science.

Contents

• The general structure of block ciphers, Feistel ciphers like DES, AES, the most suitable modes-of-use, e.g. CBC or OFB.
• Hash functions, Message Authentication Codes.
• The principle of public key cryptography.
• Basics of finite fields and their arithmetic
• Diffie-Hellman key exchange, El Gamal, several methods to compute discrete logarithms (baby-step giant-step method, the Pohlig-Hellman method, Pollard-rho and the index calculus method).
• Elliptic curves in different representations, cryptosystems and signature schemes based on elliptic cures.
• The RSA system for encryption and signing, generating prime numbers by means of probabilistic primality tests, primality proof, several factorization algorithms (Pollard-(p-1), Pollard-rho, the random square method, the quadratic sieve method) lattice methods for breaking special keys.
• Code-based cryptography.

#### Announcements

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.

• Lectures at TU/e start in the week of September 06, 2021.
• This course will be held completely online. The lecture slots are Tuesdays 13:30 - 15:15 and Thursdays 10:45 - 12:30.
We will use the inverted-classroom approach this year. I will present the topics in short videos which you will find here and in a dedicated YouTube channel. You are supposed to watch these videos before the lecture slots and come prepared. During the Tuesday slots I and 3 PhD students will interact with you on the material; you should by all means attend those classes. We'll use https://wonder.me for those sessions. The correct link was announced on Canvas on 7 Sep. The Thursday slot is reserved for questions and answers. These sessions will be held using Canvas conference. Please prepare questions for those sessions.
• The Zulip server for the course is up and running. Please follow the invite link you received via Canvas. IMHO Zulip is noticeably better than Slack, Discord, and Mattermost and much, much better than Canvas. You can also ask questions there and I'll post my announcements there, so make sure to keep a tab open with it.
• There will be weekly homeworks as an opportunity for you to check your understanding and how to formally write up things. The teaching assistants will send you corrections but the homeworks do not count towards the final grade.
• Your teaching assistants this year are
• Anina Gruica
• Mike Kudinov
• Florian Weber
• Some students prefer long-form videos from actual course teachings as those allow for more time for repetitions and different ways of explaining topics. There are some differences in contents compared to previous years, but most parts are covered in the old recordings.
You can find recordings from 2019 and earlier years of the lectures at http://videocollege.tue.nl. Note that this page shows lectures from multiple years and that there are some differences between the course versions; I taught the course in 2019 and my colleague Andreas Hülsing taught in 2018, so you can get different explanations. The course page for 2019 has pictures of the blackboards and short summaries of what was covered in the lectures, so the best way to find a video for a particular topic is to go there, find the topic and then find which date it was covered.
• The exam will take place online on 2 Nov 2021 13:30 - 16:30. The best preparation for the exam is to try yourself at the old exams

#### Literature

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):

• Jean-Philippe Aumasson "Serious Cryptography", no starch press,
• Dan Boneh and Victor Shoup A Graduate Course in Applied Cryptography. Whole book is online.
• Steven Galbraith Mathematics of Public Key Cryptography, Cambridge University Press 2012. All chapters are online (even extended versions).
• Jonathan Katz and Yehuda Lindell "Introduction to Modern Cryptography", CRC Press
• Neal Koblitz "A course in Number Theory and Cryptography", Springer, 1994.
• Tanja Lange "Number Theory and Algebra" ( Chapter of draft book "Discrete Mathematics")
• Tanja Lange "Finite Fields" (Chapter of draft book "Discrete Mathematics")
• Christof Paar and Jan Pelzl "Understanding Cryptography", Springer, 2010
• Bruce Schneier "Applied Cryptography", John Wiley & Sons, 1994. This book does not have the mathematical rigor we use for this course but you might like it for background. It is getting a bit outdated, though.
• Doug Stinson "Cryptography: Theory and Practice", CRC Press, 1995
You can also find a lot of information (though not written as a textbook) in the Handbook of Applied Cryptography. Note that the authors were so nice to offer chapters of HAC online for download.

#### Examination

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.

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. The format will b the same as for the first exam.

#### Videos

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.

#### Introduction

This video sets the context for the course and introduces the concepts of public-key cryptography and symmetric-key cryptography.

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

#### Elliptic-curve cryptography

This video explains the Diffie-Hellman key exchange and shows one example of a group in which to use it, namely the clock.

This video covers clock arithmetic over finite fields and shows the double-and-add method. It also has some important warnings.

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.

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.

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.

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.

This video covers improvements of the double-and-add method using windows to save point additions and information on timing attacks.

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.

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.

This video states the properties we want to achieve with signatures as well as the security notions and powers the attacker may be given.

This video presents the Schnorr identification system, Schnorr signatures, EdDSA and ECDSA.

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.

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.

• For many more (and computer verified!) formulas see the EFD.

• See RFC 7748 for more details on Curve25519 and Curve 448 and how to implement them correctly and efficiently.
• For an overview of suggested curves and their security properties see http://safecurves.cr.yp.to/, where we check security properties of curves against mathematical and implementation-based attacks.
• I mentioned that the designer of a system can choose the parameters, 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 somebody has to sneak in a backdoored curve (not that we know of any way of backdooring curves). Our results are online. Have fun!

• For Weierstrass curves I motivated the addition law in a geometric way, for Edwards curves by analogy with the clock group. We wrote a paper about geometric addition laws for Edwards curves and one of my co-authors recorded a video about it together with his kids which you can find here.

#### Discrete logarithm problem

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.

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.

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.

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.

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.

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.

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.

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 ECC XII for attack optimizations for elliptic curves and the DL in finite field lectures below for improvements specific to ECC and finite fields.

• 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!

#### Hash functions

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.

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

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.

This video covers reductions between hardness assumptions, both as a general concept and applied to the properties of hash functions.

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.

• Andreas Hülsing gave a lecture on hash functions in this course in 2019. He also covered the Merkle-Damgaard construction and Davis-Meyer mode. His slides are available online: His presentation also covers hash-based signatures, a topic in post-quantum cryptography; see below for more.

#### Symmetric cryptography

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.

In this video 4 variations on TEA are shown and broken. Each of these illustrates a technique used in symmetric-key cryptanalysis.

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.

• I cover stream ciphers RC4 and LFSRs to build stream ciphers in detail in the bachelor Introduction to Cryptology'' (2WF80) course. See the course homepage for videos and slides.
• A full specification of Poly-1305 is given in RFC 7539
• In spring 2021 Marc Stevens recorded a series of lectures on symmetric-key cryptanalysis for the MasterMath course Selected Areas in Cryptology'''. Visit his course page to learn more.
• Eran Lambooij wrote his master thesis on the cryptanalysis of Simon, a cipher designed by the NSA. The first few chapters give a nice introduction to symmetric-key cryptanalysis with a different cipher than TEA. You can find the thesis online

#### RSA, primes, and factorization

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.

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.

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.

This video gives and overview of factorization methods and explains Pollard's rho method for factorization.

This video explains the p-1 method and its generalizations to the p+1 method and the elliptic-curve-method of factorization (ECM).

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.

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.

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.

This video is easy listening for some disaster stories about RSA with bad randomness.

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.

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.

• For details on the PGP key format see RFC 4880.
• Last year I wrote this slide set on fast exponentiation methods, including sliding windows.
• I gave a long summer school talk in integer factorization. Some of the slides went into lectures 7 and 8. You can find the full slide set here
This talk also covers Coppersmith's attack and gives a newer example in the ROCA attack (see page 72 onwards). I was not part of the ROCA attack but we wrote a longer blog post on it here.
• In 2012 together with Daniel J. Bernstein and Nadia Heninger I gave a talk at 29C3 on factorization. You can find the slides here and a video here. We also posted a lot of code snippets in Python (2.0) at http://facthacks.cr.yp.to/
• If you want to learn more about Coppersmith's method 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.
• If you want to play with ECM you can find a demo script here. The script just runs through 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-coordinates. You can also vary the curves or the s to see the effects.

#### DL systems over finite fields

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.

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.

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.

This video presents a small example for the schoolbook version of index calculus.

• Florian Weber wrote some background information on proofs by reduction to give more details and an example from the Diffie-Hellman world. The 2020 version does not require any changes.
• For previous years I've written notes for the Pohlig-Hellman attack for finite fields, see here.
This is no different from what we have covered for the ECDLP, but written for a multiplicative group.
• The slide already mention the logjam attack https://weakdh.org/ which makes use of precomputation to attack individual DLPs very quickly. Check out their page for details.
The logjam paper also shows details for efficiently using index calculus attack. Nadia Heninger gave a talk about their attack at ECC 2015 and you can take a look at the slides.

This video introduces pairings and shows how they can be used to attack ECC (in cases where efficient pairings can be computed).

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.

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).

This video covers Paillier's cryptosystem, an additively homomorphic system. The video shows how the homomorphism works and that decryption correctly recovers the message.

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.

• There is a lot more to say about pairings – how they are computed, how to construct pairing-friendly curves, what else they are good for, and the current state-of-the art in attacking the DLP in the target group. However, for this course it suffices that you know that such maps exist and that there is an easy test to see whether they are efficient, namely by computing the embedding degree, which just needs the number of points on the curve.
• If you want to get more insight into the details of pairing, Pairings for cryptographers by Galbraith and Vercauteren is a good start.
• Stay on for 2DMI10 - Applied cryptography by Andreas Hülsing to see these systems used in practice.
• Stay on for 2DMI00 - Cryptographic protocols by Berry Schoemakers to see more advanced systems than Paillier's.
• Stay on for Selected Areas in Cryptology (MasterMath course in Sprin 2022) to learn a lot more about post-quantum cryptography. Last year I taught that course as an online course and so you can already watch the videos for it at the course page or the matching YouTube channel. The course has a second half which is on symmetric-key crypto; that part will change from the 2021 round to the 2022 edition and be taught by Bart Mennink this time.

#### Class notes & exercises

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

• Note that a break need not find the private key.
• Why? Because perfect code.
• Break? Try to get the intermediate step.

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.
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.

#### What's next?

Here are a few courses that you might find interesting:
• To find out how crypto is used in practice take 2DMI10 - Applied Cryptography taught by Andreas Hülsing in Q2.
• 2DMI00 - Cryptographic protocols by Berry Schoenmakers covers more advanced crypto, building on the primitives RSA, DL and symmetric crypto that we covered in this course.
• If you want to learn more about post-quantum cryptography, make sure to take the MasterMath course Selected Areas in Cryptology The other part of that course covers symmetric cryptography. The course is given by Bart Mennink and me. in Spring 2022.
• Coding Theory in Spring.
• If you want to understand how quantum computers break RSA and ECC and what else they can do, attend MasterMath course Quantum Computing by Ronald de Wolf.
• Finally, to defend against quantum computers, we're working on Post-Quantum Cryptography.

#### Old exams

Old exams by me:

• Exam from 02 Nov 2021 here
This was another online exam under the same conditions as below.
• Exam from Jan 19, 2021 here.
This was another online exam under the same conditions as below.
• Exam from Oct 27, 2020 here.
This was an open-book open-Internet exam so the last exercise doesn't give as many details as normally. The inspiration this time was The Long and Winding Path to Secure Implementation of GlobalPlatform SCP10, though that system was worse than what I made out of it (apart from having a longer key).
• Exam from Jan 21, 2020 here.
• Exam from Oct 29, 2019 here.
• Exam from Jan 23, 2018 here.
• Exam from Oct 31, 2017, here.
• Exam from Jan 24, 2017, here.
• Exam from Dec 14, 2016, here. Note that the g in exercise 3b is the same as in exercise 2, i.e. g=3. The curve equation in exercise 6b is y^2=x^3-3x+5.
• Exam from Nov 01, 2016, here.
• Exam from Jan 19 2016, here.
• Exam from Oct 27 2015, here.
• Exam from Apr 14 2015, here.
• Exam from Jan 27 2015, here.
• Exam from Apr 15 2013, here.
• Exam from Jan 28 2014, here.
• Exam from Apr 13 2012, here.
• Exam from Jan 27 2012, here.
• Exam from Apr 28 2011, here.
• Exam from Jan 28 2011, here.
Note that in exercise 5 the definition of PA should be [a]P.
• Exam from Jan 21 2011: here.
• Practice exam 2010/2011: here.
• Exam from Apr 15 2010, here.
• Exam from Jan 29 2010: here.
• Practice exam 2009/2010: here.
Andreas Hülsing gave the course in 2018. His exams are available online
• Second exam for students from Eindhoven and the TRU/e security master and first for MasterMath, Jan 25, 2019, here
• First exam for students from Eindhoven and the TRU/e security master Oct 30, 2018, here.
Henk van Tilborg has agreed that I put up his old exams for you to practice: