3
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$
  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.

$\endgroup$
7
  • $\begingroup$ 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$ $\endgroup$
    – Conrado
    May 6, 2022 at 13:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – knaccc
    May 6, 2022 at 16:49
  • $\begingroup$ @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 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. Do you want to say this in (5)? $\endgroup$
    – dbog
    May 9, 2022 at 7:27
  • $\begingroup$ @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? $\endgroup$
    – knaccc
    May 9, 2022 at 8:44
  • $\begingroup$ @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)." $\endgroup$
    – dbog
    May 9, 2022 at 9:03

Your Answer

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

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