The compressed public key byte header

Question

I've noticed that compressed public keys are always either 0x02 or 0x03, but what exactly determines whether it's 0x02 or 0x03? I can go look at the OpenSSL code to answer this, but I'm hoping someone already knows the answer and can tell me :P

Answer 1

The public key format that OpenSSL and Bitcoin use is described in SEP 1, published by the Standards for Efficent Cryptography Group on page 10.

1. Convert the field element x_P to an octet string X of length ceil([log₂ q]/8) octets using the conversion routine specified in Section 2.3.5.
2. Derive from y_P a single bit ȳ_P as follows (this allows the y-coordinate to be represented compactly using a single bit):
3. If q = p is an odd prime, set ȳ_P = y_P mod 2.
4. If q = 2m, set ȳ_P = 0 if x_P = 0, otherwise compute z = z_m-1x^m-1 + · · · + z₁x + z₀ such that z = y_Px_P and set ȳ_P = z₀.
5. Assign the value 02₁₆ to the single octet Y if ȳ_P = 0, or the value 03₁₆ if ȳ_P = 1.
6. Output M = Y || X.

... and page 53 ...

• If C is an octet string and the leftmost octet of C is 02₁₆ or 03₁₆, parse the leftmost ceil([log₂ q]/8)+1 octets of C as an octet string R, the rightmost maclen octets of C as an octet string D, and the remaining octets of C as an octet string EM.
• If the leftmost octet of C is 04₁₆, parse the leftmost 2 * ceil([log₂ q]/8) + 1 octets of C as an octet string R, the rightmost maclen octets of C as an octet string D, and the remaining octets of C as an octet string EM.
• If the leftmost octet of C is not 02₁₆, 03₁₆, or 04₁₆, output “invalid” and stop.

So, in plain English:

• It can be 0x04 too. That's is the 'uncompressed' key. If you generate a key today, it won't create one of these. However, if you have an old wallet, you might have some. They are equivalent in security to compressed keys.
• Whether it's 0x02 or 0x03 depends on on the value of ȳ_P. We can generate ȳ_P instead of including the full y coordinate, which saves us a nice bit of space. That's what compressed keys are.

I'm not sure what q is in this context, if somebody wants to tell me in comments, it'd be appreciated.

Answer 2

Parity determines if its 0x02 or 0x03

Node.JS:

if (y.isEven()) {
    publicKeyBytesCompressed.unshift(0x02)
} else {
    publicKeyBytesCompressed.unshift(0x03)
}