Elliptic curve generator in SageMath for curve25519

Question

I'm trying to learn more about elliptic curves by playing with the math objects in sage.

I'm getting weird results and wonder what I'm doing wrong...

I'm trying to get the generator of the cyclic subgroup from curve25519.

ec = EllipticCurve(GF(2**255-19), [0,486662,0,1,0]) //should gen the curve

ec.lift_x(9) //should give me the generator of the subgroup?

However I get:

(9 : 43114425171068552920764898935933967039370386198203806730763910166200978582548 : 1)

I should get:

(9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1)

What am I doing wrong?

Answer 1

The calculation method is given in rfc7748 A.3. Base Points Section for Curve25519:

The base point for a curve is the point with minimal, positive u value that is in the correct subgroup. The findBasepoint function in the following Sage script returns this value given p and A:

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

And outputs

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

---

In your case use

ec = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
ec.lift_x(9,all)

lift parameter all (bool, default False) – if True, return a (possibly empty) list of all points; if False, return just one point, or raise a ValueError if there are none.

output

[(9 : 43114425171068552920764898935933967039370386198203806730763910166200978582548 : 1),
 (9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1)]

Your code was only finding one point on the curve with $x=9$ due to the default False parameter. If you set True you will get two points with $x=9$ and according to the standard, you need the choose the minimum that is what you wanted.

Also, note that the two $y$'s comes from $P$ and $-P$, so if you add them you will get zero. That is another way to find the other $y$.

k.<a> = GF(2^255 - 19)

y1 = k(14781619447589544791020593568409986887264606134616475288964881837755586237401)
y2 = k(43114425171068552920764898935933967039370386198203806730763910166200978582548)

print y1+y2 

0