Pollard's kangaroo ECDLP solver

[CrunchyF]

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

[1714478471]

1714478471

[1714478471]

1714478471

[1714478471]

1714478471

[1714478471]

1714478471

[1714478471]

1714478471

[1714478471]

1714478471

[Feron]

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

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

[dextronomous]

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

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

you share a copy of that one, ty

[CrunchyF]

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

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

[Feron]

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

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

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)) == "<PrivateKey: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN>":
     f=open("win.txt","a")
     f.write(str(x0+x1)+(str(ke))+"\n")
     f.close()

[bjpark]

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.

[_Counselor]

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.

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.

[PawGo]

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.

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

Powerful GPUs with large number of cores won't be very efficient on small range, you can try to decrease the grid size in order to have less kangaroos but the GPU performance may not be optimal.

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

[bjpark]

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.

_Counselor
PawGo

Thank you so much.
Thanks to you, I'm doing well on the test.
I wish you all the best.

[bigvito19]

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.

[brainless]

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.

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

[MrFreeDragon]

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)

[PawGo]

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)

I think he is just not interested anymore, as #120 seems to be unsolvable in reasonable time with the current software & hardware.
I do not know, maybe there were other tensions, maybe some users wanted to use him as a free source of tools to crack bitcoin. No idea, but reading his topics I see there were many demanding ignorant.
Or maybe he is still here, using other account. Who knows.

[paniker]

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

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

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)) == "<PrivateKey: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN>":
     f=open("win.txt","a")
     f.write(str(x0+x1)+(str(ke))+"\n")
     f.close()

Hello i was playing with reverse brut on 62-63? but not so fast as they found it it interesting
i try to change ranges in:
(for y in range(170,200)
 ( for cc in range(922,1845): )  

and got strange results.
only even numbers on end (...99679470) (..00198327750)

and it's going not random, searching 1 by1

[BorisTheHorist]

I found a method to find any private key within 2^255 bit space. Is that new?

[paniker]

I found a method to find any private key within 2^255 bit space. Is that new?

Can you tells us more about it?))

[bigvito19]

I found a method to find any private key within 2^255 bit space. Is that new?

Depends on what the method is, what is the method?

[Alpaste]

I found a method to find any private key within 2^255 bit space. Is that new?

Fake! Don't trust anything like this.

[wedom]

I found a method to find any private key within 2^255 bit space. Is that new?

Tell us if you've already decided to brag  

Upd. Better yet, just prove it. I generated a random key. Here is the public key for it
0337aff652dd11e2870636b0c4ce4fb324f4b0df45e70f7d8c77d15fcc9ae73525

[BorisTheHorist]

I found a method to find any private key within 2^255 bit space. Is that new?

Can you tells us more about it?))

Absolutely, so it seems that the amount of valid public x-coords is exactly half the amount of private keys.
So as the theory is any key in the full range (1-115792089237316195423570985008687907852837564279074904382605163141518161494336 ~2^256) either it is less than half (57896044618658097711785492504343953926418782139537452191302581570759080747168) or has the same x coordinate as one that does (above 57896044618658097711785492504343953926418782139537452191302581570759080747169).

I have a mathematical function to find the resulting twin on either side.
I really do like the work that has been done here on the Kangaroo software so I will provide my python function for reference of finding said twin so long as you know 1 of 2 private keys you will know both.

~2^255 is still a very large number.
In the case of uncompressed keys you still have to compute the y coord after but it is trivial.
(using the bit library for python as the function is not intensive)

from bit import Key
import secrets
def twin(i, pubhex):
    max = 115792089237316195423570985008687907852837564279074904382605163141518161494336
    if len(pubhex) == 66:
        publichex = str(pubhex)[2:66]
        if i < 57896044618658097711785492504343953926418782139537452191302581570759080747169:
            twin = max - (i-1)
            if str(pubhex)[:2] == '02':
                twinprefix = '03'
                return [twin,f'{twinprefix}{publichex}']
            elif str(pubhex)[:2] == '03':
                twinprefix = '02'
                return [twin, f'{twinprefix}{publichex}']
        elif i > 57896044618658097711785492504343953926418782139537452191302581570759080747168:
            twin = 1 + (max-i)
            if str(pubhex)[:2] == '02':
                twinprefix = '03'
                return [twin,f'{twinprefix}{publichex}']
            elif str(pubhex)[:2] == '03':
                twinprefix = '02'
                return [twin,f'{twinprefix}{publichex}']
    elif len(pubhex) == 130:
        publichex = str(pubhex)[2:66]
        if i < 57896044618658097711785492504343953926418782139537452191302581570759080747169:
            twin = max - (i-1)
            return [twin,f'uncomp,{publichex}']
        elif i > 57896044618658097711785492504343953926418782139537452191302581570759080747168:
            twin = 1 + (max-i)
            return [twin, f'uncomp,{publichex}']

max = 115792089237316195423570985008687907852837564279074904382605163141518161494336
for x in range(100):
    q = secrets.randbelow(max)
    k = Key.from_int(x)
    t = twin(x,k.pub_to_hex())
    pt = t[0]
    ptpub = Key.from_int(pt).pub_to_hex()
    print(t[1],ptpub)

'''
# Or you can do this
for x in range(1000):
    x = secrets.randbelow(max)
    k = Key.from_int(x)
    t = twin(x,k.pub_to_hex())
    pt = t[0]
    ptpub = Key.from_int(pt).pub_to_hex()
    assert t[1] == ptpub
'''

'''
# for uncompressed
for x in range(100000):
    x = secrets.randbelow(max)
    k = Key.from_int(x)
    k._public_key = k._pk.public_key.format(compressed=False)
    t = twin(x,k.pub_to_hex())
    pt = Key.from_int(t[0])
    # this next line is not nessicary as we format the response without the leading '04'
    pt._public_key = pt._pk.public_key.format(compressed=False)
    ptpub = pt.pub_to_hex()
    assert t[1] == f'uncomp,{str(ptpub)[2:66]}'
'''