6
$\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)\in E$ for which $x$ is positive, and
  • $B$ corresponds to the basepoint used on the birationally equivalent curve Curve25519.

The actual coordinates of $B$ are: [15112221349535400772501151409588531511454012693041857206046113283949847762202, 46316835694926478169428394003475163141307993866256225615783033603165251855960]

I'm not sure I fully understand the choice of this point:

  1. I can't really see that $B$ is unique and that '$x$ is positive'. (What does positive mean here?)

  2. Does this point have any special security properties that other points do not have, or is it just a 'rigid' choice to convince us that no backdoor was built-in?

If you know anything about this point, please tell me! Many thanks!

$\endgroup$
4
$\begingroup$

1. The equation $-x^2+y^2=1-(121665/121666)x^2y^2$ defining the curve $E$ is quadratic in $x$, hence for any given $y\in\mathbb F_q$, there are at most two points on $E$ which have $y$ as their second coordinate. In this case, the two possible $x$-coordinates for a point on $E$ with $y$-coordinate $4/5\in\mathbb F_q$ are the solutions to the equation $$ -x^2+(4/5)^2=1-(121665/121666)x^2(4/5)^2 \text. $$ that is $$ x^2=\frac{1-(4/5)^2}{-1+(121665/121666)\cdot(4/5)^2} \text. $$ Now by considering the symmetric representants (that is, from the set $\{-(q-1)/2,\dots,(q-1)/2\}$) for the elements of $\mathbb F_q$, we can interpret one of the roots of this equation as being positive and the other as negative, corresponding to the signedness of their symmetric representant. The unique "positive" solution to the equation above is precisely $15112221349535400772501151409588531511454012693041857206046113283949847762202$.

2. As far as I am aware, the base point is chosen pretty arbitrarily. As described in the Ed25519 paper, it arises from the choice $u=9$ in the original Curve25519 paper, but there seems to be no justification for that either. However, to the current state of knowledge, there are only very few bad choices for the base points, most importantly those whose order has no large prime divisor. (A nice overview of known weaknesses is SafeCurves.) Besides that, the choice of base point is not all that important, as the discrete logarithm problem has a property called random self-reducibility: An attacker who can efficiently compute logarithms with respect to a sufficiently large fraction of possible base points can in fact compute logarithms with respect to all base points.

$\endgroup$
  • 4
    $\begingroup$ Actually, this random self-reducibility allows us to make a stronger statement; if there is a point (with sufficiently high order) for which we can efficiently compute the discrete log with that as the base, we can compute the discrete log with respect to any base (hence there are either no weak points, or all points are weak). In addition, random self-reducibility also applies to the (computational) Diffie-Hellman as well; if you can solve it with respect to a (high order) point, you can solve it with any base point $\endgroup$ – poncho Aug 9 '15 at 21:40
  • 1
    $\begingroup$ SafeCurves has a sort-of justification for 9 at the bottom of the page here: safecurves.cr.yp.to/rigid.html $\endgroup$ – otus Aug 10 '15 at 8:23
  • 1
    $\begingroup$ @yyyyyyy, sorry for missing your reply, the other values smaller than 9 do not work either, since their order isn't the desired $r = \#E / 8$. $\endgroup$ – otus Sep 2 '15 at 7:55

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.