Subject: [Cfrg] Curve25519 meets NUMS rigidity definition

From: Watson Ladd <[email-masked]>
Date: Sat, 3 Jan 2015 13:07:07 -0500

Dear all,

In  draft-black-numscurves-02 we see the following sentence: "The
domain parameters SHALL be generated in a simple,  deterministic
manner, without any secret or random inputs."

If we actually take this sentence as written, it would seem the
Brainpool curves work. After all, there were no secret or random
inputs to the algorithm that output the Brainpool curves. Same with
the BADA55 curves: there were no secret or random inputs. I doubt that
these were what was meant to be rigid.

So it's clear to me that this was scrivener's error: something else
was meant. But what?

Given the details of the various processes that have all be claimed to
be rigid by the NUMS group, it seems to be that one takes a
parametrization of a certain set of elliptic curves, and searches for
the minimal parameter achieving certain properties forced by security
considerations, then takes the generator with one coordinate minimal,
and this is the only kind of method allowed.

So I'll take p=2^255-19, y^2=x^3+ux^2+x, and search for the minimal
positive u that makes the order of the curve 8 times prime, order of
the twist 4 times other prime, and minimal x coordinate on the curve
with prime order for the generator, with u congruent to 2 mod 4. I can
even throw in restrictions on endomorphism ring and supersingularity,
and it won't change the result.

Of course, this gives Curve25519 on the nose. So what's actually being
claimed is something much weirder: only certain curve shapes lead to
good results. Weierstrass does, and Edwards does, and twisted Edwards
does, but Montgomery doesn't. Either that, or Curve25519 does fall
within the set of curves that are generated by NUMS, and with the
original generators too.

This appears in the original paper presenting Curve25519, and seems to
be the core objection to Curve25519. I'd like to know if the chairs
propose to move for consensus on Curve25519 in the Turner draft form,
or if they still want to drag this out longer, or consider drafts
containing generation methods. If they do want to drag this out
longer, I'd like to know if the Powers That Be have any plan to deal
with this farcical situation.

Sincerely,
Watson Ladd

---

From: Tanja Lange <[email-masked]>
Date: Sat, 3 Jan 2015 21:58:28 +0100

> and it won't change the result.
Thanks for spelling this out in full detail. 

See also http://safecurves.cr.yp.to/rigid.html 
	
	Tanja