Elliptic Curve Diffie-Hellman Key Exchange Explained

[00:00:00]hi today I would like to talk about elliptic curve Diffy Helman a key exchange protocol so what are elliptic curves an elliptic curve is a set of points defined by the solutions to the equation y^2 = x Cub + a x + B where A and B are elements of the field K together with a point at Infinity there is also Al a condition that 4 a cub + 27 b^2 not be equal to zero some examples of fields that elliptic curves are defined over are the real numbers the rational numbers the complex numbers and the integers modulo P what do elliptic curves look like here are several examples of eliptic curve graphs over the real numbers and here's an example of an elliptic curve graph over the complex numbers finally here's an example of elliptic curve plot over the integers modulo 17 so what is so special about elliptic curves when it comes to cryptography and key exchanges for a given level security elliptic curves require shorter key lengths which in turn requires fewer memory and CPU resources to implement the protocol this is an important factor since Computing on mobile devices has become more prevalent this chart Compares key sizes and bits for cryptographic protocols that utilize the multiplicative group of integers modu op such as RSA versus the key sizes for elliptic curve cryptographic schemes these key sizes are listed at different levels of comparable security notice two things first the elliptic curve keys are much smaller second the ratio of the key links for protocols utilizing the multiplicative group mod P to the key links for elliptic curve protocols increases from approximately 6 to1 for 80 bits of comparable security to 30 to1 for 256 bits as more security is required the more efficient elliptic curves are compared to protocols based on the integers mod P the next step in understanding elliptic curve Crypt graphy is to become familiar with the group operations the first operation is point addition if we are given two points on an elliptic curve together with a point at Infinity how do we add these points to arrive at a third point on the curve let's examine this geographically if we have the points p and Q both on an elliptic curve compute a third Point r equal p+ Q the first step is to draw the line through p and Q we then find the third third point of intersection of this line on the curve this point is R finally we take the reflection of Nega R in the xaxis to arrive at R which is the sum of points p and Q now let's look at this algebraically the first step is to find the slope of the line through p and Q This is computed in the familiar manner as a difference in the y-coordinates divided by the difference in the x coordinates let's call this slope s to compute the x coordinate of point R we compute S2 minus the sum of the x coordinates of points p and Q to compute the y-coordinate of point R we compute stimes x sub P minus X subr we then subtract y sub P from this value what about Computing p + p = r or Point doubling geog graphically this is very similar to Computing p+ Q instead of drawing the line through p+ Q we just draw the tangent line to P we then find the point of intersection of this line with the Curve this point is -2p finally we reflect this point with respect to the xaxis to get the point 2 p what about Computing P plus P algebraically we first compute the slope s by dividing 3 * * x sub p^ 2 + a by 2 * y sub P remember a is a perimeter of the curve to compute X of R we subtract 2 * X of P from S2 the computation for y subr is identical to the computation for y subr for p+ Q we multiply s by x sub P minus x a bar we then subtract y and p from this value there is one more case we need to address when it comes to the addition operation on elliptic curves adding vertical points anytime the line through two different points or the tangent line for Point doubling is a vertical line then p + Q equals a point at Infinity this happens if the two points p and Q have the same x coordinate for Point doubling this happens when the x coordinate equals zero the point at Infinity also acts as the identity element for the elliptic curve group there is one more group operation that we need to be familiar with in order to implement a DIY Helman key exchange protocol using elliptic curves this operation is scalar multiplication this is not really a new operation in its own right if we have a point p on the curve and some integer k then the point q = k * p is computed using repeated addition of the point p in other words K * p is just p + P plus p and so on K times how do we develop a crypto system from this eliptic curve structure what we need is a one-way function a oneway function is a function that has the property of being relatively easy to compute the image of some element in the domain but it's very difficult to reverse engineer this process to determine what that original element was if you were only given its image this brings us to the elliptic curve discreet logarithm problem this problem basically states that scalar multiplication on elliptic curves is a one-way function from here on out our curves will be defined over the integers modu the prime P if we are given a curve and the points p and Q on that curve where Q is some multiple of P the elliptic curve discreete logarithm problem states that finding the integer K such that Q equals K * p is a very hard problem this is the fundamental principle behind the elliptic curve Dy Helman key exchange protocol the final piece of the puzzle we will need in order to implement elliptic curve Diffy Helman is the base point or generator the generator G is a point on the the curve that generates a cichet subgroup this means that every point in the subgroup can be reached by repeated addition of the generator point we Define the order of G as the number of points in the group that it generates the order is also the smallest positive integer K such that K * g equals the point at Infinity we label the order of G with a variable n the co-actor H is defined as a number elements on the elliptic curve divided by the order of g a co-actor of one is ideal elliptic curves along with generator points that produce co-actors larger than four are more susceptible to attacks and are undesirable this brings us to The Domain parameters this is the public information that is required by both parties to implement the Diffy Helman key exchange protocol this information is also available to Eve the eve dropper whom we will meet in a minute the parameters are the FI perimeter P this specifies which finite field our Curve will be defined over the curve parameters A and B these parameters along with the field parameter Define our curve the generator Point G the order of g n and the co-actor h we are now ready to discuss the elliptic curve Diffy Helman protocol let's say Bob and Alice want to communicate with each other that their only medium of communication is through a public network where anyone with the right knowhow can intercept their Transmissions Bob and Alice need to establish a key to encrypt and decrypt their messages at the same time Eve the EAS dropper who has just started to study cryptography believe she can decipher the messages between Bob and Alice if she can get a hold of their key unfortunately for Eve Bob and Alice implement the elliptic curve Dy Helman protocol to establish their public key this is how it works all parties are aware of the domain parameter the modulus P the curve parameters A and B generator Point G the order of g n and the co-actor H Bob Begins by picking a random integer beta between one and N minus one this is Bob's private key and he does not share this with anybody Bob then computes the point Big B this point lies on the curve and is computed through scalar multiplication as beta time g at the same time Alice Picks her private key Alpha in the same manner as Bob after doing so she also computes her Point big a on the curve which is Alpha time G next Bob and Alice SWA the points A and B with each each other eve can see this information during transmission so not only do Bob and Alice both possess the points computed by the other party but Eve knows that Bob has computed point B and Alice has computed point a she can even verify that these are indeed points on the curve with the agreed upon domain parameters what Eve does not know however is how many hops from the generator Point Big B and big a are this is the elliptic curve discreet logarithm problem when Bob receives Alice's point he multiplies that point by his secret key beta this generates a new point on the curve let's call it P at the same time Alice multiplies Bob's Point by Alpha this generates the same point p on the curve and that's it bob and Alice now have the same information a point on the curve this point consists of an ordered pair they are free to use this information how they wish as to what constitutes the actual key one possibility is to use just the x coordinate and to throw away the y-coordinate most importantly Eve has no easy way to compute this new Point P to do so she would need either beta or alpha or she would need to know how to solve the elliptic curve discreet logarithm problem so let's actually look at an example we want to implement the elliptic curve Diffy Helman protocol using the curve y y^2 = X Cub + 2x + 2 17 we want to generate a cyclic group from this structure so we will need of course a generator this curve has been worked out in advance so I can tell you that the point 51 is a generator for this curve in practice you do not want to try and make up your own curves you want to use curves that have been developed by professional mathematicians have been checked to make sure they are indeed secure this is also a good time to point out that the parameters used in this curve are much too small for any serious cryptography this is a simple curve used to demonstrate the mechanics of the group operations and the protocol in a minute we will see an example of an actual curve used in real cryptography now that we have a generator we need to actually generate the cyclic group in order to generate the cyclic group we start by computing multip of the generator Point G the first step is to compute 2 G this is a point doubling operation to do this we need to First compute the slope of the tangent line through G we use the formula introduced earlier S = 3 * x subg ^ 2 + a / 2 * y subg remember we are Computing in mod 17 first we compute the numerator as 3 * 5^ 2 + 2 this gives us 77 next we divide by 2 * 1 or just two but how do you divide in mod 17 simple we compute the multiplicative inverse of two mod 17 this can be done by using the extended ukian algorithm after a little bit of work we find that the inverse of 2 mod 17 is N9 reducing 77 mod 17 also gives us N9 when we compute 9 * 9 mod 17 we get 13 next we compute the x coordinate for 2G the formula is s^2 - 2 * X subg substituting 13 for S and 5 for X subg gives us 13 2 - 2 * 5 Mod 17 this works out to 6 mod 17 finally we compute the y-coordinate for 2G the formula is y subg subtracted from the value of 2 * x subg minus x sub 2G substituting 13 for S 5 for x subg 6 for x sub 2G and one for y subg gives us 3 l 17 therefore the point 2G equals 63 so here we go we have computed our second point on the curve in order to completely generate the Clic group we need to next compute 3G then 4G and so on until we compute a point at Infinity this is a lot of work if you're doing this by hand fortunately somebody has already computed the rest of the points in the cylic group feel free to check some of these computations yourself is a good practice to work a few of these by hand to get a feel for the group operations also notice that the point 3G is not a point doubling operation it is just 2G plus G therefore we will need to use the point addition formula for computing the slope and x coordinate of 3G if you count out the number of points in the group we find that the order of G is 19 the co-actor for this curve with generator 51 is one now we can implement the key exchange protocol once again we have Bob and Alice who want to communicate they don't want Eve to discover their secret key everybody knows the domain parameters including the curve parameters and the generator Point 51 First Bob picks a secret key beta equals 9 he then computes big bals 9 * G in this case this works out to be the 76 on the curve at the same time Alice Picks her secret key Alpha equals 3 she computes big a = 3 * G which is the 106 Bob aliston exchange these points over public channels aliston computes Alpha time B which equals 27 * G but remember the order of G was 19 so 27 G reduces to 8 G Bob computes beta time a which also equals a g now both Bob and Alice have the same information the point a g which equals the ordered pair 137 Eve however is stomped she sees Big B and big a but she has no efficient method to compute the key a well that's it I hope this video has been informative what we have gone over today is just the basics of elliptic curve cryptography I stated earlier I said there would be an example of elliptic curve parameters that are used in the real world this is the curve that was used by Microsoft in the digital Rights Management associated with their Windows media framework is applied to third party vendors as you can see the parameters are much bigger than what we were using in our example at the same time these numbers are much smaller when compared to parameters for Diffy helmet implemented over the integers mod P