Loading

Module 1: Cyclic Groups

Notes
Study Reminders
Support
Text Version

Cyclic Groups based on Elliptic Curves

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bangalore Lecture – 41 Candidate Cyclic Groups for Cryptographic Purposes Part II (Refer Slide Time: 00:44) Hello everyone, welcome to this lecture in this lecture we will continue our discussion on the candidates cyclic groups for cryptographic purposes and in this lecture, we will introduce specifically the cyclic groups based on elliptic curves. So let us start with the discussion on elliptic curves based cyclic groups. So remember in the last lecture we had seen that if p and q are primes where p is of the form r times q + 1 and if we take all the r th residues modulo p then the resultant set which we denote as G constitutes a subgroup of Zp* and we can prove that this set G along with the operation multiplication modulo p constitutes a cyclic group. However, it turns out that for practical security we have to operate or select very large values of this prime p namely we have to ensure that the p is at least 2048 bit prime numbers which actually ends up ensuring that the resultant time of the sender and the receiver is also very slow. So what we are now going to do is in this lecture we will see cyclic groups based on the points on elliptic curves and these are basically alternative cyclic groups where the DLog problem the CDH problem and the DDH problems are indeed believed to be hard.More specifically if the size of prime that we are going to operate with is of size n bits, then the best known DLog solver that we know for these groups is of order 2 n/2 and that means its sufficient to operate with a prime number which is a 256 bit prime number for most practical purposes and that gives us highly efficient instantiations of DLog, CDH and DDH based crypto systems compared to instantiations based on prime order subgroups of Zp* right. So that is plus point of this groups compared to the instantiations based on the prime order subgroups of Zp*. Another interesting property of the cyclic groups based on the elliptic curves is that it provides us with additional structures what we call as pairings which we are not going to discuss in this course. Because these are advanced concept but just for your information this additional structure which we call a pairing can be used to build highly advanced cryptographic primitives such as aggregate signatures, broadcast encryption, functional encryption and so on. (Refer Slide Time: 02:59) So before going into the exact elliptic based cyclic group that we are going to use for the cryptographic purpose let us do a warmup and see how exactly elliptic curves over the real numbers look like. So let R be the set of real numbers and let a and b be 2 real numbers or constants publicly known such that this relationship whole namely 4a3 + 27b2 is not 0.The reason for this constant will be clear soon and imagine we have such an a and b constants a and b consider this equation in x and y, y2 = x3 + ax + b then if I plot the points on this equation or if I plot x, y value satisfying this equation and if you take all those x, y pairs which are real numbers satisfying this equation and along with that if I take a special point which I did not as O then the resultant set I call as E. So for instance if I take the curve or the equation y2 = x3 - x and plot all the real x, y satisfying this equation then I obtained this curve in the same way if I take the curve y2 = x3 - x + 1 and plot all the real x, y satisfying this equation then I obtain this curve. So what E is basically once we have fixed the equation we take all the x, y real numbers which satisfies this equation and along with that a special point which we denote as O and this special point O is called as the point at the infinity which is kind of an imaginary point which you can imagine sitting at the top of the yaxis and lying on every vertical line. So you can imagine that every vertical line will eventually meet at a horizon at a single point and that point where all the vertical lines are going to meet is considered as the point at infinity which would be denote by this special notation O. So that is how I construct the set E now the set of points E that we have defined above is called a non-singular elliptic curve over the set of real numbers and why it is called non-singular, is because we have ensured the condition 4a3 + 27b2 ≠ 0 which is a necessary and sufficient condition to ensure that the resultant curve that we have defined here namely y2 = x3 + ax + b has 3 distinct roots because it is an equation of degree 3 in x. However, if we do not ensure this condition namely 4a3 + 27b2 ≠ 0 if we let it to be 0 then the corresponding curve or the set of points that we obtain is called a singular elliptic curve it will not have 3 distinct roots. (Refer Slide Time: 05:55)So that is the definition of elliptic curves. Now what we are going to do here is we are going to find a very sophisticated way of doing performing operation : addition operation on the points on this elliptic curve. So imagine you are given a non-singular elliptic curve over the real numbers and we define the additional operation on these points such that the way we are going to define the addition operation it satisfies all of our group axioms namely it will satisfy the closure property, associativity property, it will be ensured we have an identity element and an additive inverse for every point on the curve and which ensures that the set E along with the plus operation that we are going to define now constitutes an additive group. So the plus operation is defined as follows so we define the point at infinity to be the identity element that is our definition. So we define that if you we defined a + operation on any point p on this elliptic curve and a point at infinity to give the result as p. So if you take any point p which could be the point at infinity itself and to that point if you add the point at infinity the result is defined to be the point p itself. So that is a first property of the addition operation that we have defined here. On the other hand, if you are given 2 points P and Q lying on the curve E and say the coordinates of the point P are (x1, y1) and the coordinates of the point Q are (x2, y2) and neither P nor Q is the point at infinity then the way we are going to define the plus operation on these 2 points P and Q is as follows. So we can have 3 of the possible cases depending upon the relationship that holds between the coordinates of P and Q. So the first case is when x1 ≠ x2 in this case the way we define the result of P + Q is as follows. So we define L of x to be the line passing through the points P and Q. So its a straight line passing through the P and Q so you have the pictorial representation here and let R be the third distinct point which lies both on the straight line as well as on the elliptic curve. So I am denoting the x and y coordinates of the third point to be x3, -y3 and I call that point to be R. So pictorial is say this curve the straight line passes through P and Q and it intersects the elliptic curve at the third point say at R whose coordinates I denote it as x3 and -y3. So in this particular example in the pictorial representation the y coordinate of R is actually positive but that need not be always the case. So that is why I am just representing it as -y3 because if for instance if your Q would have been here then on passing the straight line or through P and Q it would have met somewhere here, and y coordinate of R would have been a negative coordinate. So irrespective of what exactly is the case. It is just a notational issue the third distinct point at which the line intercepts the elliptic curve is denoted as R and its x coordinate is x3 and the y coordinate is -y3. Now what we do here is we just reflect the point R along the x axis and if we reflect the point R along the x axis the x coordinate is going to remain the same, but the y coordinate its sign will get changed. If it was –y3 it will become +y3 whereas if we would have been plus, then it becomes minus. And the result of the addition of P and Q is defined to be that reflected point. So that is the way we define the plus operation on points P and Q both neither P and Q are infinity point and x1 ≠ x2. So now if we want to mathematically compute the exact value of x3 and y3 here is how we can compute: it turns out that x3 and y3 are related to the coordinates x1, x2, y1, y2 by this relationship 3 = 2 − 1 − 2 , 3 = 1 − 3 − 1 and here λ is basically the slope of the straight line passing to the points P and Q and the slope of the line passing to the points P and Q comes through this formula 2− 1 2− 1 and since we are in the case where x1 ≠ x2 that means the denominator is not 0 and hence the λ is well-defined. So that is the way operation of addition (plus) operation on points P and Q is defined for this case for the case where x1 ≠ x2 now let us take the second case where x1 = x2 but the y coordinates of P and Q are just opposite of each other right. So in this case what we do here is the line that we make pass through P and Q it basically ends up converging at the point at infinity right. So the idea here is also the same we actually pass a line pass into the points P and Q and see where exactly it meets the elliptic curve. But in this case since the x coordinates of P and Q are same but only their y coordinates are different in the in the sign the straight line passing through P and Q basically meet the point at infinity, converge at point at infinity and that is why we define the P + Q operation in this case to give the result the point at infinity that means we can interpret 2 points x1, y1 and x2, -y1 where x1 and x2 are same to be the additive inverse of each other. Right whereas for the third case where x1 = x2 and y1 = y2 we have 2 sub-cases if y1 = 0 then we can interpret y2 to be =-y1 because 0 and + 0 and - 0 as same right? so if y1 = 0 then we can interpret y2 to be = - y1 and then we basically come to the previous case where x1 = x2 and y1 is - y2. In that case the way we have defined the plus operation we get that the summation of P with the same point which is basically 2P gives you the point at infinity. On the other hand if y1 is not 0 that means say we have a point like this P and we want to add P to itself then the line passing through this point is defined in a different way : the line here is basically the tangent to this curve E passing through the point P and we see where exactly the tangent touches the curve we call that point as say R and say the coordinates of R is x3 and -y3 which is the third point, 2 of the points are P and the third point lying on the curve is R and what we now do is we just reflect the point R along the x axis and that is the result of adding P to itself. So the result P + P, which is 2P in this case will be x3, y3 and mathematically again x3 and y3 are exactly the same as it was defined for the case where x1 was not equal to x2 the only difference now is that the slope of the line is different here compared to the first case. Because in the first case the points P and Q are distinct points but here are the points P and Q are the same points and that is why the line is the tangent and the slope of the tangent is computed by this formula 31221+ .. And since y1 is not 0 right we are in the case where y1 is not 0 the denominator 2 times y1 is non 0 and that is why the slope is well defined. (Refer Slide Time: 13:55) So that is the way we perform the addition operation for elliptic curves defined over the set of real numbers but as I said earlier for cryptography primitives we want to operate on a set which has a finite size that is why now what we are going to do is we are going to compute perform operations on elliptic curves modulo prime number which will not have nice geometrical representations as we had for elliptic curves over the real numbers but property wise we can extend the definition of the plus operation as we have done for the case of real numbers here as well. So here is how we define elliptic curves modulo a prime : so let E be a non-singular elliptical over the set Zp basically what it means is we form an elliptic curve equation here namely the equation is y2 = x3 + ax + b modulo p and we take all x,y elements or x , y pairs from the set Zp x Zp and take all the elements of the form x,y where x is in the range 0 to p - 1 and y is also in the range 0 to p-1 which satisfies this equation and along with those x , y pairs we take the special imaginary point namely the point at infinity.So as it was the case for elliptic curves defined over the set of real numbers the point at infinity serves as the identity element namely we define that any non any point P belonging to the state E if we perform the plus operation with respect to the point at infinity then we get back to the same point P whereas if we have 2 points P and Q belonging to the set E which are not the points at infinity and say the coordinates of P are x1, y1 and x2 , y2 where x1, y1, x2, y2 are all elements of the state Zp then the plus operation is defined as follows. For the case where x1 = x2 and y1 = - y2 we define P + Q to be infinity, this is exactly the case this is the same as in the case 2 for the elliptic curves over the real numbers. Whereas if otherwise if x1 ≠ x2 or y1 ≠ y2 then we define P + Q to be (x3, y3) where x3 and y3 are elements of Zp and where x3 will be this value namely it will be λ2 – x1 – x2 of course everything modulo p and y3 will be λ times (x1 – x3) – y1 modulo p right and the λ will be computed in a different way for 2 sub-cases : if P = Q then λ is defined in this way namely (3x12 + a) * (2 y1-1 ) and this basically corresponds to this case that is how we have defined x3, y3 for the real number case and if P ≠ Q then the λ is basically the slope of the line passing through the points P and Q which basically is similar to the first case for the elliptic curves over the real number. And it turns out that all the plus operations and all the multiplications operation that we are performing here are modulo p when we are actually performing operation on the elliptic curves modulo p and if you see here the way we have defined λ this is the element 2 times y1-1 is not 2/y1. That is not the case. This should be interpreted as the element 2 times y1‘s multiplicative inverse which exists because we are performing modulo prime p operation and in the same way for the second case where λ is of this form 2− 1 2− 1, this (x2 - x1)-1 is the multiplicative inverse of the element (x2 - x1) modulo p which is also guaranteed to exist because x2 - x1 will be a non 0 value. So that is the way we naturally extend the definition of the plus operation for elliptic curves defined over modulo prime. (Refer Slide Time: 18:18)And for an illustration let us take this example say I perform all my operations on Z11. I take my curve to be equation x3 + x + 6 modulo 11 and I take my set E to be the set of all x, y belonging to the set Z11 x Z11 satisfies this equation along with the point at infinity. So if you take all x, y belonging to the set Z11 x Z11 and see which of them satisfies this equation then we obtain the set E to consist of these values all the pairs satisfies this equation modulo 11 and along with that we have a point at infinity. So since the size of this E is a prime number namely we have 13 entities in this set E it follows from a basic fact from the number theory that the set E along with the plus operation that we have defined constitutes an additive cyclic group and since the order of this group is a prime number every element in this group except the identity element which is the point at infinity can be treated as the generator for this group. So for instance we can take the element (2,7) belonging to the set E which is a non-identity element and you can verify that indeed it constitutes a generator namely different powers of this element (2,7) will give you all the elements of the state E. So 0 times g as per the definition it gives you the identity element namely the point at infinity and if we perform the operation 1 times g, 2 times g, 3 times g then the way we have defined additive group operation we will get back each of the elements from the state E namely the non-identity elements of the set E once, that means the element 2,7 indeed constitutes a generator of the set E.(Refer Slide Time: 20:12) Now we have another candidate group namely the elliptic based cyclic groups and let us see how exactly the DLog problem, CDH problem and DDH problem will look like over these groups because in the description of the DLog, DDH and CDH problem that we had seen in the last lecture we assumed that underline group operation is the multiplicative operation but now we just want to recast those definitions in the elliptic curve based cyclic groups. So what you are given here is the given description of a cyclic group based on the points on the elliptic curve modulo prime and say the size of the group is a prime number q and you are given a generator that means different powers of g namely up to q – 1 th power of g would have given you the all the set E. Then the DLog problem is as follows the challenger here picks a random index from the set 0 to q – 1. And it gives gα which basically is α times g which is nothing, but the element g added to itself (α – 1) times and the challenge for the adversary is to find out the index α. There is a CDH problem is the challenger has picked 2 random points from the elliptic curve by picking the indices α and β and computing α times g and β times g and the goal of the advisory is to compute the Diffie Hellman function without knowing α and β.And the DDH problem is the challenger prepares a triplet where the first 2 components are random points from the elliptic curve and the third component is either the output of the DH function the Diffie Hellman function with respect to the first 2 components or a random point from the curve and the goal of the adversary is to find out whether he is seeing a Diffie Hellman triplet or a non-Diffie Hellman triplet (Refer Slide Time: 22:06) So now we have seen the definition of elliptic curves for cryptography applications so the next question that we would like to answer is, is it the case that all elliptic curves modulo prime suitable for cryptographic applications? So before answering that let us see an interesting result for elliptic curve based on elliptic curve modulo prime. So let p be a prime and say E be an arbitrary elliptic curve defined over Zp which could be a singular curve, non-singular curve namely say E is the collection of all x, y pairs satisfying this equation along with the point at infinity then a very well-known bound which is called as Hasse bound gives you a lower bound as well as upper bound on the number of points which we have on this elliptic curve. So this is the lower bound (and this is your upper bound (and interestingly we have poly time algorithms polynomial in the number of bits that we need to represent a prime p which can give you the cardinality of the elliptic curve, we also have poly time algorithms for picking random points from the curve, we also have poly time algorithms for adding 2 points and we also know how to generate an elliptic curve where the size of the elliptic curve is a prime number. So the next question that we would like to answer is that is the DLog, CDH and DDHproblem computationally difficult to solve in every elliptic curve based cyclic group and answer is not really. So there are certain curves which we should completely avoid for instantiating cryptographic primitives. So we cannot take the curves defined over Zp where the size of the curve or the number of points on the curve is exactly p which because there are well known algorithms for solving the DLog problems in those groups, so these such curves are called as anomalous curves. In the same way we should avoid curves where the size of the curve p + 1 which are called a super singular curves and we should also avoid curves where the size of the curve is pk - 1 for a small group. All these curves are cryptographically weak curves because as I said earlier the instances of DLog problem is very easy to solve in this group. That means if tomorrow you are proposing a new elliptic curve based modulo prime then we have to very rigorously analyze the security property of those elliptic curves before we take those elliptic curves and perform operations on those curves to instantiate any cryptography primitive say for example a Diffie Hellman key exchange protocol and it turns out that analyzing any newly proposed elliptical is a very challenging task. So an alternative that you can do is that you can trust and use any of the NIST recommended curves if for example P256 curve, curve 25519 which have been rigorously analyzed by NIST and they claim that they have not found any weaknesses in those curves in terms of solving the DLog problem that means there exists no polytime algorithms to solve the DLog problem for computing the DLog of any randomly given point on those curve. But you should trust the claim of NIST at your own risk and that is why when a government of any country tries to adopt any cryptographic primitive where the underlying cyclic group is based on elliptic curves then they become very skeptical of using or trusting the curves which are recommended by NIST because they believe that there might be some loopholes which only NIST knows, but it is not known in the public domain and that is why the government for such critical application pushes to come up with new curves and try to analyze those curves and use those curves for instantiating the cryptography primitives. But it turns out that for many practical purposes these curves are very popularly used for instantiating the elliptic curve and the cyclic groups for instantiating the cryptography primitives. So that brings me to the end of this lecture just to summarize in this lecture we have introduced the second class of cyclic groups where we believe the DLog, CDH and DDH problem to be difficult namely the cyclic groups based on elliptic curves modulo prime. The advantage of these groups compared to the cyclic groups Zp* multiplicative modulo p is that here the best known algorithms for solving DLog problem is of the order 2n/2. So we do not have to operate with very large modulus namely 2048 bit modulus which was the case for cyclic subgroups of Zp* its suffice to set the model as size to be 256 bits and we get the same level of security as you could expect from AES 128 and not only that the cyclic groups based on elliptic curves gives you another additional structure which we call as pairings which