Pages:
Author

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

a.a
member
Activity: 126
Merit: 36
September 27, 2021, 02:33:25 PM
I added also following to my original post

Quote
So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.

Quote
Why will we have 31 public keys and not 32?

You will have 32 pubkeys, but from those 32 pubkeys only one will be in the desired range. The other 31 pubkeys will be all over the place, and thus being uninteresting.
a.a
member
Activity: 126
Merit: 36
September 27, 2021, 02:26:39 PM
You could give me your 40 bit public key. But cracking it is kind of waste of time, as I would need to do alot manually, you know...

But how to crack it:
I would bit shift your public key by 65536 ( 2 ^ 16).  I will then have 65536 pubkeys and one of them is in range 2 ^ 24. I will run it on BitCrack and get the key in 2 ^24. By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.
a.a
member
Activity: 126
Merit: 36
September 27, 2021, 01:59:20 PM
It doesnt matter if you know if it is even or odd. If you shiftdown you always get a solution for last bit being even and one for odd.

So if you divide by 32, you will have 31 publickeys which are out of your modified searchrange not leading to the solution and one which will be in the searched range.
a.a
member
Activity: 126
Merit: 36
September 27, 2021, 01:06:16 PM
This makes actually no sense, because the underlying principle is different.

example:

Puzzle 11
https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000483

038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b

halving the publickey:
03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d

03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 is the result, when the privatekey of puzzle 11 is even and
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d if the the privatekey of puzzle 11 is odd.

02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is the correct one, as the privatekey of puzzle 11 is odd  
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000241

So if you do 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d + 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d, you get 038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b (untested, I guess you need also adding the Generatorpoint for + 1 as we do 241 + 241 + 1 = 483)

So what is 03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 then? It is 241.5.
241.5 + 241.5 = 483

So, where do we find 241.5?

https://privatekeys.pw/key/7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b1e5f

How did I find it? key middle range minus half of our privatekey: 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 - 0x241 => tada

So from complexity of 11 bits, i just needed to check 10 bits now.

If I divide by 32, I actually do what?

2 * 2 * 2 * 2 * 2 = 32

So we are halving the public key 5 times. This means, that when we do this on key 11, we get 32 keys, from where one of them has the correct endsequence of the private key. So we have to check all keys if they are in the range of 2^6. If we get one, than we know how the first 6 bits of the privatekey are. We can from here determine the last 5 bits easily. I am not interested in the other ranges, as i have now a total valid privatekey

legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
September 27, 2021, 12:55:29 PM
When openSSL uses /dev/urandom, then even the last 5 digits will be random.

OpenSSL private keys aka. 256-bit random numbers by themselves will not help with reducing the number of keys, however it is estimating the bias (as in - empirically, some bits will appear in a certain state more often than others - when several thousand random numbers are generated) in OpenSSL random numbers this estimation method draws its power from.

Also this doesn't work if your sample only one private key, that's why I mentioned that thousands of random numbers need to be sampled. My calculations get away with just 1000, though.

That's the whole problem.
For example, when we divide it by 32, we get 32 public keys, which will be defined in 32 (predefined zones), including in our zone, where we expect it. One key per zone.
BUT which of the 32 zones the report starts with is not known. If you know at least one key in which zone is located, it is easy to calculate the remaining 31. Since they go "around the circle" in order. The starting point depends on the remainder of the division by 32, which we do not know.

Hence why it's more efficient to just guesstimate the most likely remainders by observing what kind of random bits appear at the end.
jr. member
Activity: 48
Merit: 11
September 27, 2021, 12:33:42 PM
...
And how is it possible to determine which PubKey is in which Zone?


That's the whole problem.
For example, when we divide it by 32, we get 32 public keys, which will be defined in 32 (predefined zones), including in our zone, where we expect it. One key per zone.
BUT which of the 32 zones the report starts with is not known. If you know at least one key in which zone is located, it is easy to calculate the remaining 31. Since they go "around the circle" in order. The starting point depends on the remainder of the division by 32, which we do not know.
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
September 27, 2021, 12:25:34 PM
propably  the benefit of calculating it in zones could be only with veryfing or and calculating nearest point in the zone.
then substract those pubkey from zone minus pubkey from nearest point , it is difficult to explain (english is not my natural languge), then in looping substracting -still veryfing nearest point you can be sure  when you are "small distance" from power of two. then you can recalculate key.

it is numerical way -> it works , but is slowly.
but it takes time.

Try find a this private key. My public key redused complexity !!!

More info https://bitcointalksearch.org/topic/--5362587
a.a
member
Activity: 126
Merit: 36
September 27, 2021, 10:52:35 AM
When openSSL uses /dev/urandom, then even the last 5 digits will be random.

What is the benefit of calculating it in zones? And how is it possible to determine which PubKey is in which Zone?
member
Activity: 330
Merit: 34
September 27, 2021, 10:44:16 AM
Please read Q and A and my explaination related to that Q start from here
https://bitcointalksearch.org/topic/m.57818498

Your Q that you have just linked to says this:

guys lets say 32 divisors will return 32 keys , one of will be guaranteed for lower range but what about other all keys , i guess they all are also valid ~~ so my question is all other keys are random in 256 range or what?

from here, my answer were no random, and exact in all 256bit range, and what is exact location, i explain about how to calc exact range, simple, bro if you mislead by my those answers and explanation, i love to say SORRY
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
September 27, 2021, 10:26:24 AM
Please read Q and A and my explaination related to that Q start from here
https://bitcointalksearch.org/topic/m.57818498

Your Q that you have just linked to says this:

guys lets say 32 divisors will return 32 keys , one of will be guaranteed for lower range but what about other all keys , i guess they all are also valid ~~ so my question is all other keys are random in 256 range or what?

Emphasis on "in 256 range"

This is what I reverse-engineered a month ago for someone who thought they can reduce 120-bit keys a N number of smaller keys, where N is a tiny number like 260: https://gist.github.com/ZenulAbidin/e8687d9e16189c99d192e97d37e71dbe

As you can see, this exactly reproduces the results of the post I quoted.

Start with this public key 03bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47

Divide it into 32 "zones", where the first zone is from f7fffffffffffffffffffffffffffffec4d965ff79ce5b39e1d3cb9869b48f37 to effffffffffffffffffffffffffffffecf03ef184454163803d538a40332dd2d (this script spits it into two ranges so that you can actually load this into brute force programs).

Now you see the problem with this?

The generated range is already much bigger than the input range. (same for the other 31 zones - which all match your test output BTW). Instead of a <120-bit range now we have to do an impossible 256-bit search!

A script that reduces keys is supposed to make the range smaller, currently, the only known script that does this is the one by iceland.

And it does that well (at the expense of making an unmanageable amount of keys).

Now here's a method for reducing PKs (by guessing which ones are more likely to be the correct one) that actually reduces the range in the process - in fact it can be used to generate the most likely N keys (where N is any positive number - larger N = higher probability obviously):



You see, the number of keys you get from this can be drastically reduced not by splitting them up into "zones", but by using statistical analysis to see what bit patterns in OpenSSL private keys are more likely to appear in. Using birthday paradox, certain combinations of the private key bits account for a large percentage of the probability - and most importantly the lower PK bits can be used as an index to the array of millions of PKs generated (say length M) - because all of the divided pubkeys have been subtracted by M first.

Example:

I divide Public Key XYZ by 32 - this makes 32 public keys with each of them have been subtracted with numbers 0-31 first before dividing.

Say the results are: A, B, C, D, E, ... etc.

Put all of these in an array so that there are 31 elements in it.

Now you randomly generate about 1000 private keys using OpenSSL (Because let's face it, the puzzle creator would've found it convenient to create hex private keys only from OpenSSL command line) and measure how frequently the 1 and 0 bits appear in the lowest ceil(log2(32)) = 5 bits.

Then you use that info to create a table of the most frequent (likely) lowest ceil(log2(32)) = lowest 5 bits.

Now the kicker here, is that instead of using them as a guess for the PK, you use them as a guess for the index.

That is because when a private key is found, you will multiply it by 32 - and add the remainder back to it to get the same lower bits as in the frequency analysis.

Therefore, the index numbers directly correlate to the lower bits of the actual private key. And this is why this method works (script is not finished yet I'm still working on it).



Again, the problem with your method is that it makes the range bigger than what we started with in the first place.

So please make sure methods you make actually reduce the range before misleading people about them in the whole thread.
member
Activity: 330
Merit: 34
September 27, 2021, 09:34:41 AM
I think a lot of people in this thread have tried to solve puzzle 120 with a kangaroo. But since bitcoins are still in place, it means no one has solved it. Brainless somehow found a way to reduce the number of keys to search and if I understand the translation correctly, solved the puzzle 120, but did not withdraw funds. I could be wrong.

I am telling you, brainless' method is baloney. (I reverse engineered his script and I can share it right here if you want - it is useless).

Brainless did not manage to reduce a 120 bit key to a smaller range (and he definitely did not solve #120). He made 2^20 zones, each of which are 2^20th the size of the 2^256 range. (He said that himself, read his posts again carefully).

Also see:

little bit more example
dec 33
hex 21
pubkey 021697ffa6fd9de627c077e3d2fe541084ce13300b0bec1146f95ae57f0d0bd6a5
use your program to get 32 keys of above pubkey

you will see 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 in your list
one step ahead pubkey is 1.03125 ( 03bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47 + 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798  )

and in private key F7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC4D965FF79CE5B39E1D3CB9869B48F38
029eda0cebe3c594b59add6dccbff3347f06ad09e83e0b9279dd821cc94284c5d0

hope you will test each zone for your understand

Sorry to rain on this, but this method is useless.

I managed to decode how to split multiple keys using this method (I even made a script that reproduces your example, but it's private at the request of someone else, not that the results would be useful/practical to anyone here), and it turns out you're just using mod(32)-sized ranges.

Now as we all know, when you modinv a small number on secp256k1 you get a very large number (and modinv a "decimal number" is really just modinv(denominator) * numerator so this still holds for that)

This effectively means that the range becomes humungous, way bigger than 2^120 where we started.



The ranges look something like this (P = public key):

1*modinv(32) 2*modinv(32)     1P
2*modinv(32) 3*modinv(32)     2P
...
32*modinv(32) 33*modinv(32) (32*modinv(32) = 1)      32P

The ranges are much bigger than when you divide-and-split them down by a number.

Now of course you can replace 32 with an extremely huge number to make the ranges manageable/smaller but what's the point? Now you have an unmanageable amount of public keys.
Please read Q and A and my explaination related to that Q start from here
https://bitcointalksearch.org/topic/m.57818498
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
September 27, 2021, 06:16:02 AM
I think a lot of people in this thread have tried to solve puzzle 120 with a kangaroo. But since bitcoins are still in place, it means no one has solved it. Brainless somehow found a way to reduce the number of keys to search and if I understand the translation correctly, solved the puzzle 120, but did not withdraw funds. I could be wrong.

I am telling you, brainless' method is baloney. (I reverse engineered his script and I can share it right here if you want - it is useless).

Brainless did not manage to reduce a 120 bit key to a smaller range (and he definitely did not solve #120). He made 2^20 zones, each of which are 2^20th the size of the 2^256 range. (He said that himself, read his posts again carefully).

Also see:

little bit more example
dec 33
hex 21
pubkey 021697ffa6fd9de627c077e3d2fe541084ce13300b0bec1146f95ae57f0d0bd6a5
use your program to get 32 keys of above pubkey

you will see 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 in your list
one step ahead pubkey is 1.03125 ( 03bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47 + 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798  )

and in private key F7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC4D965FF79CE5B39E1D3CB9869B48F38
029eda0cebe3c594b59add6dccbff3347f06ad09e83e0b9279dd821cc94284c5d0

hope you will test each zone for your understand

Sorry to rain on this, but this method is useless.

I managed to decode how to split multiple keys using this method (I even made a script that reproduces your example, but it's private at the request of someone else, not that the results would be useful/practical to anyone here), and it turns out you're just using mod(32)-sized ranges.

Now as we all know, when you modinv a small number on secp256k1 you get a very large number (and modinv a "decimal number" is really just modinv(denominator) * numerator so this still holds for that)

This effectively means that the range becomes humungous, way bigger than 2^120 where we started.



The ranges look something like this (P = public key):

1*modinv(32) 2*modinv(32)     1P
2*modinv(32) 3*modinv(32)     2P
...
32*modinv(32) 33*modinv(32) (32*modinv(32) = 1)      32P

The ranges are much bigger than when you divide-and-split them down by a number.

Now of course you can replace 32 with an extremely huge number to make the ranges manageable/smaller but what's the point? Now you have an unmanageable amount of public keys.
jr. member
Activity: 81
Merit: 2
September 26, 2021, 11:47:29 PM
How do you generate these pubkeys?

he learnt recently about 02 and 03 relation and he is trying to jump between them but i covered that million times in most advance way which he only can dream. but no luck ~~

let me tell you guys if you are trying to do some math things keep in mind they called it curve (with logarithm problem) and no matter what calculations you will do. there will be always blockage and relationship of keys with each other which will puzzle you. so just try your luck dont try to defeat it with math.


simple thing let me tell you how they solved up to 115 .

assume you calculation power is 100 and you are trying to find 50 ~ in blink you can find (like 40 or 60 bits)
assume your calculation power is 100 and you are trying to find 50000000000000000000 ~ still you gonna over come it as its some how possible over some period of time x. (like he solved 115 in 2 month i guess)
assume your calculation power is 100 and you are trying to find 5000000000000.........000000 . well good news you still able to find it but bad news you grand grand grand grand grand grand child will find that key and will enjoy that money while your body will be just a dust.(120 is that thing)


but luck game is on ~~

jr. member
Activity: 81
Merit: 2
September 26, 2021, 11:33:21 PM
This is a “subtracted” 120 puzzle public key:

0368c52337698581d2509522b7e0cbeb500bb613b6ad0c27cda7e86988c796ee90



Keyrange 2: 1000000000000000000000000000


How I begin to read about how to use “subtracted” ?
I try to read up to date from 6 month I missing update all knowledge (unfortune some knowledge I forget between un used, now try to understand again it is very complex)


https://bitcointalk.org/index.php?topic=5244940.1920 start from this page toward end page  ~ you will know many things just for your understanding  Grin
member
Activity: 406
Merit: 47
September 26, 2021, 11:27:56 PM
This is a “subtracted” 120 puzzle public key:

0368c52337698581d2509522b7e0cbeb500bb613b6ad0c27cda7e86988c796ee90



Keyrange 2: 1000000000000000000000000000


How I begin to read about how to use “subtracted” ?
I try to read up to date from 6 month I missing update all knowledge (unfortune some knowledge I forget between un used, now try to understand again it is very complex)
jr. member
Activity: 81
Merit: 2
September 26, 2021, 11:22:21 PM
This is a “subtracted” 120 puzzle public key:

0368c52337698581d2509522b7e0cbeb500bb613b6ad0c27cda7e86988c796ee90



Keyrange 2: 1000000000000000000000000000

With who will find a private key we share 1.2 btc 50/50%

Find a privkey and post privkey in this thread.

ASAP privkey needed !!!

Regard

WonderPhilosofer, try find this puzzle ? We share 1.2 btc 50/50 ? You have so many keyrate power, help solve the this please Huh

i dont want to reply your foolish things but you pushed me in limit ~ let me give you bad news and please stop your childish acts


lets say if 120 is in 8..... range and you will subtract  900000...... or even f00000..... you will end up with higher range than the orignal key range and big lol. you try more by flipping (02 with 03 or 03 with 02) the key you will never know which bit you have to search. assume you flip the key and its come in 119 and you start searching in 118 or in some other range. well good luck to you

you need to be so precise and in other word should know private key of lower range  Kiss

and remember what you are trying to do here i cover this shit million of time so its waster of time. rather than going with your so call one key i will prefer to go with divisor 32 keys as at least i know they are in 115.

now stop this shit and talk about math first . show us your calculation with any other key etc. i know already what you are doing . you are flipping the key and assuming this is in this range but let me tell you .

its all wrong what you are doing ~ wasting your time and our time as well.

a.a
member
Activity: 126
Merit: 36
September 26, 2021, 10:33:32 PM
Please describe what you are doing. I mean, we should invest calculation power on the premise, that your key is resulting in a solution. But till now, you are lacking the proof, that it makes sense.

And why dont you reduce it further and further?

member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
September 26, 2021, 09:45:28 PM
How do you generate these pubkeys?

With my private formula. This is not a simple divide or substract.

Let’s go fin a key and we slit profit.
a.a
member
Activity: 126
Merit: 36
September 26, 2021, 09:19:41 PM
How do you generate these pubkeys?
member
Activity: 406
Merit: 47
September 24, 2021, 07:30:25 AM

I was reduce 120 public key, find a privkey, and we share 1.2 btc 50/50.


https://bitcointalk.org/index.php?topic=5358408.new#new

What you mean reduce 120 public key? Sorry I not yet back to read all information?

I busy and not follow thread over 5-6 month, What I miss, What new interesting?

I think may be some one running Pollard's kangaroo continue 6 month may be some one solve already but still not that mean nobody running continue too longer enough can solve puzzle.

I agree about fine other methods to can solve puzzle.

I forget a lot of knowledge, may be I need to re-learning again.
Pages:
Jump to: