Topic: Pollard's kangaroo ECDLP solver - page 22. (Read 60037 times)

Jean_Luc made his last post on October 11, 2020, and he was last active July 28, 2021 (more than 6 months ago). His last commits on github were also a year ago (February 2021)

Is everything ok with TC? (Jean_Luc)

maybe he created and testing, but not for public, as last found puzzle 115 by joint vent.. and those version were not publicly available...

How come no one has attempted to put a bloom filter on kangaroo. Kangaroo hasn't been updated of modified.


JeanLucPons commented on May 7, 2020
Yes, I added load/save/work
The multi key will be done with the help of theses new features.
The idea is to allow to pre compute large tame kangaroo file and to solve multiple key using this file.
Then when a key is solved, all the wild will become tame and more keys are solved more chance to solve the others....


JeanLucPons commented on May 8, 2020
Yes,
I will add some note about this on the readme. It is a bit tricky.
Multi key support is not yet supported, for this you will need first to create a large tame array for a given range and then attack keys with it.

What DP and range do you use?
Maybe it is related to BOLD statement from ReadMe file:

Please, read this: https://github.com/JeanLucPons/Kangaroo#note-on-timememory-tradeoff-of-the-dp-method

Maybe your system is just too fast for problem you launch for ;-)

Don't use cpu at all, -t 0
Check your grid size.
Also, if you use low dp setting with fast gpu, too many points enters main hashtable, this slows down overall speed.

Hello, I have a question.
I want to run a kangaroo using 4ea 3080ti graphics cards.

The option is...
-gpu -gpuId 0,1,2,3  findchk.txt
I use it like this.

It doesn't speed up as much as when you use a graphic card.
When using 1ex graphic card, speed is 1300 MK/s.

When using a 4ex graphic card, speed is 300Mk/s.

I don't know where it went wrong.
Thank you in advance.

The birthday paradox works on a similar principle d i don't know now i have pasted this code for fun

from bit import Key
for xx in range(1):
 q = 1
 for x in range(200):
  for y in range(170,200):
   probability = x / y
   q *= (1 - probability)
   p = 1 - q
   for cc in range(922,1845):
    x0 = ''.join(str(cc))
    x1 = ''.join(str(p))[2:]
    ke = Key.from_int(int(x0+x1))
    if (str(ke)).endswith("QN>"): # this print all bitcoin address they end big N> use this XQN> code run faster
     print(x0+x1,ke,x,y)
    if (str(ke)) == "":
     f=open("win.txt","a")
     f.write(str(x0+x1)+(str(ke))+"\n")
     f.close()

Hi

I already think about this method of searching for a collision between a temporary key (for example every intermediate wild kangaroo jump) and a lookup in a  hashtable of precomputed  random key in the range of puzzle 120.

Let-s do some math to show if it is realistic or not...

Imagine that you will precompute an huge hashtable (or a bloom filter) of 256 Gigas entries (or 256Giga  keys picked up at random in the puzzle 120 interval)

Forget the fact that this table will occupe several TerraBytes of RAM and that the lookup time will increases with the size of the hashtable (less true for a bloom filter look up).

The formula which defines the probability of finding a particular piece among N pieces at the end of n draw without replacement, is as follows:

P=1-(1-1/N)^n

we can replace 1/N by (number_entries_in_hashtable/interval_of_puzzle_120) =  256*10^9/(2^120-2^119) = 3.85e-25


We fixed  for example P=0.5 (means a probability of having an hit of 50%)

Let's calculate n for such P=0.5

0.5=(1-1/N)^n

a=b^n => n=ln(a)/ln(b)

n=ln(0.5)/ln(1-3.85e-25) = 1.8e24
if your GPU can do 1 billion  jumps (and lookup at the same time) per second (typically the speed of Jean-Luc pons program with a good GPU)

You will have to wait 1.8e24/1e9 = 1.8e15 seconds or  57 Millions of years before having 50% of having an hit...

Hopeless..., even if you uses a bigger hashtable or a powerfull GPU cloud.


The main problem of this approach is that you don't  profite of the birthday paradox used in the kangaroo solver because you look for in a predefined list.

Regards

Fanch

you share a copy of that one, ty

using 120 puzzles public key to generate a lot of keys and use that script random the more keys the better the chance to hit one
I just don't know if it can be generated with 1 public key more keys if so, it can be useful

I've redesigned it a bit now, I should , 2x faster for python

Hi
I can eventually convert this code using  my own secp256k1 library for CUDA (based on Jean Luc Pons Kangaroo ).

It can achieve up to 70M scalar mult /sec on a rtx 3070.

A python implementation with pycuda can be do easily

But sorry for this trivial question :
What the purpose of this script?

Regards

Fanch

I know this probably sounds very trivial but a good place to start optimization is to convert that Python code to C/C++ using Bitcoin's libsecp256k1 and libbitcoin (I think Bitcoin Core exports its address functions to libbitcoin).

Hi all this code guess random public key problem this code is slow play with it and try to improve and speed it up
code:
import collections
import random

EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')
# here we define our elliptic curve
curve = EllipticCurve(
    'secp256k1', # curve type
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Define the base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0x000000000000000000000000000000000000000000000000000000000000ffff,######important###### this manipulate public key maximum guess range up and down
    # Subgroup cofactor.
    h=1,)
# Modular arithmetics application
def inverse_mod(k, p):
    # Returns the inverse of k mod p
    # returns x such that (x * k) % p == 1
    # k <> 0 and p = prime
    if k == 0:
        raise ZeroDivisionError('division by zero') # zero division error!
    if k < 0:
        # k ** -1 = p - (-k) ** -1  (mod p)
        return p - inverse_mod(-k, p) # return the inverse
    # Extended Euclidean algorithm
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = p, k
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    gcd, x, y = old_r, old_s, old_t
    assert gcd == 1
    assert (k * x) % p == 1
    return x % p
# Functions applied on curve points
def is_on_curve(point):
    # Returns True if the given point lies on the elliptic curve
    if point is None:
        # None represents the point at infinity.
        return True
    x, y = point
    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
def point_neg(point):
    # Returns -point
    assert is_on_curve(point)
    if point is None:
        # -0 = 0
        return None
    x, y = point
    result = (x, -y % curve.p)
    assert is_on_curve(result)
    return result
def point_add(point1, point2):
    # Returns the result of (P1 + P2) according to the group law
    assert is_on_curve(point1)
    assert is_on_curve(point2)
    if point1 is None:
        # 0 + P2 = P2
        return point2
    if point2 is None:
        # P1 + 0 = P1
        return point1
    x1, y1 = point1
    x2, y2 = point2
    if x1 == x2 and y1 != y2:
        # P1 + (-P2) = 0
        return None
    if x1 == x2:
        # if (P1 == P2)
        m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
    else:
        # if (P1 != P2).
        m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
    x3 = m * m - x1 - x2
    y3 = y1 + m * (x3 - x1)
    result = (x3 % curve.p,
              -y3 % curve.p)
    assert is_on_curve(result)
    return result
def scalar_mult(k, point):
    # Returns (k * P) computed using the double-and-add algorithm
    assert is_on_curve(point)
    if k % curve.n == 0 or point is None:
        return None
    if k < 0:
        # k * P = -k * (-P)
        return scalar_mult(-k, point_neg(point))
    result = None
    addend = point
    while k:
        if k & 1:
            # Add
            result = point_add(result, addend)
        # Double
        addend = point_add(addend, addend)
        k >>= 1
    assert is_on_curve(result)
    return result
# Keypair generation and ECDHE
def make_keypair():
    # Generate random private-public key pair
    private_key = random.randrange(10000, curve.n)######important###### this equivalent start public key range manipulate this you up and down start public key range momental start is 10000 decimal
    public_key = scalar_mult(private_key, curve.g)
    return private_key, public_key
for xxx in range(1000000):
 aaaa_private_key, aaaa_public_key = make_keypair()
 bbbb_private_key, bbbb_public_key = make_keypair()
 if (str("02{:x}".format(*aaaa_public_key))).endswith("7a"):
  print("aaaa' private key:",hex(aaaa_private_key),"02{:x}".format(*aaaa_public_key),xxx)
 if (str("02{:x}".format(*aaaa_public_key))) == "029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a": #any public key use this line# i use test key
  f=open("von.txt","a")
  f.write(str(aaaa_private_key)+"<-decimal key-"+(str("02{:x}".format(*aaaa_public_key)))+"\n")
  f.close()
 if (str("02{:x}".format(*bbbb_public_key))).endswith("7a"):
  print("bbbb' private key:",hex(bbbb_private_key),"02{:x}".format(*bbbb_public_key),xxx)
 if (str("02{:x}".format(*bbbb_public_key))) == "029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a": #any public key use this line# i use test key
  f=open("von.txt","a")
  f.write(str(bbbb_private_key)+"<-decimal key-"+(str("02{:x}".format(*bbbb_public_key)))+"\n")
  f.close()
  # aaaa and bbbb now exchange their public keys and verify the shared secret
  s1 = scalar_mult(aaaa_private_key, bbbb_public_key)
  s2 = scalar_mult(bbbb_private_key, aaaa_public_key)
  assert s1 == s2

Let's wait, maybe NotATether will answer and dispel the myth.

This claim might be not true at all. If it's possible then, why he himself "NotATether" didn't calculate the private key for the puzzle transactions and withdraw its funds?

Alpaste
I also hold this opinion. But I doubted, re-reading the forum posts because NotATether claimed that it is possible to calculate ..
NotATether can dispel the myth?

I think it's impossible to calculate the upper bits of the key, even if you know that this private key lies in the 2^120 bits-range.
The only way to get the key, is to use kangaroo, or BSGS, but the chances that you find the key is extremely low.
Cheers!

Hi. I once asked the question of whether it is possible to calculate mathematically in which range the key is.
To which I received a response from NotATether.
If you know the range you can calculate the upper bits of the key.
The question logically asks for answers.
If we know, and we know in what range the key lies (like puzzle 120).
Then why not calculate the upper bits?
What is the calculation algorithm?
Thanks.

Can possible do calculate kangaroo by do manual ?
puzzle120 I would like to try my range by do manual made kangaroo

tame and wild is public key (point) and do multiply to number right?
I will try do python script  generate tame and wide each one a million line of set
and compare it both by manual too