Re: [Cfrg] ECC mod 8^91+5

[Ilari Liusvaara <[e-mail]>]

On Wed, Aug 02, 2017 at 02:11:35PM +0000, Dan Brown wrote:
> Hi Ilari,
> 
> I did not know about the condition on uniqueness of a point of order
> 2.  So, I will try to better learn this important implementation
> issue.  If you happen to know off-hand a reference to the theorem
> you cited, then please let me know - but don't sweat it, I'll eventually
> find it (99% sure).

Safecurves says: "2006 Bernstein had shown a more limited form of
completeness for the Montgomery ladder on Montgomery curves y^2=x^3+Ax^2+x
with a unique point of order 2, i.e., with A^2-4 not a square.
Specifically, given X0(P) as input, the Montgomery ladder always produces
X0(nP) as output; here X0(P) means 0 if P=0, and otherwise the x-coordinate
of P. It is possible that ladders provide completeness for other curves,
but the analysis is not easy; the only literature is a second 2006 
Bernstein paper on this topic."

> I did not understand what you meant by the "worst problem" being a
> "notation" for low-order points.   (My only guess (1% sure) is that
> "notation" could be some kind of "exception"?)  Also, I'm assuming
> that "worst" is in some relative sense, since Curve25519 has low-order
> points.  Also, is your implied assertion that "a complete curve has
> low-order point" a theorem?  (I had mistakenly thought complete
> formulas for NIST had been found, albeit slower - maybe they were only
> unified, so my understanding of what "complete" means is off.)

If you can represent all points on the curve, you can also represent
the additive identity, which has order 1.

And being able to feed any low-order points (including point of order
1) into some ECC algorithms causes trouble.

E.g., if fed as key to Schnorr signature algorithm, the resulting
signatures have undesirable properties (which may be exploitable in
some applications that assume nonstandard properties from signatures).

> In my slides, I mentioned that the propose curve's cofactor (72)
> not being a power of 2 is problematic for easily generating signature
> ephemerals without bias. This has some known workarounds, but it is a
> serious issue.  Did you have something else in mind in saying that a
> subgroup of order 9 was problematic?

Well, the easiest way to generate signature ephremals on such groups
without bias is to include the factor of 9 into initial space.
This causes just some very minor slowdown.


Also, there is a fast check for low-order points on Edwards curves.
However, that check only works if cofactor is 4 or 8.




-Ilari