Lecture 17: Elliptic Curve Cryptography (ECC) by Christof Paar

For slides, a problem set and more on learning cryptography, visit www.crypto-textbook.com

[@eliatkinson7528]

Nails it again. There should be an entire series Prof Parr explains Math for unruly Germans

[@zedmed3191]

Thank you very much Christof Paar, you are the best Professor I have ever seen in my life! Yes, that's really what I think of you. For me you are very smart, so pedagogical, so clear, so humble (necessary for any teaching) and so funny too! I discovered this course in 2014 in Morocco when I started my studies on Cryptography at the University of Rabat, Morocco. I really enjoyed this course at that time, and I can't tell you how it helped me to understand these topics that seemed very complicated (unfortunately due to the lack of explanation by other professors). You made them very easy for me, like magic. Your method is really inspiring and I really appreciate it. And I know if I am now working in this field as a security analyst with a background in cryptography, it is somehow thanks to your wonderful courses! After seven years, I still enjoy these courses and now I decided to go back to this elliptic curve course because I am interested in CHESS-2021 this year about white box cryptography based on elliptic curves. Thanks again my best professor!

[@cherokeelol]

This lecture and lecture 16 are the best explanation for ECC I have found on the internet. Thank you so much for putting this online!

[@Coldwind12]

Generator point can be represented as an x integer and 1 bit for y. Y can be determined as one lying on a curve and this one y bit determines "upper" or "lower" part of solution. So we can "compress" point representation and operate only on x(int) + 1 y bit point representation AND save some memory space. And finally all points lying on a curve can be represented like this.

[@nikolagamesTV]

Great lecture, as always

[@alexxiong6401]

Dear Prof. Paar, Great Lecture, always enjoys your detailed and meta-knowledge explanation. I have one question on the "hardness of ECDLP", could you please persuade me why is it so difficult to compute the # of hops in a publicly known standard EC? I was thinking, if the cardinality of the NIST EC is known, then there may be a database recording every points/elements in the group,right? And then given the starting point and ending point, why isn't the problem as easy as item query in a database? Appreciate your time!

[@introductiontocryptography4223]

You are right; *if* there were such a database with all elements and the corresponding multiple WRT a base point, one could look every DLP up. The problem is that the required size of the data base. Today, ECC are mostly used with 256 bits or more, so that there are roughly 2^256 ECC points and, thus, data base elements. Since there are only about 2^170 atoms on planet Earth, it seems very very hard to build the data base or even a tiny fraction of it :) regards, christof

[@alexxiong6401]

Thank you so much Prof. Paar for your kind reply. It totally makes sense, now I understand. One follow-up question, how do we derive the exact number of elements without exhausitively computing every one of them?

[@alexxiong6401]

And one more question: according to conservative estimate on NSA database in Utah and Maryland, their storage capability is 4 zettabyte, which is equilvantly 4*10^18, or 10^18 in terms of magnitude. Now, if I estimate 2^256 = 10^78, so total storage needed = 2.56*10^80. Let's assume we use cache and probably dynamic programming, my crazy definitely not proven thought goes like this: NSA doesn't need to store all the elements, but they selectively store part of them, and for the rest, they either don't care, or store the repectively "distance"(if possible, not sure....my imaginary parameter) to its nearest stored element. Such scheme with an ASIC (application specific integrated circuit) which enables optimal modular computation speed. suddenly, it doesn't feel that secure to me.... which assumption i made was way too off?

[@introductiontocryptography4223]

This is called point counting and there are special efficient algorithms for it. It is quite involved mathematically, though. In practice, people mostly use standardized curves for which "some other people" did the point counting.

[@alexxiong6401]

Alright, Understood! Thanks a lot, you answer really helps! Respect.

[@karthikeyanS2291]

The board content is not visible clearly professor

[@funfest.]

As the discrete logarithm problem produce same results when no squared reaches the point when its square in modNo-1 so do this happens in ecc to

[@spicemasterii6775]

Hahaha. "Back to sleep" -> subscribed!

[@coshvjicujmlqef6047]

Put those sleepers to gulags

[@mojtabakomeili]

Why do they call this a discrete logarithm problem? It is multiplying P by d to get dP. It looks more of a discrete division in an elliptic group to me. I agree that it look a lot like the DLP we saw before. Is that the reason?

[@introductiontocryptography4223]

+Mojtaba Komeili Good point. Please also have a look at Lecture 14. Every time we build a one-way function from a cyclic group in this specific way (adding or multiplying a group element n times), it is called a discrete log. *IF* we would call the point addition P+Q on an ell. curve "multiplication" instead of "addition", the name "logarithm" would actually make more sense. However, more than 100 years ago mathematicians started to name the operation P+Q addition, and now we are stuck with it :) regards, christof

[@dharmalingamganesan5232]

