Ed25519 to X25519 Public Key Derivation

[jose-gataca]

Hi,

I am no expert, but I have been trying to analyze the code to understand how the Key derivation works, because I have not been able to replicate it and make it compatible with other crypto libraries.

As far as I understand, the transportation from Ed25519 to X25519 is possible, but one would need to translate the point coordinates, as explained in this thread

Other implementations, like the one from Noble:noble-ed25519#x25519-and-curve25519 do in fact use that approach:
See line 573 https://github.com/paulmillr/noble-ed25519/blob/main/index.ts#L573

But from what I see, you use that algorithm to derive an X25519 Public Key from a Ed25519 Public Key, and have a completely different algorithm to derive the private key. Can the inverse algorithm also be used for public keys? Where could I find information about the second algorithm you're using?

I have implemented your key derivation algorithms in my code, but when I want to test them I find that the resulting X25519 values do not work correctly on Elliptic Curve Cryptography for curve 25519.
More precisely, if I try to test against: https://github.com/indutny/elliptic I get the following problems:

1. The private key resulting after derivation is modified if I try to import it into an x25519 key (because it is converted into the modulo of the curve to ensure multiplication holds) :https://github.com/indutny/elliptic/blob/43ac7f230069bd1575e1e4a58394a512303ba803/lib/elliptic/ec/key.js#L81
   This however doesn't affect to the deriving a secret to perform DH

2. The public key associated to the obtained private key doesn't match the public key derived from the Ed25519 conversion algorithm

3. The public key derived from the Ed25519 conversion can't be validated as a valid x25519 public key - so no secret can be derived using it to perform a DH. More precisely, the operation failing is the following:
   https://github.com/indutny/elliptic/blob/43ac7f230069bd1575e1e4a58394a512303ba803/lib/elliptic/curve/mont.js#L25

I am not sure if the elliptic library is wrong. I would expect the public keys obtained to be on the montgomery curve, but maybe I am wrong in my understanding?

Thank you in advance for your time and sorry for the long explanation.

[dchest]

I'm sorry, I remember the exact details, but the indutny/elliptic package is know to have non-standard implementation of curve25519: indutny/elliptic#98 (comment)

As for the algorithm, ed2curve indeed implements this approach:

montgomeryX = (edwardsY + 1)*inverse(1 - edwardsY) mod p

I believe this is the most common approach, and it's implemented in the libraries listed here: https://github.com/dchest/ed2curve-js/tree/master#other-libraries (the ones that are mentioned to be compatible).

Can the inverse algorithm also be used for public keys?

If you mean, x25519 key to ed25519, then it's possible but you need to keep a sign somewhere, so it will not be compatible with existing ed25519 implementations. This is the approach used by libsignal, and if I remember correctly, it keeps the sign in signatures.

Where could I find information about the second algorithm you're using?

This is just the preprocessing (hashing and bit clearning) of the secret value that ed25519 does before doing EC operations on them: https://github.com/dchest/tweetnacl-js/blob/master/nacl.js#L704-L713 It's needed here so that the resulting x25519 key will correspond to the converted public key.

[jose-gataca]

Hi,

If you mean, x25519 key to ed25519, then it's possible but you need to keep a sign somewhere, so it will not be compatible with existing ed25519 implementations. This is the approach used by libsignal, and if I remember correctly, it keeps the sign in signatures.

No, I just want ed25519 to x25519 key.
I meant that I have seen in other libraries (like the noble one that I mention on my first comment) use the derivation of the montgomery X point from the edwards Y point using the private key, not the public key.
I wasn't sure if the Y point is contained on the public key or on the private key, it's a bit confusing since on the JWK representation of edwards curves, the public key only contains the X point.

I will explore the issue with the indutny/elliptic package to see if I can make them compatible (it seems it is a matter of reversing the bytes).

[jose-gataca]

Hi,

I can confirm that the compatibility issue seems to be in the other library, their derivation algorithm doesn't work with the test vector on the RFC. I opened them a ticket:
indutny/elliptic#297

I will close this issue, but am still curious about the relation of the Y point to the Edwards public/private keys.