Lecture 17: Elliptic Curve Cryptography and ECDH Key Exchange

[00:00:22]Okay, so welcome everybody to the uh extremely exciting second week on elliptic curve cryptography. So what we did last week even though it it seemed like a lot of material what we what what we really did did we essentially introduced one more cyclic group and we mainly talked about this elliptic group um elliptic curve group operation. So what what we want to do today is we want to um essentially do two things and you know each of these things are a little bit more complicated because elliptic curves are complicated. We want to talk about elliptic curve defy uh discrete logarithm problem which I think is a pretty cool idea and then we want to put things a little bit um into practice and show demonstrate a little bit what we can do with elliptic curve and we we picked the s most simple protocol which is elliptic curve defy helman okay so two things discrete logarithm problem defy helman what is nice about this whole stuff as you saw elliptic curves are pretty complicated it. What I like about today's lecture, we essentially do the same thing we did over the last four weeks or so, namely talk about discrete logarithm problem, but with a different structure here. So, we kind of we combine this new weird things elliptic curves with something we did before with respect to the discrete logarithm problem oneway functions and stuff. And um secondly, again, we take this new complicated stuff and somehow relates this to defy helman. What I hope is also that you get a better understanding what is a discrete logarithm problem what is defy helman really. Okay. So I think from a pedagogical point of view this is hopefully a useful thing that we're doing today. Okay.

[00:02:11]So first chapter of today is again EC by itself stands for elliptic curve and if it's ECC it's elliptic curve cryptography. So this is elliptic curve discrete log logarithm problem.

[00:02:51]So what we showed what we showed is if you consider in our certain type of equation in uh over the real numbers we get this type of of curve and then what we did this kind of repetition from last week and Then given two points P and Q, we came up with this weird thing doing addition. And this is, you know, what what you suffered through last night when you started working on your homework, right? You know, we did group addition P plus Q. So um and now and I I um we ended last week at the end saying they form a cyclic group.

[00:03:54]Okay. And that was just a theorem and you you did your homework but I I want to do that together with you uh one more time to put a little bit life into that whole thing by looking at an example.

[00:04:12]you know, I I really want to look is is this really a cyclic group for one specific example. Okay, we look at an um example elliptic curve as a cyclic group. And again in your lecture notes, this should be immediately under we stopped last Wednesday, okay? You know because the last theorem was under certain condition elliptic curves form a cyclic group and now we look at an elliptic curve that actually is a cyclic group the points of which are an ellip are a cyclic group. So um very often in literature you just give a name to this equation. It's it's typically called E for elliptic curves.

[00:04:58]So the curve we're looking at is exactly the one that we're using in our textbook all the time. It's y square is equivalent to x cq + a x + b and a has a value 2. So xq + 2x + 12 and the the modulus of prime that we consider is 17. Okay.

[00:05:34]And now comes an important remark for this specific curve.

[00:05:48]All points form a cyclic group.

[00:06:02]which is not always the case, but this is an easy case here from from a teaching point of view. That's why we picked that curve.

[00:06:13]Um, so and now we want to really look at the um at the cyclic group. As said at last week, what is the requirement for cyclic groups? A very very simple requirement.

[00:06:25]What kind of thing do we do do we need to have for a cyclic group?

[00:06:32]I'm not continuing until I hear an answer. What's that?

[00:06:36]I'm now a generator. So, and this generator, another word for generator is primitive element.

[00:06:47]The primitive element is for instance there are a whole bunch of primitive elements but we look at this primitive element P equals to 5 comma 1. So the X coordinate is five Y coordinate is one. Okay.

[00:07:02]What is a generator? What is a primitive element? If you take the the powers or the multiples in additive group if if you keep adding P to itself you generate the entire group. And what we also did last week um actually for this specific point and uh curve we computed 2p which is you know p + p and it turned out this is last night right 11 p.m. right transition you were when you did your homework, right? This this is this stuff here. So this is this complicated formulas, right? With the s the slope and so forth. So this is turns out it has the dots here. So this is not non-trivial, right? This, you know, if you do the pocket calculator, it takes you whatever five minutes to do that. Um then we can do 3 P which is 2 P + P added 2 again and again you know 5 minutes pocket calculator and you end up oh my my mistake here is 6a 3 and the next point is 10 comma 6 and so forth. course. Okay. And we not doing all of that here obviously. And then at some point we add we hit um 18p which has this coordinate. Okay.

[00:08:44]And one thing you know if you look at it what happens is you see this x coordinate and this x coordinate is are the same.

[00:08:53]And there's actually more happening.

[00:08:55]Namely, did anyone know how the 16 and the ones are related here?

[00:09:03]They're the inverse modulus 17, right? With the with, you know, with the with the coordinates itself, we do this modulo p arithmetic.

[00:09:13]So this is the same as 5 comma minus one.

[00:09:24]You know you take minus one you add 17 you end up with 16 right this is in in in in in in in set zipped in right in Z7.

[00:09:35]So but this is the condition. So what is this equal now to?

[00:09:44]If you compare those two here, does anyone know what is this? You know, this is Yep.

[00:09:52]is exactly this is minus this is minus P.

[00:09:58]Good that I force you to do homework, right?

[00:10:02]I mean, I can tell you there's no way anybody would remember that we did that 168 hours ago, right?

[00:10:09]166 hours ago, last Wednesday, if you hadn't done the homework yesterday or whatever or 5 days ago. Very good.

[00:10:16]Super. So, and just tiny tiny reminder uh uh rem um I mentioned that there there are two minuses here in this expression, right? There's this minus which is a minus with respect to modulo 2 and there's this minus with respect to group operation and they're completely different beasts.

[00:10:47]Okay, they mean something completely different. They both look like you know innocent little bars. They something completely different. They essentially have nothing in common just to stress that. So coming back to our cyclic group stuff.

[00:11:02]So we we've seen 18 P is the same as the inverse of P. So now let's continue this this cyclic thing you know let's continue adding P to itself. So the next would be 19 P. So how do we arrive 19 P? Well obviously we take 18 P and we add the point one more time.

[00:11:27]Okay.

[00:11:29]And now you have to be careful and you have in this coordinate system you really have to manually check that you can't use the group the group equation at this point. Okay. So you what what you really have to do before you do the group operation you have to check whether the two points that you're adding.

[00:11:58]I'm sorry it's too early here for me.

[00:12:01]Five and 16 plus 5 and 1. You have to check whether the ycoordinates are the inverses of each other. Modul p and they are. And in this case, what is the result?

[00:12:31]Any ideas?

[00:12:33]No, element. Exactly. The neutral element. Okay. Which doesn't have coordinates. You don't have to use your pocket calculator or do anything funny here. Right. If as soon as you see that you know the you know inverse of a point plus the point itself is point of infinity you can't really do arithmetic arithmetic it has to do with the fact that this is this imaginary imagin point you know it's not doesn't have real coordinates okay so this is 19p so what what's going to happen now we want to continue the We want to compute the next point 20p. What is that? Well, 19p we've just seen is a point of infinity plus p.

[00:13:21]And it was really good. Nobody said point of infinity. You said neutral element. And this is exactly what happens here. Neutral element plus p is p again, right? So 20 p is equal to p.

[00:13:38]21 P is of course 20 P + P.

[00:13:44]But 20 P we've just seen is is equal to the point itself. So this is 2 P.

[00:13:54]You get the idea, right? I do one more 22 * P is 21 + P. This is Of course.

[00:14:22]Yeah.

[00:14:33]probably I probably made a mistake.

[00:14:35]Yeah. Yeah, I might have Yeah. Yes. So I made a You see that there? It's plus two. The elliptic curve equation is wrong.

[00:15:33]Get rid of that one. Very good.

[00:15:39]So what is this big thing that I want want to want to bring across the big learn effect here is after 19 P's number I'm back back to the beginning. I'm back to P again. Right.

[00:15:56]20 * P is equal to P. 21 is 2 P and so forth. So I'm starting cycling around which is this very property of a cyclic group. Right? I wanted to show you that here. Okay. What I really ble um what I really like about that is that this is so different than looking at cyclic group with integers. you know looking at integers saying well this is some kind of odd behavior with integer and modular arithmetic here we have this completely pathological you know kaft group operation right this really odd thing you doing arithmetic on elliptic curves adding points and suddenly we get exactly the same behavior we observe with integers and sometimes if you generalize things you get a deeper insight you know and I hope this happens maybe with the next homework assignment But it's I I I like that. I think it's it's it's very cool to do. Okay. So again, you see this starts cycling around here. Um what we really want to do in crypto, why why do we do that? We're not that fascinating with, you know, groups with some kind of cyclic structure per se. We want to do something with that. Namely, we want to build crypto systems. Okay?

[00:17:17]And in particular we can build crypto systems by looking at certain type of problems.

[00:17:24]And in this case with with with cyclic group we built DL problems discrete logarithm problems. And that's what I want to do now.

[00:17:35]We obtain immediately a discrete logarithm problem and I'm I'm going to show that um the pages from our textbook which is definition 9.2.1 on page something rather.

[00:18:32]Okay.

[00:18:34]Okay, so this is what I want to you know briefly talk about and it's it's almost the same we had before about discrete logarithm problems. So the algebraic structure that means the the the set where we do arithmetics that we consider is not mod p but this is of course an elliptic curve right. So so we look at an elliptic curve we look at a primitive element.

[00:19:00]Why is there a primitive element?

[00:19:02]Because discrete logarithm problems you know live in cyclic groups. So there must be a primitive element and another element T right which is called here right and remember what what what what what is the property of a cyclic group if you have a generator if you have a primitive element this primitive element of course generates all possible po all points all existing points including obviously the point t here okay so that means this point t can in fact be expressed as a mult multiple of the primitive element, right? You do P plus P plus P plus P a certain number of times, you know, and this is a hard thing to figure out. And here we call it D times, you know, and then if if you add P D times, you know, D is, I don't know, five or seven or some 256 bit number, it's equal to T. Okay. And the discrete logarithm problem is the discrete logarithm problem is given p given t you know given this the first point given the other point what is the small parameter d which has an extremely nice graphical interpretation of the discrete logarithm problem much much nicer than modul p.

[00:20:23]Okay, which all the books don't tell you but I I do.

[00:20:34]Okay, so a graphical interpretation and it it's not very deep of the discrete logarithm problem is um you know if this is our generator P kind of our starting point.

[00:21:01]Okay. And now what we do we start hopping around on the elliptic curve. It means we do the group operation where we do P plus for instance P plus B and we end I don't know what that would be here would maybe be 2 P and then you do the group operation again and you would end up perhaps here you get 3 P and you get 4 P and 5 P and so forth. You keep you keep doing that, right? And at some point you stop and you get some final point maybe here.

[00:21:40]Get t how did he get there? Well, you hop many many many many times on the curve, right? And now the discrete logarithm problem is the following.

[00:21:48]Everybody awake? It's it's it's 10 seconds. 10 seconds.

[00:21:53]I give you the starting point, the primitive element. I give you the final point which is the public key and you tell me how often did I hop on the curve. The number of hops is what? What? What is the number of hops in cryptographic terms? This is the is a private key. The number of hops. So the number of group operations that are executed this D right D times the lowerase D is the secret key and this is a hard thing if I give you the start point and the final point it's really hard to tell how often I hopped around in order to compute that. Okay, again none of the books tell you this graphically. Okay, back to sleep.

[00:23:04]So looking at this definition here, we can maybe look at the example example for the discrete logarithm problem. Let's say the starting point at in in this in this elliptic curve we looked at before is this primitive element. Now I give you one of the points one of this 19 points that are being generated namely the point T. Right? What we do know, what we do know is since this is since P is a generator, we know that this is possible, right? This is possible. Meaning there exist a D. There exist an integer D.

[00:24:02]So that this that that that this point can be written as a multiple of P you know multiple additions. The question is what is D here right?

[00:24:16]It means in in in other terms here just to put a little bit life into that.

[00:24:28]What is D? Can anybody tell me what D is here?

[00:24:34]It's not 19 n because 19 you know 19 * p was the point of infinity and this is not the point of infinity here.

[00:24:47]This is hard to do. You can't do it with even with this small example. You cannot you cannot do that. You can look in the book and or we actually we look you know it's we look at this example we just here. So we here you know you have to look at at this table that's that's uh uh from the book. If you look at this, can anybody tell me what um D is? What's the private key is here?

[00:25:14]We have to look. Yeah. DC13P, right? So from the textbook, we conclude that D is equal to what did I say? 13. Is that right? Yeah.

[00:25:39]Okay.

[00:25:49]So, yeah. Another mistake. I'm sorry.

[00:26:09]Sorry, sorry, sorry. But very good. Very good. Of course, you know, P is this primitive element here.

[00:26:38]Okay. So, um, so let's stay let's stick a little bit more with this uh um with this definition. I I blow that up again.

[00:26:58]Okay. So what is very important here from this definition you know again we we we we looked at it we we saw that the first we have this primitive element which is kind of a little bit boring then but what is interesting is that we have to look at the two type of keys that we have okay namely note about elliptic curve discrete log algorithm problem ECDLP is that D is a private key and again D is the number of hops on the curve and this is the data type what what kind of thing is D is that a complex number or a differential equation or a matrix or a rational number or it's It's an integer. The number of hops, this is an integer. This is nothing weird. Okay, so this is an integer. Okay, very well behaved.

[00:28:13]And this is true for all for all discrete logarithm problems. It's always an integer no matter what curve, what group you're you're working with.

[00:28:25]Not so. How did I call the T? Right, this uppercase T is a public key.

[00:28:36]And what kind of thing is that? What kind of algebraic structure? What kind of data type? If you more in in computer science, what's it? Two integers in this case. In general, this is a point. This is this point on curve IE does highest a group element and this is always true for all discrete logarithm problems.

[00:29:18]The public key is whatever weird thing you're using. Okay, this is elliptic curve. So you think this is strange.

[00:29:25]There are stranger things. Okay, there's algebraic varieties, the hyper elliptic curves. So the even wilder type of discrete logarithm problems, generalizations of elliptic curves, the public keys, whatever weird thing you're you're working with. Okay, not so the that means the public key here, not so the private key. The private key is always so the number of hops if you wish the number of of of group operations.

[00:29:49]This is always a well- behaved integer.

[00:29:51]So this is always elementary school, right? This is guli here. You know this is you start to count, right? You know three teddy bears, right? You know how many circles are you know what I'm saying? So this is this is always this is not nothing strange. This is very often strange. Okay.

[00:30:13]Okay. So now we have to stick with this weirdness for a little bit longer. Um, so one question maybe is um that game say what is very important if you do discrete logarithm problems in practice.

[00:30:44]What is very important? One question that you need to answer and this has to do with attacks. For certain attacks, it's very important to know how many elements are in the group. The group cardality. Okay. So group cardinality which is a really fancy way of saying how many points are in my cyclic group right this is what we it's also called the order order of the group I like group cardality a little bit better um what is the group cardality how many points are on the curve Okay, maybe let's look let's go back to this example first. You know, we looked at this specific elliptic curves and we kept adding. This is the example we did.

