Re: [Cfrg] Safecurves draft redux

Robert Ransom <rransom.8774@gmail.com> Thu, 09 January 2014 15:41 UTC

Return-Path: <rransom.8774@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0B9A91AE405 for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 07:41:28 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id gQDuJSCkMmvK for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 07:41:26 -0800 (PST)
Received: from mail-qe0-x229.google.com (mail-qe0-x229.google.com [IPv6:2607:f8b0:400d:c02::229]) by ietfa.amsl.com (Postfix) with ESMTP id B5FC21AE350 for <cfrg@irtf.org>; Thu, 9 Jan 2014 07:41:26 -0800 (PST)
Received: by mail-qe0-f41.google.com with SMTP id gh4so3306969qeb.14 for <cfrg@irtf.org>; Thu, 09 Jan 2014 07:41:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=iv+SQ5zn3hpfvZI7KhqEyy716Ze5NvxUkjAMbjy+2Fk=; b=yv4ebJWbxtB2rXYQNvMEjNVuXGwwdb+J3f+VFh2VWYQB3Gqn1UClmaDK7J362dncLf NMxyoaj8fNp1zqAhq507/PlguPqO10pat1fFtspOKfbknlFqQOLKb2MMK16LxMj+u7cT imXFGN0na9Ms7Qzgc7nJL/9BvSNZLnrk65D0vW50hVU/YyzIwLXKbU5n6eWmySxNafaP m6u4jnEXGhEWeqqUWtJm9KGDRbc32hS+VlZh/37kklALSmTmvy1KVH2AqDvLV0NppPjY wpSgeAwVDamlxyqdRIX2bHo0TjBqt6O8TiPLMk/lAqL+sqTBOWHQJMefSrjoXhs//M2p nC9Q==
MIME-Version: 1.0
X-Received: by 10.49.53.66 with SMTP id z2mr8586467qeo.45.1389282077036; Thu, 09 Jan 2014 07:41:17 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Thu, 9 Jan 2014 07:41:16 -0800 (PST)
In-Reply-To: <CACsn0cn4paZTmeVExn+na0MwzdvSn+MF_bmyRZ869pJrWb_8Bg@mail.gmail.com>
References: <CACsn0cn4paZTmeVExn+na0MwzdvSn+MF_bmyRZ869pJrWb_8Bg@mail.gmail.com>
Date: Thu, 09 Jan 2014 07:41:16 -0800
Message-ID: <CABqy+soA8FTWTtp-tZ7GKq-NqJiTXwtczF2CXay0Lfa-3ASZyA@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Safecurves draft redux
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 09 Jan 2014 15:41:28 -0000

On 1/9/14, Watson Ladd <watsonbladd@gmail.com> wrote:

> But as for efficiency, pontification about what is fast and what isn't
> will always be behind the drive of implementors to accelerate
> everything. What seems like an awkward limb placement can be fixed by
> some clever use of fractional radix arithmetic.

There is a limit to how much ‘fractional-radix arithmetic’ can help.
2^255 - k has a nice regular (vectorizable) pattern of 10 limbs ([26,
25]*5); no other pattern works as well.  2^414 - k can be split into
18 or 9 equal-size limbs, or a vectorizable pattern of 16 or 8 limbs.
None of the other curves' coordinate fields (with the possible
exception of M-221) have both a good arrangement of limbs and a
sufficiently small k to postpone carrying after multiplication until
after modular reduction.

> Lastly, just because a protocol suggests a form to go on the wire does
> not mean that the calculations an implementation does need to resemble
> it. Robert Ransom has made this point, and I agree with it.

And I also made the exact opposite point: twist security is only
useful because implementations will be free to use Montgomery's ladder
formulas.

> Good
> standards specify observed behavior, not how it is attained.

Good standards specify *both* the intended observable behaviour *and*
how to attain it.  The whole point of SafeCurves is to assist in
*implementing* ECC both safely and efficiently.

> As a metacomment: we shouldn't let our desire for "The Idiots Guide to
> ECC" in RFC form get in the way of standardizing these curves. I don't
> think our job is done with putting these curve formulas in an RFC, but
> it does substantially help anyone who wants to use these curves in
> another IETF protocol.

Shoveling this pile of curve equations into an I-D or RFC accomplishes
nothing.  What matters is specifying how to use curves of this class
in protocols, and that requires not only specifying point formats and
curve-operation formulas, but choosing the right set of point formats
to support in each case, and documenting how to assemble the primitive
curve operations into the exact procedures that the protocol requires.
 It's a matter of systems engineering, not mathematics or cryptography
alone.


Robert Ransom