Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
arulbero
on 27/05/2020, 15:29:59 UTC
-snip-
1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)
-snip-

I know that EC collision is not proved as there is no example.
Yes, for each private key there is only 1 point, however not necessary that if we have n private key we will have n different points.

Simple example for the group of 10 elements:
Code:
Key   Point
1       7
2       6
3       5
4       7
5       3
6       2
7       7
8       0
9       9
0       7

You can see that for each key (0..9) there is only one Point, i.e. we do not receive 2 or 3 or more points for each key. We have only one point. However key 1,4,7 and 0 lead to Point 7 (collision). For group of 10 elements it is easy to check.

However how could you be sure that for group with almost 2^256 elements for every private key we have the unique Point?

'Group' has a specific meaning in math, it is not a simple set of elements, moreover a group with a prime number of elements has the property to be cyclic, i. e. you can 'generate' each element using one element of the group (not zero) and adding it to itself: G, G+G, G+G+G, .....  it is like to assign a number, a order to each element from the point of view of G.

In the secp256k1 the group is a group of point, a cyclic group, and the private key is the order of all points from the point of view of G (a chosen point). Because it is cyclic, if you perform G, G+G=2*G, G+G+G=3*G, ...., you generate all the elements before the return to G.

If you apply the Fermat's little theorem in a additive group, a*(n+1) = a, a+a+a+a+a....+a=a  and
 (n+1)*G = G.