Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 10. (Read 59389 times)

copper member
Activity: 821
Merit: 1992
October 16, 2023, 08:26:06 AM
Quote
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.

Quote
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.
newbie
Activity: 27
Merit: 4
October 16, 2023, 08:11:13 AM
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?
copper member
Activity: 821
Merit: 1992
October 13, 2023, 04:36:03 PM
Quote
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.

Quote
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
copper member
Activity: 1330
Merit: 899
🖤😏
October 13, 2023, 03:54:47 PM
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.😉
newbie
Activity: 27
Merit: 4
October 13, 2023, 01:29:37 PM
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?
member
Activity: 110
Merit: 61
October 13, 2023, 01:04:35 PM
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.
newbie
Activity: 15
Merit: 0
October 13, 2023, 06:22:11 AM
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!

member
Activity: 43
Merit: 10
October 08, 2023, 10:00:51 PM
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!  Smiley

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

copper member
Activity: 1330
Merit: 899
🖤😏
October 08, 2023, 05:26:29 AM
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?
member
Activity: 110
Merit: 61
October 08, 2023, 02:40:54 AM
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!  Smiley

Because statistics are wrong until all threads loads kangaroos. Wait about 10-15 seconds to get right numbers.
member
Activity: 43
Merit: 10
October 08, 2023, 02:31:22 AM
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!  Smiley
newbie
Activity: 15
Merit: 0
October 08, 2023, 01:26:15 AM
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
copper member
Activity: 1330
Merit: 899
🖤😏
October 07, 2023, 05:41:26 PM
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.
newbie
Activity: 15
Merit: 0
October 07, 2023, 03:44:40 PM
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?
copper member
Activity: 1330
Merit: 899
🖤😏
October 07, 2023, 08:07:05 AM
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.
hero member
Activity: 630
Merit: 731
Bitcoin g33k
October 07, 2023, 07:54:11 AM
Pollard rho will not iterate the same values. it means that second or third run command maybe will find the key,
Wait, what do you mean by this? You mean when we use kangaroo it will change searching methods? Or you mean when we set a different search range?

come on, such question from such a guy - really ? what's next ?
copper member
Activity: 1330
Merit: 899
🖤😏
October 07, 2023, 07:38:17 AM
Pollard rho will not iterate the same values. it means that second or third run command maybe will find the key,
Wait, what do you mean by this? You mean when we use kangaroo it will change searching methods? Or you mean when we set a different search range?
hero member
Activity: 630
Merit: 731
Bitcoin g33k
October 07, 2023, 06:18:50 AM
One more question related to Kangaroo program. Let's say I run Kangaroo and search for a 145bit key. I run it for 1 hour and then quit it because no key was found. Then I re-execute exactly the same command. Will the program iterate through the same values as it did on run first or is it theoretically possible that the 2nd run will find a key? My question basically is: does it behave like VanitySearch where it's theoretically possible to find a match each second regardless of what happened in the history and which range was scanned. Or does it behave more like BitCrack which searches in linear mode ?

Answer: You are right. Pollard rho will not iterate the same values. it means that second or third run command maybe will find the key,

Thanks for your kind feedback.
member
Activity: 43
Merit: 10
October 06, 2023, 02:42:55 PM
understood. Thank you for clarification @ecdsa123
I just ran a successful test with a 129bit key and it worked like a charm.

One more question related to Kangaroo program. Let's say I run Kangaroo and search for a 145bit key. I run it for 1 hour and then quit it because no key was found. Then I re-execute exactly the same command. Will the program iterate through the same values as it did on run first or is it theoretically possible that the 2nd run will find a key? My question basically is: does it behave like VanitySearch where it's theoretically possible to find a match each second regardless of what happened in the history and which range was scanned. Or does it behave more like BitCrack which searches in linear mode ?



I have the same doubt!
copper member
Activity: 1330
Merit: 899
🖤😏
September 22, 2023, 07:47:16 AM
is there a way for search y coordinate square modulo p
Why would you want that? Imagine you are searching for y coordinates.

Example :
X=
0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Y=
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Private key= 0x1

X= 0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb
Y=
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Private key=
0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

X=
0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb
Y=
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Private key=
0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce

They all have the same y coordinates, are you sure you want to search for them?
Pages:
Jump to: