| Contents | Announcements | Exams | Literature | Videos | Course notes & exercise sheets | Follow-up courses | Old Exams |
Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room MF 6.104B
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands
Phone: +31 (0) 40 247 4764
The easiest ways to reach me wherever I am:
e-mail:tanja@hyperelliptic.org
Contents
Note that one of the course requirements is algebra. I will not repeat basic background on groups, rings and fields in class. If you don't have the necessary background, take the summer and work through the "Number Theory and Algebra" script.
It is not necessary to purchase a book to follow the course.
Previous versions of this course used
Henk van Tilborg's "Fundamentals of Cryptology", Kluwer academic
Publishers, Boston, 2000. But the book is out of print.
A preliminary author's copy by Henk can be downloaded in pdf form
here
and as a mathematica worksheet here.
Other books you might find useful (in alphabetical order):
The exam will take place online 1 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 some practice exam available for testing the interface. That exam is mostly for testing knowledge, just to see how Ans works. The study admin people were super fast and added you to the course in Ans Delft so 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, yet, of course. You will find the practice exam there to see how Ans Delft works. This practice exam will be available till 31 Oct 12:00. You can use the arrows in the bottom row to jump between exercises or click on the boxes in the middle to 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.
After the exam you will get access to the exercises and your answers
through Ans Delft. You then have 30 min to record a video of you. The
video should start with you presenting your student ID and saying your
name. Then you explain your solution to 3 exercise parts. You may
choose these parts yourself among the exercise parts that are not
numerical questions but those that required some text in the answer field.
An exercise part is any piece that has it's own answer field, so I don't
expect all parts of exercise 3 for example and you an pick parts of different
exercises to explain. Aim for 5 min, but up to 10 min
is OK. This videos will be used only to establish that you are the
person who wrote those exercises, it does not influence your grade.
Name the file as
ID_{student ID]_[Last name].[file format]
filling in your TU/e student ID, your last name, and the file format (mp4, webm)
instead of the brackets
and upload your file to
Surfdrive (file drop only, this implies that you cannot see your
own file after upload, but you can ask Tanja to check).
You should upload your video by 17:00 for regular time, 17:30 if you
got extra time.
If your connection is too slow, store the video on your computer and compute the SHA-256 checksum of it and mail that to Tanja Lange before the deadline
you can continue to upload your video after the deadline.
If you want to practice file upload, use the Surfdrive test site (file drop only, this implies that you cannot see your own file after upload, but you can ask Tanja to check).
If you want to opt out of recording a video, please contact me (Tanja) at the latest on 30 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 24 Jan 2023 18:00 – 21:00. The format will be the same as for the first exam. Note that I will add ChatGPT to the list of forbidden contacts. The link for uploading videos for the resit is hee.
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 in 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.
06 Sep 2022
This lecture was given by Florian Weber.
General introduction to cryptography; concepts public key,
symmetric key cryptography, and hash functions.
Spoiler alert! Don't follow the upcoming link if you sill
want to solve exercise 1 yourself.
As an example we attacked the
"Perfect Code Public Key System" by Fellows and Koblitz. Attention,
this was never proposed for cryptography but only as a teaching tool.
I don't have the slides from Florian, yet, here are the slides from last
year
pdf for the perfect code
system. Other hints:
08 Sep 2022
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. This is an example of a cryptosystem
against which the best attacks have subexponential (but superpolynomial) complexity; we
will get to this attack much later.
Finally we saw Edwards curves and the addition law and how much it resembles addition
on the clock.
If you're following this course with the short videos from last year you should watch
the first three videos on elliptic curves. It's not a 1-to-1 match (some missing, some
extra) but covers the core.
Homework is optional. If you want feedback, please submit by next Thu (15 Sep)
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 first homework sheet.
The pdf file has been updated to fix exerice 1 (1 missing on right side of the equation)
and 2 (the point of order 2 is (0,-1)).
Pictures of blackboards are here.
13 Sep 2022
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 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.
The number of points on the curve over F_p is in [p+1-2√ p, p+1+ 2 &rad; p].
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 Weierstrass curves and showed how isomorphisms let us take the long
Weierstrass form and (for characteristic not equal to 2 or 3) move to the short Weierstrass
form. I finished with showing pictures of the addition law but haven't written out the
formulas, yet.
If you're following this course with the short videos from last year you should watch
ECC IV and V. It's not a 1-to-1 match (some missing, some
extra) but covers the core.
Pictures of blackboards are here.
15 Sep 2022
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.
Montgomery curves are another special curve shape; we covered the addition law
(to the extent that it differs from the Weierstrass case); showed that over a
finite field that are 3 points of order 2 or points of order 4 (meaning that the
group order is always divisible by 4); and then showed that Montgomery curves
and twisted Edwards curves are birationally equivalent.
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
and then showed Curve25519 as a real-world example of what you use in Signal,
WhatsApp, and https for doing a key exchange. I used
slides to show these latter items.
Homework is optional. If you want feedback, please submit by next Thu (22 Sep)
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 2nd homework sheet.
Pictures of blackboards are here.
If you're following this course with the short videos from last year you should watch
ECC V, VI, and IX. It's not a 1-to-1 match (some missing, some
extra) but covers the core.
20 Sep 2022
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 42P 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.
For the second half 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 (a transposed version of) 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.
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - IX and DLP I - II.
22 Sep 2022
Complexity estimates for BSGS, big-O notation, worst-case and average-case cost
for BSGS for computation and storage.
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 pseudorandom function f can just be some hash of the coordinates
of W which produces b and c (we'll see a cheaper way next week). Getting the
DL a from the collision is just computing a=(bj-bi)/(ai-aj) modulo N.
Finally we looked at van Oorschot and Wiener's parallel collision search to
use T computers efficiently to solve the DLP T times faster. The attack designer
can choose the frequency of distinguished points to control the lengths of the
walks, storage (and communicaion) costs, For solving DLs we recompute the whole
walk up to the DP to get the coefficients; when we see this method again in
breaking hash functions it's important to find the first collision.
I used
slides to show what the resulting graphs look
like.
Homework is optional. If you want feedback, please submit by next Thu (29 Sep)
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.
If you're following this course with the short videos from last year: we have now
covered ECC I - IX and DLP I - V, apart for the additive walks.
You should now be able to solve the exercises from the presence exercise sheets
from 2021 up to and including exercise 5 on sheet 3. Solve those for checking
your progress.
27 Sep 2022
We covered additive walks as a cheaper alternative to doing one double-scalar multiplication
per step and analyzed the effect of anti-collisions which make these walks less random.
Given k different stepps (we looked at k= 10, 100, and 2^m) the effect is a slowdown
of Pollard rho by a factor of 1/\radic(1-1/k), so we need to choose k large enough.
For these walks 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.
See the lecture of 20 Sep regarding projective and affine coordinates.
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.
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 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.
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - IX and DLP I - VIII.
Further reading on DLP:
29 Sep 2022
This lecture was devoted to hash functions. We first did a round of informal
definitions of preimage resistance, second-preimage resistance, and collision
resistance and how long attacks should take against good hash functions. If you
have a bad hash functions, e.g. just take the integers mod 2^128 to get a 128-bit
output, these can be computed much faster.
Then we analyzed details of how to apply what we learned about Pollard's rho
method to compute collisions of hash functions without needing much memory.
Note that there was a typo on the last line of the blackboard in that the
comarision should take xi,k and compare it with xj,k+lj-li.
The i and j were missing. This has been fixed (in yellow)
on the picture of the board.
In the second hour we covered the same security notions in a formal way. We
needed to introduce keyed hash functions in order to be able to formalize
collision resistance. The slides recapped
the language of complexity theory and reductions between algorithms. We showed
that CR reduces to SPR while the relation between SPR and PRE is less clear and
depends on the ratio l(n)/n. I used slides for
hash III and
hash IV for this.
I briefly showed how sponge functions work, these are modern examples of hash
functions. They have the benefit that we only need to study the function f in
cryptanalysis and can reduce the properties of the hash function to properties
of f. To learn more about it check out the full slide set
hash V and the
corresponding video.
Homework is optional. If you want feedback, please submit by next Thu (06 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.
If you're following this course with the short videos from last year: we have now
covered ECC I - IX, DLP I - VIII, and hash I - V.
Further reading on hash functions
04 Oct 2022
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.
We covered how to use symmetries to gain a speedup in attacking ECC. These
symmetries will come back a few more times, so we spent some extra time on this.
In principle we gain a √2 speedup from identifying a point with its negative
when using the Pollard rho method. However, This requires attention to redefine the
walk and causes fruitless cycles of length 2 with probabllity 1/(2k) if the step
function has k different steps. We covered how to escape from cycles (pick a
unique representative of the points in the cycle and double that) to ensure that
we do not destroy collisions by taking different exits from the cycle. We covered
this part in more detail than in talk ECC XII on the videos, so students following
remotely should watch the first 30-40 min of today's lecture or at least study the
blackboard picktures.
We then 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. 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.
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - XII, DLP I - VIII, and hash I - V.
06 Oct 2022
I failed to take photos; so here is a more detailed description of what we did.
We started with some comments on signature systems. 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.
In the homework you'll see that this enables an evil Alice to craft a private key
a that allows her to sign two chosen but fixed messages m1 and m2 with the same
signature, so that she could later claim that her signature on m1 was a signature
on m2. Note that doing this also reveals her private key. 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.
In symmetric crypto A and B share a key k. They then use it to encrypt their
message. Note that they will also need to ensure authenticity and integrity of
the message, we will cover that in the next lecture. 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.
We covered block ciphers; these are maps that take an l-bit key and an n-bit
plaintext and produce an n-bit ciphertext so that Dec(k,Enc(k,m)) = m. We want
a block cipher to be indistinguishable from a pseudo-random permutation(PRP). As
an example we studied the Tiny Encryption Algorithm (TEA) and also how small
variations can lead to catastrophic attacks. The slides 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 this, take the
Selected Areas in Cryptology course next spring.
I briefly 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. We covered Counter mode, where ci = m + Enc(IV,i), for some
randomly chosen initialization vector IV and counter i in binary representation.
The ciphertext needs to include 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).
Homework is optional. If you want feedback, please submit by next Thu (13 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.
If you're following this course with the short videos from last year: we have now
covered ECC I - XII, DLP I - VIII, hash I - V, symmetric I - VI.
As said above, I don't have pictures of the board but Iris
let me copy her handwritten notes.
Here are the photos of her
lecture notes. Another student, Xander Smeets, shared his
handwritten notes with me (in pdf format).
11 Oct 2022
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.
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. After seeing KeyGen, Enc, and Dec for RSA we observed that it is not
IND-CPA because it is deterministic and it is not OW-CCA because it is
homomorphic. I showed RSA-OAEP from the last slide of
rsa-1.pdf.
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - XII, DLP I - VIII, hash I - V, symmetric I - VII (the first 4
are on Tomer Ashur's channel), and RSA-I,.
13 Oct 2022
We covered RSA signatures, RSA-CRT incl. how it is used in GPG, primality tests
(Fermat, Miller--Rabin), the Pocklington primality proof (see the last slide
of rsa-3.pdf), and several
factorization methods. For the latter I showed how congruences of squares lead
to factorization, so that computing square roots modulo n is as hard as
factoring n (in the lead up to the Miller-Rabin test). Dixon's method
builds congruences of squares, each step requires the factorization of
an auxillary number, but those are easy to factor. See rsa-6.pdf for Dixon's method.
For these auxillary methods I mentioned trial division as a useful
subroutine; for larger factors you want to use Pollard's rho method for
factoring and the p-1 method (and generalizations to p+1 and ECM).
We covered p-1 and will do rho next week. I showed some numerical examples from
rsa-5.pdf for the p-1. Note that you need at
least one of the factors of n to divide the gcd and one not to divide it.
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.
If you're following this course with the short videos from last year: we have now
covered ECC I - XII, DLP I - VIII, hash I - V, symmetric I - VII (the first 4
are on Tomer Ashur's channel), and RSA I - III and V - VI.
18 Oct 2022
Pollard's rho method for factorization looks for collisions in a random walk
modulo p, so should find them after √p steps. gcd computations turn into
the bottleneck, so we combine them into one single gcd computation at the end
of the computation at the expense of one multiplication per step.
A big factorization attack using the Number Field Sieve factors the auxillary
numbers by first doing trial division, then rho, then p-1 and ECM, keeping only
those numbers that factor sufficiently well. Actually the NFS sieves for small
primes, rather than doing trial division.
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 we used Coppersmith's method and LLL as black boxes, then
explained what LLL does and how it works. In the next lecture we'll see when
and how Coppersmith's method works and how to use it on stereotyped messages;
another example of wrong use of RSA. We used the first 2 full pages of
rsa-11.pdf for this and will continue
there on Thursday.
Note that next week there are no lectures but I plan to use wonder.me for interactions. Please let me know if
you don't like that Interface, I can also switch to using big blue button
(Canvas conference).
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - XII, DLP I - VIII, hash I - V, symmetric I - VII (the first 4
are on Tomer Ashur's channel), and RSA I - VI and IX - XI, the latter only half.
I wrote that there would be a 7th HW but realized after the lecture that you would not get the corrections back in time. I had planned on doing a Coppersmith exercise. Instead I have changed the settings on Ans for the practice test so that you can get automatic feedback on the Coppersmith exercise there.
20 Oct 2022
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 resultig polynomial as it as an integer root (instead of just a root modulo
p or modulo n). This shows why the example on Tuesday recovered all of p from
knowing the top 2/3 of the bits of p. 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. See rsa-11.pdf
for the details of the example.
In the lecture I got stuck in showing that bigger matrices allow us to
reconstruct larger parts of p. Where I messed up was that I was keeping b^k=p
instead of going up there as well. So, the next I should have done was a system
modulo p^2, by taking n^2, n*f, f^2, X*f^2, X^2*f^2. This means that the matrix
would be
M=matrix([which has determinant n^3*X^10 approximately p^6*X^10. The second condition for Howgrave-Graham is then that the 5th root of this is less than p^2 which means that X is less than p^(2/5) (which is larger than p^(1/3)).
[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.
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.
See ff-dl-2.pdf and
ff-dl-4.pdf for index calculus attacks
(that's why the clock group is not good) and
ff-dl-3.pdf
for resulting keysize recommendations.
Pictures of blackboards are here.
If you're following this course with the short videos from last year: we have now
covered ECC I - XII, DLP I - VIII, hash I - V, symmetric I - VII (the first 4
are on Tomer Ashur's channel), RSA I - VI and IX - XI,
and finite field DLPs II-IV.
25 Oct
We got a lot of questions, and that's good. Some relevant ones are
Question: An exam used Pohlig-Hellman in F_p^* while we have done it only in E(F_p). Does
that mean this exercise is out of scope?
Answer: No. We have seen this method in one group, I expect that you can apply
it to another group.
Question: Where do the polynomials come from in the above notes (fix for
Coppersmith) from 20 Oct?
Answer: We need to go to higher powers of p to get a better bound in
Howgrave-Graham. For the higher power of p, e.g. p^i, we can use f^i in place
of f as the polynomial, but now that has degree i, so we need to fill up with
expressions that are also 0 mod p^i and contribute as little as possible to
det(M). Since X is smaller than n it's better to use increasing powers of f
along with decreasing powers of n rather than of n alone.
You could fill the diagonal with X^jn^i but that would lead to a larger
determinant (check this). This explains everything up to
M=matrix([for i=2, but this gives a very bad bound on X. So we continue as before and include X*f^2, which gives a better bound, then X^2*f^2, which gives an even better bound. Including also X^3*f^2 does not improve the bound further and going for higher powers of X alone actually makes it worse. That's what I ran into for the simple example I did in class (forgetting to go up to p^2, p^3, ....). It's probably good for you to check this yoursef to understand what I mean.
[X^2,2*a*X,a^2],
[ 0, X*n,a*n],
[ 0, 0,n^2]
])
Old exams by me:
