Pubkey scaling/subtracting/other tips for reducing search time

[NotATether]

This discussion was forked from the various Bitcrack, VanitySearch, and Kangaroo threads about public key scaling.

for 20 bit down = 1024*1024 = 1048576 pubkeys
~

1048576 and 1073741824 pubkeys with each other addition and mutiplication will return you 260 pubkeys apear where 16 pubkeys sure inside 10 bit down from main pubkey
these 260 pubkeys again played for get 30 bit down for 1/720 pubkeys

I don't get this tip. When I tried to shift down #120 by 20 bit I was looking at 2^20 total pubkeys generated from this. How do you manage to make do with only 260 or 720 of them? That's even less than the 1024 pubkeys I obtained from shifting 10 bits down.

Here is one tip, division equals twice as many pubkeys. Look at my post above, I can shift 16 bits down with the expense of only 2^15 keys, cutting the fat by half.
With brainless, who knows, he is a wizard at pubkey/range reduction.

Yeah that part was obvious to me, since in order to shift down by a bit you have to multiply the total number of result pubkeys by 2, effectively increasing the power.

The thing is that 260 and 720 are not powers of two so it would be helpful if brainless could explain what he's doing here to get this result.

[brainless]

This discussion was forked from the various Bitcrack, VanitySearch, and Kangaroo threads about public key scaling.

for 20 bit down = 1024*1024 = 1048576 pubkeys
~

1048576 and 1073741824 pubkeys with each other addition and mutiplication will return you 260 pubkeys apear where 16 pubkeys sure inside 10 bit down from main pubkey
these 260 pubkeys again played for get 30 bit down for 1/720 pubkeys

I don't get this tip. When I tried to shift down #120 by 20 bit I was looking at 2^20 total pubkeys generated from this. How do you manage to make do with only 260 or 720 of them? That's even less than the 1024 pubkeys I obtained from shifting 10 bits down.

Here is one tip, division equals twice as many pubkeys. Look at my post above, I can shift 16 bits down with the expense of only 2^15 keys, cutting the fat by half.
With brainless, who knows, he is a wizard at pubkey/range reduction.

Yeah that part was obvious to me, since in order to shift down by a bit you have to multiply the total number of result pubkeys by 2, effectively increasing the power.

The thing is that 260 and 720 are not powers of two so it would be helpful if brainless could explain what he's doing here to get this result.

Here i mention what is div numbers work in ecc
https://bitcointalk.org/index.php?topic=5244940.msg57373246#msg57373246

[WanderingPhilospher]

This discussion was forked from the various Bitcrack, VanitySearch, and Kangaroo threads about public key scaling.

for 20 bit down = 1024*1024 = 1048576 pubkeys
~

1048576 and 1073741824 pubkeys with each other addition and mutiplication will return you 260 pubkeys apear where 16 pubkeys sure inside 10 bit down from main pubkey
these 260 pubkeys again played for get 30 bit down for 1/720 pubkeys

I don't get this tip. When I tried to shift down #120 by 20 bit I was looking at 2^20 total pubkeys generated from this. How do you manage to make do with only 260 or 720 of them? That's even less than the 1024 pubkeys I obtained from shifting 10 bits down.

Here is one tip, division equals twice as many pubkeys. Look at my post above, I can shift 16 bits down with the expense of only 2^15 keys, cutting the fat by half.
With brainless, who knows, he is a wizard at pubkey/range reduction.

Yeah that part was obvious to me, since in order to shift down by a bit you have to multiply the total number of result pubkeys by 2, effectively increasing the power.

The thing is that 260 and 720 are not powers of two so it would be helpful if brainless could explain what he's doing here to get this result.

Yeah that has nothing to do with what I was really saying. When you divide, you create double the pubkeys versus other methods, to get down to the same bit range.

Brainless is his own person, he will give you tips but not the whole formula 

[Stroncow]

I did a test run here: https://pastebin.com/raw/QZj7VSa3

I tried scrolling down from different spots. And I tried these different points with Puzzle 120. The result is negative.

[NotATether]

I did a test run here: https://pastebin.com/raw/QZj7VSa3

I tried scrolling down from different spots. And I tried these different points with Puzzle 120. The result is negative.

I'm assuming that this is output from https://github.com/albertobsd/keysubtracter , which can only subtract keys but not divide them? Also, what exactly do you mean by "the result is negative", since it's obviously infeasible to test these keys by attacking #120?

I wonder what would happen if we first divided by one of @brainless magic ecc numbers followed by adding subtracting the pubkey to get one of these numbers of public keys?

2   447   7572   564114
3   596   9536   752152
4   631   10096   1128228
6   894   14304   1504304
8   1192   15144   2256456
12   1262   20192   3008608
16   1788   28608   4512912
24   1893   30288   6017216
32   2384   40384   9025824
48   2524   60576   18051648
64   3576   94019   
96   3786   121152   
149   4768   188038   
192   5048   282057   
298   7152   376076   

I'm not sure of the significance of these numbers so maybe a backstory on how you came about these numbers could be useful. Does it make the overall search time faster?  

[_Counselor]

I'm not sure of the significance of these numbers so maybe a backstory on how you came about these numbers could be useful. Does it make the overall search time faster?  

Those numbers are factors of secp256k1 modified order

n    = 115792089237316195423570985008687907852837564279074904382605163141518161494337 (prime number)
n-1 = 115792089237316195423570985008687907852837564279074904382605163141518161494336 (composite number)

factorisation of n-1 into primes: 2*2*2*2*2*2 * 3 * 149 * 631 * 107361793816595537 * 174723607534414371449 * 341948486974166000522343609283189

18051648 = 2*2*2*2*2*2 * 3 * 149 * 631
9025824   = 2*2*2*2*2 * 3 * 149 * 631
6017216   = 2*2*2*2*2*2 * 149 * 631

and so on

I don't see any special magic here. In fact, BTC's real private key can be divisible by any prime number and also can be prime by itself. Due to the fact that secp256k1 is a cyclic group, we cannot check whether the result of dividing an unknown number (public key) is an integer or a fraction (in real math, outside of cyclic group), so we cannot make any meaningful conclusions from the results obtained.

[COBRAS]

TELL  ME PLEASE SOMEONE, HOW TO SUBSTRACT OR DIVIDE PUBKEY FROM for. ex. 120 TO 60 BITS WITHOUT GENERATING PUBLIC KEY IN AMOUNT 2^60 OR IN AMOUNT (2^120 - 2^60) ?

80 GIGABYTES OF PUBLIC KEY'S IS DRAMATICALLY UNUSABLE !!!

REGARDS !!!

[NotATether]

TELL  ME PLEASE SOMEONE, HOW TO SUBSTRACT OR DIVIDE PUBKEY FROM for. ex. 120 TO 60 BITS WITHOUT GENERATING PUBLIC KEY IN AMOUNT 2^60 OR IN AMOUNT (2^120 - 2^60) ?

80 GIGABYTES OF PUBLIC KEY'S IS DRAMATICALLY UNUSABLE !!!

REGARDS !!!

You can't. Also as WanderingPhilosipher mentioned in a linked thread, you have to be careful not to divide by too much, or you will actually increase the number of group operations that you have to do and increase the runtime. 2^60 is way too much, even 2^20 makes the number of group ops bigger than a single 2^120 key.

[COBRAS]

TELL  ME PLEASE SOMEONE, HOW TO SUBSTRACT OR DIVIDE PUBKEY FROM for. ex. 120 TO 60 BITS WITHOUT GENERATING PUBLIC KEY IN AMOUNT 2^60 OR IN AMOUNT (2^120 - 2^60) ?

80 GIGABYTES OF PUBLIC KEY'S IS DRAMATICALLY UNUSABLE !!!

REGARDS !!!

You can't. Also as WanderingPhilosipher mentioned in a linked thread, you have to be careful not to divide by too much, or you will actually increase the number of group operations that you have to do and increase the runtime. 2^60 is way too much, even 2^20 makes the number of group ops bigger than a single 2^120 key.

Thank you for the answer.

I was look at my bookmarks and get link about cracking secp256k1, I the link infromation about group operations too, like in this thread

https://github.com/christianlundkvist/blog/blob/master/2020_05_26_secp256k1_twist_attacks/secp256k1_twist_attacks.md

Regars.

[abrahamtownsend]

By dividing, you can increase the number of public keys in comparison to other methods. I don’t think anyone would ever give you the whole formula to do it correctly.

[COBRAS]

By dividing, you can increase the number of public keys in comparison to other methods. I don’t think anyone would ever give you the whole formula to do it correctly.

Definitely Yes ! No on not know exact.

This is some my trying's:

https://bitcointalk.org/index.php?topic=5244940.msg57402519#msg57402519

it was just an example (random k generated)

from 120 puzzle we substract the starting range 800000000000000000000000000000 and we obtain the following K 03D943C68C5F958B14524CDBEF68168D6C018E101F4F7074E0C31686384A82F52F

N/2 - above K = 026C25951D1BB97C7DE3020DF0F725487FC33CC1210A155755514B7BF384AACFAD

From this K which is basically N/2 - Puz120 K + START-RANGE we add random K in the interval (0x1 - 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
We compute 10kk points in the range (N/2 - 10kk, N/2), points which cover the following range if we exclude parity (N/2 - 10kk, N/2 + 10kk)
Maybe i will draw something tomorrow for better understanding.

PS: I'm not saying this method will be exponentially "better" but it will double the chances to find k

this is not work !

https://bitcointalk.org/index.php?topic=5244940.msg57386530#msg57386530


Just FYI, for my 2 cents, if you know the range a key lies in, or want to gamble and take a chance where you think the key may lie, then I think subtraction is better.

Like I said a few posts back; we will take #120 puzzle for example. The private key can only start with 1 of 8 possibilities: 8, 9, A, B, C, D, E, F

Let's say you think it starts with C. You can then take the pubkey and subtract by C00000000000000000000000000000. Let us now say for example purposes the private key is:
C23BD97E765A75F0D6D4A6C6B67221.

So for your search range, after subtracting the C000....would be 0:FFFFFFFFFFFFFFFFFFFFFFFFFFFFF

By subtracting, you went from a search range of 2^120 to 2^116; 16 times smaller the original search range. BUT if you guessed wrong and the key does not start with C, then you will not find the key.

Staying with the same example, if you thought it started with C, D, E, or F and you subtracted by C000....then you could search the range of:
0:3FFFFFFFFFFFFFFFFFFFFFFFFFFFFF, and now you've went from 2^120 down to 2^117, 8 times smaller. BUT again, if the key does not start with C, D, E, or F, you won't find the key.

Dividing is fascinating because in your mind you see a much smaller search range, BUT the amount of pubkeys you have to search GROWS the smaller you cut the search range.

So I understand you subtract C00000000000000000000000000000 from 02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630 the public key for 120 and for example if you wanted to search F then you would subtract F00000000000000000000000000000 from 120 public key? and then search the same range 0:FFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Correct.
------
i was thinking last night that we treat each keyspace as if they were  separated by a wall but they are not so i measured the distance between 115 and the center of 60 then reduced the public key of 115 by that amount. i hit the 115 public key ( i scanned a thru f on 60 and about one hour later I got a hit. Key found privkey fc07a1825367bbc
Publickey 0242257a130fe109c25c2ca6c60af60e5849305f77370401299b63da2094ec0297 and the addition  + 31464123230573851029232324144930570 . Trying it on 120 but so far no luck. i wish I had this kind of luck on 120 or the powerball lol. I have a image of the hit but don't think I can post it. The addition goes to the private key found
Awesome!

i was thinking last night that we treat each keyspace as if they were  separated by a wall but they are not so i measured the distance between 115 and the center of 60 then reduced the public key of 115 by that amount. i hit the 115 public key ( i scanned a thru f on 60 and about one hour later I got a hit. Key found privkey fc07a1825367bbc
Publickey 0242257a130fe109c25c2ca6c60af60e5849305f77370401299b63da2094ec0297 and the addition  + 31464123230573851029232324144930570 .

...

So the center of 60, which was what, in your calculation? so you took 115 - minus middle of 60 = x and subtracted x from original 115 pubkey, right?
And then you did a search in the 2^60 range?

I cant copy what he was do it. I was try and unsuccessful ((((((((9999. Not known start range he was reduced or end of 115 range....

Another look to dived pubkey to 2:

https://ask.sagemath.org/question/50288/multiply-the-point-by-2-1-mod-n/?answer=50743#post-id-50743


https://ask.sagemath.org/answers/50743/revisions/

Any worked I ideas ?

[NotATether]

By dividing, you can increase the number of public keys in comparison to other methods. I don’t think anyone would ever give you the whole formula to do it correctly.

I finally got around to testing my hacked-up script which you can copy here to check that it produces the correct results when you divide public keys by numbers. I was pleasantly surprised to find out that they in fact matched the list of pubkeys that @WanderingPhilosipher gave me a while back (for #120's pubkey divided by 30, including the division by zero).

That means we got at least one working method to do the division.

Wait I think you actually are right, given my example was done with 48 as the divisor which is not a power of two, and to generate the 2^110 shrunk pubkeys I called it with 2**10.

It's a simple test. I will run my script to generate 30 pubkeys (of #120s pubkey, mine will actually kick out 31 because I also print out the 0 fraction), not a power of 2. They are listed below:

~

Now you run your script/the script you posted and see if the lists match.

[bigvito19]

By dividing, you can increase the number of public keys in comparison to other methods. I don’t think anyone would ever give you the whole formula to do it correctly.

I finally got around to testing my hacked-up script which you can copy here to check that it produces the correct results when you divide public keys by numbers. I was pleasantly surprised to find out that they in fact matched the list of pubkeys that @WanderingPhilosipher gave me a while back (for #120's pubkey divided by 30, including the division by zero).

That means we got at least one working method to do the division.

Wait I think you actually are right, given my example was done with 48 as the divisor which is not a power of two, and to generate the 2^110 shrunk pubkeys I called it with 2**10.

It's a simple test. I will run my script to generate 30 pubkeys (of #120s pubkey, mine will actually kick out 31 because I also print out the 0 fraction), not a power of 2. They are listed below:

~

Now you run your script/the script you posted and see if the lists match.

What all I have to install to compile the hacked-up script because I keep getting errors when I'm trying to compile it?

[NotATether]

What all I have to install to compile the hacked-up script because I keep getting errors when I'm trying to compile it?

You just need fastecdsa PyPI package. But to compile that you need gcc and the other build tools (on Ubuntu you can run "apt install build-essential" to get them all) you might also need something called libgmp-dev , -devel or similarly named. That'll give you the header files for arbitrary-precision math, required to implement ECC apparently.

[COBRAS]

Try someone find a privkey for this https://bitcointalk.org/index.php?topic=5350551.msg57521232#msg57521232

[dextronomous]

you just explained that it has already been spend found. whe testing that key or what, what addition to add if found to get the right pvk. address. thanks

[COBRAS]

you just explained that it has already been spend found. whe testing that key or what, what addition to add if found to get the right pvk. address. thanks

This is another good example with privrange ( ((2^60) - 986458768829923488 ) pubkey:



0x db09b0615ad40a0 * 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918

=

0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d(this is has a range 2^60 (address - 1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su))

This is a part of privkey - 986458768829923488 in hex db09b0615ad40a0.



No one can't find a privkey of 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918 ? 

[NotATether]

This is a part of privkey - 986458768829923488 in hex db09b0615ad40a0.

No one can't find a privkey of 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918 ?  

Then the problem just became easier, all you have to do is start from that hex number, add an appropriate amount of zeroes at the end, and search only that range until those zeroes become "f"'s.

BTW. The range is actually 256-(15 hex chars in prefix * 4 = 60) = 196 bits of keyspace, so still far to high to find.

[wedom]

This is another good example with privrange ( ((2^60) - 986458768829923488 ) pubkey:


0x db09b0615ad40a0 * 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918
=
0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d(this is has a range 2^60 (address - 1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su))

This is a part of privkey - 986458768829923488 in hex db09b0615ad40a0.


No one can't find a privkey of 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918 ?  

0x db09b0615ad40a0 * 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918
= 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
formula is incorrect

0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d - is puzzle 60 with private key = 0XFC07A1825367BBE

0XFC07A1825367BBE * inv(0xdb09b0615ad40a0) = 0xb839c25f765a0167754204e7c60b26866dbc64e7f596f7a924f697475c50b51c (private key)
pubkey = 0247c5b786a019f5575605c6c02b3e3e6c298d2b564d2e205313fac01a07557cb2

correct formula: 0xdb09b0615ad40a0 * 0247c5b786a019f5575605c6c02b3e3e6c298d2b564d2e205313fac01a07557cb2
= 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d

[COBRAS]

This is another good example with privrange ( ((2^60) - 986458768829923488 ) pubkey:


0x db09b0615ad40a0 * 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918
=
0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d(this is has a range 2^60 (address - 1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su))

This is a part of privkey - 986458768829923488 in hex db09b0615ad40a0.


No one can't find a privkey of 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918 ?  

0x db09b0615ad40a0 * 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918
= 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
formula is incorrect

0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d - is puzzle 60 with private key = 0XFC07A1825367BBE

0XFC07A1825367BBE * inv(0xdb09b0615ad40a0) = 0xb839c25f765a0167754204e7c60b26866dbc64e7f596f7a924f697475c50b51c (private key)
pubkey = 0247c5b786a019f5575605c6c02b3e3e6c298d2b564d2e205313fac01a07557cb2

correct formula: 0xdb09b0615ad40a0 * 0247c5b786a019f5575605c6c02b3e3e6c298d2b564d2e205313fac01a07557cb2
= 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d

Hello Man !

Glad to see there some who thant think )))

0x db09b0615ad40a0 * 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918
= 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
formula is incorrect

This is correct, but this 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918 not privkey, this is publick key.Look:
https://ibb.co/58B7ccr

have you any ideas how to find a privkey for pubkey 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918 ? because if this will be known this, not need to use a 0XFC07A1825367BBE.

And you use a known privkey 0XFC07A1825367BBE, but then we not know privkey what to do ? I think need find a privkey for 038141a3381c97660163ce69acf22d5a0cc8c09fcbb624fa556ff17629b4b31918.

0XFC07A1825367BBE * inv(0xdb09b0615ad40a0)

Interesting constraction ! I now will try to understand why is worked  )))


Respect.