2
$\begingroup$

Using

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

it is possible to transport an Edwards curve point (Ed25519 public key) to the Montgomery curve. Does it have any side effects if the Ed25519 public key is not valid, in case of a small subgroup or invalid curve attack for example?

And if yes, what would be the best solution to handle that properly?

$\endgroup$
10
  • $\begingroup$ Why do you want to convert? Do you want to use the same key for ed25519 and DHKE X25519? They are birationally eqiuvalent are you asking 25519 point validation or X22519 key exchange? $\endgroup$
    – kelalaka
    Feb 7, 2022 at 13:22
  • $\begingroup$ My goal is to create a shared secret using x25519 ECDH, but the existing protocol shares ed25519 keys. So to be a bit confusing, both. $\endgroup$
    – FooBar
    Feb 7, 2022 at 13:28
  • $\begingroup$ Which protocol are you talking about? X25519 is designed for ECDH. The one who uses Ed25529 for ECDH use it incorrectly. See libsodium.. $\endgroup$
    – kelalaka
    Feb 7, 2022 at 14:12
  • 1
    $\begingroup$ And convertion is $$x = \frac{u}{v}\sqrt{-486664}, \quad y = \frac{u - 1}{u + 1}$$ and use XEd25519 as used by Signal uses Curve25519? $\endgroup$
    – kelalaka
    Feb 7, 2022 at 14:40
  • 1
    $\begingroup$ Is there a reason you can't just create a fresh, ephemeral X25519 keypair for each ECDH, and have each party sign the X25519 public key with their Ed25519 key? That would provide forward secrecy. And if there is a good reason to have long-term keys for ECDH, is there a reason that people can't present both an Ed25519 public key and an X25519 public key to others? They're only 32 bytes each. $\endgroup$
    – knaccc
    Feb 7, 2022 at 20:17

1 Answer 1

3
$\begingroup$

Curve25519 and Ed25519

A Montgomery curve defined over a field $K$ is defined as; $$M_{A,B}: Bv^2 = u^3 + Au^2 + u$$ for certain $A,B \in K$ and with $B(A^2-4) \neq 0$.

Curve25519 uses prime $q = 2^{255} − 19$ to form the finite field $\mathbb{F}_q$ and first defined for ECDH and later named X25519. Montgomery equation is $$v^2 = u^3+486662 u^2+u$$ with $486664$ is a square in $\mathbb{Z}_p$, i.e. It is a Quadratic Residue (QR). $u = 9$ has choosen as a base point. The Weierstrass form ( one need for SageMath)

$$y^2 = x^3 + A x + B $$

This curve “Curve25519” is birationally equivalent over $\mathbb{Z}_p$ to the Edwards curve Ed25519 $$x^2 + y^2 = 1 + (121665/121666)x^2y^2$$ with;

$$x = \frac{\sqrt{486664}u}{v}, \quad y = \frac{(u − 1)}{(u + 1)}$$

The reverse is operations is;

$$u = \frac{(y + 1)}{(1 - y)}, \quad v = \frac{\sqrt{486664}u}{x}$$

The Edward form has an isomorphic curve

$$-x^2 + y^2 = 1 - (121665/121666)x^2y^2$$ since $-1$ is QR in a $\mathbb Z_p$


Questions

montgomeryX = (edwardsY + 1)*inverse(1 - edwardsY) mod p it is possible to transport an edwards curve point (ed25519 pubic key) to montgomery curve.

Yes, As given above, from Montgomery to Edwards $$u = \frac{(y + 1)}{(1 - y)}$$

Does it have any side effects if the ed25519 public key is not valid, in case of a small subgroup or invalid curve attack for example?

Edward25519 key can be converted to Curve25519 and if already the secret key is constructed with the legitimate user's responsibility

  • The legitimate users are assumed to generate independent uniform random secret keys. A user can, for example, generate 32 uniform random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the last byte, and set bit 6 of the last byte.

In a set definition, we want the secret keys of X25519 as

$$\{n: n \in 2^{254} +8\{0,1,2,\dots,2^{251}-1 \}\},$$ in other words, select a uniform random number between $[0,2^{251}-1]$ multiply it with $8$ than add $2^{254}$.

The order of base point is (little-endian);

edd3f55c1a631258d69cf7a2def9de1400000000000000000000000000000010

The clearing $0,1,2$ makes sure that

  • we are not in a small group for which an attacker takes advantage of DHKE and reveals information at most $\lceil log_2 h\rceil$ bits (the co-factor $h=8$ in Curve25519).

  • and clear 7 and set 6 is against a possible timing attack.

The below is the maximum value (little-endian) and we can see that there two private keys can have the same public key, however, this is a negligible but findable event.

0x8ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7

then there is no need since the birational equivalence will produce points that have no small order if the legitimate user's already used the rules.

Under the birational equivalence of Curve25519 and edwards25519, each X25519 public key corresponds to two possible Ed25519 public keys). X25519 uses only $x$ coordinate (where the name comes) and Ed25519 uses the coordinates of the points. When we have only $x$ coordinate of a point, there are two possible points $(x,y)$ and $(x,-y)$ except $y=0$.

And if yes, what would be the best solution to handle that properly?

There is no danger of Validating the points.


Some extra

Using the same key

I cannot directly say that is insecure, however, our general rule is not using the same key for different purposes. Until one proves that there is no danger keeping yourself away from using the same key for different purposes.

It might be better to have one uniform random 256-bit key and derive two keys with HKDF-expand for both X25519 and Ed25519.

X25519

Remember that the public key is fixed and when you execute a DHKE this means that you have static-static DHKE. This doesn't have forward secrecy. The better is what Signal protocol does; double rachet and you can sign the new public key with Ed25519.

$\endgroup$
0

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.