Title: On safety of ECDLP used in Bitcoin Post by: aplistir on May 10, 2018, 01:25:35 PM I recently reviewed an interesting work about solving ECDLP (that Bitcoin uses too.)
Most people think we will need a quantum computer(QC) for cracking ECC, but I am not so sure about it anymore. Conventional methods may prove to be good enough. Bitcoin uses "Elliptic Curve Discrete Logarithm Problem" (ECDLP). But why is it called Discrete Logarithm Problem? It has nothing to do with DLP. Apparently someone thought that ECC would sound COOLER and SAFER if it is called DLP! And hence the DLP. In DLP we try to solve x in equations like this: 6^x ≡ 8 mod 11. It is hard (with big numbers) because 6^x can get quite big, many times bigger than the (mod 11) and you will have to subtract 11 many many times. eg. 6^7= 279936 =8 mod 11. That makes it hard to "guess" x and you will have to try different x values to find the correct one. In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve. So basically we try to solve x (x=private key) from x*G=P , where G is point representing 1 in this system and P is the public key point, and x is always between 1 and n. The possible weakness comes from the fact that we NEVER go over the order n of the curve. Unlike in DLP, which goes over the "order" (=11 in the example above) many many many times. Because we always stay between 1 and n, we are not really dealing with DLP and some possibilities arise. Odd or even. If we can reliably know if a point is odd or even, we can also break ECC. One point about Finite fields is that they do NOT hide if a number is odd or even. For example. Finite field of 11 points. 0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8... If we ALWAYS stay in the first "round" of the field 0-10 (like we do in ECC) the numbers are as they are. 1,3,5,7,9 are odd, 2,4,6,8,10 are even. So even if odd and even are not really defined inside finite fields, when we stay in the first "round", then odd and even work like they do in the real world. If we go to the second "round" then odd and even would flip around. eg. odd number 13=13 mod 11=2 which "looks" like an even number. But we never go there, because we are actually not dealing with a DLP problem. Luckily for the safety of Bitcoin, Bitcoin uses coordinate points instead of numbers. Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done? If you divide the point by 2 it will of-course behave differently depending on if the point is odd or even, but since the result is symmetrical this wont lead very far. But the conclusion was that they did not get it to work, and ECC is still safe. FOR NOW. Wonder if this kind of work is the reason NSA stopped recommending ECC. Title: Re: On safety of ECDLP used in Bitcoin Post by: DevilOper on May 10, 2018, 04:32:40 PM I recently reviewed an interesting work about solving ECDLP Would you mind to share it to us?Quote It has nothing to do with DLP. Yes, formally saying it hasn't. But it is called that way in the likeness and similarity.Quote ...to solve x in equations ... you will have to subtract 11 many many times And so you (may) do for EC points.Quote In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve. Sure, you can go over n.It depends on what algorithm you do use. Quote Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done? Scalar division (as well as multiplication) is not defined for EC math. So basically dividing by 2 has the same complexity as dividing by any other number x (and thus solving ECDLP).If you divide the point by 2 ... Title: Re: On safety of ECDLP used in Bitcoin Post by: aplistir on May 10, 2018, 10:49:43 PM I recently reviewed an interesting work about solving ECDLP Would you mind to share it to us?Quote from: DevilOper Quote It has nothing to do with DLP. Yes, formally saying it hasn't. But it is called that way in the likeness and similarity.Quote from: DevilOper Quote ...to solve x in equations ... you will have to subtract 11 many many times And so you (may) do for EC points.Quote from: DevilOper Quote In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve. Sure, you can go over n.It depends on what algorithm you do use. Quote from: DevilOper Quote Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done? If you divide the point by 2 ... Scalar division (as well as multiplication) is not defined for EC math. So basically dividing by 2 has the same complexity as dividing by any other number x (and thus solving ECDLP). Here you are wrong. You certainly CAN multiple an ECC point with a number. That is what you do when you multiple a point with your private key to get the public key. Dividing with a number is also possible. Even though it is almost never mentioned anywhere. IT is possible. I can do it, and if you understand finite fields, so can you. What you cannot do is multiplying a point with a point, or dividing a point by a point. That is a completely different thing and is not defined in EC. Title: Re: On safety of ECDLP used in Bitcoin Post by: DevilOper on May 11, 2018, 02:18:43 AM Quote from: DevilOper Quote In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve. Sure, you can go over n.It depends on what algorithm you do use. Quote from: DevilOper Quote ...to solve x in equations ... you will have to subtract 11 many many times And so you (may) do for EC points.Quote from: DevilOper Quote Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done? If you divide the point by 2 ... Scalar division (as well as multiplication) is not defined for EC math. So basically dividing by 2 has the same complexity as dividing by any other number x (and thus solving ECDLP). Here you are wrong. You certainly CAN multiple an ECC point with a number. That is what you do when you multiple a point with your private key to get the public key. Dividing with a number is also possible. Even though it is almost never mentioned anywhere. IT is possible. I can do it, and if you understand finite fields, so can you. What you cannot do is multiplying a point with a point, or dividing a point by a point. That is a completely different thing and is not defined in EC. The operation defined over EC point group is called group law, I suggest you to learn some group theory basics (https://en.wikipedia.org/wiki/Group_(mathematics)) before inventing your own interpretations. Quote from: DevilOper Quote It has nothing to do with DLP. Yes, formally saying it hasn't. But it is called that way in the likeness and similarity.The similarity is quite obvious. When you do exponentiation, you actually calculate X power of n as Y = X•X•....•X n times. So finding n is finding logarithm of Y. When you do scalar multiplication by n on EC, you calculate it as Q = G•G•...•G n times. Where "•" - is a group law. Thus finding n is similarily named as finding (digital) logarithm of Q. |