[CFRG] EdDSA square roots (RFC 8032)

[James Muir <[e-mail]>]

https://datatracker.ietf.org/doc/html/rfc8032

Ed25519 and Ed448 use point compression and require a square-root-mod-p 
operation to recover the x-coordinate from an expression involving y. 
Decoding procedures are given in Sections 5.1.3 (for Ed25519) and 5.2.3 
(for Ed448).

Mark Wooden noted in a 2017 blog post that the square-root computation 
can be simplified:

   https://vox.distorted.org.uk/mdw/2017/05/simpler-quosqrt.html

I wanted to summarize Mark's observation here so others can comment on 
it.  The method given in RFC 8032 is taken from page 15 of the Ed25519 
paper, "High-speed high-security signatures", but I don't see any reason 
why it should be preferred over Mark's method, which saves a few 
multiplications.

Link to the Ed25519 paper:

   http://ed25519.cr.yp.to/ed25519-20110926.pdf

Note that the same observation appears to have also been submitted to 
the RFC 8032 Errata by Franck Rondepierre:

   https://www.rfc-editor.org/errata/eid5758
   https://www.rfc-editor.org/errata/eid5759

Unfortunately, no explanatory notes were included with those errata and 
they were rejected.

Here is my description of the simplified method.

Let u = y^2 - 1 and v = d*y^2 + 1.

We want to find a square root of the ratio u/v, assuming that u/v is a 
square;  i.e. we want to find x such that x^2 = u/v.

Start by computing w = u*v.

If u/v is square, then w is also a square, which in turn implies that 
the order of w modulo p divides (p-1)/2.

Consider the Ed448 case first, where p is congruent to 3 mod 4.

Compute x = u * w^((p-3)/4).  Then x is a square root of u/v because

   x^2 = u^2 * w^((p-3)/2)
       = u^2 * w^((p-1)/2 - 1)
       = u^2 * w^(-1)
       = u/v

So, we see that if u/v is a square, then u*w^((p-3)/4) is one of its 
square roots.  ( Compare this to the expression given in Section 5.2.3: 
u^3*v * (u^5 * v^3)^((p-3)/4). )

For the Ed25519 case, p is congruent to 1 mod 4 and 5 mod 8.  Minus one 
is a square modulo p; let i denote one of its square roots.

The approach suggested in the Ed25519 paper is to find x such that x^4 = 
(u/v)^2, which implies that x^2 = u/v or x^2 = -u/v, which implies that 
either x or i*x is a square root of u/v.

Compute x = u * w^((p-5)/8).  We have

   x^4 = u^4 * w^((p-5)/2)
       = u^4 * w^((p-1)/2 - 2)
       = u^4 * w^(-2)
       = (u/v)^2

So, we see that if u/v is a square, then either u*w^((p-5)/8) or 
i*u*w^((p-5)/8) is one of its square roots.  ( Compare this to the 
expression given in Section 5.1.3:  u*v^3 * (u * v^7)^((p-5)/8). )

-James M