2
$\begingroup$

I ran the following Sage script from A.3. Base Points Section of rfc7748 for Curve25519

def findBasepoint(prime, A):
       F = GF(prime)
       E = EllipticCurve(F, [0, A, 0, 1, 0])

       for uInt in range(1, 1e3):
         u = F(uInt)
         v2 = u^3 + A*u^2 + u
         if not v2.is_square():
           continue
         v = v2.sqrt()
         point = E(u, v)
         pointOrder = point.order()
         if pointOrder > 8 and pointOrder.is_prime():
            Q=u^3 + A*u^2 + u
            return u, Q, sqrt(Q), point

res=findBasepoint(2^255 - 19, 486662)
res

(9, 39420360, 14781619447589544791020593568409986887264606134616475288964881837755586237401, (9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1))

and got the expected result (from 4.1. Curve25519):

The base point is u = 9, v = 1478161944758954479102059356840998688726 4606134616475288964881837755586237401.

But now I can't understand how sqrt(39420360) can be such an enormous value. Seems sqrt() is not math.sqrt() here. How did Sage calculate it?

$\endgroup$
  • 1
    $\begingroup$ -1 for yet another question by someone trying to do elliptic curves when they don't know basic modular arithmetic. $\endgroup$ – fkraiem May 3 '17 at 12:35
7
$\begingroup$

It computed the squareroot modulo $2^{255} - 19$

A normal (that is, computed in the field of the reals) squareroot of 39420360 would be that value $Q$ such that $Q^2 = 39420360$, where the squaring operation is done as multiplication within $\mathbb{R}$

What Sage did is the equivalent operation within the field $GF(2^{255}-19)$. That is, it found a value $Q$ such that $Q^2 = 39420360$ when computed in that field, or equivalently, $Q^2 \equiv 39420360 \pmod{2^{255}-19}$.

Because such a $Q$ is an integer between 0 and $2^{255}-19$ (all elements of $GF(2^{255}-19)$ are), it's not surprising it's a large value.

$\endgroup$
  • $\begingroup$ $Q^2=486662$ or $Q^2=39420360$? $\endgroup$ – Meysam Ghahramani May 3 '17 at 13:44
  • $\begingroup$ @MeysamGhahramani: you're correct; I meant 39420360 $\endgroup$ – poncho May 3 '17 at 13:48
  • $\begingroup$ Thanks. It took me some time to just vaguely understand elliptic curves over a finite field calculations. I'll drop my implementation of X25519 function here. $\endgroup$ – savas Jun 1 '17 at 7:29

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.