### Re: [Cfrg] Curve selection revisited

Robert Ransom <rransom.8774@gmail.com> Sat, 26 July 2014 02:25 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 D63961A01E5 for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 19:25:56 -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 cRmR8KMXYvp3 for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 19:25:55 -0700 (PDT)

Received: from mail-qg0-x22a.google.com (mail-qg0-x22a.google.com [IPv6:2607:f8b0:400d:c04::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A70981A01D5 for <cfrg@irtf.org>; Fri, 25 Jul 2014 19:25:55 -0700 (PDT)

Received: by mail-qg0-f42.google.com with SMTP id j5so6036906qga.1 for <cfrg@irtf.org>; Fri, 25 Jul 2014 19:25:54 -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=zs21VYF2/O9gJI620pb+jO0xPdulIe8y2Sjm41cDB9o=; b=dOSKZHOnAikmeHk8NnqtmpCXGqqoB9xiUCdwSgBuTcE9cj0dWrXvLy+QNpE8l4jEUb iNBHCli2hqPVc9+b6ApUpY562OtBt2iAHtVVto9/Mkb6Cp0pdHLTovgjQ7qmGEdV0IhP XrDu4mHzdlDOZthCp/PKruTRnLmFdNW8NqyH482zo81xfNK7jWfOAiD53WaII6V2c9Kg Gvjq2XjNc/JvOGz0frS13Nwsb5yOp1H6hQ/2iOVnVmWztScfKWAwWHaaAP5ndeIwFDig r5c2dbBEK6uAb6W1DUierqJGD40F6mn44JSh9KqdkC/4LpvwYoEtmy4CsBo630+3gKZ2 SxQw==

MIME-Version: 1.0

X-Received: by 10.224.134.201 with SMTP id k9mr33883918qat.59.1406341554734; Fri, 25 Jul 2014 19:25:54 -0700 (PDT)

Received: by 10.140.98.233 with HTTP; Fri, 25 Jul 2014 19:25:54 -0700 (PDT)

In-Reply-To: <CACsn0ckqFigWoH2+OOEHSd2VWPp8y6=m8H5OsFRyjXmjK7+m4w@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>

Date: Fri, 25 Jul 2014 19:25:54 -0700

Message-ID: <CABqy+srxMNuG0AaQd0SaegHvZWgbW762EQq+iAHL_fbu6sOJJQ@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/Wvsgkn1nuKPf5Gal8WCII7a_AMM

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 02:25:57 -0000

On 7/25/14, Watson Ladd <watsonbladd@gmail.com> wrote: > So I'd like to explain a bit about how implementations work, and why > performance will not help us decide between Curve25519 in twisted > Edwards form and the NUMS curve of similar size in twisted Edwards > form. > > The first question is how to do the field arithmetic. All the primes > being considered are of the form 2^s-c, so either one of saturated > arithmetic > or unsaturated will work. Unsaturated is more portable: C cannot > access the carry flag. It offers more freedom in radix, and lets carry > chains be vectorized. Karatsuba can be used or not, which depends on > the saturated/unsaturated choice. But the exact values of s and c > don't matter as much. The exact value of c determines whether a portable or vectorized implementation can delay carries until after reduction. For example, after curve25519-donna performs a multiply or squaring, each of 19 64-bit limbs has absolute value less than 14*2^54. When freduce_degree reduces a field element to 10 limbs without carrying, the result has absolute value less than (c+1)*14*2^54 = 280*2^54, or a bit more than 2^62. In the Microsoft field 2^255 - 765, or even 2^256 - 189, this would not be possible. 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. The exact value of s determines whether carries can be vectorized within a coordinate-field element. For example, 2^251 - 9 can be represented using one 26-bit limb (in the least significant position) and 9 25-bit limbs, but this interferes with the vectorization strategy described in the neoncrypto paper (by Dr. Bernstein et al.). Since c=9 is so small, this can be worked around by representing coordinates modulo 2^252 - 18 instead, but this trick is rarely possible without running into the bound on c. > The second question and third question what coordinates and what > addition formulas to use when, and what algorithm to use. All twisted > Edwards curves expose the same possibilities here: large precomputed > tables with mixed coordinate addition vs. smaller tables for variable > base, or a conversion to some other isogenous curve for variable base > exponentiation. Affine Montgomery-form points can be unpacked to and packed from projective (optionally twisted) Edwards-form points at a trivial extra cost over unpacking from or packing to a compressed affine Edwards-form point. Variable-base scalar-multiplication operations which use Edwards form internally are not slowed significantly by having a projective rather than affine input (if any operations rely on their input being affine, they must occur during table setup), and they are not slowed at all if they double and/or apply isogenies to clear the cofactor group before operating on an ‘incomplete’ curve (e.g. a=-1 in a field in which -1 is a non-square). As you should know, fixed-base scalar-multiplication operations which use Edwards form internally are not slowed at all by producing Montgomery-form output. Affine Edwards-form points cannot be unpacked to affine Montgomery-form points for use with the Montgomery ladder without an extra inversion at the beginning of a scalar multiplication, and using a projective input in the Montgomery ladder is always slower than inversion by coordinate exponentiation. Since the Montgomery ladder remains the simplest implementation strategy, and the performance benefit to more complex implementations from using an Edwards-form point format is small at most, I still see no reason to use an Edwards-form point format. > If we are willing to use Montgomery form (which the TLS WG initially > had strong support for in Curve25519) Has the TLS WG changed its support for using the widely implemented, de-facto standard point format for Curve25519? If so, when was this decision made? > one caches ephemeral DH > parameters so the cost of fixed-base exponentiation is amortized > across connections. OpenSSL does this anyway, and this affects > technique > slightly. This is good for performance even if you use a table to optimize fixed-base scalar multiplications. > But to be clear, a fast implementation for one prime and > curve of a certain size and shape will likely be adaptable to a > different curve > over a similar prime with the same shape. This is simply not true. Curve operations can often be reused, and some other utility routines can easily be modularized in a way that supports other coordinate fields with similar properties (e.g. q=3mod4), but primes which make portable or vectorized coordinate operation implementations efficient are too rare for there to be any pairs of ‘similar prime’s. > Performance data will not distinguish between s=255 and s=256. It will distinguish between Curve25519 and the Microsoft curves in the implementations (either portable, open-source C, or heavily-optimized machine code) which are actually used. Robert Ransom

- [Cfrg] Curve selection revisited Benjamin Black
- Re: [Cfrg] Curve selection revisited Yoav Nir
- Re: [Cfrg] Curve selection revisited Paterson, Kenny
- Re: [Cfrg] Curve selection revisited David Jacobson
- Re: [Cfrg] Curve selection revisited Watson Ladd
- Re: [Cfrg] Curve selection revisited Robert Ransom
- Re: [Cfrg] Curve selection revisited Watson Ladd
- Re: [Cfrg] Curve selection revisited Robert Ransom
- Re: [Cfrg] Curve selection revisited Robert Ransom
- Re: [Cfrg] Curve selection revisited Watson Ladd
- Re: [Cfrg] Curve selection revisited Andrey Jivsov
- Re: [Cfrg] Curve selection revisited Ilari Liusvaara
- Re: [Cfrg] Curve selection revisited Robert Ransom
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Michael Hamburg
- Re: [Cfrg] Curve selection revisited Michael Jenkins
- Re: [Cfrg] Curve selection revisited Michael Hamburg
- Re: [Cfrg] Curve selection revisited Hannes Tschofenig
- Re: [Cfrg] Curve selection revisited Hannes Tschofenig
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Stephen Farrell
- Re: [Cfrg] Curve selection revisited Michael Hamburg
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Michael Hamburg
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Paul Lambert
- Re: [Cfrg] Curve selection revisited Paul Lambert
- Re: [Cfrg] Curve selection revisited Mike Hamburg
- Re: [Cfrg] Curve selection revisited Robert Ransom
- Re: [Cfrg] Curve selection revisited Andrey Jivsov
- Re: [Cfrg] Curve selection revisited Robert Ransom
- Re: [Cfrg] Curve selection revisited Robert Ransom
- Re: [Cfrg] Curve selection revisited Phillip Hallam-Baker
- Re: [Cfrg] Curve selection revisited Robert Moskowitz
- Re: [Cfrg] Curve selection revisited Russ Housley
- Re: [Cfrg] Curve selection revisited Salz, Rich
- Re: [Cfrg] Curve selection revisited Phillip Hallam-Baker
- Re: [Cfrg] Curve selection revisited Salz, Rich