Very nice lecture. One comment at ~ 1:06:43. The proof uses P = (XB, YB). Think P = (x, y) must be the same for both Alice and Bob. This sounded like different Ps.

[@ubadify]

Dear Prof. Paar, thank you for the nice lecture. A small typo in your book on page-212 last paragraph (that) is two time. I am sorry if it is the old version of the book.

[@mr.shanegao]

EC Discrete Logarithm Problem 2:00 EC DH 54:20

[@Mamacoka18]

I really really love this lecture! One question though, at 21:27 why is 3P in this quadrant? Shouldn't it be mirrored and therefore be below the y-axis?

[@introductiontocryptography4223]

This is not very exact, but: Let's assume 2 P is really in the 4th quadrant. If you draw a line between P and 2P, you'll get an intersection also in the 4th quadrant (a bit to the left of 2P). Now mirror this along the x-axis and, voilà, you'll end up in the 1st quadrant. Again, this is not super exact but should roughtly work. regards, christof

[@Mamacoka18]

Thank you so much! I now see my mistake, I just thougth of doubling the points again, but of course 2P is different from P

[@snjklim]

Given d = 173 and generator point p (5,1). How do I calculate the resulting point T?

[@introductiontocryptography4223]

That is done with the "double-and-add algorithm". I explain this algorithms starting at 1:15:30. cheers, christof

[@akshaygoel1]

Does best known algorithm requires square root of d steps for solving ECDH.where d is the cardinality of the set.

[@introductiontocryptography4223]

Ja. The "set" is the group formed by the points on the curve. To be exact, the points that form the cyclic group that one uses for the ECDH. regards

[@Jenairaslebol27merde]

hasses schranke? - ich kenn nur pommes schranke. xD

[@wohnungt4642]

Dear Professor As far as I understood, the ECDLP describes that the attacker not knowing d would have to keep adding up p with itself (1p, 2p, 3p, ... Ep) until he has found the point and the curve he is looking for (brute-force), which is not feasible, because there are too many points so it would take too long for the attacker. I know that you spoke of an attack which is faster (square-root of p) but let's leave that aside for the realm of this question. The contradiction with this explanation is that you also explained that Alice calculates the PubKey the exact same way (adding up p for a times). As such, Alice would have to deal with the exact same difficulty as the attacker, which makes this cryptosystem useless. Then, at the end of the Video, you explain that Alice can actually use a more efficient algorithm because she knows d. Namely she'd use the double-and-add algorithm. The attacker can obviously not do this, because knowing d is necessary for applying this algorithm. Is it because of this advantage for Alice, that it becomes feasible for her to calculate the PubKey in little time while it would take hundreds of years for the attacker to do so? Besten Dank für Ihre Hilfe, aber vorallem fürs Teilen Ihres exzellenten Unterrichts!

[@introductiontocryptography4223]

Yes, exactly. The algorithm that Alice use for computing d x P fast is the double-and-add algorithm. It is almost identical to the square-and-multiply algorithm. Please have a look at the RSA video of this series. Best Grüße, christof paar

[@Yuri-bt4wl]

0:10 Lecture info 0:20 Lecture program 2:10 ECDLP 54:16 ECDH

[@yossigohar]

Hello Profesor Paar, I'm a huge fan of you and your lectures, which are conveyed in a very understandable way. At first I started watching your lectures (from the begining) as a supplementry information for Cryptography course that I take now, but very soon they became my 1st source for Cryptography learning. Ich danke dir sehr (Hope I wrote it right :-)) I have two questions regarding the EC private (secret) key, and EC public key: 1. Alice anb Bob should (randomally) choose a and b (respectievly) from the range of {2, 3, ... , #E-1}, but as you explained in your lecture #E cannot be exactly computed, and it is roughly considered to be in the range of p+1 - 2*sqrt(p)

[@travelgalaxy8291]

"I am not going to continue until an answer" at 06:40 minutes was the best part. Thanks professor

[@jimbob2810]

At 5:30, Prof. Paar writes the EC as E: y^2 = x^3 + 2x + 12 mod 17. His comments confirm that formulation of E. At 7:00, Prof. Paar states that P=(5,1) is a primitive element of the EC. I tried to work this out to make sure I really understood what EC were all about, and found that my understanding may be mistaken. Either that, Prof. Paar made a transcription error somewhere. I am pretty certain the latter is the case, and the EC should have been written E: y^2 = x^3 + 2x + 2 mod 17. If my understanding is correct, (5,1) is indeed a primitive element of my corrected equation. PS: At about 15:30 Prof. Paar is advised of the discrepancy. Spent about an hour questioning whether I understood EC. It wasn't waste of time because now I'm fairly sure that I get the concept.

[@rootshell101]

He literally corrected it minutes later in the video :)

[@ladiesman7608]

how come the students sleep. this lecturer is awesome.

