# Elliptic curve generator in SageMath for curve25519

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?

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))

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
• Thank you very much! Nov 21, 2019 at 7:49