### Re: [Cfrg] Curve selection revisited

Robert Ransom <rransom.8774@gmail.com> Sat, 26 July 2014 05:42 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 263511A0305
for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 22:42:48 -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 NIpWFNH0-HBl for <cfrg@ietfa.amsl.com>;
Fri, 25 Jul 2014 22:42:46 -0700 (PDT)

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

Received: by mail-qg0-f47.google.com with SMTP id i50so6159850qgf.34
for <cfrg@irtf.org>; Fri, 25 Jul 2014 22:42:45 -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=GA23fuAP+/r59UhKkIa1+v7729i/s8yM3MlrYk34ipY=;
b=vpjZVlq1Lmhr3HTJ0TWLYMy+38cDwHTWGXfjvKoBMrwTDMKBTOeE8bjFBTabo9KOg6
pGkpB/N+xhOJp+5+Zf6vOJXGFpXP+V9getiaoJJEnpOvlDkB4kbEC33jDaOGnUBn/TsL
KR4F1520X+IFeQo4R3QNXnLqzYL+6fgWFYOY0xuTWXmHo/+g+A2ktJGvoY5GsLKmy2WF
g1iViktNI7r0yVATpyHzHc1F/XgTs4lSBjNUSa0Kur0aBNJVHPzoDx5kZXVXxjsbVi0y
2PJzLJU8/rZoOVydJuIzV5QAoNGEzL0Wfhgs0XXj47ON0ov5+C/pZGETiBEy/N3g6Q7A
WVEw==

MIME-Version: 1.0

X-Received: by 10.224.137.135 with SMTP id w7mr35038245qat.52.1406353365284;
Fri, 25 Jul 2014 22:42:45 -0700 (PDT)

Received: by 10.140.98.233 with HTTP; Fri, 25 Jul 2014 22:42:45 -0700 (PDT)

In-Reply-To: <CACsn0ck-nmwtKVmoC=qTuWwJWDZPE6SwKreeJjjdyew+mAcfYw@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>
<CACsn0ck-nmwtKVmoC=qTuWwJWDZPE6SwKreeJjjdyew+mAcfYw@mail.gmail.com>

Date: Fri, 25 Jul 2014 22:42:45 -0700

Message-ID: <CABqy+spNJYWyBHLY5YL3kh6PcDm_tTbqyN0tpDNs-Bme7de1hg@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/WO_lN9ZHq39qzHG3NVM5kWUHme4

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:42:48 -0000

X-List-Received-Date: Sat, 26 Jul 2014 05:42:48 -0000

On 7/25/14, Watson Ladd <watsonbladd@gmail.com> wrote: > Thanks for the much more detailed analysis: I'll have to revise my opinion. > On Fri, Jul 25, 2014 at 7:25 PM, Robert Ransom <rransom.8774@gmail.com> > wrote: >> On 7/25/14, Watson Ladd <watsonbladd@gmail.com> wrote: >>> 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). > > I think I follow all the way up to the last phrase: the incompleteness > means some > additions might blow up, complicating the analysis, and I think a=-1 > only gives the twist > if -1 is a nonsquare. I'm not talking about using the twist. I'm talking about mapping from the ‘complete’ Edwards/Montgomery curve which the specification states and simple implementations use to an ‘incomplete’ curve (i.e. a (twisted) Edwards curve with non-affine points defined over the base field), by whatever means (isomorphism or isogeny), on which the unified addition formula has exceptional cases for inputs with even order. When this is a useful thing to do -- i.e. when the curve is defined over a field in which -1 is a non-square, and thus (twisted) Edwards curves with a=-1 are always incomplete -- there is almost always more than one suitable curve to map to. For example, Mike Hamburg suggests in <https://eprint.iacr.org/2014/027.pdf> a 4-isogeny from Ed(1,d) to Ed(-1,d-1); when d is a non-square, there is also an isomorphism from Ed(1,d) to Ed(-1,-1/d). My point is that most implementation strategies which want to *use* an incomplete Edwards curve start with operations which (a) modify the original input point such that it is guaranteed to have odd order, and (b) produce a non-affine result, which all further operations use as their input. Because of (b), using a Montgomery-form input point format in such an implementation has almost no performance cost (only a few multiplies). Dr. Bernstein's Curve3617 implementation (he now wants to call it Curve41417) operates on a complete Edwards curve; its implementation strategy is more complex than the Montgomery ladder, and slightly less complex than one using an incomplete curve. As a consequence, it benefits more than the fastest implementation strategy from having an affine Edwards-form input point: it saves an additional 7M in the process of constructing a 15-element table. I don't think this benefit to exactly one sub-optimal implementation strategy justifies the cost to the simplest implementation strategy (the Montgomery ladder). > Otherwise it is a curve isogenous to the > original one, under a 1-isogeny. The proper term for a ‘1-isogeny’ is “isomorphism”. Otherwise, people will think that “isogeny” is just the term used for an isomorphism between elliptic curves, rather than a very different type of map. >> 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. > > Signatures: the y-encoding strategies I've seen are too clever by > half, so keys for > ECIES and signatures look very different. What do you mean by this? > There is no security issue > with reuse and > there are papers to that effect, or so I'm told. > That said adding Edwards support or Montgomery support to an implementation > of the other partner in the isogenous pair is easy: we can live with > two point formats. “Easy” does not mean “low-cost”. Adding support for Edwards-form input points to a Montgomery-ladder implementation is easy, but has a high performance cost (1I per scalarmult). Adding support for Montgomery-form input points to an implementation which operates on Edwards form is easy, and has much smaller performance cost. > (there is an additional question of small parameters: a Montgomery > curve with small > parameter is birationally equivalent to a twisted Edwards curve of > small parameter, but > the converse is not (obviously) true. Most generated curves seem to be > in Edwards form > however.) Curve25519 chose (A+2)/4 to be a small integer because Edwards curves had not been published yet. All new curves should be chosen to have Edwards d be a small integer, because that makes the Edwards-form unified addition formulas faster at no cost to the Montgomery ladder on the isomorphic Montgomery curve. (I've mentioned this to CFRG before; I wish more people had listened to me.) >>> 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. > > Very true: the NUMS performance results are thus dead wrong in ECDHE costs, > which are two variable-base multiplications plus a very amortized > fixed-base multiplication, not > the fixed+variable base they used. I don't see anything wrong with what MSR states as the cost of ECDHE -- they're consistent across the implementations, and not reusing ephemeral keys is the simplest implementation strategy. (If they did change their figures to take key reuse into account, though, the cost would be only one variable-base scalar multiplication, not two.) 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