Pollard's kangaroo ECDLP solver

[COBRAS]

The kangaroo server is live! DP 25 and currently at DP 2^24.229/2^35.55. The server handles all user Kangaroo backups and work saves, join the discord for more information: https://discord.gg/DjMksx8wqr

we also need to have an open discussion on the best way to split the prize for all involved on the server.

How long more you will be brute ?

Good lack !

[1714490508]

1714490508

[1714490508]

1714490508

[1714490508]

1714490508

[1714490508]

1714490508

[1714490508]

1714490508

[COBRAS]

The kangaroo server is live! DP 25 and currently at DP 2^24.229/2^35.55. The server handles all user Kangaroo backups and work saves, join the discord for more information: https://discord.gg/DjMksx8wqr

we also need to have an open discussion on the best way to split the prize for all involved on the server.

Bro, try downgrade range for 5bits, from 120 to 115, you get f 32 public keys with guaranteed 1 pubkey in range 115.

[yoyodapro]

The kangaroo server is live! DP 25 and currently at DP 2^24.229/2^35.55. The server handles all user Kangaroo backups and work saves, join the discord for more information: https://discord.gg/DjMksx8wqr

we also need to have an open discussion on the best way to split the prize for all involved on the server.

Bro, try downgrade range for 5bits, from 120 to 115, you get f 32 public keys with guaranteed 1 pubkey in range 115.

The kangaroo server can only search for 1 public key at a time, we would have to run the server 32 times for that to work which will take longer than just searching for 120 natively

[COBRAS]

The kangaroo server is live! DP 25 and currently at DP 2^24.229/2^35.55. The server handles all user Kangaroo backups and work saves, join the discord for more information: https://discord.gg/DjMksx8wqr

we also need to have an open discussion on the best way to split the prize for all involved on the server.

Bro, try downgrade range for 5bits, from 120 to 115, you get f 32 public keys with guaranteed 1 pubkey in range 115.

The kangaroo server can only search for 1 public key at a time, we would have to run the server 32 times for that to work which will take longer than just searching for 120 natively

yes... but I think 1000 pubkeys in range 100 will be faster then 1 in 120 ?

[WanderingPhilospher]

The kangaroo server is live! DP 25 and currently at DP 2^24.229/2^35.55. The server handles all user Kangaroo backups and work saves, join the discord for more information: https://discord.gg/DjMksx8wqr

we also need to have an open discussion on the best way to split the prize for all involved on the server.

Bro, try downgrade range for 5bits, from 120 to 115, you get f 32 public keys with guaranteed 1 pubkey in range 115.

The kangaroo server can only search for 1 public key at a time, we would have to run the server 32 times for that to work which will take longer than just searching for 120 natively

yes... but I think 1000 pubkeys in range 100 will be faster then 1 in 120 ?

Cobras does not read...it's been explained in this thread

It would take 1,024 (2^10) pubkeys to get down to the 110 bit range

119/2 + 1 = 60.5
109/2 + 1 = 55.5; 2^55.5 * 2^10 (number of pubkeys you have to run/check) = 2^65.5
2^65.5 > 2^60.5

[BitcoinADAB]

...
yes... but I think 1000 pubkeys in range 100 will be faster then 1 in 120 ?

If you downgrade to range 100, you will have ~1,000,000 pubkeys and only 1 of them is the right one.
You would have to calculate far more than the original one in #120.

[yoyodapro]

...
yes... but I think 1000 pubkeys in range 100 will be faster then 1 in 120 ?

If you downgrade to range 100, you will have ~1,000,000 pubkeys and only 1 of them is the right one.
You would have to calculate far more than the original one in #120.

^^

[COBRAS]

...
yes... but I think 1000 pubkeys in range 100 will be faster then 1 in 120 ?

If you downgrade to range 100, you will have ~1,000,000 pubkeys and only 1 of them is the right one.
You would have to calculate far more than the original one in #120.

YeEyYas  Bro, not 1000 for 10 bits but 1000000 = 32(120->115)*32(115-110) etc...

[brainless]

maybe your all calc wrong, giving you example
generate 70 bit random key, and use kanagroo to find it, note the time
then split 70 bit 65 bit with 32 keys and try to find one by one in 65 bit and note time,
then split 70 bit 65 bit with 32 keys and try to find 32 keys parallel in 65 bit and note time,
you will have time calc result

[WanderingPhilospher]

maybe your all calc wrong, giving you example
generate 70 bit random key, and use kanagroo to find it, note the time
then split 70 bit 65 bit with 32 keys and try to find one by one in 65 bit and note time,
then split 70 bit 65 bit with 32 keys and try to find 32 keys parallel in 65 bit and note time,
you will have time calc result

Why run the test when you have an average/expected run time calculation?
Running your test, you would have to set -m option to 1.x or 2.x to ensure you find key if it is the key that is in the range; expected/average can sometimes go over the 50% mark.
You can run parallel only if you have 32 GPUs and run a different program.

Granted, if the key is in the 0 or 1 spot, you would definitely save some minutes at 65 bit range, but 120 bit range is a different monster, way bigger bit range and who wants to chance it?

[COBRAS]

maybe your all calc wrong, giving you example
generate 70 bit random key, and use kanagroo to find it, note the time
then split 70 bit 65 bit with 32 keys and try to find one by one in 65 bit and note time,
then split 70 bit 65 bit with 32 keys and try to find 32 keys parallel in 65 bit and note time,
you will have time calc result

@brainless, you realy can downgrade 120 bit to 110 bit or 105bit and get exact 1 public key only vs. many pubkeys ? 

[NotATether]

Guys, take a look at this: https://link.springer.com/content/pdf/10.1007/s11227-020-03441-5.pdf

A faster modular multiplication implementation for the P-192 curve.

Granted this is the wrong curve, but it has the same general formula y2 = x3+ax+b, so all that theoretically has to be done is to extend the summations to a few extra terms (they'll just be 32 words instead of 24, which means a 32x32 word multiplication size instead of 24x24) and accommodate for the missing ax.

E.g. where it defines range shifted representation (RSR) of a large number, which it uses in the algorithm:

Code:

X = ∑ i=0,i=23 xiWi−12 = x0W−12 + x1W−11 + ⋯ + x23W11,
Y = ∑i=0,i=23 yiWi−12 = y0W−12 + y1W−11 + ⋯ + y23W11,
Z = X ⋅ Y = ∑i=0,i=47 ziWi−24 = z0W−24 + z1W−23 + ⋯ + z47W23

We can just replace it with this:

Code:

X = ∑ i=0,i=31 xiWi−16 = x0W−16 + x1W−15 + ⋯ + x31W15,
Y = ∑i=0,i=31 yiWi−16 = y0W−16 + y1W−15 + ⋯ + y31W15,
Z = X ⋅ Y = ∑i=0,i=63 ziWi−32 = z0W−32 + z1W−31 + ⋯ + z63W31

(x, y, z summation terms are all between 0 and 255 inclusive)

Then the rest of the modular multiplication follows suit.

They say it's 26% faster than the usual ECC multiplication algorithm. I wonder if this representation also handles modular addition well. If it does, then we got ourselves a faster way to do modular arithmetic.

The study was carried out on some 8-bit embedded machine. Modern pipelines stuff 64 bits in a register so we may even be able to reduce the number of RSR words by a factor of 8 i.e. only 2 x and y words and 4 z words (and ovbiously the maximum range of each word increases proportionally).

[wedom]

maybe your all calc wrong, giving you example
generate 70 bit random key, and use kanagroo to find it, note the time
then split 70 bit 65 bit with 32 keys and try to find one by one in 65 bit and note time,
then split 70 bit 65 bit with 32 keys and try to find 32 keys parallel in 65 bit and note time,
you will have time calc result

Jean_Luc planned to release a new version (after solved #115), where it will be possible to use the saved file (they got 300GB file) for other keys in the same range. I think that would speed up checking a lot of keys.  No news about this?

[COBRAS]

Guys, take a look at this: https://link.springer.com/content/pdf/10.1007/s11227-020-03441-5.pdf

A faster modular multiplication implementation for the P-192 curve.

Granted this is the wrong curve, but it has the same general formula y2 = x3+ax+b, so all that theoretically has to be done is to extend the summations to a few extra terms (they'll just be 32 words instead of 24, which means a 32x32 word multiplication size instead of 24x24) and accommodate for the missing ax.

E.g. where it defines range shifted representation (RSR) of a large number, which it uses in the algorithm:

Code:

X = ∑ i=0,i=23 xiWi−12 = x0W−12 + x1W−11 + ⋯ + x23W11,
Y = ∑i=0,i=23 yiWi−12 = y0W−12 + y1W−11 + ⋯ + y23W11,
Z = X ⋅ Y = ∑i=0,i=47 ziWi−24 = z0W−24 + z1W−23 + ⋯ + z47W23

We can just replace it with this:

Code:

X = ∑ i=0,i=31 xiWi−16 = x0W−16 + x1W−15 + ⋯ + x31W15,
Y = ∑i=0,i=31 yiWi−16 = y0W−16 + y1W−15 + ⋯ + y31W15,
Z = X ⋅ Y = ∑i=0,i=63 ziWi−32 = z0W−32 + z1W−31 + ⋯ + z63W31

(x, y, z summation terms are all between 0 and 255 inclusive)

Then the rest of the modular multiplication follows suit.

They say it's 26% faster than the usual ECC multiplication algorithm. I wonder if this representation also handles modular addition well. If it does, then we got ourselves a faster way to do modular arithmetic.

The study was carried out on some 8-bit embedded machine. Modern pipelines stuff 64 bits in a register so we may even be able to reduce the number of RSR words by a factor of 8 i.e. only 2 x and y words and 4 z words (and ovbiously the maximum range of each word increases proportionally).

I think all modern methods about speed up SECP operation include point addition and multiplication etc in this article(codes included) https://paulmillr.com/posts/noble-secp256k1-fast-ecc/ if use a Jacobian coordinates with a endomorphism  and windows method/

I think this is an interesting method, if we do not forget that brute forse is jast addition of points, multiplication and comparison of the result with the target pubkey is an endomorphism and a splitting point into 2 parts, and the brute 2 parts separately.... but due to the fact that many people here, like me, are a bit lazy, all the methods are being implemented too slowly.

[bigvito19]

maybe your all calc wrong, giving you example
generate 70 bit random key, and use kanagroo to find it, note the time
then split 70 bit 65 bit with 32 keys and try to find one by one in 65 bit and note time,
then split 70 bit 65 bit with 32 keys and try to find 32 keys parallel in 65 bit and note time,
you will have time calc result

Jean_Luc planned to release a new version (after solved #115), where it will be possible to use the saved file (they got 300GB file) for other keys in the same range. I think that would speed up checking a lot of keys.  No news about this?

Who said that was going to happen, Jean_Luc was last active on here last week and still hasn't said a word about anything.

[batareyka]

Hello .
Someone can suggest.
How to write a program in python for taking away and adding the Public key from the public key.
An example.
031656894a2e404e652e3a2b368c7df820b0e92fe32529c41931a9f7b234457d5b (d456ba310f)   - 022fa21d1cea4bc1f9911a9d501e3d8b3c97d15aaa76a63fecd0d529b9ef2e22f5    (23fa540bcd)


result
0297539272d59d6e75488df9a5628e7b0efc03b4fec79de246ac116ae40c05225a (B05C662542)


I get everything, but not this result.
Also, with addition, the result is not correct.

I would be grateful if you indicate where to find the corresponding sketch in python.
Sincerely .

[NotATether]

Hello .
Someone can suggest.
How to write a program in python for taking away and adding the Public key from the public key.

You mean something like this?

Code:

from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

pk1 = '031656894a2e404e652e3a2b368c7df820b0e92fe32529c41931a9f7b234457d5b'
pk2 '022fa21d1cea4bc1f9911a9d501e3d8b3c97d15aaa76a63fecd0d529b9ef2e22f5'

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def add(pk1, pk2):
    P = pub2point(pk1)
    Q = pub2point(pk2)
    R = P + Q
    # Remove the following code if you are doing multiple additions successifly
    # as it brings a speed improvement, and just return R
    if (R.y % 2 == 0):
        prefix = "02"
    else:
        prefix = "03"
    hx = hex(R.x)[2:].zfill(64)
    return hx

add(pk1, pk2)

I get everything, but not this result.
Also, with addition, the result is not correct.

With which program did you do the addition?

[batareyka]

Yes, I used the program almost like yours is written below.
But I compared it with yours and noticed a fundamental mistake.
And now everything works.
I am very grateful to you for your help.
I hope that my way of calculation is correct and I can share my work with here.

[yoyodapro]

Kangaroo pool up and running if anyone wants to join!

the pool is currently at 2^27/2^35.55 DP in only 4 days! we will be finding this address soon as more people join.

The prize will be split according to the number of kangaroos you supply to the pool as well as your speed. We only want QUALITY kangaroos, which means if you change your gpu grid to supply more kangaroos but decrease your speed to do so these are not quality kangaroos and you be paid on your speed to the pool.

https://github.com/yoyodapro/Kangaroo-Server

[ssxb]

@NotATether

i have 300 public keys and loading one by one in this script is painful. can you please modify this script to get a file of public keys and process one by one all.

Code:

from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

pubkey = '03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4'

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)



# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def shiftdown(pubkey, divisor):
    Q = pub2point(pubkey)
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    for i in range(divisor+1):
        P = Q - (i * G)
        P = k * P
        if (P.y % 2 == 0):
            prefix = "02"
        else:
            prefix = "03"
        hx = hex(P.x)[2:].zfill(64)
        hy = hex(P.y)[2:].zfill(64)
        print(prefix+hx, "04"+hx+hy)

shiftdown(pubkey, 32)