Topic: On safety of ECDLP used in Bitcoin (Read 240 times)

Keep in mind do not confuse EC order n, which is number of EC points, with modulo p.

Strictly speaking, it is neither addition nor multiplication.
The operation defined over EC point group is called group law, I suggest you to learn some group theory basics before inventing your own interpretations.


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.

Not my thing to share. Sorry. But It will probably be published sometime.

Quite strange, because there is very little similarity and in maths usually things are not named based on "feelings". Imho

Not in the same sense. Yes, in adding points you do use mod, but the points themselves go only from 1 to n and never over n. (like they do in DLP)
 
Well. If your private key is bigger than n then your private key will be subtracted by n, but that is a different thing, since then your private key will actually be the smaller key...


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.

Would you mind to share it to us?
Yes, formally saying it hasn't. But it is called that way in the likeness and similarity.
And so you (may) do for EC points.
Sure, you can go over n.
It depends on what algorithm you do use.
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).

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.