So when you want to import a private key, the software has to know which of the public keys (with corresponding address) should be used. The solution is to add a flag bit to the base58 encoding of the private key, notifying the importer whether or not to use the compressed public keys. Typically, these get called compressed and uncompressed private keys - but it's really just a bit saying whether the corresponding public key is compressed or not.
Thanks for the explanation. Being in progress of writing my own library for BTC-stuff,
I tried to "feed" it a compressed key (from my wallet) and an uncompressed key from
vanitygen, and I got a leading (hex)"80" octet for both. The number from the compressed
key was 8 bits longer, though.
Depending on the length (essentially the "ceil(log_2(N))" ) appears a bit fragile to me, for
the decision if the decoded priv-key is intended as a compressed or uncompressed key.
Is software expected to check for leading 5 or L/K on the base58 string, or did I miss
some sound discriminator within this larger N (maybe check it against the order of G
in secp256k1 ?)
If I intended to create a "compressed-key brain wallet", what do I have to do with the
sha²-output (before doing the chksum+base58 stuff) to get a priv-key that I could import
into a standard (sufficiently new) wallet?
Unfortunately, the bitcoin wiki-page about WEF-encoding priv-keys doesn't mention
compressed keys.
(hoping that you still have this thread monitored...)
The private key is always exactly 256 bits, or 32 bytes. The exact same private key corresponds to two different public keys. One is uncompressed in the form of (x,y), and the other is compressed in the form of (x,p). The two forms have different representations, and thus different hashes, and thus different addresses. The compression flag just tells the system which of the two possible addresses to use.
You should pretty much always do compressed keys for new generation. There is no reason to ever use uncompressed keys, at least none that I'm aware of.
So, to create the WIF, suitable for importing later, you take the 32 byte binary private key, prepend the 0x80 bytes, and append the 0x01 flag for compression, then run through base58encode and the output is the WIF. For reference, to create an uncompressed WIF, just don't append the 0x01 before encoding.
To create the matching address, calculate the public key as usual, but when you go to encode it, check the parity of Y. If Y%2 is even, encode it as 0x02 + x. If Y%2 is odd, encode it as 0x03 + x. (Uncompressed, it would be 0x04 + x + y.) Note that I'm using + to mean concatenation here. Then the address is created as usual.
If you need to accept WIF as input, after the base58decode step, you'll always have 33 or 34 bytes. If 33 bytes, it is uncompressed, and the private key is the 32 bytes after the 0x80 header. If 34 bytes, it is compressed, the last byte must be 0x01, and the private key is everything between the 0x80 header and the 0x01 compression flag. Once you have the private key and know whether the compression flag was present or not, you can calculate the public key and address as above.