[00:31:42]Can anybody telling tell me from looking at the blackboard? You can actually you can see that how many points are in this cyclic group here that we're looking at.

[00:31:52]19. Very good. Be careful that you're absolutely 100% right. They're like 18 actual points, real points, you know, P2, P3, P up to 18 P with actual coordinates. And point number 19 is point of infinity. But this counts, right? This is this neutral element of course is part of the group. Okay. So for this specific group we have a group cardality and there's a special symbol for that.

[00:32:34]I'm going to introduce that in this mo this second this is okay you know this doppel it's is number of unsal right number of e this is is 19 okay so this is was an example here okay so in general for general elliptic curves what is the what are the number of points and there is a very useful theorem by I believe a German mathematician just went over this which is Hassa. Okay, hass theorem or hassa bound or hass shranker right in German hass shranker which tells us if you look at an elliptic curve and this is the case mod p you can also do that over general finite fields but if you do that modulo p this number here right means the number of points is bound is angle shranked on the lower hand it's essentially P you know you have P here you have P there plus if you wish some correction term okay namely you know minus and uh here you have essentially here you know minus 2 * roo<unk> of P plus 2 * root of P here okay so and This gives you bound shrank. Okay.

[00:34:25]So, Hassa theorem gives us a lower and upper bound for E.

[00:34:52]Okay.

[00:34:57]And this is what what is that compare theorem 9.2.2 from the textbook. Um what um in in very engineering very rough terms what this tells us very rough approximation approximation You know continue underneath here is number of point is roughly very very roughly P. Okay.

[00:36:03]If I see critical faces in this room, this is great because if you look at this expression here, it doesn't seem that E is that close to P. There seem to be all the square roots going on, blah blah blah blah blah.

[00:36:18]But what what we're really seeing up there, what what this is really what this is what the Hassa point really says is E is in the range of P + 1 which is P you know this plus one we we we don't we we don't worry too much about it plus minus square root of P okay so what this really tells us a number of of points is a prime itself and then plus minus we go in in in direction of two times the square root okay square root still look big looks big and can be in in absolute terms this is a huge number although the absolute v is is gigantic the relative value relatively to p is small to give you an idea what is popular is um p for instance is a 160 bit number I'm going to talk more about 160 bits in a minute.

[00:37:37]How many bits are in P here in in square root POS P? Yep. 80 bits. If you take the square root of a number, you have the number of bits. So that means okay. So what's you know and then factor of two what happens with the bit length if if you multiply a number by two by one bit right it double so it's so this is 81 bits now okay this is okay so what hassles bound tells us is very engineeringish you know second semester we have 160 bit number and the Maximum we do we e the maximum derivation up of this p value is you add or subtract 80 bits. That means you add up or subtract something here kind of in the lower half. Okay to put things in into perspective this is the same you do v millionaire right you win this 1 million and the correction factor is square root of 1 million. What's the square root of 1 million?

[00:38:59]thousand, right? So, you win 1 million and this is plus -1,000.

[00:39:06]If you win 1 million euros, it's essentially you don't care whether you will win 1 million 1,000 or what is it?

[00:39:15]900 999 999,000.

[00:39:19]Everybody with me? This correction term of square root P is pretty small in absolute terms. The absolute V is gigantic. I mean the absolute value is 2 to the 80. It's some huge huge huge number relatively to 160 bit number is not that huge. Okay. So this why this is not such a bad approximation. So but things are actually not that pretty. the um as it's um as I'm make it use as make it as as I made it sound here. Okay. In in reality things are a little bit more difficult because um in practice um one needs the exact number of points.

[00:40:27]In order to thwart up probably thwart is up to thwart um certain attacks.

[00:40:51]Okay. It means it's great that h that the hassle bound gives us a rough idea which is very important. You know we want to know how big the this algebraic structure how big the discrete logarithm problem is for some attacks. You know you need a minimum size for instance to protect against brute force attacks and square root attacks. But for other attacks we have to look we have to know exactly how big the um u um elliptic uh um what the cardinality is. We we we need to know that exactly and Husbond doesn't give that give give that to us.

[00:41:27]Husbond only tells us you know 160 bit plus minus the correction factor and we need it you know down to the little last bit. We need the exact number and this is unfortunately hard to do. Um finding number of points exactly is computationally difficult [Applause] and I'm not going to talk about that how we do that. I mean this is pretty advanced number theory how to find the number of points if you get really frustrated oh you know as soon as we want to use it professor par doesn't tells us tell doesn't tell us the whole truth um this is so hard it's not that so hard any there's libraries out there that compute that um but very often in practice because this is hard people use standardized elliptic curves there's standards out There's there's a very popular standard by the um American standardization body NIST which many people use that we call about we call them the NIST curve NI national institute for standard technology I think is the abbreviation so they're called the NIST curve there are about I don't know 14 curves or something okay there's also the German BSI the BSE also proposed curves they're secure And those for these curves you you you have the number of points on the website I think even there's a Wikipedia entrance Wikipedia English Wikipedia for the NIST curves and he finds the curves that means he finds the coefficient a and b where is that somewhere here?

