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 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
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
y), we can think about whether we need to store both
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
y actually relates
y^2, and so we cannot quite uniquely work out
x. To account for this we'd need to also store the sign of
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.
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
-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
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
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 are "related" by being "additive inverses" of one-another. This means that when we add the two numbers together, we get
3 + (-3) = 0).
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.
-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.
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 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
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
This is how point compression works for an odd
yis even, then we use the prefix
yis odd, then we use the prefix
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
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.
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
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
y1 (the actual
y co-ordinate) vs.
y2 (the value
As you can see, the value for
y2 is always smaller than
y1 (which can seen by comparing the first octets).
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
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
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
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.
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.