9
$\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$

1 Answer 1

5
$\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$
7
  • 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, 2015 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, 2015 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, 2015 at 7:55
  • $\begingroup$ @yyyyyyy if $y = 4/5$, how come the y-coordinate of $B$ be 46316835694926478169428394003475163141307993866256225615783033603165251855960 and not $4/5$? $\endgroup$
    – einstein
    Dec 11, 2019 at 18:27
  • $\begingroup$ hmm... I think I have a problem understanding the derivation of the x-value as well. Not really experienced with modular arithmetic at this level. $\endgroup$
    – einstein
    Dec 12, 2019 at 10:03

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.