[@bushayijadavid803]

exactly

[@MikeSmith-vb8ul]

Because it doesn't go fast enough. I mean his program is great but he doesn't need to spend as much time covering certain obvious points. That is what puts people to sleep (but then again it's a university so presumably any "lecture meant for the students" is necessarily going to be slowed down (or to put it more bluntly ---> slower students paid money too))

[@coshvjicujmlqef6047]

Let's put those sleepers to gulags

[@FilipLaurentiu]

well...I generate a random number, which is also my PrivKey. My PubKey is n*P. But how I can generate that PubKey without brute force ?

[@introductiontocryptography4223]

Good question. Please watch the part starting at 1:14:00 where I talk abou "point multiplication". Regards, Christof

[@williamkimball7303]

What a wonderful lecturer. Much love from the states.

[@Sagolel4797]

Why do the groups (the curves) have to be cyclic? Wouldn't it be enough to have an element that generates ALMOST the whole group so when you calculate with that element you would still have a cyclic behaviour but with a bit less elements?

[@introductiontocryptography4223]

That's actually what is done in practice. Most ECC implementation use *cyclic subgroups*, i.e. not all points on the curve are part of the group in which the discrete logarithm problem "lives". regards, christof

[@Sagolel4797]

Ok and thanks for the fast reply!

[@steven4158]

Best crypto course on the web but here is my question. I see the math but conceptually I don't see why the order of the group isn't equal to (mod p) which subtracting zero it is in standard DH if I am not mistaken

[@introductiontocryptography4223]

The group is formed by the POINTS on curve, and the group order (or group cardinality) is, thus, the number of points on the curve. It is tricky to determine the exact number of points for a given curve but there is a good approximation, Hasse's bound. It says that the number of points is *roughly* equal to the modulus p. In practice, most people use standardized curves for which the number of points are known and published in the standards. Note that this is different from standard Diffie Hellman mod p. Here, the group is formed by the numbers (1, 2, ..., p-1) and, hence, the group order is exactly p-1. Hope this helps. regards, christof

[@steven4158]

First thank you for answering. Second yes it does and just to make sure I understanding whenever operations are done on individual points they are mod p so all points must be mod p - (x,y) each x and y are mod p, however unlike straight DH that does not mean the total number of points is mod p. Do I have it? What else do you give online? This was so good I'll take anything you give Thx Steve

[@introductiontocryptography4223]

If you do the group operation, you use mod p arithmetic to compute the new points (x,y). However, the number of points are not related to p (at least not in an obvious way). cheers

[@steven4158]

Perfect thanks for getting back to me Steve

[@WAMProducties]

both x and y are in {1,2, ... p-1}, but that means you have (p-1)^2 different possibilities for (x,y). On top of that, not all of these combinations of (x,y) will satisfy the equation y^2 = x^3 + ax + b mod p.

[@StefanRichter]

Actually, finding the order of an elliptic curve group is NOT computationally hard. See this: en.wikipedia.org/wiki/Schoof%E2%80%93Elkies%E2%80%93Atkin_algorithm

[@hipsterkennyrogers909]

In Lecture 17, I was totally and completely lost until he corrected the equation @15:30. I was lost but now I'm found.

[@meenas2754]

sir, do you have video lecture about DSA and undeniable signature???? and thanks in advance....

[@introductiontocryptography4223]

Unfortunately not. regards, christof

[@KLaRue91]

Hi Professor Paar, I have been studying asymmetric cryptography since last fall. I am struggling with how to build an ECC cryptosystem and encrypt a string of integers (that were originally a message). Do you have any advice on how to approach this?

[@steveking7719]

Cyclic Groups make great state machines in EE and CS. Yes!?

[@1UniverseGames]

Any programming explanation of these lessons. Or any resources to learn programming for these lecture. Any helps

[@Mamacoka18]

I am still looking into this topic :) In Lecture 16, at the end there was a theorem: "The points on an elliptic curve, including the point at infinity have cyclic subgroups. Under certain conditions all points on an EC form a cyclic group." What are these certain conditions or is there a good book regarding this? Also, when we are talking about #E, is this the number of points of the elliptic curve or the number of elements of the cyclic group, since we stated above that not alway ALL points of the EC form a cyclic group, these two values should be different or not? Kind regards, Katharina

[@scp3178]

FYI: Man sagt im Englischen (Amerikanischen) nicht "one way function" sondern eher "trapdoor function". Interessantes Thema. Thanks. ---- FYI: You better say "trapdoor function" in english than "one way function". Interesting topic. Thanks.

[@mppound]

