EC Key Compression

Using the secp256k1 curve, will the below yield the same result?

1. Generate private key -> compress private key -> generate public key

2. Generate private key -> generate public key -> compress public key

I have tested both using openssl and I believe the answer is yes, but was hoping someone with an understanding of the underlying math could confirm before I assume this is always true.

Thanks

Generally, with cryptosystems based on secp256k1, a private key is a secret scalar $$n$$—an integer $$n$$ in the range $$0 \leq n < \ell$$ where $$\ell$$ is the order of the group, which for secp256k1 is a little under $$2^{256}$$—and a public key is a point on the curve obtained by repeatedly adding a standard base point $$G$$ to itself $$n$$ times, $$[n]G = \underbrace{G + \cdots+ G}_{\text{n times}}.$$ No matter how you store the private key, whether with ASN.1 DER or with ASN.1 XER gzip-compressed or with US-ASCII text PEM format, the scalar $$n$$ is needed to perform private-key operations like signing messages. (Some cryptosystems like Ed25519 have additional information in the private key.)

Since the scalar is typically chosen uniformly at random or near uniform, it can't be compressed. More often, compression applies to public keys or curve points: one way to look at the curve secp256k1 is roughly the set of integer solutions $$(x, y)$$ to the equation $$y^2 \equiv x^3 + 7 \pmod{2^{256} - 2^{32} - 977},$$ so we could represent it by two 256-bit strings $$\underline x$$ and $$\underline y$$ representing integers. But for any particular $$x$$ coordinate, there are only two possible $$y$$ coordinates (if any), so it suffices to store a 256-bit string $$\underline x$$ together with a single bit to determine which square root of $$x^3 + 7$$ is the $$y$$ coordinate such as the even one vs. the odd one, for a total of 257 bits—plus any encoding overhead, such as a container format's ASN.1 metadata, and the ANSI X9.62 point encoding which starts with 0x04 for an uncompressed point, 0x02 for a compressed point with even $$y$$, or 0x03 for a compressed point with odd $$y$$.

So, for a key pair $$(x, y) = [n]G$$, the two procedures are as follows:

1. Pick $$n$$.
2. Compute $$(x, y) = [n]G$$.
3. Compute $$y \bmod p \bmod 2$$ and store the compressed key pair $$(n, x, y \bmod p \bmod 2)$$.
4. Publish the compressed public key $$(x, y \bmod p \bmod 2)$$.
1. Pick $$n$$.
2. Compute $$(x, y) = [n]G$$.
3. Store the uncompressed key pair $$(n, x, y)$$.
4. Compute $$y \bmod p \bmod 2$$ and publish the compressed public key $$(x, y \bmod p \bmod 2)$$.

The first option stores a compressed private key; the second stores an uncompressed one. Either way, it's the same private key and public key, and the resulting compressed public key $$(x, y \bmod p \bmod 2)$$ has the same bit encoding no matter which path you take.

• Thanks for the excellent explanation. Not sure I total understood all of it or if you are confirming that the two above steps will give the same results. – K Stewart May 22 at 16:15
• @KStewart I am not sure what you mean by compressing the private key; maybe you can elaborate on what specific actions you are taking that you are describing as compressing the private key? – Squeamish Ossifrage May 22 at 16:25
• @SqueamishOssifrage It's actually a compressed key pair. Most software manipulates key pair objects, containing both the private value and the public key, even when it calls such an object “private key”. – Gilles May 22 at 16:44
• @Gilles I assumed your interpretation in your comment is correct and elaborate accordingly, rather than waiting for KStewart to elaborate, because when I read your comment I accidentally misattributed it to KStewart. – Squeamish Ossifrage May 22 at 16:53
• 04,x,y or 02/03,x is NOT ASN.1; it is X9.62. In particular, for points over Fp whose coordinates are integers, it uses a fixed-size unsigned representation of each coordinate, not a variable-size twos-complement representation as ASN.1 BER/DER does. However, that point encoding is sometimes wrapped within an ASN.1 encoding (typically BIT STRING). – dave_thompson_085 May 23 at 1:55

Actually, you don't need to know the underlying math (but if you want to, read Squeamish Ossifrage). Compression only affects the representation of the key, it does not change what the key is. Extracting the public key from the private key creates the same mathematical object, whether it's represented with the public key in compressed or uncompressed form.

More precisely, compression changes the representation of the public key; there's essentially only one way to represent the private key itself. Furthermore, what OpenSSL and many other programs call “private key” is in fact a key pair, containing both the private key and the public key. This is why a compressed private key makes sense, even though only the public key gets compressed. If you had a representation of the private key that didn't include the public key at all, it wouldn't have a compressed form and an uncompressed form. By the way, for EC keys, it's easy to reconstruct the public key from the private key, so the representation as a key pair is redundant, but standard representations of the private key include the public key for convenience.

The way the public key is compressed is not a generic compression like zip. It's a specific way to compress public keys on most elliptic curves in common use. A public key is a point on the curve, represented by its coordinates, i.e. by two numbers. But it's enough to know one coordinate, plus the sign of the coordinate, to reconstruct the other coordinate. (“The sign” is actually not really a sign, but close enough: there are at most two points on the curve with a given value of $$x$$, and the “sign” indicates which of these two is the desired point.) The uncompressed representation a starting byte 0x04 to say “an uncompressed representation follows”, followed by the two coordinates $$x$$ and $$y$$. The compressed representation (also called compact representation) is a starting byte 0x02 or 0x03 to say “a compressed representation follows, and $$y$$ is positive/negative” followed by the $$x$$ coordinate.

• The standard OpenSSL uses for EC privatekey, namely SEC1, stores all three of: curve OID (or X9.62 explicit parameters, but those are never used in practice), d, Q (compressed or un, or even X9.62 hybrid but that's useless). But there are other standards; e.g. many bitcoin wallets support 'Wallet Import Format' which contains only d plus a bit saying whether Q will be compressed, plus a byte indicating which network the key will be used on, and the curve is implied as secp256k1. – dave_thompson_085 May 23 at 1:56