Base point in Ed25519?

Question

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!

Answer 1

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.