Montgomery Curves

import os

def generate_25519_key():
	#Generate Random Number
	key = bytearray(os.urandom(32))
	#Set the last 3 bits to Zero this makes the random divisible by 8. 
	#Where 8 is the cofactor of the curve. 
	#This makes sure that every point multiplied by this is in the correct subgroup
	key[0] &= 0xF8
	#Clear the Highest bit to 0
	key[-1] &= 0x7F
	#Set the second highest bit to 1
	key[-1] |= 0x40

	return int.from_bytes(key, byteorder='little')

from sage.all import *

def generator_point(E):
	order_coprime = [p for p, _ in E.order().factor()]
	for test_x in range(1, 100):

		test_points = E.lift_x(Integer(test_x), all=True)

		if test_points:
			pointOrder = test_points[0].order()
			if pointOrder < 20:
				print(f"{test_x},{pointOrder}: {test_points}")



E = EllipticCurve(GF(pow(2,255) - 19), [0, 486662, 0, 1, 0])
print(f"Curve Order: {E.order()}")
print(f"Order Factors: {E.order().factor()}")

g = generator_point(E)
print(g)
"""
Order Factors: 2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989
1,4: [(1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1), (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)]
"""

# Test That the 

E = EllipticCurve(GF(pow(2,255) - 19), [0, 486662, 0, 1, 0])
print(f"Curve Order: {E.order()}")
print(f"Order Factors: {E.order().factor()}")

generator_point = E.lift_x(Integer(9))
generator_point_order = generator_point.order()

#This Point is in a small subgroup of size 4
subgroup_points = E.lift_x(Integer(1), all=True)
print(f"subgroup_points: {subgroup_points}")
#subgroup_points: [(1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1), (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)]

#Test that the G.order() * point is the infinity point
# This will work on any multable of G since G*random*order can be simplified to INF*random
test_point1 = subgroup_points[0] * generator_point_order
print(f"g_ord * subgroup_points: {test_point1}")
#g_ord * subgroup_points: (1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1)

test_point2 = generator_point * generator_point_order
print(f"g_ord * generator_point: {test_point2}")
#g_ord * generator_point: (0 : 1 : 0)