2MMC10 Cryptology - Fall 2023

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.103
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven

Phone: +31 (0) 40 247 4764

The easiest ways to reach me wherever I am:



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

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.


The exam took place 31 Oct 13:30 - 16:30. The retake will take place 23 Jan 18:00 - 21:00 in Neurn 0.266.

The resit for 2MMC10 is planned for 23 Jan 2024 18:00 – 21:00.


The videos from this course appear on this page of videocollege,tue.nl. You can find older editions of this course here. Note that this page shows lectures from multiple years and that there are some differences between the course versions; I taught the course with recordings in 2022 and 2019 and my colleague Andreas Hülsing taught in 2018, so you can get different explanations.
For the 2021 edition of the course I recorded a lot of short videos which you can find on the YouTube Channel.
course page for 2021 has short descriptions of all videos, slides, and no-cookie links to the YouTube videos. Watch them from there 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.

Class notes & exercises

This section is extended through the course with notes of what happened in class and links to blackboard pictures.

05 Sep 2023
General introduction to cryptography; concepts public key, symmetric key cryptography, and hash functions. We covered Diffie-Hellman key exchange and related problems (computational Diffie-Hellman problem, decisional Diffie-Hellman problem, and discrete logarithm problem) abstractly,.
Then we covered the clock group over the reals (or rational numbers) as a bad example where the attacker can easily solve the discrete logarithm problem, but this study also gave us the addition formulas for the clock group which we then used to consider the clock group over the integers modulo a prime. We showed that the addition law has (0,1) as neutral elemment, -(x,y) = (-x,y) and that the law is associative. In the instruction you'll show that the resulting poinn is on the clock. We skipped associativity as it is not particularly illuminating. For computing aP we use the double-and-add method. If this does not ring a bell with you, watch ECC II from the YouTube Channel
Clocks modulo primes are an example of cryptosystems against which the best attacks have subexponential (but superpolynomial) complexity; we will get to this attack much later. If possible, we would like to have systems where the best attacks are exponential.
Finally we saw Edwards curves and the addition law and how much it resembles addition on the clock.
As promised, here is a link to a blog post describing a unified way of addition on circles and Edwards curves by Thomas Hales. I prefer the simple and intuitive addition law on the circle which we've seen to be a special case of the Edwards addition law for d = 0. He goes the other way around – starting with a geometric interpretation of the addition law that I worked out with Arene, Naehrig, and Ritzenthaler, and then showiing that that can also be used for the circle. But tastes differ, so you might like his presentation better.
For our paper, Michael Naehrig recorded a video about it together with his kids which you can find here.

Pictures of blackboards are here. Please note the fixed typo for: The parameter d is not 0 or 1.

Here is the sheet for the instruction session (block 7 & 8).

Submitting homework is optional. If you want feedback, please submit by next Tue (12 Sep) before 13:30 through Canvas. Please submit in groups of 2-3 people; we do not have capacity to grade everybody individually.
To explain the 'optional': I do expect that you lookat the exercises (homwork and instructions, in particular if they cover pieces we leave out in the lectures. In general it's a good idea to engage with the material.
Here is the first homework sheet.

07 Sep 2023
Recap of Edwards curves; proof that denominators are never 0 over the reals if d is negative. For the proof that there are no exceptions over F_p for p>2 and d a non-square please watch ECC III from the YouTube Channel.
We showed that the points on Edwards curves form a group under this addition with neutral element (0,1) (see homework) and -(x,y)=(-x,y). The group is commutative.
We looked at what happens if 0 < d < 1 and d > 1 and that the pictures show that there are points at infinity. So typically the addition law has exceptions and is thus not complete.
Twisted Edwards curves are a generalization of Edwards curves but the number of points over any finite field remains divisible by 4. This will be shown once we cover Montgomery curves.
Finally we covered short Weierstrass curuves over fields with p>3 (or the reals), what the imaage looks like, what singularities (cusp and node) look like, and how additions are defined on Weierstrass curves usinng the chord-and-tangent method.
Pictures of blackboards are here. There is a mistake on the pictures: the condition is 4a_4^3 + 27a_6^2 != 0 (I accidentally wrote 16 instead of 4).

12 Sep 2023
This lecture was given by Andreas Hülsing and covered hash functions and proofs by reduction.

Here are the slides for his presentation

Further reading on hash functions

Please see my version from 2022 or the short videos from 2021 for a more algorithmic focus.

Here is the sheet for the instruction session (block 7 & 8).

The next homework is due on 19 September at 13:30 via Canvas. Here is the homework sheet.

14 Sep 2023
Because of questions I covered briefly what a keyed permutation is giving the example of simply xoring/adding modudlo 2 a key of the same length. The details do not matter for the reduction proofs and we'll see some more interesting keyed permutations when we get to block ciphers, but for having an intuition for what these are this is enough.

Recap of Weierstrass curve addition. We developed the addition formulas incl. proving that there is exactly one 3rd. point on the curve for a line of the form v= λ u + μ and then showed that there are 5 cases to consider for the inputs for addition. The Weierstrass form is the most general curve equation for elliptic curves but also the most annoying to implement – missing one of the special cases can cause wrong resutls and in crypto that's often enough for an attacker to get in.
I stated the long Weierstrass form and the Jacobi criterion which can be used to show that a curve is non-ingular. Isomprphisms between curves are bijective maps that are compatible with the group operations. For elliptic curves these are polynomials in x and y. If the characteristic of the field is not 2 or 3 then any elliptic curve in long Weierstrass form is isomorphic to one in short Weierstrass form. A relaxation of isomorphisms are birational equivalences which satisfy the same but permit a finite number of exceptions; as the name suggests, these are given by fractions of polynomials.
Montgomery curves are another special curve shape; we covered the curve is nonsingular if A is not 2 or -2 where we used the Jacobi criterion. Finally, we covered the addition law on Montgomery curves and I said (without proof) that these are birationally equivalent to Edwards curves.
Pictures of blackboards are here.

19 Sep 2023
Well. This didn't quite go as planned, to put it mildly.
We showed that over a finite field there are 3 points of order 2 or points of order 4 (meaning that the group order is always divisible by 4). This boils down again to using that in a finite field g^2 is a square while g^(2i+1) is not, where g is a generator of the multiplicative group or the finite field. The part of showing that the claimed poitns of order 4 actually have order 4 is part of the exercises (see below).
We then showed that Montgomery curves and twisted Edwards curves are birationally equivalent by giving the explicit map and also checking for exceptional cases.
Inversions are computationally expensive, so for efficient implementations we like to work with fractions and clear denominators only at the end of the computation. Geometrically, this means working with projective coordinates (the normal coordinates that we've looked at are called affine coordinates) and instead of using just two coordinates (x,y) we work with three (X:Y:Z) with the understanding that x=X/Z and y=Y/Z; this requires Z nonzero and means that we do not have a unique representation (the : in (X:Y:Z) are used by convention to indicate the redundancy of the representation; note (X:Y:Z)=(cX:cY:cZ) for nonzero c). I showed how the Edwards curve addition law looks using projective coordiantes. Projective coordinates also help understand the points at infinity. these appear when Z=0 while at least one of X or Y is nonzero. For Edwards curves it's nicer to study points at infinity with having seperate denominators for x and y, so that (x,y) turns into ((X:Z), (Y:T)) and we found two points at infinity in the x direction: ((1:0),(± √(a/d) : 1)) if a'd is a square; this matches the picture I drew for twisted Edwards curves when both a and d a non-squares and the curve stretches far out in the x and -x direction.
For more addition formulas in projective coordinates and the operation count in multiplications etc. see https://hyperelliptic.org/EFD/.
Finally, we very briefly covered the baby-step giant-step (BSGS) algoirthm, just enough to see what it does but without any explanation. Those will come on Thu.
Pictures of blackboards are here.

Here is the sheet for the instruction session (block 7 & 8).
Given the mess that today's lecture was you only know how to solve exercises 1, 3, and 5. In 2021 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
I showed the algorithm for 5 but not why it works nor did I show an example. I wanted to show you a Sage session, so here are the pieces I had prepared:
E=EllipticCurve(GF(41),[1,5]) generates an elliptic curve. Typing E in an intereactive session or print(E) otherwise outputs
Elliptic Curve defined by y^2 = x^3 + x + 5 over Finite Field of size 41
E.cardinality() tells us how many points there are on E, which is 47 in this case. To avoid knowing what the solution is I'll generate basepoint and target randomly
P=E.random_point() for me resulted in P=(38 : 4 : 1), note the projective coordinates we covered today. We also need a target discrete log problem, so
PA=E.random_point() which gave me (28 : 3 : 1).
If you want to reporoduce exactly this example, you will use
PA=E((28,3)) to create the point PA on E. If you need the point at infinity it's Q=E(0) which Sage then outputs as (0:1:0) (this is the same on Montgomery and Weierstrass).
After this setup phase everything is nice, you can just compute 2*P or PA + 5*P and Sage does all the work for you. Sage is based on python, so you an build loops and if statement and for the BS you can make a set.
This would have been better live and in person but I hope it gets you ahead a bit.

21 Sep 2023
In the DLP we want to find a with P_A = aP and a should be less than the number of points n. The number of points on the curve over F_p is in [p+1-2√ p, p+1+ 2 &radc; p]. To compute a we covered attacks on the discrete logarithm problem, starting from the naive search through all multiples of P to randomizing the target, turning one target into many, and more, how many targets are useful at most, and how to systematize this. This led us to the Baby-Step-Giant-Step (BSGS) attack, which computes a = i - jm mod N for m=√ N and 0≤ i,j ≤ m. Hence, the DLP in a group is no harder than the square root of the group order. BSGS has storage costs of m which might beprohibitive and thus choosing less optimal ratio of BS and GS might be better.
We covered the double-and-add method and its speedup in the windowing method. An attacker might be able to obtain side channel information, such as timing (at different levels of precision), electomagnetic radiation, or power consumption and from this infer information on the secret scalar that was being used. I showed the timing distribution from some TPMs (Trusted Platform modules) from TPM-Fail where you can clearly see the influence of length of a and Hanning weight of a. In several cases this leakes 12 bits; for Diffie-Hellman that's not a big problem, but for the signature system that they were attacking it was -- and you don't know where your scalar multiplication will be used. In terms of defenses, we covered the double-and-always add menthod and the Montgomery ladder; the latter is interesting for efficient implementations as it ensures that each addition is an addition of points with known, fixed difference P. On Montgomery curves, such differential additions can be efficiently commputed using only the u-coordinates of the points and their difference. I showed the projective version of this computation. All of this is covered in these slides, I also scribbled a small example of computing 5P on the board.
If you want to see a lot more on side-channel attacks and countermeasures, check out the CHES conference series. Talks are available on YouTube on the "The IACR" channel.

Finally I showed some pictures explaining colisions of random walks on a finite set and that the resulting graph looks like the Greek letter ρ. The reason we see collisions after about √n steps is the birthday paradox. The tim to collision splits about evenly over the tail and the cycle part.
Pictures of blackboards are here.

26 Sep 2023
Birthday paradox and how we can use this to develop a probabilistic algorithm that also runs in time √n but does not require storage. Pollard's rho method with Floyd's cycle-finding method runs in O(√n) and only uses two points. The method does a fast (two basic steps by fast step) and a slow walk and only compares the current points, not past points. The step function can just be some hash of the coordinates of W which produces b and c. Getting the DL a from the collision is just computing a=(bj-bi)/(ci-cj) modulo n.
We covered the schoolbook method of Pollard rhow and general additive walks as a cheaper alternative to doing two scalar multiplications. I stated that doing a pseudo-randoom walk with 2^k different precomputed R_i makes these walks less random leading to a slowdown factor of 1/\radic(1-1/2^k), so we need to choose k large enough.
I didn't say this but you will notice in solving the exercises that for these walks, as well as for BSGS, we work with unique representatives of points, so we need to use affine coordinates rather than projective ones, and there Weierstrass curves are faster. We can use the birational equivalence to move our attack targets to Weierstrass form in case it is given on a twisted Edwards curve.
Finally we looked at van Oorschot and Wiener's parallel collision search to use M computers efficiently to solve the DLP M times faster. The attack designer can choose the frequency of distinguished points to control the lengths of the walks, storage (and communicaion) costs, The same approach is also taken in finding collisions in hash functions using many computers. There it is important to find the first collision, for DLPs any collision is good as long as c_i is not c_j mod n.

To solve the DDHP (P,aP,bP,cP) we can see whether we have any tests failing for a*b = c mod n. If n is even, we can easily test whether the parity of c matches that of a*b by computing the parity of a (and if necessary of b). We get the parity by computing (n/2)(aP) which is 0P if a is even and (n/2)P is a is odd. We can do similar test for any divisor of n.
Pictures of blackboards are here.

Here is the sheet for the instruction session (block 7 & 8).
Homework is optional. If you want feedback, please submit by next Tue (03 Oct) before 13:30 through Canvas. Please submit in groups of 2-3 people; we do not have capacity to grade everybody individually. Here is the homework sheet.

28 Sep 2023
The Pohlig-Hellmann attack turns the informartion of a modulo divisors of n into a DLP attack on aP which recovers a if the prime factors of n are small enough. Important For N = Π pi ei the attack solves ei DLPs in a group of size pi, not one DLP inn a group of size pi ei. I showed slides to give a numerical example and to highlight the different costs of what you might try to do in sort of following this attack idea. These costs state the costs of the DLPs; the scalar multiplications don't matter asymptotically, and the CRT computation is very fast. The slides also contain a systematic statement of how to run the Pohlig-Hellman attack which you should look at and understand.
If you don't remember how the CRT computation works, take a looks at this YouTube video I made for 2WF80 and the corresponding slides.
The lesson of the Pohlig-Hellman attack is that the DLP is no harder than the DLP in the largest prime-order subgroup, so we try to choose points P with prime order l; there might be some cofactor c so that the curve has c*P points.
As a step towards signature schemes we covered Schnorr's identificaion scheme. We showed that a valid transcipt passes verification. Think about whether an attacker can learn a from seeing many transcrips. Pictures of blackboards are here.

Further reading on DLP:

03 Oct 2023
We covered properties of signatures: authenticity, integrity, and non-repudiation, meaning that the message really came from the sender, was not modified, and the sender cannot claim not to have sent it. A signature scheme is part of public-key cryptography; the public key is used to verify a signature while the private key is used to sign. Note that the message is known to the sender and the verifier.
As a step towards signature schemes we covered Schnorr's identificaion scheme which is a zero-knowledge proof of knowledge of the discrete log of PA. We showed why this is zero knowlege and why it proves that A knows a with Pa =aP. The latter part also showed that if one signs two messages with the same randomness R thn an attacer can compute the private key, see also the second homework.
In Schnorr signatures the random challenge picked by the verifier is replaced by the output of a hash function which is computed over the message and the commitment. I didn't have enough time to show EdDSA and ECDSA, these are shown at the end of ECC XI, please look at the slides (and video). I will briefly state one of them at the beginning of the next lecture for some additional comments on symmetries but expect that you have seen the systems. EdDSA is a direct instatiation of Schnorr signatures with some improvements and handling that the basepoint P has order N/8 (where N is the total number of points on the curve and N/8 is prime). ECDSA is slightly different in the order of how the operands are combined and is more annoying in the verification because we need to compute inverses modulo the order of P -- which is a good reason in addition to Pohlig-Hellman to choose groups of prime order. The Sony playstation disaster (see 27C3 talk PS3 Epic Fail) gives a real-world example where Sony failed to update the random r. As you will also see in the homework, this means you can compute a from just two signatures. To avoid this fragility, EdDSA picks r peudorandomly, by generating the private key as (a,b), with a the usual DL of the public key and b a seed for generating r = hash(b,m), so ensure that different messages lead to differnt r.

A scheme is considered broken if an attacker can produce a new valid signature (R',s') different from any (R,s) they have seen. Note, that m can be there same here. Schemes like ECDSA that only use the x-coordinate of a point and do not include R in the hash inputs are malleable, meaning that one can state a different signature for the same m by flipping signs. This is not considered an attack but is not really desired either.

As a second topic we covered schoolbook RSA, how KeyGen, Encrypt, and Decrypt work and why m'=m. I showed Fermat's primality test (more to come) and that one can speed up encryption by choosing small e which have only very few non-zero bits in the binary expansion such as e=65537. For decryption we cannot make special chioces of d as that's part of the secret key and we shoudln't restrict the number of choices there. The CRT method (named after the Chinese Remainder Theorem) gives a speed-up by a factor of 3 - 4 (depending on whether the modular arithemtic uses quadratic-time schoolbook multiplication of Karatsuba multiplication).
Pictures of blackboards are here.

Here is the sheet for the instruction session (block 7 & 8).
Homework is optional. If you want feedback, please submit by next Tue (10 Oct) before 13:30 through Canvas. Please submit in groups of 2-3 people; we do not have capacity to grade everybody individually. Here is the homework sheet.

05 Oct 2023
I showed trial division/sieving and gave some details of how to efficiently figure out what numbers factor completely into powers of small primes or have just one larger prime factor. Then we covered Pollard's rho method of factorization and that it takes time about √p to find p. Then we covered the p-1 method and its generalization, the Elliptic Curve Method (ECM) of factoriation. The question of how to find points on a curve modulo a composite integer led us to discussing that computing square-roots modulo p * q can be used for factoring. I showed Dixon's method (congruence of squares) for how to build a and b with a^2 and b^2 congruent to each other modulo n. This is the first method we see for factoring RSA numbers and the motivation for considering the factorization of the auxilary numbers before.
Pictures of blackboards are here.

10 Oct 2023
We covered rsa-6.pdf as an example for Dixon's method. I showed an idea for keeping the sizes of the auxiliary numbers small and how that still works with sievingl A big factorization attack using the Number Field Sieve factors the auxillary numbers by first doing sieving or trial division, then rho, then p-1 and ECM, keeping only those numbers that factor sufficiently well.
NFS runs in subexponential time, as Ln(1/3), we covered the L-notation as a way to express complexities between exponential and polynomial and how those are covered as L(1) and L(0).

Coppersmith's attack works when we know some parts of the prime, and I showed on the example of https://smartfacts.cr.yp.to that this can happen in practice. See rsa-9.pdf and rsa-10.pdf for the slides I showed.
In this lecture I showed Coppersmith's approach and how his method works; we first treated LLL as black box. Finally I explained what LLL does and what guarantees it gives on the shortness of the output vectors. Coppersmith's attack uses LLL to find a polynomial with bounded coefficients. A theorem of Howgrave-Graham gives a bound on how large the root may be so that the resulting polynomial has an integer root (instead of just a root modulo p or modulo n). I was a bit fast to go through why this means that you can factor n if you know the top 2/3 bits of p, so I turned this into a homework to trace through these steps. Using just a 2x2 matrix would not have worked. We covered how to set up the systems in general and did stereotyped messages as another example to see how to deal with polynomials of degree larger than 1. See rsa-11.pdf for the details of the example.

Here is the sheet for the instruction session (block 7 & 8).

Homework is optional. If you want feedback, please submit by next Thu (20 Oct ) before 10:30 through Canvas. Please submit in groups of 2-3 people; we do not have capacity to grade everybody individually. Here is the homework sheet.
Pictures of blackboards are here.

10 Oct 2023

I showed that going to x^2*f does not improve the number of bits of p that can be recovered. I then showed how to build a system modulo p^2, by taking n^2, n*f, f^2, X*f^2, X^2*f^2, X^3*f^2..... for d = 4 that didn't give more than the same n^(1/6) we already had but setting up

[X^4,2*a*X^3,a^2*X^2, 0, 0],
[ 0, X^3,2*a*X^2,a^2*X, 0],
[ 0, 0, X^2,2*a*X,a^2],
[ 0, 0, 0, X*n,a*n],
[ 0, 0, 0, 0,n^2]
helps. It has determinant n^3*X^10. The second condition for Howgrave-Graham is then that the 5th root of this is less than p^2 which is about n. This means that X is less than n^(1/5) (which is larger than n^(1/6)).
The next step would be to make a system modulo p^3, starting with n^3, n^2*f, n*f^2, f^3, including also X*f^3, X^2*f^3, X^3*f^3. This reaches X < p^(3/7) (which is larger than p^(2/5)). As you can see we're getting closer to p^(1/2) which is the asymptotic limit of this method.

Try setting up a matrix for stereotyped messages with e=5 and consider how many bits you can recover for e = 3 (as in the example) and for e = 5.

For RSA encryption we covered the attack scenarios OW (one wayness) and IND (indistinguishability) and the attacker powers KOA (key-only attack), CPA (chosen plaintext attack), and CCA (chosen ciphertext attack). For public-key encryption the attacker can always encrypt chosen plaitexts, so has at least CPA power.
RSA is not IND-CPA secure because encryption is deterministic. I didn't show, but you can check, that it is also not OW-CCA because we can ask for the decryption of c2^e to get 2m. I showed RSA-OAEP from the last slide of rsa-1.pdf and explained how the fixed patterns stop the use of c2^e – but only to some extent. Using the hash functons does stop it completely.
We then covered ElGamal encryption, as a system that is IND-CPA secure but not IND-CCA-II secure, and security notions for signatures along with the RSA signature system.
Pictures of blackboards are here.

17 Oct 2023
I answered some questions regarding the exam, please see the pictures for details. The exam is scheduled to be held in person and your answers will be writen on paper.

I repeated the distinctio btween primality tests and primality proofs and then coverd the Miller–Rabin primality test and the Pocklington primality proof see rsa-3.pdf for the exact algorithm for Miller–Rabin (I covered the ideas on the board) and the numerical example for Pocklington.

In symmetric crypto A and B share a key k. They then use it to encrypt and authenticate their message. We will cover block ciphers and some modes in the next lecture. I only showed the general functionality of a block cipher and commented that the Electronic Codebook mode (ECB), which just encrypts each block independently, is a bad mode. The picture to have in mind is the ECB penguin which shows the issue with repeating plaintext blocks leading to the same ciphertext blocks.

A Message-Authentication Code (MAC) ensures authenticity and integrity of messages between two users sharing a key. The authentication tag should be such that an attacker has only negligible chance of forging a valid message. We apply the MAC to the ciphertext so that the decryption key gets used only on ciphertexts that are valid. Always use a MAC when encrypting, we want authenticated encryption. As an example we covered Wegman-Carter MACs, first as a small example and then Poly1305 which is deployed in practice; see the last slide of sym-7.pdf for full details of Poly1305.

Pictures of blackboards are here.

Here is the sheet for the instruction session (block 7 & 8).

19 Oct 2023
Today we covered block ciphers and modes; you should watch Tomer Ashur's awesome videos symmetric crypto, stream ciphers, block ciphers, and modes of operation. for some general introduction.
We covered Galois Counter mode, where Ci = Mi + Enc(IV,i), for some randomly chosen initialization vector IV and counter i in binary representation. The ciphertext needs to include C0 = IV so that the receiving party can decrypt. Decryption is easy: Mi = Ci + Enc(IV,i). The n-bit block input to Enc gets split between IV and the counter. The counter limits how many blocks can be sent with the same IV. To encrypt longer messages, pick another IV, this costs < n bits. If the IV repeated then two messages would be encrypted by adding the same strings, which would be a security problem, so IV needs to be long enough to make this unlikely. (Note that the birthday paradox applies for randomly chosen IVs, so if n=128 gets split into 96 bits for the IV and 32 bits for the counter then a new key needs to be chosen after about 2^48 encryptions (2^(96/2)). After that many messages a new key needs to be used (generated by using Diffie-Hellman or as k' = h(k) for some hash function h)).
AES-GCM then takes the output ciphertext blocks, additional data to be authenticated, and s=Enc(IV,0) and computes a Wegman-Carter MAC in F_{2^{128}}. I didn't write out how H is computed and also simplified things a bit. The full description handles shorter IVs and some parallelism in the computation. See NIST's SP800-38D for the official standard and Dan Bernstein's dummy submission for the Caesar competition which used AES-GCM as an example of what a submission should look like.

As an example of block ciphers we studied the Tiny Encryption Algorithm (TEA) and also how small variations can lead to catastrophic attacks. I should have emphasized at the beginning what properties we're out to get -- getting the key is of course nice, but ciphers are already discarded if they are distinugishable from a pseudo-random permutation (PRP), i.e. a bijective map from {0,1}^n to itself. Finding any special structure that always holds for a cipher but not necessarily for a PRP gives a distinguisher. The slides I used are here and here. These attacks give a taste of how symmetric-key cryptanalysis works, showing small examples of linear and differential attacks as well as the slide attack. For more on symmetric crypto, take the Mastermath Selected Areas in Cryptology course next spring.

Index calculus attacks have many similarities with the number-field sieve attack: again we replace one hard computation with many easier ones. Here we solve the DLPs for many small primes by setting up a system of linear equations (to get there we again need to factor). Note that these attacks require fixing a factor base for which it is easy to see whether a given element factors over it. We have this for finite fields (including extension fields) using factorization into integers (or irreducible polynomials) but not for elliptic curves over finite fields. That's why we can safely use elliptic curves over fields of size 256 bits while the DLP in finite-field needs to have 3072 bits to be equally hard. I explained the idea and how to proceed on the board and then showed ff-dl-4.pdf for a small example of index calculus attacks. For keysize recommendations.see e.g. the ECRYPT-CSA Algorithms, Key Size and Protocols Report. This report is from 2018 and an update from 2020 exists but is locked up with ENISA. If you just want the summary (which hasn't changed) see the first slide of ff-dl-3.pdf.

I also answered some questions about the exams but the board got erased before I could take some picture. Please remember that if you have a group of finite order n then the order of an element of that group is a divisor of n. This limits a lot what multiples you need to test for. Furthemore, if the question is about the order of a point on an Edwards curve you can save further time by recognizing points of order 1,2,4, and 8 and writing a short argument about what this means, e.g. if aP = (1,0) and you haven't seen another point of small order before getting to a then P has order 4a because aP has order 4. Using such arguments you can minimize how much computation you need to do. Also you should recognize that if 2(x,y) = (-x,y), i.e., the negative of the point, then (x,y) has order 3.

Pictures of blackboards are here.

24 Oct
The two main topics we covered are Pohlig–Hellman in the multiplicative group in a finite field and the p-1 method. Along the way I stressed the importance of the simple math statement that the order of an element is a divisor of the group order. We used that in PH and also to explain why the p-1 method worked. We also discussed one of the last exercises, namely the one about RSA signatures using CRT; note that that year I had not covered RSA signatures or the CRT method in class. One question I got was why I wrote m_p rather than m and the relevance is that we want to get the operands small, so you should first reduce m modulo p and only then compute the exponentiation.

Pictures of blackboards are here.

For the exercise session take a look at the exam from Jan 21, 2020 here.

26 Oct
I repeated that you'll find Pari-GP and a copy of the course page on the laptops.
We covered exercises 5 & 6 from the first exam in 2019 (file first.pdf) and the last exercise from the second exam in 2017 (file second.pdf) about RaCoSS.

Pictures of blackboards are here.

What's next?

Here are a few courses that you might find interesting:

Old exams

Old exams by me:

Andreas Hülsing gave the course in 2018. His exams are available online Henk van Tilborg has agreed that I put up his old exams for you to practice: