Topic: Pollard's kangaroo ECDLP solver - page 9. (Read 59436 times)

// test 1 (WORKING) returns correct public key and BTC address for 0x01 and 0x02 private keys
privateKey.SetBase16((char*)"0000000000000000000000000000000000000000000000000000000000000001");
point = secp->ComputePublicKey(&privateKey);
std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;

privateKey.AddOne();

point = secp->ComputePublicKey(&privateKey);
std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;


// test 2 (NOT WORKING) returns correct public key and BTC address for 0x01 private key only
privateKey.SetBase16((char*)"0000000000000000000000000000000000000000000000000000000000000001");
point = secp->ComputePublicKey(&privateKey);
std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;

point = secp->NextKey(point);

std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;


// test 3 as arulbero suggested (NOT WORKING) returns correct public key and BTC address for 0x01 private key only
privateKey.SetBase16((char*)"0000000000000000000000000000000000000000000000000000000000000001");
Point P(secp->ComputePublicKey(&privateKey));
std::cout << " (" << secp->GetPublicKeyHex(true, secp->ComputePublicKey(&privateKey)) << ") [" << secp->GetAddress(P2PKH, true, secp->ComputePublicKey(&privateKey)) << "]" << std::endl;

P = secp->NextKey(P);   

std::cout << " (" << secp->GetPublicKeyHex(true, P) << ") [" << secp->GetAddress(P2PKH, true, P) << "]" << std::endl;

Looking at this code:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L42C1-L52C4


I would try this:

Yes.
I'm using ComputePublicKey() function from vanitysearch project, not from kangaroo project. It do reduction by default at the end of ComputePublicKey() function.
NextKey() function still not working as it should.

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L59C7-L59C60

Secp256K1::ComputePublicKey(Int *privKey,bool reduce)

do you set bool reduce = True?

Hard to tell anything without the results of what your program is spitting out.

What happens when you use NextKey? Give exact examples.

But what if I need to start not from G point...

Int* privateKey = "some random private key";
Point* point;

This is working:
point = secp->ComputePublicKey(&privateKey);
while(1)
{
   privateKey.AddOne();
   point = secp->ComputePublicKey(&privateKey);
}


This is NOT working:
point = secp->ComputePublicKey(&privateKey);
while(1)
{   
   point = secp->NextKey(point);
}

For sequential private keys there is the NextKey function.

DoubleDirect does, as the name indicates, only the double of P.

Then, if you start from G:

G
P = DoubleDirect(G)  :  G -> P = 2G
P = NextKey(P)         :  P -> P+1 = 3G
P = NextKey(P)         :  P -> P+1 = 4G
P = NextKey(P)         :  P -> P+1 = 5G

and so on

Thanks.
DoubleDirect() works, but it only about 10% faster, than do entire private key to public key calculation with ComputePublicKey() function.
Is any faster way possible to do this 'increment private key by 1 and get public key' method?

UPD: 25.12.2023
Actually DoubleDirect() also not working. It starting to calculate wrong keys after some interval. Why this is can happen?
The only function work so far for sequential private keys to public keys is ComputePublicKey().

A public key is a point of the elliptic curve. A point can be represented by 3 coordinates (X,Y,Z) (projective coordinates) or by 2 coordinates (x,y) (affine coordinates).

The passage from projective to affine coordinates is the "reduction"

x = X/Z
y = Y/Z

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/Point.cpp#L64



The addition between 2 points in projective coordinates is performed by the function Add:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L369

and it is faster, because it avoids the inverse of x;


the addition between the same 2 points in affine coordinates is performed instead by the function AddDirect:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L238.

To compute NextKey function (that calls the AddDirect function), you have:

a) to use a point in affine coordinates (because the AddDirect function needs affine coordinates)
b) to avoid the case P = G, because to perform G+G (in the general P + P ) the AddDirect function doesn't work

you need instead the DoubleDirect function:
https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L438  

Hello.

Point Secp256K1::NextKey(Point &key) {
  // Input key must be reduced and different from G
  // in order to use AddDirect
  return AddDirect(key,G);
}

Is anybody can explain me why this function in secp256k1.cpp file not work correctly?
As I understand it should return next public key like as increment private key by 1 and compute public key from it.
What is reduced public key?

Thanks.

After some tests I found that memory speed is an issue. It GPU memory bound, not GPU chip. This is why it can't scale well for more GPU cores.

I see. While i have no idea which optimization can be done, you might want to try fork of this software or implementation written by different people. Here are few example,
https://github.com/ZenulAbidin/Kangaroo-256
https://github.com/PawelGorny/Kangaroo
https://github.com/secoc/Pollard-Rho-kangaroo

P.S. i haven't tried any of those.

Yes. I tried all possible grid size combinations. Also, I tried to compile on latest cuda version using more recent compute_89 shader model. Same result. The maximum I have on 4090 is about 2500 MK/s. On 3090 is 2200 MK/s. 4090 should be faster. Looks like Kangaroo need some optimization for large number of cores 4090 have. Any ideas where this optimization can be made? Thanks.

Hi, i'm studying Kangaroo Software made by JeanLucPons and I'm trying to know if there is a possibility to compute more pubkeys during an attack.

Searching in the official git I've found that Jean said:

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 does it mean? large tame array? Means maybe doing an one pubkey attack in a specific range complete that range using save.work and use it for other keys to attack? If I wanna do multi pubkey attack?

Thank you guys for replies.

After searching for all post in this thread[1] and github repository[2], it looks like you're first person who mention "4090" or any RTX 4000 series. And while it's obvious, have you tried all guidance on github repository. For example,



[1] https://ninjastic.space/search?content=4090&topic_id=5244940
[2] https://github.com/search?q=repo%3AJeanLucPons%2FKangaroo%204090&type=issues

Hello. What parameters or something to change in the code to speed-up this program on 4090 card? It only 1.2 times faster than on 3090 card, but it should be about 1.9 times faster. Thanks.

It's right that all 3 are wrong
I got it from the public key by subtracting the public key value, but I'll get it from the actual key again.



[new]
Thank you.
We found the cause.
An error occurred because the y value of the public key main key was entered incorrectly
main = 0x0c8a2c9469582f356343842ad36a9272e434eb5259807923f0046840e77b28b6 , 0x2fed4282430443b400cbefe2f1d7c8fbc6452bf68623c8993a3efb7b767fcd7b
I should've put it in and calculated it
main = 0x0c8a2c9469582f356343842ad36a9272e434eb5259807923f0046840e77b28b6 , 0x2fed4282430443b400cbefe2f1d7c8fbc6452bf68623c8993a3efb7b767fc

An error occurred because the y-value was missing a few characters in the back
Thank you.

How did you obtain it exactly? In fact all 3 are invalid.

"I'm testing Kangaroo 2.2, and I'm encountering an error with the public key value. It contains 66 characters, including 02 03, yet I'm unsure why I'm getting an error. I've conducted numerous tests thus far, but this is the first time encountering such an issue."

kangaroo.exe -gpu test.txt

test.txt ===>

11111
1111111111
038aa5e9f35d54df0ce7ea2131cd54c54c3100e89eb41c905a40c66c1d03648e5e
02402e14312240377f607dd6700fba6245bf26a866cc4e608441dcc938b4992e3c
0242ac97574153a0aed0b8115c0b1a430f8ff1040e5cc377d76d3886e2696edf06

error

Kangaroo v2.2
ParsePublicKeyHex: Error invalid public key specified (Not lie on elliptic curve)
C:\Users\admin\Desktop\result.txt, error line 4: 0242ac97574153a0aed0b8115c0b1a430f8ff1040e5cc377d76d3886e2696edf06

Why code uses self made hash table?

Isn't it much faster to use C++ std::map ?