Topic: Pollard's kangaroo ECDLP solver - page 116. (Read 58667 times)
congrats to Zielar
Good job! Jean_LUc, your program is very good!
Did zielar confirmed he solved it? Congrats to him as well!
Did zielar confirmed he solved it? Congrats to him as well!
congrats to zielar 
congrats to the winner, what a man,
cheers from amsterdam, nl.
cheers from amsterdam, nl.
congratulation to the solver
what i do not understand why zielar is not solve key yet..
with him power he can already done 4*sqrt(n) simply.
I left the race because I feel like something is wrong here.
It’s not a compute only problem. It’s a compute, storage, and network bandwidth problem when you place solving time constraints on large intervals. Hopefully after he solves it, he will disclose the resources used and any challenging issues that he had to overcome. with him power he can already done 4*sqrt(n) simply.
I left the race because I feel like something is wrong here.
what i do not understand why zielar is not solve key yet..
with him power he can already done 4*sqrt(n) simply.
I left the race because I feel like something is wrong here.
there is no negative no positive, there is reverse point in other zone, it is not important zone is connect each other, like pubkey for x is same as ffff....4140 but y is difrent till 128 bit range zone, if you see at last of 128 bit range, last key you match reverse in fff...128bit minus zone, very next key you cant match it in next zone, but i can calc where that key zone will be exist, for detail of experiment i will write with examples later with him power he can already done 4*sqrt(n) simply.
I left the race because I feel like something is wrong here.
what i do not understand why zielar is not solve key yet..
with him power he can already done 4*sqrt(n) simply.
I left the race because I feel like something is wrong here.
with him power he can already done 4*sqrt(n) simply.
I left the race because I feel like something is wrong here.
Any body know if it is possible to know point is positive or negative? Or it is imposssible to know?
Only after solving the DL for that point, otherwise it would be trivial to solve the DLP on that curve. In a way, there are no negative or positive points because of the modular group.There are no negative or positive points, because -1 = n-1 mod n, -1 'looks' negative and n-1 'looks' positive, but the point is the same.
It is not correct to think at this group like a line, it is more correct to think at it like a circle (that means 'modular' and 'cyclic group'). There are not concepts like "come before" or "follow", it doesn't make any sense say that a point P "comes before" Q , then there are no negative (before zero) or positive (after zero) points.
Any body know if it is possible to know point is positive or negative? Or it is imposssible to know?
Only after solving the DL for that point, otherwise it would be trivial to solve the DLP on that curve. In a way, there are no negative or positive points because of the modular group.Code:
#3-5=-2
#3
ptX=0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
ptY=0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
#5
ptsubX=0x2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
ptsubY=0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
sub_point = (ptsubX, (p-ptsubY))
print ("sub_point= (%x,%x)" % sub_point)
result = addpt((ptX,ptY),sub_point, p)
print ("result_point= (%x,%x)" % result)
As you can see Y coordinate is not the same as for 2, because 2 is
(c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5,1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a)
So we can say that (c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5,e51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705)
is negative point on curve and
(c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5,1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a)
is positive. But any way if there no way to get sign it is no matter.
Any body know if it is possible to know point is positive or negative? Or it is imposssible to know?
Only after solving the DL for that point, otherwise it would be trivial to solve the DLP on that curve. In a way, there are no negative or positive points because of the modular group.
Any body know if it is possible to know point is positive or negative? Or it is imposssible to know?
-snip-
Perhaps there is an implementation in C++ or Python code?
A negative point is the same point only with a negative coordinate YPerhaps there is an implementation in C++ or Python code?
In python i use operator.neg(point_y))%p then ordinary addplt
p in your case is modulo of the curve.
To be honest operation (p-y) is faster than (-y)%p/ I have just tested for random 100 million 256bit numbers just the subtraction (p-y) and division by modulo (-y)%p --> division by modulo took 1.4527 longer
-snip-
Perhaps there is an implementation in C++ or Python code?
A negative point is the same point only with a negative coordinate YPerhaps there is an implementation in C++ or Python code?
In python i use operator.neg(point_y))%p then ordinary addplt
If you know how to add - it is enough to perform the subtraction:
M = P - Q = P + (-Q) - here M point is P point minus Q point, which is the same as P point plus (-Q) point. So you make the addition of points P and (-Q).
If Q point has coordinates (Qx, Qy), so (-Q) point will have coordinates (Qx, modulo - Qy)
Now you can easily can make a subtraction:
M = P - Q = (Px, Py) - (Qx, Qy) = (Px, Py) + (Qx, modulo - Qy)
Perhaps there is an implementation in C++ or Python code?
python
Code:
p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F #field
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #curve
def inv(a,p):
u, v = a%p, p
x1, x2 = 1, 0
while u != 1 :
q = v//u
r = v-q*u
x = x2-q*x1
v = u
u = r
x2 = x1
x1 = x
return x1%p
def add(ax, ay, bx, by): #A + B -> C
bxax_inv = inv(bx-ax, p) #1/(x2-x1)
m = ( (by-ay) * bxax_inv ) % p #m = (y2-y1)/(x2-x1)
cx = (m*m - ax - bx) % p
cy = (m * (ax - cx) - ay) % p
return cx, cy
def sub(ax, ay, bx, by,): #A - B -> C
bxax_inv = inv(bx-ax, p) #1/(x2-x1)
m = ((p-by-ay) * bxax_inv) % p #m = (-y2-y1)/(x2-x1)
cx = (m*m - ax - bx) % p
cy = (m * (ax - cx) - ay) % p
return cx, cy
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #curve
def inv(a,p):
u, v = a%p, p
x1, x2 = 1, 0
while u != 1 :
q = v//u
r = v-q*u
x = x2-q*x1
v = u
u = r
x2 = x1
x1 = x
return x1%p
def add(ax, ay, bx, by): #A + B -> C
bxax_inv = inv(bx-ax, p) #1/(x2-x1)
m = ( (by-ay) * bxax_inv ) % p #m = (y2-y1)/(x2-x1)
cx = (m*m - ax - bx) % p
cy = (m * (ax - cx) - ay) % p
return cx, cy
def sub(ax, ay, bx, by,): #A - B -> C
bxax_inv = inv(bx-ax, p) #1/(x2-x1)
m = ((p-by-ay) * bxax_inv) % p #m = (-y2-y1)/(x2-x1)
cx = (m*m - ax - bx) % p
cy = (m * (ax - cx) - ay) % p
return cx, cy
If you know how to add - it is enough to perform the subtraction:
M = P - Q = P + (-Q) - here M point is P point minus Q point, which is the same as P point plus (-Q) point. So you make the addition of points P and (-Q).
If Q point has coordinates (Qx, Qy), so (-Q) point will have coordinates (Qx, modulo - Qy)
Now you can easily can make a subtraction:
M = P - Q = (Px, Py) - (Qx, Qy) = (Px, Py) + (Qx, modulo - Qy)
Perhaps there is an implementation in C++ or Python code?
How did you manage to get it down to 16 bytes per point?
@BitCrackI am storing only 8bytes of the x-coordinate and lookup information (8bytes with HT overhead included) on how to retrieve the rest of the information in the event of a collision. This is accomplish by using a custom version of Google’s Sparse_Hash_Set in a distributed setup. The cost is network bandwidth but all clients are on a 1 GigE network.
https://github.com/sparsehash/sparsehash
Maybe with a Bloom filter you can save more space ...
Hardware, how long are you running your precomp for? You have a set # of DPs or a percentage? 2/3 ops?
@WanderingPhilospherThe goal is ~512GiB worth of precomputed points (@ 16bytes/point).
How much bytes do you have for x-coordinate and for distance?
For the whole distance in 109bit range we need 109/8 ~ 14 bytes. If you allocate lower space, you need to brute the remaining bytes/bits if the collision is found.
If you have 16 bytes space per point, so you should split somehow it between x-coordinate and distance.
@MrFreeDragon
Please see my previous comment. Only 8bytes of the x-coordinate is needed plus ~4bytes for lookup information.
How did you manage to get it down to 16 bytes per point?
@BitCrackI am storing only 8bytes of the x-coordinate and lookup information (8bytes with HT overhead included) on how to retrieve the rest of the information in the event of a collision. This is accomplish by using a custom version of Google’s Sparse_Hash_Map in a distributed setup. The cost is network bandwidth but all clients are on a 1 GigE network.
https://github.com/sparsehash/sparsehash
Jump to: