Score:2

Curve448 - Can Ed448 key material be reused for X448?

in flag

Currently I am facing a situation in which Ed448 key pairs (private + public key) are available and the system should be extended by a Diffie-Hellman (ECDH) operation. First of let me summarize what I have understand so far.

Ed448: Is the digital signature algorithm on edwards448.

X448: Is the Diffie-Hellman function build for Curve448.

Curve448: Is an elliptic curve in Montgomery format as specified in RFC7748.

edwards448: Is an elliptic curve which is related to Curve448 by a map as specified in RFC7748.

For Curve25519 I read the Curve25519 over Ed25519 for key exchange? Why? and for me it sounded like it is possible to transform an existing Ed25519 public key to a X25519 key by applying a defined map. Somehow I am not that familiar with all the math being used here. Then after some more reading I found What does "birational equivalence" mean in a cryptographic context? which provided some more insights to me. Then I read RFC7748 again and saw that birationally equivalence is true for Curve448 too. Additionally there is the "edwards448" definition which provides a map between Montgomery and Edwards curve points too. The map to use is defined as:

$$ (u, v) = (\frac{y^2}{x^2}, \frac{(2 - x^2 - y^2)*y}{x^3}) $$

If I understood the above references correctly one should be able to transform the public key to a coordinate to be used in X448 function. The exception is that in case $x$ from above equation is 0 then the map can not be applied and there is no transformation possible. Additionally the chapter related to Curve448 in Elliptic Curve Cryptographx Ecc leads me to the same direction that it may be possible to transform existing key material and reuse it afterwards for X448. If I understood it correctly the private key in ECC is an integer instead of a "curve point".

Now I am curious if it is really possible to transform an existing key pair such it can be reused for ECDH and how. Or if it is necessary to "introduce" a second key pair for ECDH only. Therefore I kindly ask for some help as I am new to this topic.

Score:4
es flag
  1. You do not need to convert the Edwards448 public key to the birationally equivalent Curve448 public key in order to do ECDH. You can just stick to Edwards448. There will be a performance gain if you use Curve448, but depending on your implementation this performance gain might be largely offset by the conversion that the verifier will have to do to derive your Curve448 public key from your Edwards448 public key. You would use the "scalar multiplication" function of your Edwards448 EC library to perform the ECDH operation.

  2. EC private keys are "scalars", which means a positive integer less than the group size of the generator point on that curve. Public keys are points on the curve, and are pairs of "field element" coordinates. A field element is a positive integer less than the prime $p = 2^{448} - 2^{224} - 1$.

  3. If you do decide to convert from Edwards448 to Curve448, then those points will share the exact same scalar private key. Note that due to the way that X448 only uses the Curve448 x-coordinate during the the variable-base-scalar-multiplication key agreement, the mapping will be such that both the Edwards448 points $P$ and $I-P$ will map to the same X448 key agreement Curve448 point (where $I$ is the Edwards448 point at infinity). Luckily for you, you are mapping from Edwards448 to Curve448, which means you do not find yourself with an ambiguity.

  4. The conversion from Edwards448 to Curve448 is simply: $$\texttt{curve448}_{x-coord} = \left(\frac{\texttt{ed448}_{y-coord}}{\texttt{ed448}_{x-coord}}\right)^2$$ Note that the "division" is achieved through multiplication with a modular multiplicative inverse. Your EC library should provide you with this functionality. The operations are done $mod\ p$.

  5. Note that Ed448 will start with a 'raw' 57-byte private key, hash it with SHAKE256, clear the most-significant byte, force the second-most-significant byte's most significant bit to 1, and clear the least-significant byte's two least significant bits. Therefore, it's the hashed-and-altered version of your raw Ed448 private key that you need to use identically with Curve448. Curve448 keys are 56 bytes, and it's safe to slice off the most significant byte of the 57-byte hashed-and-altered Edwards448 key, since that Edwards448 key will always contain zeroes in the most-significant byte. Note that since all field elements are little-endian, the "most-significant byte" is the last byte in the byte array.

  6. It's interesting to observe that the BouncyCastle X448 implementation performs a scalar multiplication with the Curve448 base point by asking the BouncyCastle Ed448 implementation to perform scalar multiplication of the exact same scalar against the Ed448 base point. BouncyCastle then converts the result back to the equivalent Curve448 point using the same formula specified in point 4 above. See the code here.

tr flag
I don't think (4) is correct; that would be the "regular map" but edwards448 is a 4-isogeny, As the OP mentioned it should be $u=y^2/x^2$
knaccc avatar
es flag
@Conrado thanks, you're right, I misread RFC7748. Exactly as you noted, the Edwards variant of Curve448 for which my old formula applies is not the same as the mapping required for Edwards448. I've fixed the answer, and wrote some code to double-check the answer works.
in flag
@knaccc thanks for you response. I have a question related to (5). Is my understanding correct that one can not directly use the private key of an existing key pair for X448. But instead the algorithm mentioned in [RFC8032](https://datatracker.ietf.org/doc/html/rfc8032#section-5.2.5) up to and including step 3 (multiplication excluded) needs to be applied to get the secret scalar s? For me the first steps are the same as in [RFC7748](https://datatracker.ietf.org/doc/html/rfc7748#section-5). Do you want to say this in (5)?
knaccc avatar
es flag
@dbog Yes that's right, what I described in point 5 is what is described in steps 1-3 of section 5.2.5 of RFC8032. That is the private key you use for X448. I don't understand specifically what you're referring to in RFC7748 - can you clarify pls?
in flag
@knaccc thanks for the fast response. In RFC7748 the following is stated in section 5: "Scalars are assumed to be randomly generated bytes.... Likewise, for X448, set the two least significant bits of the first byte to 0, and the most significant bit of the last byte to 1. This means that the resulting integer is of the form 2^447 plus four times a value between 0 and 2^445 - 1 (inclusive)."
knaccc avatar
es flag
Yes, X448 key agreement takes the raw private key you give it, and does `&= 0xFC` on the first byte and `|= 0x80` on the last byte. Since this has already been done to the raw Ed448 private key during steps 1-3 of 5.2.5 of RFC8032 as described in my point 5 above, the hashed-and-altered Ed448 key you use for X448 will not be altered by the X448 clamping, and will be compatible.
in flag
@knaccc thanks a lot! This answered my question :)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.