Get points of an Elliptic Curve defined over a Finite Field on Twisted Edwards Extended Coordinates

Question

I'm working on a crypto library, and I need to perform some tests for the implementation of:

• Point Addition.
• Point Subtraction.
• Point Doubling.
• Scalar Mul Point.

The operations are performed on Twisted Edwards Extended Coordinates so (X, Y, Z, T).

The problem is that apart of the Identity point which is: (0,1,1,0), It's being hard for me to get other points to test the operations.

So being the Eq of the curve: -x²+y²=1-$\frac{86649}{86650}$x²y² over the Finite Field modulo P = 2^252 + 27742317777372353535851937790883648493.

(So a = -1 and d = 86649/86650 (mod P).

My idea was to pick random X values and get it's corresponding Y values. Then find T is trivial. But the problem is that I end up with things like:

For whatever X,

Y = +- (sqrt(-x^2 -1)) / (sqrt(d*x^2 -1))

My question is if this approach of getting random points over the curve is correct. And in that case: Since I cannot get decimal values over a Finite Field, how should I treat the sqrts?

With division we know that a/b = a * inverse_mod(b, P).

But what about the SQRT operator? How can I deal with it?

Answer 1

You will have a weistrass equation of the form:

$Y^2 = aX^3..$

Where x is the only unknown variable on the right hand side. Insert a random X value in to the right hand side. Then evaluate the right hand side. This would need to be done modulo whatever prime you are using.

You will end up with an equation of the form:

$Y^2 = K$ where K is your evaluated right hand side.

This number K is either a Quadratic Residue or it is not. You can check this using the Legendre symbol.

If it is, then you can perform the sqrt of K modulo your prime to get the value for $+Y, -Y$

How you do the sqrt depends on what algorithm you decide to use, you can use Tonelli-Shanks which is a more generic square root algorithm