Using Pollards Kangaroo on an Weierstrass curve

kangaroo_ecc.py

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