mckemo (OP)
Newbie
Offline
Activity: 15
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 21, 2024, 03:31:18 PM |
|
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/quickSomebody got an idea?
|
|
|
|
satashi_nokamato
Jr. Member
Offline
Activity: 50
Merit: 3
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 21, 2024, 05:41:28 PM |
|
Let's do it together, here we have this public key Public_key= 03774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb Private_key= 0xb We divide by 2, simply by multiplying the public key by this scalar N/2= 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 Result 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 (OP)
Newbie
Offline
Activity: 15
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 22, 2024, 12:41:55 PM |
|
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
Legendary
Offline
Activity: 1708
Merit: 7188
In memory of o_e_l_e_o
|
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 22, 2024, 07:14:31 PM |
|
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?
|
_______. ______ __ ______ ______ __ ___ .______ ______ ______ __ ______ .______ _______ / | / __ \ | | / __ \ / || |/ / | _ \ / __ \ / __ \ | | / __ \ | _ \ / _____| | (----`| | | | | | | | | | | ,----'| ' / | |_) | | | | | | | | | | | | | | | | |_) | | | __ \ \ | | | | | | | | | | | | | < | ___/ | | | | | | | | | | | | | | | / | | |_ | .----) | | `--' | | `----.| `--' | __| `----.| . \ | | | `--' | | `--' | | `----.__| `--' | | |\ \----.| |__| | |_______/ \______/ |_______| \______/ (__)\______||__|\__\ | _| \______/ \______/ |_______(__)\______/ | _| `._____| \______| | 2% fee anonymous solo bitcoin mining for all at https://solo.CKpool.org | No registration required, no payment schemes, no pool op wallets, no frills, no fuss. |
|
|
|
|
mckemo (OP)
Newbie
Offline
Activity: 15
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 22, 2024, 08:30:52 PM |
|
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.
|
|
|
|
satashi_nokamato
Jr. Member
Offline
Activity: 50
Merit: 3
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 23, 2024, 05:26:52 PM |
|
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 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 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 And that one is known, while working with unknown keys, there is no easy way other than trying all above.
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 902
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 25, 2024, 02:33:49 AM |
|
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 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 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 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
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 118
Merit: 36
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
March 15, 2024, 10:04:55 PM |
|
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
Jr. Member
Offline
Activity: 46
Merit: 12
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 23, 2024, 01:08:01 PM |
|
Original_PVK = Offset_PVK * Total_Offsets + Offset_position - 1This is how you go from the offset back to the initial private key. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
1CY4NiDEaNXfhZ3ndgC2M2sPnrkRhAZhmS
|
|
|
dexizer7799
Newbie
Offline
Activity: 30
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 23, 2024, 01:14:17 PM |
|
Original_PVK = Offset_PVK * Total_Offsets + Offset_position - 1This is how you go from the offset back to the initial private key. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) Hi sir can you share real example with that library, thank you.
|
|
|
|
dexizer7799
Newbie
Offline
Activity: 30
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 23, 2024, 01:26:55 PM |
|
Original_PVK = Offset_PVK * Total_Offsets + Offset_position - 1This is how you go from the offset back to the initial private key. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) Example for this public key 0245a6b3f8eeab8e88501a9a25391318dce9bf35e24c377ee82799543606bf5212 how can I calculate with that formula?
|
|
|
|
dexizer7799
Newbie
Offline
Activity: 30
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 23, 2024, 01:41:40 PM |
|
Let's do it together, here we have this public key Public_key= 03774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb Private_key= 0xb We divide by 2, simply by multiplying the public key by this scalar N/2= 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 Result 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
Jr. Member
Offline
Activity: 46
Merit: 12
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 23, 2024, 01:47:22 PM |
|
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] 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 = 120For the sake of simplicity I'll run this on python: PVK = 992397627627 * 1024 + 120 - 1 hex_PVK = hex(PVK) print(hex_PVK) print(PVK) Result: 0x39c3e0843ac77, 1016215170690167 in decimal.
|
1CY4NiDEaNXfhZ3ndgC2M2sPnrkRhAZhmS
|
|
|
dexizer7799
Newbie
Offline
Activity: 30
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 23, 2024, 01:57:58 PM |
|
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] 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 = 120For the sake of simplicity I'll run this on python: 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
Newbie
Offline
Activity: 30
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 24, 2024, 02:29:57 PM |
|
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] 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 = 120For the sake of simplicity I'll run this on python: 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 (OP)
Newbie
Offline
Activity: 15
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 24, 2024, 07:58:16 PM |
|
solution found. can be closed
|
|
|
|
CY4NiDE
Jr. Member
Offline
Activity: 46
Merit: 12
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 24, 2024, 10:27:57 PM |
|
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.
|
1CY4NiDEaNXfhZ3ndgC2M2sPnrkRhAZhmS
|
|
|
Chail35
Newbie
Offline
Activity: 5
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 18, 2024, 06:15:19 AM |
|
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. I ran this equation using your example and the 40 bit pvk was found whether I ran the bsgs algo in the 50bit, 40bit or 30bit range. The same public key was found as long as I did not search in a range above 50bit. I don’t understand why it’s finding the same public and private key pair on line 120 in the output file. How is it finding a 40 bit private key in a 50 bit or 30 bit range? Do you know why?
|
|
|
|
CY4NiDE
Jr. Member
Offline
Activity: 46
Merit: 12
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 20, 2024, 11:45:53 PM |
|
I ran this equation using your example and the 40 bit pvk was found whether I ran the bsgs algo in the 50bit, 40bit or 30bit range. The same public key was found as long as I did not search in a range above 50bit. I don’t understand why it’s finding the same public and private key pair on line 120 in the output file. How is it finding a 40 bit private key in a 50 bit or 30 bit range? Do you know why?
I'm not sure why this would happen as I don't really know much about how these algorithms work. Maybe the algorithm's precomputed table covers the entire area of these smaller ranges without the need for further calculations? You can reach out to the person who created the BSGS implementation you are using I'm sure they will be able to better answer you.
|
1CY4NiDEaNXfhZ3ndgC2M2sPnrkRhAZhmS
|
|
|
|