Public key derivation for Ed448

Question

Another potentially silly question here, but I seem to have developed tunnel vision and I am missing something very basic.

In RFC 8032 one can find a number of test vectors for Ed488 - for example:

SECRET KEY:
   c4eab05d357007c632f3dbb48489924d
   552b08fe0c353a0d4a1f00acda2c463a
   fbea67c5e8d2877c5e3bc397a659949e
   f8021e954e0a12274e

   PUBLIC KEY:
   43ba28f430cdff456ae531545f7ecd0a
   c834a55d9358c0372bfa0c6c6798c086
   6aea01eb00742802b8438ea4cb82169c
   235160627b4c3a9480

   MESSAGE (length 1 byte):
   03

   SIGNATURE:
   26b8f91727bd62897af15e41eb43c377
   efb9c610d48f2335cb0bd0087810f435
   2541b143c4b981b7e18f62de8ccdf633
   fc1bf037ab7cd779805e0dbcc0aae1cb
   cee1afb2e027df36bc04dcecbf154336
   c19f0af7e0a6472905e799f1953d2a0f
   f3348ab21aa4adafd1d234441cf807c0
   3a00

The public key, in the encoded format, is 57 bytes in size. Now my understanding is that the public key is obtained by computing the scalar product of the private key (encoded as described in RFC 8032) times the base point. The operations are to be carried out mod the prime p = 2^448 - 2^224 - 1, which is 56 bytes long.

How can the public key be 57 bytes long, if all the operations are mod a 56 bytes long quantity? It is true that the public key is not directly the scalar product above, for this product has to be encoded as described in RFC 8032. However, this encoding is very straightforward, and can't add an extra byte.

I must be missing something very obvious here - but I can't see what it is.

Answer 1

If you read all of the RF 8032 you will see that there is a compression (endcodings) of the points.

def point_compress(P):
    zinv = modp_inv(P[2])
    x = P[0] * zinv % p
    y = P[1] * zinv % p
    return int.to_bytes(y | ((x & 1) << 255), 32, "little") 

Compression just stores the sign and restores it back with this information

def point_decompress(s):
    if len(s) != 32:
        raise Exception("Invalid input length for decompression")
    y = int.from_bytes(s, "little")
    sign = y >> 255
    y &= (1 << 255) - 1

    x = recover_x(y, sign)
    if x is None:
        return None
    else:
        return (x, y, 1, x*y % p)

The above has been defined for Ed25519, there is no code for Ed448 in the RFCs as I can see. However NIST.FIPS.186-5-draft defined it for both;

For a curve point $(x,y)$ with coordinates in the range $0 \leq x, y < p,$ first encode the $y$-coordinate as a little-endian string of 32 octets for Ed25519 or 57 octets for Ed448. For Ed25519, the most significant bit of the final octet is always zero, while for Ed448, the final octet is always zero. To form the encoding of the point, copy the least significant bit of the x-coordinate to the most significant bit of the final octet

As we can see, the LSB of the $x$-coordinate is placed in the MSB of the final octet (byte) of the $y$ coordinate. Therefore, the total size of the public-key is 57 bytes.

Although the compression has a time-consuming and little advantage on the storage/transmission it also helps in the point validation. The second and third options are verified during decompression.

2. The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
3. $P$ satisfies the curve equation - against the twist attack.