Solving partial WIF with two missing parts

I try to find an easy/faster/efficient way to get what is the next valid WIF in this case finding the next 01 in the Encode byte, but seems that it require more operations that my current method, so i will pass that approach. PawGo if you know an easy way to calculate it please tell us.

NOW I will post here one example of what I'm doing in my program, step by step and i will show you guys the public key operations that i do to the public key in order to get a new "Transformed Public key" and how i solve the problem with that new public key.

The target public key is:

Code:

02FEE659ACF67F63F13AB4A7D676782F89EF8C51FCC9077A8709831FCEABFE261F

Lets to suppose that the only missing characters are the second chunk of 6 characters at the middle.

Code:

L1dU1111d4NTd7******6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t

I know that the key is not there, but lets to suppose that for the first example and at the end i will show you the real location and how to solve it with keyhunt. (Since you already know how to solve it with bitcrack and kangaroo).

So lets to calculate the start range and the End range for this example:

Code:

Start: L1dU1111d4NTd71111116zCyXqGyWXhXTa16dNWXZs7cpdk6en2t
Start: 808391fe958e6543b739b52db45eb396b672fc42d48472ee321f50b150cd4f8c338407d5b039

Code:

End: L1dU1111d4NTd7zzzzzz6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t
End: 808391fe958e6543b73a1667b0dbc3b3c8fe91fb939a818d5e0f8de094de4432a74307d5b039

If we remove the Encode bytes and the check sum the range in hexadecimal is:

Code:

Start: 8391fe958e6543b739b52db45eb396b672fc42d48472ee321f50b150cd4f8c33
End: 8391fe958e6543b73a1667b0dbc3b3c8fe91fb939a818d5e0f8de094de4432a7

So if we are sure that the target public key is there we can assume that the private key start by:

Code:

8391fe958e6543b7000000000000000000000000000000000000000000000000

Lets to call it "Base Private key" It's public key is:

Code:

02d1132913ea23066aeb2c862e74781cae270d06861eff13a224966dffa760a979

In that case we can substract to our target public key the value of the base publickey:

Code:

  02FEE659ACF67F63F13AB4A7D676782F89EF8C51FCC9077A8709831FCEABFE261F - 
  02d1132913ea23066aeb2c862e74781cae270d06861eff13a224966dffa760a979
= 035ba75d3476e534fc7c5f356236eac0da7a7a1285a13e2fa36725927228fa64d2

Call the Result "PublickeyStep1"

Now, as PawGo mention in this post and others of his post the problem with middle missing characters is tha they usually overwrite the encode byte 01 and others (not this case) the checksum part.

In this case the full base58 stride is:

Code:

Stride: 211111111111111111111111111111111
Hex: 0af820335d9b3d9cf58b911d87035677fb7f528100000000

If we see the hexadecimal part the last 4 bytes (8 hexadecimal characters) are 0 so in this case the Checksum is not overwritten so we can remove those not overwritten bytes and work only with the encode byte overwritten.

New Stride hex:

Code:

Hex: 0af820335d9b3d9cf58b911d87035677fb7f5281

So, to work with our actual public key "PublickeyStep1" we need to add to it one extra byte, this can be done multiplying it by 256

Code:

  035ba75d3476e534fc7c5f356236eac0da7a7a1285a13e2fa36725927228fa64d2 x 256
= 03813771bcfdb1f531273698c62adb3ed1a02693cf53e9ed1358350e8bf3ded880

Call the Result: PublickeyStep2
Also we need add 1 to the PublickeyStep2 because we expected that the valid Target (Unknow Private key) have an 0x01 value in the Encode byte

Code:

  03813771bcfdb1f531273698c62adb3ed1a02693cf53e9ed1358350e8bf3ded880 + 1
= 02019eedafe6ffa5ccc19cbc2d547edadfcfc2dc1cd1cc096794e9c2ebbbd994a3

Call the Result: PublickeyStep3

Now with that extra byte set to ONE we can work with the current stride.

You remember that we substract to the target publickey the "Base Public key" value? well now is time to subtract to the "PublickeyStep3" the value of the remainder of the of the base publickey in this case is the value of:

Code:

0x39b52db45eb396b672fc42d48472ee321f50b150cd4f8c3384

Please check the value include the extra encode byte, but with the overwritten value 0x84

Code:

  02019eedafe6ffa5ccc19cbc2d547edadfcfc2dc1cd1cc096794e9c2ebbbd994a3 - 
  03ef6c26cb9ebf5f81b80fa255602eeb5f721dd5b7d8504aa506bf010f56adcf9f
= 0361835cf65529916765ac4a5830f0ce0896312b5c0ab32e565cef0b3d0e6212a7

Call the result PublickeyStep4, I know, is getting a little complicated to follow, but it is only because the results are publickey in a ECC Operations and those operations are not in our day to day.

Now if the partial WIF is valid, I can guaranty you that the "PublickeyStep4" is perfectly divisible by our stride.

Code:

  0361835cf65529916765ac4a5830f0ce0896312b5c0ab32e565cef0b3d0e6212a7 / 0x0af820335d9b3d9cf58b911d87035677fb7f5281
= 033ba345c9f89c2a1e86c40838afd672ba691da3ca82fd47765ca645d3422026f5

This result is now our Expected "Transformed Public key" and it will be in the range from 1 to 58^6
1 to 38068692544 or in hexadecimal from 0x01 to 0x08DD122640 that is 36 bits and it can solve instantly with almost all the programs mentioned above.

Summary:
PublickeyStep1 = Target Public key - Base Public key (This last value change if we change the original first 4 missing characters)
PublickeyStep2 = PublickeyStep1 x 256 (This part add and extra "blank byte to the current public key")
PublickeyStep3 = PublickeyStep2 +1 (We add the public key of G to the current public key)
PublickeyStep4 = PublickeyStep3 - Base Public key remainder with extra overwritten byte
Transformed Public key = PublickeyStep4 / Stride

Real example:

Code:

Partial WIF: L1dUm2Fzd4NTd7******6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t
Start
L1dUm2Fzd4NTd71111116zCyXqGyWXhXTa16dNWXZs7cpdk6en2t
808393b7c5abb73dc94b37951701bc29da3d749d904321915bc2c7d71ca89579c38407d5b039
End
L1dUm2Fzd4NTd7zzzzzz6zCyXqGyWXhXTa16dNWXZs7cpdk6en2t
808393b7c5abb73dc94b98cf137ecc46ecc90a564f59303087b3050660b98a20374307d5b039

Base privatekey key: 8393b7c5abb73dc9000000000000000000000000000000000000000000000000
Base public key: 03ffc5e2fa8ec2ecee2a15750c511cc41af6aa0756064b67665de1f7934af222de
---
PublickeyStep1 = Target Public key - Base Public key
  02FEE659ACF67F63F13AB4A7D676782F89EF8C51FCC9077A8709831FCEABFE261F - 
  03ffc5e2fa8ec2ecee2a15750c511cc41af6aa0756064b67665de1f7934af222de
= 02bafc4682ea5e3ffdf3eef19627431f06db48551ee56c6e462bca82f88d4a9e89
---
PublickeyStep2 =  PublickeyStep1 x 256
  02bafc4682ea5e3ffdf3eef19627431f06db48551ee56c6e462bca82f88d4a9e89 x 256
= 02cb57cc0aed672511bfb34bb987f64d5037d3230d66929fdc1ccb012ea142cc18
---
PublickeyStep3 =  PublickeyStep2 + 1
  02cb57cc0aed672511bfb34bb987f64d5037d3230d66929fdc1ccb012ea142cc18 + 1
= 029374d087692b29b2016b78a8a50d1ac107375dc6965dfccd4f342fb675ba63c5
---
PublickeyStep4 =  PublickeyStep3 - Base Public key remainder  with overwritten byte ( 0x4b37951701bc29da3d749d904321915bc2c7d71ca89579c384 )
  029374d087692b29b2016b78a8a50d1ac107375dc6965dfccd4f342fb675ba63c5 - 
  03e0077463f9bc522a079599ddc934743dab4b8bebfb6fdd045fd776633426096d
= 039601bb5d5f6549fe2edf8638e749f43a5ef4b70408afcb4f7a2dd163574efb02
---
Transformed Public key = PublickeyStep4  / Stride
  039601bb5d5f6549fe2edf8638e749f43a5ef4b70408afcb4f7a2dd163574efb02 / 0x0af820335d9b3d9cf58b911d87035677fb7f5281
= 03d5a61365f2e219a34e93632c29b85694f4a3847cefccd45858d45a364f0423f8

Now we find the Transformed Public key with any of our tools in the range from 0x01 to 0x08DD122640

Code:

albertobsd $ time ./keyhunt -m bsgs -f target.txt -q -r 1:1000000001 -S -n 0x100000000
[+] Version 0.2.211117 SSE Trick or treat ¡Beta!, developed by AlbertoBSD
[+] Quiet thread output
[+] Mode BSGS secuential
[+] Opening file target.txt
[+] Added 1 points from file
[+] Range
[+] -- from : 0x1
[+] -- to   : 0x1000000001
[+] N = 0x100000000
[+] Bloom filter for 65536 elements : 0.88 MB
[+] Bloom filter for 2048 elements : 0.88 MB
[+] Bloom filter for 64 elements : 0.88 MB
[+] Allocating 0.00 MB for 64 bP Points
[+] Reading bloom filter from file keyhunt_bsgs_4_65536.blm .... Done!
[+] Reading bloom filter from file keyhunt_bsgs_6_2048.blm .... Done!
[+] Reading bP Table from file keyhunt_bsgs_2_64.tbl .... Done!
[+] Reading bloom filter from file keyhunt_bsgs_7_64.blm .... Done!
[+] Thread Key found privkey 61111eefd
[+] Publickey 03d5a61365f2e219a34e93632c29b85694f4a3847cefccd45858d45a364f0423f8
All points were found

real    0m0.181s
user    0m0.139s
sys     0m0.008s

In case of found one of those public keys you only need to do the inverse Operations in reverse way in order to get the Target privatekey

PrivatekeyStep4 = Transformed Privatekey x Stride
PrivatekeyStep3 = PrivatekeyStep4 + Base Private key remainder with extra overwritten byte
PrivatekeyStep2 = PrivatekeyStep3 - 1
PrivatekeyStep1 = PrivatekeyStep3 / 256
Target Privatekey = PrivatekeyStep1 + Base Private key

Code:

0x61111eefd x 0x0af820335d9b3d9cf58b911d87035677fb7f5281
= 0x428c000f436b8bde1ab3c9ff2ed9147a23571758f719777d

0x428c000f436b8bde1ab3c9ff2ed9147a23571758f719777d + 0x4b37951701bc29da3d749d904321915bc2c7d71ca89579c384
= 0x4b7a211710ff95661b8f515a42506a703ceb2e34018c933b01

0x4b7a211710ff95661b8f515a42506a703ceb2e34018c933b01 - 1
= 0x4b7a211710ff95661b8f515a42506a703ceb2e34018c933b00

0x4b7a211710ff95661b8f515a42506a703ceb2e34018c933b00 /  256
= 0x4b7a211710ff95661b8f515a42506a703ceb2e34018c933b

= 0x4b7a211710ff95661b8f515a42506a703ceb2e34018c933b + 8393b7c5abb73dc9000000000000000000000000000000000000000000000000
= 0x8393B7C5ABB73DC94B7A211710FF95661B8F515A42506A703CEB2E34018C933B

Obviously this need to be automatically to avoid errors, also remember that the first missing part is 4 characters length, this mean that we need to repeat all those operations almost 58^4 times this is 11316496 times

Topic: Solving partial WIF with two missing parts (Read 268 times)