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:



   MESSAGE (length 1 byte):


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.


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
        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.

  1. The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
  2. $P$ satisfies the curve equation - against the twist attack.
  • $\begingroup$ I am not sure I follow - I don't think this response addresses my question. The functions that you mention seem to be meant for Ed25519, where we are dealing with 32-byte quantities. In addition, in RFC 8032 for Ed448 projective coordinates are used, not extended homogeneous ones. $\endgroup$ – SWK Apr 13 at 20:58
  • $\begingroup$ @SWK thanks for the notice. No RFC as I can see shows this. NIST 186-5 mentioned that I've forgot. sorry for the blunder. $\endgroup$ – kelalaka Apr 13 at 21:30
  • $\begingroup$ That's OK. The question still remains though - how can one get a 57-byte long public, when all the operations involved in the scalar multiplication must carry out modular reductions over a 56-byte modulus? The only way out I see is the description of the encoding process in section 5.2.2, which would seen to imply that one has to append a 0x00 byte to the end of the y affine coordinate. Is this your reading as well? $\endgroup$ – SWK Apr 13 at 21:55
  • $\begingroup$ Isn't clear? The final octet (byte) of the $y$ is always zero. This bit used to store the LSB of the x coordinate on the MSB of the final octet. That still makes the 57 octets. Later this used for the resolution. $\endgroup$ – kelalaka Apr 13 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.