Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two erratas opened against RFC 8032 (EdDSA)

From: Chloe Martindale <[email-masked]>
Date: Sun, 13 Feb 2022 23:38:51 +0000

Hi all,

sorry for being a bit slow. I agree with Thomas that both errata are
correct. One extra detail: the original formulas are true in more general
situations (for example, in the first case, I believe this holds if p = 5
mod 8). The proposed errata are correct, as Thomas proved above, but only
hold for these specific choices of p; the second one even relies on u and v
being constructed from d and y rather than just random field elements.
(These are things I just checked experimentally in Sage). They are slightly
faster, so maybe worth having, but perhaps with this caveat added in case
people erroneously try to use these formulae for computing square roots in
other situations.

All the best,
Chloe

On Fri, 28 Jan 2022 at 13:48, Thomas Pornin <[email-masked]>
wrote:

> As for efficiency, the gain is slight. The modular exponentiation (with
> exponent (p-5)/8) costs at least 250 squarings, and an extra dozen
> multiplications. The proposed formula saves two squarings and three
> multiplications, i.e. we are talking about an improvement of less than 2%.
> Nothing ground-breaking here.
>
> Thomas
>
> On 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Pornin" <
> [email-masked] on behalf of thomas.pornin=
> [email-masked]> wrote:
>
>     OK, the proposed formulas are correct. The original formulas were
> correct, too.
>
>     For p = 2^255-19: given u and v in the field, then:
>     v*x^2 = v*(u*(u*v)^((p-5)/8))^2 = v*(u^2)*(u^((p-5)/4))*(v^((p-5)/4))
> = u * (u^((p-1)/4) * v^((p-1)/4))
>     If u/v is a square (and u != 0, v != 0) then u^((p-1)/2) * v^((p-1)/2)
> = 1 (i.e. both u and v are squares, or both u and v are non-squares).
>     (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) *
> v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 = u or -u.
> In both cases, this leads to a square root of (u/v) by applying step 3 of
> RFC 8032 section 5.1.3: if we got x such that v*x^2 = u, then x is a square
> root of u/v; if x is such that v*x^2 = -u, then x*i is a square root of
> u/v, using i = sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), and it is
> indeed a square root of -1).
>     Thus, the proposed formula, inserted in the RFC text, indeed yields a
> square root of u/v if it exists. It does not necessarily yield the same
> square root as the original formula, but that does not matter since step 4
> of the decoding process normalizes the solution using the least significant
> bit.
>     Note that step 3 of section 5.1.3 includes explicitly checking that
> v*x^2 = u or -u, and if u/v is not a square then there cannot be a x value
> that matches that test; thus, the new formula does not incorrectly return a
> value for a non-square u/v.
>
>     For p = 2^448 - 2^224 - 1, it is slightly simpler:
>     v*x^2 = v*(u*(u*v)^((p-3)/4))^2 = u * (u^((p-1)/2) * v^((p-1)/2)
>     If u/v is a square then u^((p-1)/2) * v^((p-1)/2) = 1 (see above),
> hence v*x^2 = u and x is necessarily a solution. Again, this is tested
> explicitly (step 3 of section 5.2.3) so there is no risk of incorrectly
> accepting a non-square.
>
>     As noted above, the normalizing step means that it makes no difference
> which of the two square roots you get, at least in the context of RFC 8032.
> I think it has some slight impact in another context, where the exact
> choice of the square root can help simplify a formula, but my memory is a
> bit hazy here. This may be related to the fact that, with p = 2^448 - 2^224
> - 1, exactly one of the two square roots of u/v is itself a square, and the
> original RFC formula always returns that one, while the proposed formula
> may return the square root which is a non-square; again, this does not
> matter in the case of RFC 8032.
>
>     Thomas
>
>     From: Crypto-panel <[email-masked]> on behalf of
> "Stanislav V. Smyshlyaev" <[email-masked]>
>     Date: Friday, January 28, 2022 at 07:45
>     To: Thomas Pornin <thomas.pornin=[email-masked]>
>     Cc: Chloe Martindale <[email-masked]>, "
> [email-masked]" <[email-masked]>, "[email-masked]" <
> [email-masked]>
>     Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two
> erratas opened against RFC 8032 (EdDSA)
>
>     Thank you, Thomas!
>
>     Regards,
>     Stanislav
>
>     On Fri, 28 Jan 2022 at 15:43, Thomas Pornin <thomas.pornin=
> [email-masked]> wrote:
>     I will have a look too. This looks weird.
>
>     Thomas
>
>     From: Crypto-panel <[email-masked]> on behalf of Chloe
> Martindale <[email-masked]>
>     Date: Friday, January 28, 2022 at 06:24
>     To: "Stanislav V. Smyshlyaev" <[email-masked]>
>     Cc: "[email-masked]" <[email-masked]>, "
> [email-masked]" <[email-masked]>
>     Subject: EXTERNAL: Re: [Crypto-panel] Request for review of two
> erratas opened against RFC 8032 (EdDSA)
>
>     Hi all,
>
>     I can take a look at this.
>
>     All the best,
>     Chloe
>
>     On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <
> [email-masked]> wrote:
>     Dear Crypto Review Panel experts,
>
>     We've received a request to have a closer look at two errata opened
> against RFC 8032:
> https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5758&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=k49Gr2WuYIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&amp;reserved=0,
>
> https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5759&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=B6QR5Z50rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3D&amp;reserved=0.
>
>
>     Previously these two errata were rejected since no mistakes in the
> current text of the draft had been found. At the same time, the two errata
> might provide more effective ways for square-roots-mod-p.
>
>     We would like to ask a Crypto Panel expert (or two experts) to check
> the proposed formulas, i.e., to verify that they are correct and more
> effective (always or in a vast majority of cases).
>
>     Any volunteers?
>
>     Best regards,
>     Stanislav (for chairs)
>     _______________________________________________
>     Crypto-panel mailing list
>     [email-masked]
>
> https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=GEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=0
>     _______________________________________________
>     Crypto-panel mailing list
>     [email-masked]
>
> https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=GEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=0
>
>     _______________________________________________
>     Crypto-panel mailing list
>     [email-masked]
>
> https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=GEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=0
>
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Mon, 14 Feb 2022 08:41:48 +0300

Dear Chloe,

Thank you so much for your work!

>> but only hold for these specific choices of p
Do I understand correctly that for this specific RFC the formulas are
always correct (i.e., the text of errata can be used in the updated version
of the RFC without additional remarks), but are not always correct in other
cases?

Regards,
Stanislav

On Mon, 14 Feb 2022 at 02:39, Chloe Martindale <[email-masked]>
wrote:

>>     If u/v is a square (and u != 0, v != 0) then u^((p-1)/2) *
>> v^((p-1)/2) = 1 (i.e. both u and v are squares, or both u and v are
>> non-squares).
>>     As noted above, the normalizing step means that it makes no
>> difference which of the two square roots you get, at least in the context
>> of RFC 8032. I think it has some slight impact in another context, where
>> the exact choice of the square root can help simplify a formula, but my
>> memory is a bit hazy here. This may be related to the fact that, with p =
>> 2^448 - 2^224 - 1, exactly one of the two square roots of u/v is itself a
>> square, and the original RFC formula always returns that one, while the
>> proposed formula may return the square root which is a non-square; again,
>> this does not matter in the case of RFC 8032.
>>
>>     Thomas
>>
>> Chloe Martindale <[email-masked]>

---

From: Chloe Martindale <[email-masked]>
Date: Mon, 14 Feb 2022 10:02:36 +0000

Dear Stanislav,

Yes they are correct. No remarks are needed for correctness, but for
completeness I would suggest adding a citation/justification and a comment
that these speed ups are possible only in these specific cases. If you
prefer to keep it simple and just accept based on correctness that's also
fine with me.

All the best,
Chloe

On Mon, 14 Feb 2022, 05:40 Stanislav V. Smyshlyaev, <[email-masked]>
wrote:

>>>     v*x^2 = v*(u*(u*v)^((p-5)/8))^2 =
>>> v*(u^2)*(u^((p-5)/4))*(v^((p-5)/4)) = u * (u^((p-1)/4) * v^((p-1)/4))
>>>     Thus, the proposed formula, inserted in the RFC text, indeed yields
>>> a square root of u/v if it exists. It does not necessarily yield the same

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 15 Feb 2022 08:36:49 +0300

Chloe and Thomas,

Thank you so much for your reviews!

We'll mark the errata as "hold for future update", with a comment about
formulas being only slightly faster than the existing ones.

Thanks again!

Regards,
Stanislav (on behalf of CFRG Chairs)

On Mon, 14 Feb 2022 at 13:02, Chloe Martindale <[email-masked]>
wrote:

>>>> [email-masked]" <[email-masked]>, "[email-masked]"
>>>> <[email-masked]>
>>>>     We would like to ask a Crypto Panel expert (or two experts) to
>>>> check the proposed formulas, i.e., to verify that they are correct and more