Prelude

compactRepresentation is a public key output format, made available when using outputting public elliptic curve keys from within Apple's CryptoKit. compactRepresentation is comparable to a "compressed point", where the former is one byte shorter. These two representations are very similar, but not the same.

This post is an investigation into how these two formats differ, what makes Apple's format is one byte shorter, and why that choice does not come without compromise.

A somewhat surprising conclusion drawn is the following: to be able to re-construct public keys in this one-byte shorter compactRepresentation, the private key-space must be reduced by 1-bit (or 50%). Public keys are derived from a randomly selected private key where, on average, 50% of public keys are not compactRepresentable. 50% of private keys are therefore unusable when using this format, and must be discarded.

The following section contains a little Math. If you want to skip it, and just want to know why Apple's compactRepresentation is different from a compressed point, skip to: Apple's compactRepresentation

Elliptic Curve Point-Compression

An elliptic curve public-key is a point on a curve. This point (x, y) has an x and a y part. Because this point is on a curve (which has an equation relating x and y), we can think about whether we need to store both x and y when storing a representation of the public key. Suppose we store x and then work out the value of y. Well, this almost works, but the equation relating x and y actually relates x and y^2, and so we cannot quite uniquely work out y using x. To account for this we'd need to also store the sign of y.

To see why this is the case, suppose we work out y^2 = 9. Well then y = 3 and y = -3 would both be valid values of y. We don't know which one to pick. But suppose that we know y^2 = 9 and that the sign of y is minus. Well now we know for sure that y = -3, uniquely.

Modulo Arithmetic

When we work in "modulo" a number (say "modulo P" or (mod P)), this means that we're essentially doing math on a clock face, with P numbers round the clock. On an actual clock face, P = 12. Here, we don't have negative numbers: instead we count backwards starting from the top of the clock 12. So -5 (mod 12) = 12 - 5 (mod 12) = 7. And for any number larger than 12, we wrap round in the other direction. For example, 15 (mod 12) = 15 - 12 (mod 12) = 3.

Another way of looking at this is that we can add or subtract P as many times as we need to to get the number we're working with to appear on the "clock face".

Note also that when working mod P, we say that P (mod P) = 0, ie. 12 (mod 12) = 0. This is because when adding 12 and working mod 12, we're essentially "doing nothing" because we can subtract 12 to bring the result back onto the clock face. In this sense, 12 behaves like 0, and so can be labelled the same.

Putting all the above together: if we're working mod P, we are doing math on a "clock face". This "clock face" includes the numbers 0 through to P -1. If we have a number below 0, we need to add P until the result is between 0 and P -1; if we have a number that is above P -1, we need to subtract P until the result is between 0 through to P -1. This act of adjusting a number so that it is in this range, is referred to as "reducing a number mod P".

Modulo Inverses

When we talked about y^2 = 9 having two solutions in the above, we noted that these possibilities were y = 3 and y = -3. 3 and -3 are "related" by being "additive inverses" of one-another. This means that when we add the two numbers together, we get 0 (ie. 3 + (-3) = 0).

Numbers mod P can exhibit a similar behaviour except that, as we've seen, we need to do something about the "negative" number here to get it back on the clock face.

Modulo 12, -3 (mod 12) = 12 - 3 (mod 12) = 9. This means that if y^2 = 9 (mod 12), then both y = 3 or y = 9 are solutions. 3 and 9 are still "inverses" of each other mod 12, because 3 + 9 (mod 12) = 12 (mod 12) = 0.

Odd and even square roots

Something interesting happens when working modulo P, where P is odd: square roots come in even and odd pairs.

The effect can be seen by taking the above example y^2 = 9, and working mod 11 instead of mod 12: y = 3 is still a solution, which is odd. The other solution is: y = -3 (mod 11) = 11 -3 (mod 11) = 8, which is even.

It turns out that, so long as P is odd, this will always happen.

Point compression and parity

We noted before that, to efficiently store a point (x, y) on a curve, we could get away with storing x and the "sign" of y. But when we are working mod P, how do we know which is the negative and which is the positive? Both of these are positive mod P! Fortunately, we have another way to distinguish y when working mod P (for odd P): we can note whether y itself is odd, or even. This is known as ys "parity".

This is how point compression works for an odd P:

• If y is even, then we use the prefix 02.
• If y is odd, then we use the prefix 03.

We then take this prefix, and prepend it to the value for x. I.e. we store prefix || x, where || means concatenate. This is a "compressed point".

When we need to work out the value of y, given a compressed point: first, we work out the value of y^2. Then we find a one possible solution for y (mod P). If what we found is even, and the prefix is 02 then we have the right solution! If the prefix was instead 03 then we need to instead look for the odd solution (i.e. find the inverse of what we have right now). If what we found was odd, we do similar, noting our stored prefix and making sure that we get the solution to match.

Apple's compactRepresentation

So what is compactRepresentation, and why does all this math matter?

compactRepresentation as it turns out, is a little too compact. It gives us x, and nothing more. We don't know if we need an odd y or an even y. How odd! (or even!)

If you skipped here, just know that when representing a public key as a compressed point, there are two possible values for y if we have only x: an odd and an even one. When we output a compressed point, if y should be even we prefix 02, and if it should be odd we prefix 03.

Then how is compactRepresentation reconstructing a unique y value, if the parity information is discarded? How does it know whether it should be odd or even?

Well, it doesn't. When initialising a public key from compactRepresentation, the smallest solution for y is chosen. That's it, nothing fancy. Just the smallest y that works!

Samples where this goes wrong

Here's some randomly generated P-384 public keys (in actual compressed point notation, including the parity prefix) for which the actual y co-ordinate for the public key is larger than its inverse:

025b195e168bbf32937a46d0ed2fb24b46ef8d46e94eb7c3055efd6c0fa84dfab6e3503984ef9ab4321faa8f1c14778946
025aa5929f84f9f30cbc3bdae58dbb4bc3b240e4050ae3b4c3fcc6d8e7cf7c90b5c45405b113d6cf7d9fab7b0a03f8da6c
033860081d64c144ad82ead5824057af362e9c6ba3c613ad529b2f2a2d6197ae8cccfe1ff6d1b6e637a38e6293d84e12e9
0343ea0656b9d7ed258a1aaadd92cfeab163ec90ef5f8c868488a234abab2c021431be80b35cbac2df5a56d542bcaa6cd3

Respectively, here's y1 (the actual y co-ordinate) vs. y2 (the value compactRepresentation found):

y1:d05a0088afc932d091db7483969af1681bcc6c6709bdbf4eac666cbbb200a1c9da5222d7e3711a0ccff987097f235890
y2:2fa5ff775036cd2f6e248b7c69650e97e4339398f64240b1539993444dff5e3525addd271c8ee5f3300678f780dca76f

y1:a645c930d62f644d6ae849dfd1b2d44aef5d02add4499a1f453b7bdca347e2d43a441fc5f190e4aa74e9ddc474ee07bc
y2:59ba36cf29d09bb29517b6202e4d2bb510a2fd522bb665e0bac484235cb81d2ac5bbe0390e6f1b558b16223c8b11f843

y1:d9a1cd0d65a3ae05c802dd4821ba3a625496014d4a7d56e11d2142477578ec6bd881bb4a2b903fa70ba341cc840be423
y2:265e32f29a5c51fa37fd22b7de45c59dab69feb2b582a91ee2debdb88a871393277e44b4d46fc058f45cbe347bf41bdc

y1:b274e945a48106b8677b2fe2d1213050799c51be89c72bca832a3d095079b130873f849b83a9331f123b3e709ea8bbbd
y2:4d8b16ba5b7ef9479884d01d2edecfaf8663ae417638d4357cd5c2f6af864ece78c07b637c56cce0edc4c19061574442

As you can see, the value for y2 is always smaller than y1 (which can seen by comparing the first octets).

Implications

Apple seems to be aware of this quirk, and this seems to be why .compactRepresentation is the only failable representation. I.e. some public keys will output nil when attempting to find their .compactRepresentation. This also seems to be why, when generating a new private key, the initialiser asks the user to specify whether or not the key should be compactRepresentable. This initialiser will ensure that the y co-ordinate for the corresponding public key is guaranteed to be less than its inverse, in order to be compatible with compactRepresentation encoding.

init(compactRepresentable: Bool = true)

The following comment is also made (one of the few in the entire ECDSA section of the library!):

Keys that use a compact point encoding enable shorter public keys, but aren’t compliant with FIPS certification. If your app requires FIPS certification, create a key with init(rawRepresentation:).

Conclusions

For the saving of one byte in encoded form, this compromise seems an odd one to make. The format from compactRepresentation (e.g. for P-384) will output public keys that are 48 bytes in length, whereas the compressed point length is 49 bytes (48 bytes for the x co-ordinate, plus an extra byte to indicate the parity of y).

This way of encoding excludes certain associated public keys from being encoded when using the default private key initialiser. And since a public key is derived from a private key, it reduces the effective key-space of private keys that can be generated (if compactRepresentable = true). Reduced key-space is a very real consequence, and means that the number of possible private keys that can be generated by this initialiser is about half of what it would be without this limitation.

Compatibility with other libraries is also a concern. In other implementations, it is perfectly possible to compute a compressed point from any public key, but when trying to work out a "compact" point (i.e. the compactRepresentation), then this can fail—seemingly without an obvious reason.

Missing Documentation

Other than the note I made above, there isn't much information at all in the CryptoKit documentation about what compactRepresentation is, and what makes it so unique (when compared to point compression). Given that these differences are probably important to be aware of, it would be great to see the documentation updated to describe these differences. Even better, maybe .compactRepresentation could be deprecated, and a new (non-failable) compressedRepresentation could be introduced.