0
$\begingroup$

I just encountered a problem when I tried to understand a basepoint conversion from x25519 to ed25519. I can't really wrap my head around how the value of $x$ can be the stated value below? Can someone please, go through the derivation steps of $x$, especially the modular arithmetic part?

From Base point in Ed25519?

$$ 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$.

$\endgroup$
2
$\begingroup$

All these operations are in a finite field, in particular, a prime field with modulus $p = 2^{255}-19$.

So, for example, $4/5$ is not $0.80$, but $4$ times the inverse of $5$ modulo $p$ (i.e. the number that, when multiplied with $5$, results in the remainder $1$ when divided by $p$). In particular, $1/5$ is $11579208923731619542357098500868790785326998466564056403945758400791312963990$ (because that times 5 is equal to 1 when reduced modulo $p$). The same applies to multiplication, addition and so on - everything is modulo $p$.

The final result is correct, as demonstrated by this Sage code:

sage: F = GF(2^255-19)
sage: xx = (F(1)-(F(4)/F(5))^2) / (F(-1) + (F(121665)/F(121666))*(F(4)/F(5))^2)
sage: xx.sqrt(all=True)
[15112221349535400772501151409588531511454012693041857206046113283949847762202,
 42783823269122696939284341094755422415180979639778424813682678720006717057747]
| improve this answer | |
$\endgroup$

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.