Subject: [Cfrg] Preserving Implementation Optimizations

From: Russ Housley <[email-masked]>
Date: Sun, 31 Aug 2014 21:56:46 -0400

I am not a cryptographer, but I have been involved in security protocols that make use of cryptography since 1986.  This experience tells me that we should preserve the hard work that has gone into existing ECC implementations if possible.  I have four thoughts in this direction...

First, the use of the same curve for digital signature and key agreement is highly desirable.  This provides obvious modularity.

Second, a lot of effort has gone into optimization of modular reduction for the NIST primes.  If a curve is selected that uses those primes, this optimization effort would carry forward to the new curves.  I have only heard one person question whether those values are actually prime, so I assume that this is not a widely held concern.

Third, many implementations have taken advantage of the "a term" chosen for the NIST curves to optimize point addition. In Weierstrass form, y^2 = x^3 + ax + b, the NIST curves use a = -3 mod p.

Fourth, recent discussion makes it clear that the Edwards form, x^2 + y^2 = 1 + dx^2y^2, offers some significant advantages, especially when the "d term" is chosen to be small.  We can make our curve selection in this form, and then transform it to Weierstrass form to determine the "b term".  The order of the curve needs to be 4 times a prime.  This allows new implementations to take advantage of the Edwards form, and it allows existing implementations to make minimal modifications to support the new curve.

If I have been following this discussion, we need to consider whether we want a Bernstien-Lange SafeCurve.  If we do, then the order of the Edwards twist needs to have a large prime factor.  As best I can tell, this requirement does not conflict with finding a curve that meets the above criteria.

I realize that this is quite different than selecting one of the choices that were presented in Toronto.  However, I think that we should preserve the implementation investment if it does not otherwise hinder security or efficiency.

Thanks for your consideration,
  Russ

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 31 Aug 2014 20:05:57 -0700

> Second, a lot of effort has gone into optimization of modular reduction for the NIST primes.  If a curve is selected that uses those primes, this optimization effort would carry forward to the new…
A lot of effort may have gone into optimizing for the NIST primes, but 
nonetheless most implementations mod these primes are not actually very 
fast.  The most widely-used primes (P-256 and P-384) have the worst 
performance of the lot, especially on 64-bit machines.  Furthermore, the 
newer primes are usually easier to implement than the NIST primes.

The exception may be in dedicated hardware, where the many coefficients 
of primes like P-256 don't make as big an obstacle, and any change is 
very expensive.

Note that P-521 := 2^521-1 is fast, and should definitely be an option.
> Fourth, recent discussion makes it clear that the Edwards form, x^2 + y^2 = 1 + dx^2y^2, offers some significant advantages, especially when the "d term" is chosen to be small.  We can make our cur…
The question of curve specification and point encodings has been 
discussed at length here.  On the one hand, this sort of encoding might 
be good for compatibility; but on the other hand, it may enable new 
attacks on recycled implementations while increasing complexity of the 
new implementations.

Personally I don't think we should put new wine in old wineskins, but I 
suppose it is an option.

Cheers,
-- Mike

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg