divided Pubkey -> Privkey

[mckemo]

Hi.
i divided a pubkey with Iceland2k´s PubDiv.

It works and reduced the range as promised.
But how can i now calculate the Privkey back?

https://github.com/iceland2k14/quick

Somebody got an idea?

[1714790526]

1714790526

[1714790526]

1714790526

[1714790526]

1714790526

[1714790526]

1714790526

[satashi_nokamato]

Let's do it together,  here we have this public key

Code:

Public_key= 03774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb
Private_key= 0xb

We divide by 2, simply by multiplying the public key by this scalar

Code:

N/2= 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1

Result

Code:

Public_key= 025702fb8a2602f41f52699f688d4b005a128762e11dfd13fd22ea751ccbedb2ef
Private_key= 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a6

You see, our target was 11, in decimal but since there are no fractions in elliptic curve,  dividing 11 by 2 would give you 5.5 and if you subtract 5 from the result you will see N/2.  All of that was just 1 bit private key, try it with a 256 bit key.

[mckemo]

Thank you for the reply.
But i think this is the wrong turn.

Lets say i use the pubkey from puzzle 35 02f6a8148a62320e149cb15c544fe8a25ab483a0095d2280d03b8a00a7feada13d
And i let the program run and i want to reduce by 10->
it generates me 1024 keys.
one of the keys will be in range 25.

This works like a charm - >
The key 028490315e76ba204a01059765fadf4a4b5c73cc90e86dee99bc7f378a2b8f3e01 is found. -> Privkey 12bb484


i asked chatgpt to put in, what has been calculated and it added "Derived by subtracting 368 times G"
i dont think this is true..


what math do i have to apply, to get the correct privkey (4aed21170) now?
i can´t get it to work

[NotATether]

Thank you for the reply.
But i think this is the wrong turn.

Lets say i use the pubkey from puzzle 35 02f6a8148a62320e149cb15c544fe8a25ab483a0095d2280d03b8a00a7feada13d
And i let the program run and i want to reduce by 10->
it generates me 1024 keys.
one of the keys will be in range 25.

This works like a charm - >
The key 028490315e76ba204a01059765fadf4a4b5c73cc90e86dee99bc7f378a2b8f3e01 is found. -> Privkey 12bb484


i asked chatgpt to put in, what has been calculated and it added "Derived by subtracting 368 times G"
i dont think this is true..


what math do i have to apply, to get the correct privkey (4aed21170) now?
i can´t get it to work

Look at albertobsd's ecctools for help, it is a working reference implementation which you can use: https://github.com/albertobsd/ecctools/blob/main/modmath.c and you can compile it and do math on public and private keys.

To divide a private key by some number, first you need to invert it => this means taking it to the power of n-2, which can be done with modular exponentation.

Then you have to multiply it by the divisor and do a modulus on the result.

Do not ask chatgpt about cryptography. It is useless for that.

[citb0in]

Indeed, if it were that simple, dividing a 256-bit key hoping to reduce the search range for private keys, it would compromise the protocol's integrity and the stringent cryptographic security requirements of this application. It's crucial to maintain the integrity and security of the protocol by adhering to established cryptographic principles and not resorting to shortcuts that could jeopardize the system's reliability and safety.

What are you trying to achieve, what's your goal?

[mckemo]

Thats the problem i got here.
The tool von iceland is indeed working. It reduces to a lower keyspace precisely.
But i don´t understand what exactly it is doing.
And thats the point-> I can not reverse anything what i don´t understand what has been done.
Thats what i am asking for. Can somebody help me to understand, what iceland exactly has done, and how to reverse it onto the found privkey?
Keymath won´t help here, because i don´t know, what i got to enter..
i don´t know the divisor or how to even get it..
It seems like it is subtracting with Generatorpoint G, but.. what about the privkey?!

maybe somebody can help me to change the script of iceland, so it shows the correct calculation like in albertos keysubtract.

[bjpark]

Hi.
i divided a pubkey with Iceland2k´s PubDiv.

It works and reduced the range as promised.
But how can i now calculate the Privkey back?

https://github.com/iceland2k14/quick

Somebody got an idea?

886 (0xaded8397c5356d2b1f340f27a0468f619c1302e5ea9d163faceec6f379047e, 0xb29a5c80db4707ec7633fc49ba2ac731943efefe844e3c4e20e7c6361cd59a74)

886/2

443 ( 0xa123452c2b7eaf3115b3a5343b3ff31a09f70c54ae33c620471e3e8227a9d6f9, 0x933d348378a71f443788194aafc545e7f53e37a6f779f96e8fa14ccdede3b4eb)

443/2 =221.5

57896044618658097711785492504343953926418782139537452191302581570759080747390
(0xcfd94b1c93f4452b1d5c28e06e867d2931b2de7294973f5786496db12cf2de9e, 0x7b99c954b633e8b960ba3d71ead76a2c8b6e7c50b26cce6dbe9c2a6969abb0c1)

221.5/2 = 110.75
28948022309329048855892746252171976963209391069768726095651290785379540373695
(0x8da8608dcd9706e83676796646099160e7581ec407f65cf9a4567f9ea064a996, 0xbc975d53d42f4b5d40f3d303f6315e6211689a2a30f485af53daefb5c789b8cd)

If it's an integer and an even number, you can divide it into /2
However, if it becomes an odd number, the private key jumps at the wrong price.


a change in one's private key

886 ==> 443 ==> 57896044618658097711785492504343953926418782139537452191302581570759080747390   ==>28948022309329048855892746252171976963209391069768726095651290785379540373695

[satashi_nokamato]

Thats the problem i got here.
The tool von iceland is indeed working. It reduces to a lower keyspace precisely.
But i don´t understand what exactly it is doing.
And thats the point-> I can not reverse anything what i don´t understand what has been done.
Thats what i am asking for. Can somebody help me to understand, what iceland exactly has done, and how to reverse it onto the found privkey?
Keymath won´t help here, because i don´t know, what i got to enter..
i don´t know the divisor or how to even get it..
It seems like it is subtracting with Generatorpoint G, but.. what about the privkey?!

maybe somebody can help me to change the script of iceland, so it shows the correct calculation like in albertos keysubtract.

If you don't understand what it is doing,  then how do you know it reduces the range precisely?  What results did you get to know it's precision?
Show us exactly what you are doing,  but you can not know the private key of the public key which you are working with,  provide the exact setup you are using so we can help you better.

When you input a public key into such tools,  whatever results you get,  they will all behave the same,  to explain better,  take 52 and divide by 4 to get 13,  but now you need to generate at least 13 points and save them in order to compare against your results when you divide.
However if the target is 51/4= 12.75, then if you multiply by 4,  you will always get the original target back and the difference is that you can't tell if you got 13 as the result or 12.75,  only way to know that is to have all the points from 1 to 13.  Now if you are dividing a key in 64 bit range by 2,  you need to have all the points from 1 to 2**63 saved to compare with the results.

Let's say you managed to reduce a key down to 28 bits,  if you are sure about it you can easily brute force it,  but when we are dealing with big numbers there is no easy way to reduce the range down to 28 bits.

Why? As an example, let's try with large keys.
This is 2**130

Code:

1361129467683753853853498429727072845824

If you try dividing it by anything other than the power of 2,  you would get much larger numbers as the result,  now let's divide by 2**64 to get this result

Code:

73786976294838206464

Here is the tricky part,  if you try to divide by 2**64+1, the result would be larger,  the only way to know for sure that you are not missing a divisor is to try dividing by 2**64+1 up to 2**65 one by one just to see if you can hit this one

Code:

36893488147419103232

And that one is known,  while working with unknown keys, there is no easy way other than trying all above.

[COBRAS]

Thats the problem i got here.
The tool von iceland is indeed working. It reduces to a lower keyspace precisely.
But i don´t understand what exactly it is doing.
And thats the point-> I can not reverse anything what i don´t understand what has been done.
Thats what i am asking for. Can somebody help me to understand, what iceland exactly has done, and how to reverse it onto the found privkey?
Keymath won´t help here, because i don´t know, what i got to enter..
i don´t know the divisor or how to even get it..
It seems like it is subtracting with Generatorpoint G, but.. what about the privkey?!

maybe somebody can help me to change the script of iceland, so it shows the correct calculation like in albertos keysubtract.

If you don't understand what it is doing,  then how do you know it reduces the range precisely?  What results did you get to know it's precision?
Show us exactly what you are doing,  but you can not know the private key of the public key which you are working with,  provide the exact setup you are using so we can help you better.

When you input a public key into such tools,  whatever results you get,  they will all behave the same,  to explain better,  take 52 and divide by 4 to get 13,  but now you need to generate at least 13 points and save them in order to compare against your results when you divide.
However if the target is 51/4= 12.75, then if you multiply by 4,  you will always get the original target back and the difference is that you can't tell if you got 13 as the result or 12.75,  only way to know that is to have all the points from 1 to 13.  Now if you are dividing a key in 64 bit range by 2,  you need to have all the points from 1 to 2**63 saved to compare with the results.

Let's say you managed to reduce a key down to 28 bits,  if you are sure about it you can easily brute force it,  but when we are dealing with big numbers there is no easy way to reduce the range down to 28 bits.

Why? As an example, let's try with large keys.
This is 2**130

Code:

1361129467683753853853498429727072845824

If you try dividing it by anything other than the power of 2,  you would get much larger numbers as the result,  now let's divide by 2**64 to get this result

Code:

73786976294838206464

Here is the tricky part,  if you try to divide by 2**64+1, the result would be larger,  the only way to know for sure that you are not missing a divisor is to try dividing by 2**64+1 up to 2**65 one by one just to see if you can hit this one

Code:

36893488147419103232

And that one is known,  while working with unknown keys, there is no easy way other than trying all above.

float part after dividing cant be lager then divider

need generate up to 2^130 pub keys for get pubkey in rande 1

[whanau]

Thank you for the reply.
But i think this is the wrong turn.

Lets say i use the pubkey from puzzle 35 02f6a8148a62320e149cb15c544fe8a25ab483a0095d2280d03b8a00a7feada13d
And i let the program run and i want to reduce by 10->
it generates me 1024 keys.
one of the keys will be in range 25.

This works like a charm - >
The key 028490315e76ba204a01059765fadf4a4b5c73cc90e86dee99bc7f378a2b8f3e01 is found. -> Privkey 12bb484


i asked chatgpt to put in, what has been calculated and it added "Derived by subtracting 368 times G"
i dont think this is true..


what math do i have to apply, to get the correct privkey (4aed21170) now?
i can´t get it to work

Do your experiment again but reduce by 8 bits. The math will be obvious.

Iceland's script takes the input and produces a table 2**8 (for 8 bits) = 256 entries.
The first entry is the public key you put in. Then the input is reduced by 1 so for your example it goes 0x70, 0x6f, 0x6e etc for 256 times.

for each entry, there is a 'division' which produces the output table. when it gets to 4aed211 -00-  the reduction is to 4aed211.

If you look at the file in a text editor surprise surprise, you will find it at line 113 which is 0x71. (because you count from 1 subtract 1 = 0x70)

Multiply this by 256 (0x100) and you will have your original value.


However, this won't help for any large range because when you multiply the whole table by 256, you get all possibilities 00-ff
They are all valid, so you are no better off.





   


 

[CY4NiDE]

Original_PVK = Offset_PVK * Total_Offsets + Offset_position - 1

This is how you go from the offset back to the initial private key.  

[dexizer7799]

Original_PVK = Offset_PVK * Total_Offsets + Offset_position - 1

This is how you go from the offset back to the initial private key.  

Hi sir can you share real example with that library, thank you.

[dexizer7799]

Original_PVK = Offset_PVK * Total_Offsets + Offset_position - 1

This is how you go from the offset back to the initial private key.  

Example for this public key   0245a6b3f8eeab8e88501a9a25391318dce9bf35e24c377ee82799543606bf5212   how can I calculate with that formula?

[dexizer7799]

Let's do it together,  here we have this public key

Code:

Public_key= 03774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb
Private_key= 0xb

We divide by 2, simply by multiplying the public key by this scalar

Code:

N/2= 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1

Result

Code:

Public_key= 025702fb8a2602f41f52699f688d4b005a128762e11dfd13fd22ea751ccbedb2ef
Private_key= 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a6

You see, our target was 11, in decimal but since there are no fractions in elliptic curve,  dividing 11 by 2 would give you 5.5 and if you subtract 5 from the result you will see N/2.  All of that was just 1 bit private key, try it with a 256 bit key.

Sir ok can you do this for this public key?

0245a6b3f8eeab8e88501a9a25391318dce9bf35e24c377ee82799543606bf5212

[CY4NiDE]

Hi sir can you share real example with that library, thank you.

Let's make this simple. I'm going to use this 50bit keypar:

Initial PBK: 027f3bd8832c4ccc73a0c741b0ab204c0a6bafa5fd57c944e391d06906f6db7d5f
Initial PVK: 0x39c3e0843ac77 [1016215170690167 in decimal]

Code:

python3 PubDiv.py 027f3bd8832c4ccc73a0c741b0ab204c0a6bafa5fd57c944e391d06906f6db7d5f 10 out.txt

This generates our out.txt file with 1024 offsets. Since its a 10bit reduction in this example, at least one offset will be in the 40bit range.

I loaded the out.txt file into the BSGS algorithm and set it to run the 2^40 bit range. It found this offset:

PUB: 03720bd6f652601111001205bf748666b60903777d8bb83dc7e558d42f37c7fb5b
PVK: 0xe70f8210eb [992397627627 in decimal]

This offset is found in the line 120 of my out.txt file, so now we have everything to set up the equation:

Offset PVK = 992397627627
Total Offsets = 1024
Offset's Position = 120

For the sake of simplicity I'll run this on python:

Code:

PVK = 992397627627 * 1024 + 120 - 1
hex_PVK = hex(PVK)
print(hex_PVK)
print(PVK)

Result: 0x39c3e0843ac77, 1016215170690167 in decimal.

[dexizer7799]

Hi sir can you share real example with that library, thank you.

Let's make this simple. I'm going to use this 50bit keypar:

Initial PBK: 027f3bd8832c4ccc73a0c741b0ab204c0a6bafa5fd57c944e391d06906f6db7d5f
Initial PVK: 0x39c3e0843ac77 [1016215170690167 in decimal]

Code:

python3 PubDiv.py 027f3bd8832c4ccc73a0c741b0ab204c0a6bafa5fd57c944e391d06906f6db7d5f 10 out.txt

This generates our out.txt file with 1024 offsets. Since its a 10bit reduction in this example, at least one offset will be in the 40bit range.

I loaded the out.txt file into the BSGS algorithm and set it to run the 2^40 bit range. It found this offset:

PUB: 03720bd6f652601111001205bf748666b60903777d8bb83dc7e558d42f37c7fb5b
PVK: 0xe70f8210eb [992397627627 in decimal]

This offset is found in the line 120 of my out.txt file, so now we have everything to set up the equation:

Offset PVK = 992397627627
Total Offsets = 1024
Offset's Position = 120

For the sake of simplicity I'll run this on python:

Code:

PVK = 992397627627 * 1024 + 120 - 1
hex_PVK = hex(PVK)
print(hex_PVK)
print(PVK)

Result: 0x39c3e0843ac77, 1016215170690167 in decimal.

Thank you very much sir for share it I will try it, thank you.

[dexizer7799]

Hi sir can you share real example with that library, thank you.

Let's make this simple. I'm going to use this 50bit keypar:

Initial PBK: 027f3bd8832c4ccc73a0c741b0ab204c0a6bafa5fd57c944e391d06906f6db7d5f
Initial PVK: 0x39c3e0843ac77 [1016215170690167 in decimal]

Code:

python3 PubDiv.py 027f3bd8832c4ccc73a0c741b0ab204c0a6bafa5fd57c944e391d06906f6db7d5f 10 out.txt

This generates our out.txt file with 1024 offsets. Since its a 10bit reduction in this example, at least one offset will be in the 40bit range.

I loaded the out.txt file into the BSGS algorithm and set it to run the 2^40 bit range. It found this offset:

PUB: 03720bd6f652601111001205bf748666b60903777d8bb83dc7e558d42f37c7fb5b
PVK: 0xe70f8210eb [992397627627 in decimal]

This offset is found in the line 120 of my out.txt file, so now we have everything to set up the equation:

Offset PVK = 992397627627
Total Offsets = 1024
Offset's Position = 120

For the sake of simplicity I'll run this on python:

Code:

PVK = 992397627627 * 1024 + 120 - 1
hex_PVK = hex(PVK)
print(hex_PVK)
print(PVK)

Result: 0x39c3e0843ac77, 1016215170690167 in decimal.

Hi sir it works perfectly but when range is 80 or more I cannot find because range is big to find the divided pubkey and do calculation. What can I do in that situation to solve that problem? Example I want to do calculation with 125 bit range pub key.

[mckemo]

solution found. can be closed

[CY4NiDE]

Hi sir it works perfectly but when range is 80 or more I cannot find because range is big to find the divided pubkey and do calculation. What can I do in that situation to solve that problem? Example I want to do calculation with 125 bit range pub key.

Unfortunately there's no workaround.

If you reduce too much you will be left with an absurd ammount of offsets which will be impossible to work with.

For a 125bit key:

10bit reduction = 1024 offsets to search in the 115bit range.

25bit reduction = 33.554.432 offsets to search in the 100bit range.

30bit reduction = 1.073.741.824 offsets to search in the 95bit range.