Re: [Cfrg] Curve selection revisited

Robert Ransom <rransom.8774@gmail.com> Sat, 26 July 2014 05:40 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 AD9261A02FF for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 22:40:52 -0700 (PDT)
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 v0HixBp2Y3hO for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 22:40:51 -0700 (PDT)
Received: from mail-qa0-x232.google.com (mail-qa0-x232.google.com [IPv6:2607:f8b0:400d:c00::232]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5E1571A02F9 for <cfrg@irtf.org>; Fri, 25 Jul 2014 22:40:51 -0700 (PDT)
Received: by mail-qa0-f50.google.com with SMTP id s7so5479766qap.23 for <cfrg@irtf.org>; Fri, 25 Jul 2014 22:40:50 -0700 (PDT)
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=WAxBpYadoOjzi11d7yoxNUYi4JeXQlRv86/hvVYV9V8=; b=nmO2rP5QYzZqxtnF3it1a0938j//STh1PSUxJORbb1HTsbCOLgbymn+POBi5lq2M2w 45uoU0H18TAHLBifNaL178INNtYZibmugv7bZix6Uqe8Yv1P9bwmeouphbn52PpCpyXa gsanMx0D1rnQhOzwrtMs5HaBm80htzVFxUPM0FEMAF2USk1mXhN1yniym0p44xufF+F9 sskS9eihWTS4rku4TCIDAL36q88WukIidGoMnIrcJVcsqeAcgbec+TcVwJD3rgWSL16s k6BPEOQaiOXi0af0wgL5V9Yg1C4w0gdTIPX2biQeO//yU2AoWsPLuwC7FAPNn3ZgABuy 0ZhA==
MIME-Version: 1.0
X-Received: by 10.140.26.110 with SMTP id 101mr19895914qgu.1.1406353250565; Fri, 25 Jul 2014 22:40:50 -0700 (PDT)
Received: by 10.140.98.233 with HTTP; Fri, 25 Jul 2014 22:40:50 -0700 (PDT)
In-Reply-To: <CABqy+srxMNuG0AaQd0SaegHvZWgbW762EQq+iAHL_fbu6sOJJQ@mail.gmail.com>
References: <CA+Vbu7xroa68=HOZtbf=oz7kK2EeUv_z1okpnjxHPR0ZtHD5cA@mail.gmail.com> <CFF7E184.28E9F%kenny.paterson@rhul.ac.uk> <53D2781B.8030605@sbcglobal.net> <CACsn0ckqFigWoH2+OOEHSd2VWPp8y6=m8H5OsFRyjXmjK7+m4w@mail.gmail.com> <CABqy+srxMNuG0AaQd0SaegHvZWgbW762EQq+iAHL_fbu6sOJJQ@mail.gmail.com>
Date: Fri, 25 Jul 2014 22:40:50 -0700
Message-ID: <CABqy+sq=38V7EUcfZtFbiXDRENG2R786pY8o-eVbzFKL_=HVwA@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
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/VpxX7AQvcqOfEPm-EH1pH4a7c58
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Curve selection revisited
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: Sat, 26 Jul 2014 05:40:52 -0000

On 7/25/14, Robert Ransom <rransom.8774@gmail.com> wrote:

> Carries between limbs can be performed more efficiently than in
> curve25519-donna -- curve25519-donna goes to extra effort to keep
> limbs signed.  In the Montgomery ladder, this optimization does not
> add any extra carry steps, because the Montgomery-ladder formulas
> never perform more than two add/subtract operations between a
> multiply/square operation.  With Edwards-curve operations, this
> optimization may require an additional carry step in the doubling
> formula.

Er.  The ‘optimization’ I'm referring to is carrying in such a way
that the resulting limb values are always non-negative, in three
operations (shift, add, and bitwise and) rather than the seven (four
shifts, two adds, one subtract) needed to chop an extra bit off the
absolute value of each limb, and possibly producing negative limbs.


Dr. Bernstein wrote up his own explanation of how the performance of
unsaturated-limb arithmetic depends strongly on the exact values of s
and c on the curves list; see
<https://moderncrypto.org/mail-archive/curves/2014/000237.html>.  The
Curve41417 paper gives a more extensive treatment of how its
coordinate field allows even more optimization.


Robert Ransom