https://gist.github.com/natmchugh/e094232a3975b89bff2d

Quote from: itod on August 04, 2019, 09:37:06 PM

Quote from: zielar on August 04, 2019, 04:34:43 PM

...
The problem is the initial stage, because python error:

Code:

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 :-)

In terminal:

Code:

pip install ecc

lol, not so simple

Its used import some old version(maybe clone) ecdsa library (there are also "class Point")
Also we can use raw.githubusercontent.com/andreacorbellini/ecc/master/logs/common.py
Also we can use raw.githubusercontent.com/qubd/mini_ecdsa/master/mini_ecdsa.py
(mini_ecdsa need some fix for python3)
(and it lib have own pollard-rho! but dont try run it for secp256k1, need custom ecc with low order! example look at homepage)
Also we can use the fastest coincurve github.com/ofek/coincurve

######

Fact: origin basepoint in code is currupted.. and origin value some exotics..

Code:

if self.__curve: assert self.__curve.contains_point( x, y )
AssertionError

######

Its code is classic/early/not_optimized kangaroo

- not use distinguished points
- total run-time of approximately 3.28(w^(1/2)) group operations

######

Who cares, i builded 4 realease with each lib
www.sendspace.com/file/wdyg2o
here the fastest based coincurve
------------------------------------
update, add cffi, +30% speed
get X,Y using .point() is slow, cffi faster

Code:

coincurve: 30528.2 j/s
cffi+coincurve: 41165.6 j/s

Code:

from cffi import FFI
ffi = FFI()
...
#x,y = Y.point()
tmp_pubkey = ffi.buffer(Y.public_key, 64)[:]
#x = bytes_to_int(tmp_pubkey[31::-1]);
y = bytes_to_int(tmp_pubkey[:31:-1]);

------------------------------------

Code:

#!/usr/bin/python

# [windows:python -m] pip install coincurve
from coincurve import PrivateKey as ECprvKey, PublicKey as ECpubKey
from coincurve.utils import int_to_bytes, hex_to_bytes, bytes_to_int, bytes_to_hex, int_to_bytes_padded

from cffi import FFI
ffi = FFI()

#####################
# secp256k1
A = 0
B = 7
p = 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
k = 15

#Gx,Gy = ECpubKey.from_valid_secret(int_to_bytes_padded(1)).point()

#####################
#
# PublicKey(data(bytes))
ecc = ECpubKey

G = ecc.from_point(Gx, Gy) # basePoint

#####################

import random
#prvkey = random.randint(1, n-1)
prvkey = random.randint(1, 2**20) # for pollard kangaroo

print('[privkey] %s (%s)' % (prvkey, hex(prvkey)))

pubkey = G.multiply(int_to_bytes(prvkey))

#####################

def f(Y):
#x,y = Y.point()
tmp_pubkey = ffi.buffer(Y.public_key, 64)[:]
#x = bytes_to_int(tmp_pubkey[31::-1]);
y = bytes_to_int(tmp_pubkey[:31:-1]);
return pow(2, (y % k))

a = prvkey - pow(2, 20)
b = prvkey + pow(2, 20)

print('a = %s' % a)
print('b = %s' % b)
print('k = %s' % 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 = G.multiply(int_to_bytes(b))

y = pubkey

N = ( f(G) + f(G.multiply(int_to_bytes(b)))) / 2 * 2
N = int(N)

for i in range(1, N):
   xT += f(yT)
   yT = ecc.combine_keys([yT, G.multiply(int_to_bytes(f(yT)))]);

print(" %s %s" % (xT, yT.point()))

"""
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, G, b, a):
   xW = 0
   yW = y
   while xW < (b - a + xT):
   xW += f(yW)
   yW = ecc.combine_keys([yW, G.multiply(int_to_bytes(f(yW)))]);

   if yW == yT:
   print(' Catch: %s %s' % (yW.point(),yT.point()))
   return b + xT - xW

   print("Not found.")

A = wildKangaroo(ecc, y, yT, xT, G, b, a)
print(" b + xT - xW = %s (%s)" % (A, hex(A)) )