[00:43:23]Do we have a and b no you have a b and p. So you have the three parameters, you have some other parameters that we haven't really introduced here and you have the colineality. Okay, because it's pretty hard and you use the standardized curves and then start building your um from that. So um we have one more thing in order to to finish this first chapter.

[00:44:01]Namely, we want to look a little bit uh again at um at this discrete logarithm problem.

[00:44:09]you know on on this lower definition there namely um all elliptic curve protocols such as defy helman which we're going to do in 5 minutes rely on the hardness of the EC DLP again.

[00:45:02]What does this mean? Rely on the hardness. Vish guide means if you want to break that protocol if you want to break defy helman if you want to break elliptic curve digital signatures you have to solve this problem and then hardness means hopefully that's a hard problem how hopefully that's really difficult to compute you know with all supercomputers on planet earth this cannot be done hopefully okay and the question how hard is that and I just want to want to talk a little bit about that so the question is you No, how hard how difficult the is it? Yeah.

[00:45:50]Yeah.

[00:45:53]Yeah.

[00:46:10]So the no otherwise he could do a brute force attack. It's a good remark. No no he had a good question. He said so with the standardized curves is there everything given? Is the primitive element given? Yes, of course. Does this help us with attack? That's maybe what you were thinking of. No, of course it doesn't help us. You know you have a primitive element.

[00:46:32]What these standardized curves do they essentially give you the curve. I mean you never thought see a drawing obviously but you essentially have the curve you have the starting point. Good luck right from there whatever app you know you have this your new itune your new app that you write with some security property and you want to make money with with with your with your uh um app. Um you you take the curve you know you I mean you take this graph you take the generator and that from there you're on your own you know you choose a random D you end up with your public key you have your private key you can build your crypto system from that and the attacker then that's kind of the interesting thing the attacker doesn't have any advantage from knowing the curve ahead of time and the point here you you can't premp compute all points if you could do that you would have brute force attack okay so how hard is that and we did talk about that a few weeks ago before no I think two two or three weeks ago when we talked about the discrete logarithm problem we talked about the attacks and maybe that seemed a little bit abstract and maybe you get a little bit more feeling for that now namely long story made short the discrete logarithm problem is very very hard so this is good for us as a designer you know if you design crypto system we we're not the crypto analysis we're not Oscar we don't want to attack We want to build something secure. This is a very good situation here.

[00:48:00]If the elliptic curve EC is chosen [Applause] carefully that means you have to be careful with a lot of things. And this is why people use a standardized curve.

[00:48:19]They chosen carefully. So they checked all kind of mathematical properties.

[00:48:24]If elliptic curve, if the elliptic curve is chosen carefully, the best known algorithm for computing The DLP or the EC DLP if you wish or DLP uh requires approximately approximately square root of P steps.

[00:49:20]Okay.

[00:49:29]And this square root here, just to warn you, this square root has nothing to do with the square root in Hassa. I mean, it's the same number, but there's there's no mathematical reason why they why they're the same. Okay, so this comes they pop out of what whatever the best attacks are which we actually when we classified them 3 weeks ago or so we called these the square root attacks for that reason because they have a square root complexity and it's a sheer coincidence that this is the square root also comes up in the in theory again let's look at an example if you consider an elliptic curve curves with with a 160 bit prime. That means all arithmetic is done with 160 bit arithmetic numbers 160 bit numbers. Um then the best known attack attack requires square root of P which is square root of 160.

[00:50:46]You remember that right? ninth grade or so, right?

[00:50:55]Steps.

[00:51:09]This is very hard actually. We um professor Gonzo showed you a kopa kubana here the first lecture I said right in way way back in October right um and actually his master sees this his diploma by whatever five years ago of professor geneu dealt um with implementing these best known attack for elliptic curves on on kaakobana okay so what you can do with you know with the best known with this custom hardware I think we can solve of 2 to the 35 or something, right? You can do 2 to the 35 operations in one year or something like that, right? And from there, we can approximate how long it will take to to the 80 and it turns out with with current hardware it will be 1 million years or something. Okay, with the hardware becoming faster and faster with more slow law, we can approximate rough estimate is 15 to 20 years. Okay, for this you know for two to the 80 we can two to the 80 this type of hopping around I mean that that was his his master sees this right we can probably do our assumption was 1 million euro so we can you know we can go on and and to Aldi not Aldi but go to a store and buy computer hardware for 1 million euros and that in if you do that not today but if you wait 20 years nearby buy computers for €1 million, you can do 2 to the 80 group operations and this baby is broken. Okay. And this is why 160 people say well you have a security for 15 20 years something like that. This is kind of the lower lower threshold what people want to use.

[00:52:57]Actually most commercial products now they switch to 192 256. These are two other popular numbers. Okay.

[00:53:07]board. So we're done with the first chapter of today. Okay. So comes now comes if now comes kind of a fun part and what's a little bit a shame here is actually about this part of the lecture.

[00:53:24]I think what what what is really good hopefully that we generalize the discrete logarithm problem to elliptic curves as what I said before you know in in in terms of of deeper understanding maybe also a niskin maybe that helps you what's a little bit a shame that there's a lot of mathematics that are really deep pretty advanced so there's no you know we can't really we don't really want to talk about where h theorem stems from we don't really want to introduce a discrete logarithm problem attacks so a lot things where I just give you facts but I'm for this right these are just give it to you which is a little bit frustrating for me as a teacher sometimes so now the second part will be different we look at elliptic curve defy helman and this is much more algorithms and we do real crypto so it's kind of a nice mixture hopefully of in in today's lecture so the second part of today deals with elliptic curve. Defy Helman [Applause] key exchange which is sometimes not always but sometimes abbreviated as ECDH it's CDha if elliptic curve D helman Okay, so now it becomes hopefully you start appreciating this beauty of discrete logarithm problems because all the discrete log problem protocols look very much the same. Once once you give me a new cyclic group and we have a new cyclic group namely elliptic curves here you can just go back to the stuff we did actually before before the the vacation before in February look at the diffma key exchange and they do exactly the same protocol exactly the same just with elliptic curves. So once you have a new group we immediately have all the crypto applications we immediately have have the key exchange later on we will have automatically digital signature we have encryption schemes Elgamal Elgamal encryption you can also do with elliptic curves it's a little bit tricky but it's essentially the same so this is straightforward straightforward is one word by the way this is very popular mistakes for in The bachelor c thesis straightforward adoption of defy helman in zp. Okay, this is in zp. This is the defy helman with integers that we've done again in February and and actually used a few times so far. Okay. So, um for the protocol we have as always we have two phases.

[00:56:38]We have the setup phase where we need the uh where we need domain parameters and the domain parameters in um with the plane element were very easy. there was just a prime P and a primitive element and it's the same here but we don't have a prime anymore. Well, we we we have a prime but the prime we we need the algebraic structure. We need the cyclic group in that P stuff we did in February. The algebraic structure is given by P, right? If I give you a prime, you immediately know what ZP is, right? If I give you if the prime is 31, well the algebraic structure is Z31. But now the algebraic structure is this baby here.

[00:57:25]So we need an elliptic curve E. I'm sorry this is E again which is given by the curve equation obviously.

[00:57:39]Okay. And we need a primitive element.

[00:58:04]So then we have to run the protocol.

[00:58:06]Okay.

[00:58:11]First phase, second phase is the protocol, the actual protocol.

[00:58:22]How does this work? Uh here, let's try to squeeze it in here. Okay.

[00:58:40]No, let's not try to do that.

[00:58:44]Second phase is here. So if just continue underneath here, right? If you if you're copying this.

[00:58:55]Um, so we have our parties Alice and Bob and Ellis. So here's here here's the story.

[00:59:05]Alice and Bob have AS really fast AS implementation. AS is really secure.

[00:59:11]People cannot break that and they do some I don't know illegal downloaded videos, right? So they just got this new Hollywood hit and they want to send it over the network and they don't and they want to encrypt that. They want to use as with 128 bit key. So they need to agree on a key and you know Edis lives in Bum and Bob lives in Munich and they don't want to you know travel down by you know with a bank or something right it's really expensive and and hard so they want to exchange a key over an unsecured channel so Ellis and Bob took my class so they know how to do that so the first thing is they agree on an elliptic curve and they pro they might use one of these standardized curves right that exist.

[01:00:07]What Ellis then does is she has to set up a discrete logarithm problem. What is a discrete logarithm problem is this here right Ellis Alice has to do the this kind of thing here. Okay so the first thing she needs is the um private key which we denote by lower case. So this is K private of Alice which is lowerase A K private of Alice.

[01:00:40]Where do we get where do we typically get a private key from? How do how do we generate a private key?

[01:00:47]very broad question random right you don't want to do anything kind of computation that maybe Oscar can compute you know and and the more random the better okay so some kind of random number And as often you don't want to use the the if you use the full cardinality here cardinality of E. If this would be a, a would end up being the unusual element, which is something you don't really want to do. Bob does the same. Bob computes his private key.

[01:02:02]Okay.

[01:02:03]So now we have the private key which we which we called D here. Right?

[01:02:10]Now you have to compute your public key which is called the T value here which we call uppercase A and uppercase B as yeah there some restriction that is greater than the P.

[01:02:35]Oh yeah yeah yeah yeah.

[01:02:37]Um, yeah. No, no, no. But this is not related to this P here.

[01:02:54]That's good.

[01:03:31]So he was worried that can we choose two? Is that a problem? Because in the definition of elliptic curve from last week you you really paid attention is it says P can't be two at but in in theory at least you you could choose two here and everything would be fine if you helman wise. So this will become our public key. What do we do? Well you do a point it's called a point multiplication. So you take private key times primitive element and again what kind of baby is that?

[01:04:11]What kind of data structure do we get out here? Public key is that an integer or point of the curve.

[01:04:20]Point of the curve. Okay. So this is this is what I told you before. Where was that?

[01:04:30]Think I told you.

[01:05:05]Why did I write that down? You know what I'm talking about.

[01:05:09]Links over the good. Thank you.

[01:05:16]Private key is an integer. Public key is a point on the curve. Very good. Okay.

[01:05:22]And this exactly what's happening. You know this is a boring integer. You know this is 918,711.

[01:05:30]You know it's some some num integer number. This is a point of the curve.

[01:05:34]Same here.

[01:05:56]And again this exactly exact analogy what what you do with uh uh over ZP. Now you exchange your public keys. They're they're public you know they you can don't have to keep them secret. You can send them over the channel.

[01:06:14]So what Alice does in order to compute the session key, she computes, she takes her secret, her private key and multiplies that with the public key she receives and this become, you know, as a she gets one result out and Bob does the same.

[01:06:43]Bob takes his secret, you know, his private key, multiplies that with the public key of Alice, and surprise surprise, he computes the same point. Okay.

[01:07:09]So that's Dy Helman just to motivate it to motivate that a little bit more to what we can do at this point is if you want to actually do encryption here what we can do now let's say we have a message M this is your illegally downloaded video file right 1 GBTE okay you want to encrypt so Um so your as encrypt m which is not the hard part that's the easy part the hard part is which key are we using you can use either the x or the ycoordinate and actually in in practice you know usually that's too long for instance x would be 160 bit number as only needs 128 bits so what you do you just take the 128 leading bits, you know, and you drop the other 32 bits, no fur of the or some, you know, you take you have 160 bit, you you take you take you have 160 bits here, you you choose 128 bit and in practice even a little bit more complicated. Typically, it's recommended to hash that, but I don't want to go into that. So for you just choose any 128 bits and we just write that this way, right?

[01:08:36]We pretend XAB is you know is 128 bit.

[01:08:40]You get your cipher text out which we call C at this. Usually we call the cipher text Y but then you get confused with the X and Y coordinates.

[01:08:48]um you send the cipher text over the channel and uh if Ellis receives the cipher text, she wants to watch the movie, right, that he downloaded. So she has to as decrypt run as in decryption mode.

[01:09:07]And here's now the beauty. She has the same key, right? You share the same key.

[01:09:24]grow theory, right? All theory is gray.

[01:09:29]So, let's look at an example.

[01:09:48]Oops. Okay.

[01:10:01]I don't even have a keyboard here. So, okay. Is this readable? Can you read that a little? The protocol Yeah. Good. Good. So, um, so just to show you here, you know, this is example.

[01:10:33]You know, it's one of the toy examples that we like. Surprise, surprise. We have the same elliptic curve we've been using the whole time here, right? So, we use this elliptic curve again. Surprise, we use the same primitive element we had before. And now we show how to do an, you know, toy size defy helman. Um yeah, Alice chooses three as a public key, a private key, sorry, and Bob chooses 10.

[01:11:01]Alice, you know, computes 3 point 3P, which you can look back in the table, right? This this is what happens. So you 3 P is this here. Bob computes his B his public key, which you know is 10 times P. And again you look in the table you find 10 * P is this this point they exchange the stuff and then here you yeah it you you have to do the group operation so you do you know 3 * B plus B plus B you do three times the group operation you end up with this point with the coordinate 13 * 10 and here's kind of the nice surprising thing here we compute including B times that means 10 times the other public key. So 10 times this here 10 times this here and it turns out da da da they compute the same point. Okay. And now you know coming back to our example, you see that you have the same x and y coordinates.

[01:12:07]It means you could use the number 13 as input. Of course, this is only like a four or five bit number. You don't want to do that with four with with with small numbers. But if you do that with really large numbers, it works just the same. Um let's talk a little bit more about that. namely um let's look whether this this really always works a proof of correctness and again this is very easy this is is very much uh uh analogous to um plain old helman Ellis computes A * B and B was the public key of Bob. Where where where was this coming from? You see it over there. uppercase B was lowerase B * P which is this due to the associivity is associative that's guilt here because it's a group um what does Bob compute?

[01:13:36]Well, Bob takes his public key, his private key, and and and multiplies that with the uppercase A here with the public key of Alice.

[01:13:52]Dunker, you get the same result again.

[01:13:59]Okay.

[01:14:04]Okay. So towards the end of the lecture there's one thing which is um uh again which is not complicated and which I think is kind of nice too.

[01:14:17]You want to talk a little bit about computational aspects. How do we implement that?

[01:14:24]So let's look at the actual computation that Alice and Bob have to do. The kind of operations they have to do.

[01:14:31]Well obviously they have to do the group operation right? They have to hop around on the curve and this is what we did last week. This is what you do for your homework, right? You can add points and we have remember that there's group point addition and point doubling. Okay, this is one thing. So we know how to do that. But this is now a little bit more complicated.

[01:14:54]You have to what's called point multiplication or scala multiplication which is something we haven't discussed really. you do a time p and here do a * b.

[01:15:05]Bob does the same.

[01:15:08]So this is what what we do towards the end of the lecture. And this is kind of something that is not really new, but it's it's kind of nice. Um question is how to compute you know essentially the orange dots.

[01:15:43]How do we do the orange dots that you see there? Okay. And let's say in general terms, let's call that a * p.

