| 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
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 exam will take place 31 Oct 13:30 - 16:30. Location still TBD.
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.
The
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.
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
M=matrix([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)).
[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]
])
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.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.
Old exams by me:
