Subject: [Cfrg] Revising RFC 6090

From: Paul Hoffman <[email-masked]>
Date: Fri, 4 Jul 2014 12:21:26 -0700

Greetings again. RFC 6090, "Fundamental Elliptic Curve Cryptography Algorithms", was published a few years ago, with the purpose of laying down which parts of elliptic curve cryptography had been described long enough ago to avoid any patent issues. A fair number of technical errata have been reported on RFC 6090. Also, the point compression patent is expiring later this month, and therefore point compression might be added to a new version of the RFC.

This seems like a good time to revisit RFC 6090 to incorporate the errata and to start to consider what else can be added to the document. I have started a new draft, listed below. The errata have been marked in the document; those marks will come out in future drafts.

To start off, it would be grand if people would read through the draft carefully for technical accuracy. I say this because the drafts leading to RFC 6090 had been reviewed here in CFRG, and yet some significant mistakes made it through the process.

At the same time, it would be useful to hear what people think additions to the document should be. RFC 6090 focused on the Suite B curves, but if additional curves and concepts can be added (while maintaining the design goal of things described fully early enough to avoid patent encumbrance), that could be interesting as well.

--Paul Hoffman

A new version of I-D, draft-hoffman-rfc6090bis-00.txt
has been successfully submitted by Paul Hoffman and posted to the
IETF repository.

Name:		draft-hoffman-rfc6090bis
Revision:	00
Title:		Fundamental Elliptic Curve Cryptography Algorithms
Document date:	2014-07-04
Group:		Individual Submission
Pages:		34
URL:            http://www.ietf.org/internet-drafts/draft-hoffman-rfc6090bis-00.txt
Status:         https://datatracker.ietf.org/doc/draft-hoffman-rfc6090bis/
Htmlized:       http://tools.ietf.org/html/draft-hoffman-rfc6090bis-00

Abstract:
  This note describes the fundamental algorithms of Elliptic Curve
  Cryptography (ECC) as they were defined in some seminal references
  from 1994 and earlier.  These descriptions may be useful for
  implementing the fundamental algorithms without using any of the
  specialized methods that were developed in following years.  Only
  elliptic curves defined over fields of characteristic greater than
  three are in scope; these curves are those used in Suite B.

  This version of the note incorporates errata that were reported on
  RFC 6090 [RFC6090].

---

From: Watson Ladd <[email-masked]>
Date: Fri, 4 Jul 2014 18:52:38 -0700

Dear Paul,
Thanks for taking on this necessary task.

I have several ideas for how to modernize, but not all of them are
going to work because of the time constraint: edwards curves are 2007,
for instance, and while I haven't heard any FUD yet, it doesn't fit
with our original goals.

The first idea is due to Tanja Lange and is to use Jacobian
coordinates. If you want to be fancy she invented faster formulas
which are in the EFD, but you might have to live with the 1986
formulas. However, the presentation in the RFC is not ideal: you
should run them through common-subexpression elimination, which the
EFD did for you.

For validation of the formulas that appear I would suggest an
automated Sage script, ala EFD.

The parameters choice section is laughable. Either make it complete or
remove it entirely.

The Montgomery ladder is old enough to be included. I don't know about
sliding windows. Signed-digit encoding was invented in 1950 under the
name Booth encoding: it gets a savings, but isn't constant time. DJB
has an extensive bibliography and paper in
http://cr.yp.to/papers/pippenger.pdf discussing various approaches.

The Shamir trick should be mentioned: it speeds verification of
signatures significantly.

Sincerely,
Watson Ladd

On Fri, Jul 4, 2014 at 12:21 PM, Paul Hoffman <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin