2
$\begingroup$

My apologies if this is obvious, but the truth is that I am confused about this.

I am looking into RFC 8032 for test vectors for Ed25519, and I have some doubts concerning the information presented in section 7.1 in that document. At the top of this section one can find the following data:

SECRET KEY:
   9d61b19deffd5a60ba844af492ec2cc4
   4449c5697b326919703bac031cae7f60

PUBLIC KEY:
   d75a980182b10ab7d54bfed3c964073a
   0ee172f3daa62325af021a68f707511a

My understanding is that the secret key is a randomly generated string of 64 bytes, the first 32 bytes of which are then further manipulated. The resulting string is interpreted as an integer, according to some rules described in that RFC, and then used to obtain the public key by adding the selected base point to itself the number of times specified by the secret key.

My questions are the following:

  1. As displayed in the RFC, is the secret key meant to be interpreted as an integer? If so, is the integer already displayed in left-to-right form - that is, with 9 being its most significant hexadecimal digit, and 0 its least significant one?

  2. Regardless of whether it is displayed as an integer or a string, is this supposed to be after the bit manipulations that the RFC specifies that should be applied to the 64 bytes obtained by hashing 32 randomly generated bytes?

To put the two questions above in a different way, is the public key obtained by adding the base point 0x9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 times to itself?

  1. As for the public key, my guess is that what is displayed is the point in the curve obtained by adding the base point to itself as mentioned above, but subjected to the compression technique described in the document. Is this correct?
$\endgroup$

1 Answer 1

1
$\begingroup$
  1. Encoding is Little-Endian ( section 5.1.2.)

    All values are coded as octet strings, and integers are coded using little-endian convention, i.e., a 32-octet string h h[0],...h[31] represents the integer h[0] + 2^8 * h[1] + ... + 2^248 * h[31].

  2. Key Generation (section 5.1.5)

    1. Hash the 32-byte private key using SHA-512, storing the digest in a 64-octet large buffer, denoted h. Only the lower 32 bytes are used for generating the public key.

    Therefore you have 32-byte private key that needs to be hashed with SHA-512.

    1. Prune the buffer: The lowest three bits of the first octet are cleared, the highest bit of the last octet is cleared, and the second highest bit of the last octet is set.

    This is for the lower 32-byte output of the SHA-512

    1. Interpret the buffer as the little-endian integer, forming a secret scalar s. Perform a fixed-base scalar multiplication [s]B.
  3. Public key (5.1.5)

    1. The public key A is the encoding of the point [s]B. First, encode the y-coordinate (in the range 0 <= y < p) as a little- endian string of 32 octets. The most significant bit of the final octet is always zero. To form the encoding of the point [s]B, copy the least significant bit of the x coordinate to the most significant bit of the final octet. The result is the public key.
  4. Python Sample (Section 6)

   # Points are represented as tuples (X, Y, Z, T) of extended
   # coordinates, with x = X/Z, y = Y/Z, x*y = T/Z

    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")
    
    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)
    
    ## These are functions for manipulating the private key.
    
    def secret_expand(secret):
        if len(secret) != 32:
            raise Exception("Bad size of private key")
        h = sha512(secret)
        a = int.from_bytes(h[:32], "little")
        a &= (1 << 254) - 8
        a |= (1 << 254)
        return (a, h[32:])
    
    def secret_to_public(secret):
        (a, dummy) = secret_expand(secret)
        return point_compress(point_mul(a, G))
$\endgroup$
9
  • $\begingroup$ So, in the case of the test vector that I mentioned, the public key is obtained by adding the base point 0x9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 times to itself - right? $\endgroup$
    – Jay Smith
    Feb 3, 2021 at 1:46
  • $\begingroup$ No, First, you have to take SHA-512 of the secret then you can use the lower part. The Python code explains very well, too. See secret_to_public calls secret_expand and uses the lower 32-byte with cleaning the lower 3 bits and setting the highest bit as mentioned in the rfc. You can use the Python code as a test base and test vector detailer for your target language. $\endgroup$
    – kelalaka
    Feb 3, 2021 at 9:44
  • $\begingroup$ Oh, thanks - that's what I wanted to clarify. The 32 bytes 0x9d61...7f60 are then the 32 randomly generated bytes, that must then be hashed with SHA-512. Out of the resulting 64 byte digest we just keep the leftmost 32 (and discard the rest) do the bit tinkering described in the RFC, interpret the resulting 256 bit string as a little-endian integer, and obtain the public key by adding the base point to itself the number of times specified by that integer. Just writing it down here in gory detail to make sure that I got it. $\endgroup$
    – Jay Smith
    Feb 3, 2021 at 15:35
  • $\begingroup$ Randomly not enough, uniform randomly is better. The other part is not discarded, it is still used, why do we need hashing if we have already uniform random?. It is used during the signing process, see page 22 of the RFC. $\endgroup$
    – kelalaka
    Feb 3, 2021 at 16:39
  • $\begingroup$ In section 5.1.6 of RFC 8032 it is specified that the private key is a 32 byte octet string. On reading section 5.1.5 it would seem that the private key is the original 32 random bytes. The SHA-512 digest and the bit tinkering seem to be there for computational efficiency reasons - the bit tinkering at least. I don't see where the rightmost 32 bytes of the SHA-512 digest are being used though. $\endgroup$
    – Jay Smith
    Feb 3, 2021 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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