4
$\begingroup$

The paper High-speed high-security signatures by Bernstein et al. introduces the Edwards curve Ed25519.

Concerning the base point $B$, it says that

$B$ is the unique point $(x,4/5)∈E$ for which $x$ is positive

and $B$ corresponds to the basepoint used on the birationally equivalent curve Curve25519.

So I haven't found on any site information about how do they get that $4/5$ value of the $y$ coordinate in order to get a small basepoint generator.

Is there any reason or origin of that $4/5$? How they determined that $4/5$ was part of the group $2^{255} -19$?

$\endgroup$
2
  • $\begingroup$ related Base point in Ed25519? $\endgroup$
    – kelalaka
    Mar 14, 2019 at 23:06
  • $\begingroup$ It's related but it doesn't answer my question. Thanks anyway! It's interesting what it's mentioned there $\endgroup$
    – CPereez19
    Mar 14, 2019 at 23:12

1 Answer 1

5
$\begingroup$

Over the field $\mathbb Z/(2^{255} - 19)\mathbb Z$, Curve25519 is the Montgomery curve $$v^2 = u^3 + 486662 u^2 + u,$$ and edwards25519 is the twisted Edwards curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2.$$ The curves correspond by the birational map

\begin{gather} x = \sqrt{-486664} \frac{u}{v}, \quad y = \frac{u - 1}{u + 1}; \\ u = \frac{y + 1}{y - 1}, \quad v = \sqrt{-486664} \frac{u}{x}. \end{gather}

The standard base point $P$ for the X25519 Diffie–Hellman function has $u(P) = 9$; the $v$ coordinate is not significant because X25519 works exclusively with $u$ coordinates, so there are two possible points, $P = (9, \pm \sqrt{9^3 + 486662\cdot 9^2 + 9})$. The choice of $u(P)$ is arbitrary as long as it corresponds to a point of large prime order—it can't affect security—but was made to be the smallest such integer. The standard base point $Q$ for Ed25519 signature was chosen to correspond to one of the possible choices for $P$, so $$y(Q) = \frac{u(P) - 1}{u(P) + 1} = \frac{9 - 1}{9 + 1} = 4/5;$$ then the $x$ coordinate of $Q$ was chosen arbitrarily from the two options.

$\endgroup$

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.