Hi, from puzzles to private keys partially lost, there are a lot of cases where the first bytes from a private key are known but not the public’s key because of ᴘ2ᴘᴋʜ. And there’re software called ꜱᴀᴛ solvers (or ꜱᴍᴛ solver when there’s integers and not just bits) that can find solutions to mathematical equations systems : basically, you unroll all loops from a program and turn all variables as equations they hold (you also try to rewrite the program in order to reverse operations like transforming additions into substations ; divisions into multiplications and so on). So you get equations you study in K‒12 (but with far more variables) and the aim is to find the unknown bits (as such or forming an Integer). The solver attempts to rewrite the equations and then performs a bruteforce search on the possible solutions if there are several possible solutions or sends the result if it can be directly determined.
https://doc.sagemath.org/html/en/reference/spkg/cryptominisat.htmlA better alternative
in this class of attacks is to compute what’s called
Gröbner’s bases. But that tends to be a manual process and is complicated enough that it was never attempted on Bitcoin despite Bitcoin’s popularity.
So going back to Bitcoin’s key bruteforce, currently either you have to brute force something like all possible 2
70 keys which looks economically infeasible or I have to brute force sha256 through an ᴀꜱɪᴄ in order to find a preimage of the public key’s.
This means either the private key portion or either the partial sha256 is useless to restrict the search space…
Given using sat solvers for Bitcoin mining (so finding pre‑images in a specific case) showed mixed results, my idea would be to use ꜱᴍᴛ/ꜱᴀᴛ solving for restricting the search space using both the partial hash along with the first private key’s bytes.
Currently, I’m not looking at making it more efficient than bruteforcing, but just to get it working.
There are 2 ways to do it : either to search for the private key directly or search for the public key which then can be reversed quickly using Pollard’s kangaroo.
- Incrementing a private key by 1 leads to incrementing the public key by 0xBAAEDCE6AF48A03BBFD25E8CD0364141 (G of secp256k1). This means there’s a range of public keys, but unless the Koblitz curve can be converted to a more useful curve, I fail to see how to use this type of information for formalizing into a useful way for at least an ꜱᴍᴛ solver.
- As retrieving a private key from a public key is the same as solving the discrete logarithm, I fail to see how to express a formula that would allow a ꜱᴍᴛ/ꜱᴀᴛ solver to restrict the sha256 search space using the restricted private key search space (since the first private key bytes are known).
Of course, a solver will end up performing a bruteforce search but any thoughts on how to mathematically link the 2 informations for an ꜱᴍᴛ solver for shrinking the brute force search space compared to searching all possible private keys irrelevant of the hash ?
