The x coordinate and y coordinate are both binary numbers in the range 2256.
the max is also a little bit less than 2
256 but unlike private keys the max is defined by P (the prime) not N (the curve order)
After reading over the description of
Pollard's kangaroo algorithm I think I understand it enough to be able to explain it to my 13 year old daughter so she can write the code as a fun educational exercise. She is always looking for a good subject for her next science fair project and I think this would make a good one.
I have some questions about the PRF that someone might be able to answer.
The only requirements listed in the article above are:
1) The PRF must map the finite cyclic group to "a set S of integers"
2) The PRF must be able to be changed in order to select a different S in order to create subsequent "kangaroos"
Since the length of the pseudorandom sequence is not specified I assumed 256 bits, is that reasonable?
So, it seems to me that f(X) = SHA256(X || nonce) where X is the binary representation of the the point X, || represents the concatenation operation, and the nonce is selected from a TRNG or is simply incremented would do the trick.
However this seems to be overkill and we want to do this as fast as possible.
Another option that comes to mind is to just define f(X) = (X + nonce) where X is the binary representation of the compressed form of X and the nonce is selected from a TRNG or is simply incremented.
What PRF is generally used?
Now that I think about this I think the science fair project could be something along the lines of measuring the conversion speed of various PRFs and PRF modification algorithms. The data set would be all the cracked addresses in this thread, the independent variable would be various PRFs and different ways of modifying them to produce the next "kangaroo", and the dependent variable would be the total time it takes to re-crack all the known cracked addresses listed in this thread.
The idea is awesome!
I'm happy to wait for the effect...
Meanwhile, digging up the finds - I found this code:
import random
from Ecc import Ecc
from Ecc import Point
A = -95051
B = 11279326
p = 233970423115425145524320034830162017933
q = 233970423115425145498902418297807005944
ecc = Ecc(A, B, p)
def f(Y):
(x, y) = Y.coords()
return pow(2, (y % k))
priv = random.randint(0, q)
print 'You will never guess my private key of %s' % priv
basePoint = Point(4, 85518893674295321206118380980485522083)
pub = ecc.scale(basePoint, priv)
a = priv - pow(2, 20)
b = priv + pow(2, 20)
print 'a',a
print 'b',b
global k
k = 15
print 'k is set to %d' % k
"""
Tame Kangaroo
xT := 0
yT := g^b
for i in 1..N:
xT := xT + f(yT)
yT := yT * g^f(yT)
"""
xT = 0
yT = ecc.scale(basePoint, b)
y = pub
N = ( f(basePoint) + f(ecc.scale(basePoint, b))) / 2 * 2
for i in range(1, N):
xT += f(yT)
yT = ecc.add(yT, ecc.scale(basePoint, f(yT)));
print xT, yT
"""
Wild Kangaroo
xW := 0
yW := y
while xW < b - a + xT:
xW := xW + f(yW)
yW := yW * g^f(yW)
if yW = yT:
return b + xT - xW
"""
print "Setting wild kangaroo off"
def wildKangaroo(ecc, y, yT, xT, basePoint, b, a):
xW = 0
yW = y
while xW < (b - a + xT):
xW = xW + f(yW)
yW = ecc.add(yW, ecc.scale(basePoint, f(yW)));
if yW == yT:
print 'catch'
print yW, yT
return b + xT - xW
A = wildKangaroo(ecc, y, yT, xT, basePoint, b, a)
print A
The problem is the initial stage, because python error:
Traceback (most recent call last):
File "polard3.py", line 2, in
from Ecc import Ecc
ImportError: cannot import name Ecc
Uncle Google has no idea how to get out of it :-)
it does not make sense
