  31 May 2022

#### 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 `y`s "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
``````

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

``````y1:d05a0088afc932d091db7483969af1681bcc6c6709bdbf4eac666cbbb200a1c9da5222d7e3711a0ccff987097f235890
``````
``````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. 31 May 2022

#### 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...[read more]

16 May 2017

Leveraging the new RPi0w to build a WiFi enabled keystroke injection tool (a.k.a. USB Rubber Ducky with WiFi)...[read more]

1 January 2017

Recently I've been working on a drop in class to manage certain "Secure Headers" in PHP.

The project, SecureHeaders is available on GitHub.

#### Why?

If you're familiar with PHP, you'll know that...[read more]

26 August 2016