Many thanks for this, a very thorough explanation! I'm trying to get my head around the random choice of the private key. {2, 3, ..., E-1 }, that's fine. But if you pick 2 by mistake then I suppose the ec discrete log problem happens to be trivial in this case? On the other hand if we restrict the choice of d to say 0.5E - E-1 then we are shrinking the search space for an attacker, but forcing them to take at least a certain amount of steps. Do we just hope that #E is so large that the choice of accidentally weakening the key with a small Kpr is infinitesimally small?

[@peacetokyo]

How individual points of elliptic curve can be represented with about 1 + log2 p bits ?

[@msaufy]

when you highlight parts of the textbook, its unclear

[@Mindraker1]

Just reverse the video and pause the video before he highlights; that's how I solve it. I think he's highlighting it for the students in the classroom.

[@TheMookieit]

Thank you

[@babakrishnaprasad8700]

Sir, Please explain s value? 2p, value 6,3? 3p=2p+p=10,6? why p is selected as 17 ?also take a message encrypt it and decrypt using elliptic curve cryptography

[@introductiontocryptography4223]

p = 17 was chosen as an example. For understanding why 2 P = (5,1) + (5,1) = (6,3) you have to carefully follow the lecture. Please watch the previous Lecture 16 first. ECC is mainly used for key exchange and digital signatures, and not for encryption. Key exchange is also explained in this lecture.

[@sarvatra539]

Professor Paar, Your videos are excellent. Thank you for sharing. I have a quick question on Double-and-ADD algorithm. If a number n is ranging between 2 power 20 ... 2 power 30 then it has approximately 20...30 bits based on the fact that the number of bits is logH (H being the exponent) to the base 2. Do the number of point additions and doublings for an average multiplication follow the same rules as S-a-M? Meaning does Add take - 0.5t and Double = t where t=20 or 30 based on the range chosen above? Assuming one group operation takes about 1 sec may be. Then 1 D-a-d operation would take 1.5t where t is total number of bits multiplied by time for one group operation. So for the case of t=30 bits. Total operations is 1.5*30 = 45 at the rate of 1 sec so it takes in total 45 sec for one D-a-D operation?

[@introductiontocryptography4223]

Yes exactly. In practice, the entire double-and-add algorithm for ECC with, e.g., 256 bits, takes only a few msec on a fast PC.

[@SimpleExplanation-hl2zv]

Thank you sir. This is a very good lecture.

[@Ramiphylo]

I'm wondering about some demonstration: "If we consider a point A on an elliptic curve mod(p), there exists an integer n that verifies: n*P=0 (point at infinity)" Do you know where I can find the demonstration? thank you,

[@introductiontocryptography4223]

+Alaeddine Sabbagh This works for any ell. curve that forms a cyclic group. It follows directly from the properties of cyclic groups. Please have a look at Lectures 13 and 14 of this series. I hope this helps, christof

[@Mamacoka18]

Ok, one more question :) Can you maybe recommend a book, youtube video, podcast or really anything that discusses lattice-based cryptography, especially Ring learning with errors key exchange for engineers/IT-students (M.Sc. level)? Its just that I find your lecture incredible helpful and I struggle finding similar helpfull material on these topics. :)

[@introductiontocryptography4223]

I am afraid this will be difficult to find. As you probably know, lattice crypto is a relatively recent topic and I doubt there is some ditactically-nice material available. Your best chance is probably finding some well made presentations on lattices on the Internet... Sorry and good luck, lg, christof

[@Mamacoka18]

Ok, thank you nevertheless!

[@unbelievable1983]

Does anyone know the book mr Christof is referring to during this lecture?

[@introductiontocryptography4223]

The lecture closely follows the book (or vice versa :) "Understanding Cryptography". You may want to have a look at the companion website, www.crypto-textbook.com. It is moderately priced and has excellent reviews on Amazon. regards, christof

[@ueda_desu]

Oh jiggly puff...!!

[@MrArmas555]

++

[@mohammedaasri2774]

Great

[@SS-605]

Dear Professor, I try to solve problem 9.5 related to elliptic curves. I just want to make sure I did it correctly. For alpha=(0,3) my points are: 2P=(2,4), 3P=(0,4), 4P=neutral element. So order of alpha=4 right? and I can say alpha is primitive because at 3P=(0,4) the x coordinate is equal to x coordinate of alpha and y coordinate is additive inverse of 3 ( which will be -3). Is this right?

[@GrashalmTuts]

First, thank you for this amazing lecture and the series in general. I assume the "mod p" at 58:40 is referring to a different p than the "primitive element p=(x,y)"? The fact that both variables have the same name confused me a bit. Cheers!

[@introductiontocryptography4223]

Yep, there can be confusion. One has to distinguish between lower case p and upper case P. The lower case p refers the PRIME that is used for the basic arithmetic (more exactly: the prime that generates the finite field GF(p)). The upper case P refers to the elliptic curve POINT P=(x,y). I apologize for the confusion but p and P are, somewhat unfortunatly, often used in the ECC literature. Cheers