[01:15:51]The problem is, and I think I talked about it. If not, I I'll do that now.

[01:15:57]There's no natural natural way direct way of doing a * p. Okay, that's it. It looks like well, you do multiplication.

[01:16:06]There is no such thing as multiplic multiplying scala by by by by points.

[01:16:11]This is just the same as doing and I think I talked about it last time, right? Doing I don't know 37 times.

[01:16:22]Okay, they ask you to do that.

[01:16:26]Nobody thinks, oh, there's some, you know, some arithmetic operation that does that. We all know maybe this is I do smaller to the fifth.

[01:16:37]You'll see why because it you look at that and you immediately see okay this is 37 * 37 * 37 * 37 * 37 right that means this is just a notation shorter notation right convenient notation same goes here okay so this is just a shortand notation for p + p + p + 8 times Okay. So was the same. But here if we have really large numbers, how do we do that?

[01:17:26]Square and multiply. Okay. And here's the beautiful thing. The square multiply works exactly the same for elliptic curves but instead of squaring you know squaring is okay in elliptic curves squaring becomes p + p so this is doubling okay squaring becomes doubling multiply was you know a * I don't know x This is multiply in elliptic curve. This becomes add. So square and multiply becomes double and add. So it's a double and add algorithm. Okay.

[01:18:21]The point multiplication a * p can be computed with the normal quotation marks with the double and add algorithm.

[01:19:08]I give you an example. Okay.

[01:19:22]So let's say we want to compute 26 * P.

[01:19:25]And remember when I introduced the double the square multiply I said well there's a dumb way of doing it and the smart way of doing it. The dumb way would be to do P plus P plus P plus P plus P 25 times. Okay 25 times the group operation. It turns out there's a better way.

[01:19:43]And again the double and add and square and multiply identical algorithms. You just replace the operations.

[01:19:51]And what we did with the square and multiply we looked at the binary representation as bin of the exponent. But now the exponent is this multiplier here. So we we have to look at 26 in in binaries turns out to be the number one one 0 1 0.

[01:20:13]time p. Okay, here's the algorithm and I just give you this one example and then you look the algorithm up in the um book and again we we derived that more formally before.

[01:20:24]So let's here we take care of the iteration number of the steps. We start with step zero.

[01:20:32]What we do in do in step zero? We do we compute you know p which is obviously equal to 1 * p. Okay. So we don't do anything here. Okay. Now the algorithm starts and an alternative name actually for the for square and multiply and double and add is left to right method because we scan the exponent coming from the left. So and we done with this one is fine here. This one is this one. Now we have to look at the next one here. So what we do step one a you double. Okay. So you do P + P is 2 P which is this binary representation which is one double here. Okay.

[01:21:28]Now you look at the second bit here.

[01:21:30]Second bit, you know, coming from the left. Is this a one or a zero? This is a one, right? Unfortunately, right? Now we have a zero here. So we have to turn this zero into a one. And any ideas how do we do that?

[01:21:43]Add and we add P.

[01:21:46]This one, this is 2 P + P is 3 P and it's one. One.

[01:21:55]Okay.

[01:22:07]Can get your stabilos ready. Okay, we need a lot of colors here. Um, so um so we're done with the second bit.

[01:22:17]Now let's look at the third bit. This is iteration 2 a first part of the second iteration.

[01:22:25]We do again double. We always double. So we have 3 p + 3 p is a doubling operation gives us 6 p or in binary 1 1 0.

[01:22:42]So the the bit we just generated was a zero at the third position is a zero here. That means we're done in this operation in this iteration.

[01:22:54]And at this point we already done with the uh okay let's go to bit number four. Again this is we that means we go to the next iteration to iteration number three or step number three. Again we double 6 P + 6 P = 12 P. 12 has a binary representation of 1 1 0 0.

[01:23:22]Okay.

[01:23:26]Again, what you always generate in the uh in the scalar here is a zero. Okay, we just generate the zero here. We're talking about this bit here, right? Bit number four coming from the left.

[01:23:39]This is a one. So we again we have to we have to flip that we have to turn the zero into one by adding by adding P. So that's iteration number 3B. This is 12 P + P becomes 13 P which is 1 1 0 1 * P which is exactly what we want to have. So the pattern looks pretty good.

[01:24:15]And now we have to do the last bit. Bit number four, number five, depending how you count.

[01:24:28]Iteration 4 A, we do um 13p. We double again.

[01:24:40]we get 26, which is our seal numa, which is exactly what we want to have.

[01:24:47]And I I'm out of colors. I don't know what to do. So, I can Okay. So, okay.

[01:25:02]And again to show you what's happening here is so you know in every iteration we doubled in the beginning. We need one more minute here.

[01:25:17]So the same rule as before.

[01:25:28]So we always double if the bit that we are processing happens to be a one we not only double but we also add. So you know the orange bit so to speak this was a one that's why we also added the green in the green case here we there was no one so we didn't have to add and this reddish red purple one we again had to add okay so it's the same algorithm same complexity um you find the full algorithm in the book I just wanted to here this is the There's the algorithm on page 248. Yeah.

[01:26:21]Classifism.

[01:26:24][Music]