Pollard's kangaroo ECDLP solver

[digaran]

Can you please be less obvious about your hurt feelings and stay on topic @citb0in?  I have no experience in coding, so I can't understand even if I read the code, hence the reason for my question.  There is no shame in asking questions to learn new things.

[1714502294]

1714502294

[1714502294]

1714502294

[1714502294]

1714502294

[EternityMessage]

Hello fellow puzzle solvers,
After spending really too much time of my life trying different code and algorithms, buying and running loud hot hardware to solve #66 & #130I started to wander about ethics of what I am trying to do !
OK, if I have a really really good luck, I will find the key after 1-2 more years!
... BUT !!! Do I have the right to take the coins in the address? ...
The coins (the money) are not mine, and the owner (the assumed puzzle creator) never said that, if I brake the private key, I have the right to take the money !!! (Also the fact that the person has more money than us, does not give us the right to take his money!)
So .. did I spent so much time of my life trying to become a thief? ...
The assumption when I started was ... That is a challenge .. I can do my best .. BUT Do I have the moral right to get money assuming it is by the rules ? ... There are no official rules? We conveniently assume the owner intentions and are ready to get his money ... but what if we are wrong?

[digaran]

Hello fellow puzzle solvers,
After spending really too much time of my life trying different code and algorithms, buying and running loud hot hardware to solve #66 & #130I started to wander about ethics of what I am trying to do !
OK, if I have a really really good luck, I will find the key after 1-2 more years!
... BUT !!! Do I have the right to take the coins in the address? ...
The coins (the money) are not mine, and the owner (the assumed puzzle creator) never said that, if I brake the private key, I have the right to take the money !!! (Also the fact that the person has more money than us, does not give us the right to take his money!)
So .. did I spent so much time of my life trying to become a thief? ...
The assumption when I started was ... That is a challenge .. I can do my best .. BUT Do I have the moral right to get money assuming it is by the rules ? ... There are no official rules? We conveniently assume the owner intentions and are ready to get his money ... but what if we are wrong?

Tell me something, when you find the puzzle key and transfer it to your address, who is going to say you weren't the real owner? The rules in crypto are different, when you hold a private key by the law you are the owner, ethically?

If it's for someone else, you should never touch them, but when someone intentionally sends bitcoins to 160 addresses starting from 1, it means they are dropping bread crumbs along the way as a beacon to signal those capable to take them if they can, to what end?  To see how fast they can take it.  Now since finding a key even in lowest ranges is not an easy task, the person who finds it, can keep it as a bounty prize. 
More importantly, solving them requires fast tools, and not everyone is able to develop such programs, so when they do and use it to find a key, they take the coins as their reward.


You might wonder, but why??   Because paying $30M to make sure +$600B is safe is a good deal.
Now where are those 600B? They reside in 255+ bit range, where are puzzle keys  30M? They reside from 66 bit up to 160 bit.    To realize how big that gap is, you'd need to multiply 2^160 by 2^96 to reach there.

The designer doesn't need to say anything, he already said thanks to those who were developing cracking tools,  also a few month ago, he increased the prize 10x folds after community's request.  Unless he is mentally happy (lol) I would doubt he would add more to the pot after #125 was solved if he wanted the coins for himself.

[EternityMessage]

Hello again,

About:
"The rules in crypto are different, when you hold a private key by the law you are the owner"
What if money were yours? Still OK with this?

"The designer ... increased the prize 10x folds after community's request."
OK! Time for another community's request:
Mr./Mrs. Puzzle creator and puzzle addresses money owner,
Please sign a message with any known non-broken puzzle address, and state your will!
Are you fine, if money from these addresses are taken?"
Or "you consider us thieves?" or ...
(the signing #150, #155... public keys are already known and will not compromise security)

Thanks

[CY4NiDE]

So I'm messing with Puzzle #130 and JLP's Pollard Kangaroo ECDLP Solver using a RTX 2070. When I first launch it, this is the speed I get:
[1553.87 MK/s][GPU 1459.12 MK/s]

After a few seconds running at that speed it will slowly decrease until it reaches this speed, where it stays for the rest of the operation:
[1209.19 MK/s][GPU 1134.42 MK/s]

Does anyone know why this is happening?

Thanks in advance!  

[_Counselor]

So I'm messing with Puzzle #130 and JLP's Pollard Kangaroo ECDLP Solver using a RTX 2070. When I first launch it, this is the speed I get:
[1553.87 MK/s][GPU 1459.12 MK/s]

After a few seconds running at that speed it will slowly decrease until it reaches this speed, where it stays for the rest of the operation:
[1209.19 MK/s][GPU 1134.42 MK/s]

Does anyone know why this is happening?

Thanks in advance!  

Because statistics are wrong until all threads loads kangaroos. Wait about 10-15 seconds to get right numbers.

[digaran]

Hello again,

About:
"The rules in crypto are different, when you hold a private key by the law you are the owner"
What if money were yours? Still OK with this?

"The designer ... increased the prize 10x folds after community's request."
OK! Time for another community's request:
Mr./Mrs. Puzzle creator and puzzle addresses money owner,
Please sign a message with any known non-broken puzzle address, and state your will!
Are you fine, if money from these addresses are taken?"
Or "you consider us thieves?" or ...
(the signing #150, #155... public keys are already known and will not compromise security)

Thanks

You should talk about it over there in puzzle thread, even though kangaroo was developed for these puzzles but it would be more or less off topic especially since OP is not active to provide any insights of morality standards.

This would be my last reply regarding your concerns, why would he send more Bitcoins to those addresses if he wanted them untouched? Moreover did you even read his post from 2019?

[CY4NiDE]

So I'm messing with Puzzle #130 and JLP's Pollard Kangaroo ECDLP Solver using a RTX 2070. When I first launch it, this is the speed I get:
[1553.87 MK/s][GPU 1459.12 MK/s]

After a few seconds running at that speed it will slowly decrease until it reaches this speed, where it stays for the rest of the operation:
[1209.19 MK/s][GPU 1134.42 MK/s]

Does anyone know why this is happening?

Thanks in advance!  

Because statistics are wrong until all threads loads kangaroos. Wait about 10-15 seconds to get right numbers.

Oh, this makes total sense. Thank you for your quick and concise answer! 

[EternityMessage]

Code question!

Why the jump table is not saved with work save file?

That way, jump table will be different every time we continue work and loading file, and the potential cycles will be different!

[_Counselor]

Code question!

Why the jump table is not saved with work save file?

That way, jump table will be different every time we continue work and loading file, and the potential cycles will be different!

Jump table generator uses hard-coded fixed seed each time to keep jump sizes equal for all workers.

[shelby0930]

Hey Guys!

I was wondering if a feedback system be established to determine the relative positions of two secp256k1 public keys? For instance, if one wishes to ascertain the distance between the public key associated with private key 100 and the public key of 1, and observes that it takes an average of 5 minutes to transition from key 100 to key 1, could one infer that the distance is halved when moving from key 50 to key 1, resulting in an average time of 2.5 minutes? Is it feasible to obtain such feedback?

[digaran]

Hey Guys!

I was wondering if a feedback system be established to determine the relative positions of two secp256k1 public keys? For instance, if one wishes to ascertain the distance between the public key associated with private key 100 and the public key of 1, and observes that it takes an average of 5 minutes to transition from key 100 to key 1, could one infer that the distance is halved when moving from key 50 to key 1, resulting in an average time of 2.5 minutes? Is it feasible to obtain such feedback?

Well, at first I thought you just cracked elliptic curve cryptography, but again when I think about your idea, of course you can have that, but it won't be accurate and precise, though you are talking about 1 and 100, while in the case of puzzle keys, we are now looking at 2^129 to be the distance between 2 keys. However if you are seeing your speed, you can guess the time yourself, just set the counter on your pc and check how long it takes.

Wait let me tell you, it takes the same as your speed rate, if 10 key per second is your speed, it should take around 10 seconds to go from 1 to 100.

Now I have an idea, what if we divide our key by 2 and start adding 100 trillion G at each step, we should see our original target +100 T at some point in time, right?

For example, target 1000, divide by 2 = 500, if we keep adding 10 to 500 we would reach 1000 after 50 steps and in 51st step we would see 1010, that way we can find our target very fast, right?

Let me go try a few things.😉

[garlonicon]

that way we can find our target very fast, right?

No. Because finite fields are, well, finite. If your key is 1234, then if you use 50 as your step, you will reach 1200, and then 1250, so you will jump over that, without noticing, that you missed it. And then, you will go up from 1250 to that huge n-value, and pass it a few times, to finally land on 1184, and then on 1234.

If you want to better understand that, maybe start with some smaller numbers first? This is a good starting point: "p=79, n=67, base=(1,18)". And when those numbers will be too easy for you, then you can go into higher, and higher values, climbing into bigger curves, by walking one step higher at a time.

For example, target 1000, divide by 2 = 500, if we keep adding 10 to 500 we would reach 1000 after 50 steps and in 51st step we would see 1010,

This is still small enough to make an image out of that. For example, vjudeu made a repository, where you can find all curves from 1 to 1000: https://github.com/vjudeu/curves1000/tree/master/png

Which means, if you have for example p-value around 1000, then you can just draw some 1000x1000 image, and put a white dot on (x,y) coordinates. In this way, you can see all points on some small curve, and explore exactly, how coordinates change, when you change your private keys.

Also, in this way, you can easily see, why prime numbers are used. If you have "p=967, n=907, base=(1,88)", then this is acceptable, and if you look at this image, there is no obvious weakness: https://raw.githubusercontent.com/vjudeu/curves1000/master/png/967.png

However, if you pick some complex numbers, then you can notice, how weak some of those curves are. For example, if you take 999: https://raw.githubusercontent.com/vjudeu/curves1000/master/png/999.png

[shelby0930]

Hey Guys!

I was wondering if a feedback system be established to determine the relative positions of two secp256k1 public keys? For instance, if one wishes to ascertain the distance between the public key associated with private key 100 and the public key of 1, and observes that it takes an average of 5 minutes to transition from key 100 to key 1, could one infer that the distance is halved when moving from key 50 to key 1, resulting in an average time of 2.5 minutes? Is it feasible to obtain such feedback?

Well, at first I thought you just cracked elliptic curve cryptography, but again when I think about your idea, of course you can have that, but it won't be accurate and precise, though you are talking about 1 and 100, while in the case of puzzle keys, we are now looking at 2^129 to be the distance between 2 keys. However if you are seeing your speed, you can guess the time yourself, just set the counter on your pc and check how long it takes.

Wait let me tell you, it takes the same as your speed rate, if 10 key per second is your speed, it should take around 10 seconds to go from 1 to 100.

Now I have an idea, what if we divide our key by 2 and start adding 100 trillion G at each step, we should see our original target +100 T at some point in time, right?

For example, target 1000, divide by 2 = 500, if we keep adding 10 to 500 we would reach 1000 after 50 steps and in 51st step we would see 1010, that way we can find our target very fast, right?

Let me go try a few things.😉

Hey Have you tried something? lemme know and btw.. do you think there exists a way to get feedback on the position of the secp256k1 public key?

[garlonicon]

Hi, is there a way to find private key range from the public key, (Start and Stop range) ?

No, because then ECDSA would be instantly broken. Also, that range is always relative to the base point. Which means:

Code:

range getRangeFromPubkey(Pubkey point);             //this will not work
range getRangeFromPubkey(Pubkey point,Pubkey base); //this could work, but would require breaking ECDSA

In general, if you give someone a public key alone, then asking for a private key is not the right question. The right question is: I have these two points, and I want to know the distance between them.

do you think there exists a way to get feedback on the position of the secp256k1 public key?

What do you mean by "position"? Because each point has just a pair of (x,y) coordinates, and for small enough curves, you can directly see that, for example if you have 1000x1000 image, you can directly see the position for each and every public key.

[EternityMessage]

Why code uses self made hash table?

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

[bjpark]

"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

[digaran]

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

[bjpark]

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

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.

[3dmlib]

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.