Subject: [CFRG] EdDSA square roots (RFC 8032)

From: James Muir <[email-masked]>
Date: Wed, 22 Dec 2021 15:10:10 -0500

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 23 Dec 2021 14:27:37 +0200

On Wed, Dec 22, 2021 at 03:10:10PM -0500, James Muir wrote:
> Decoding procedures are given in Sections 5.1.3 (for Ed25519) and
> 5.2.3 (for Ed448).
> 
> 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.
> 
> Unfortunately, no explanatory notes were included with those errata
> and they were rejected.

To be precise, it seems that the "a few multiplications" above means 2
multiplications and 2 squarings. As the fastest methods jointly compute
(u*v^3,u*v^7) and (u^3*v,u^5*v^3) are both 2S+3M, while (u,u*v) can
obviously be jointly computed in 1M. And furthermore turns out that one
of the three multiplies in both original formulas happen to be u*v. The
costs after that are the same in all cases (especially the large
exponents are the same, as effect of those is nontrivial to analyze). So
I agree that there is no reason to prefer the original over Mark's
method.

-Ilari

---

From: James Muir <[email-masked]>
Date: Thu, 23 Dec 2021 11:00:25 -0500

> I agree that there is no reason to prefer the original over Mark's

Thanks for your comment, Ilari.  It is nice to have an RFC 8032 author 
add their voice here.

I'm not sure where this info should be recorded (maybe one of the chairs 
can comment).

For people working from RFC 8032, it is probably most discoverable as an 
erratum (even though it does not involve an actual error).  I see from 
https://www.rfc-editor.org/errata.php it is possible to report an error 
in an existing erratum, so perhaps the two errata that Franck R opened 
could be updated.

-James M

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 23 Dec 2021 18:22:47 +0200

On Thu, Dec 23, 2021 at 11:00:25AM -0500, James Muir wrote:
> I'm not sure where this info should be recorded (maybe one of the
> chairs can comment).
> 
> For people working from RFC 8032, it is probably most discoverable as
> an erratum (even though it does not involve an actual error).  I see
> from https://www.rfc-editor.org/errata.php it is possible to report an
> error in an existing erratum, so perhaps the two errata that Franck R
> opened could be updated.

I once checked all the RFC 8032 errata, but apparently did not send the
results. As for those two errata, my conclusion was "hold for document
update". As the old methods were not wrong, but new methods were Pareto
improvement.

Then for some other errata, my conclusion was that the language in some
parts (especially description of EdDSA2) of RFC 8032 is extremely
confusing. Fortunately, direct descriptions of Ed25519 and Ed448 are
much better, as otherwise the confusing language could have caused
serious issues.

-Ilari

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 23 Dec 2021 09:44:30 -0800

Given the information in this thread, and the observation that some 
parts of RFC 8032 could be a lot clearer, revising the RFC with one that 
obsoletes the old one would be helpful to the community.

--Paul Hoffman