Re: [Cfrg] On the use of Montgomery form curves for key agreement
Robert Ransom <rransom.8774@gmail.com> Tue, 02 September 2014 07: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 404111A00AA for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 00:25:23 -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 6roylkOwiluX for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 00:25:22 -0700 (PDT)
Received: from mail-qg0-x22d.google.com (mail-qg0-x22d.google.com [IPv6:2607:f8b0:400d:c04::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DC47A1A00AD for <cfrg@ietf.org>; Tue, 2 Sep 2014 00:25:20 -0700 (PDT)
Received: by mail-qg0-f45.google.com with SMTP id e89so6052068qgf.4 for <cfrg@ietf.org>; Tue, 02 Sep 2014 00:25:20 -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=MqPYW4j2xVRSzuYXTjpSclTtgaOBlC732M+Jo0taSkk=; b=Oo23bv5wEM2JZrW5NxHrE2kaw5EJOcqpe8jADfCOvv2QKOOEscXkEs8Pc1utheYd+o wrBvZLLuyms0FD0m8e+ovMeV0hxAnW8DNWtKtukEFTZBxrqYVDbJDId5Hqm3VwycK8YU 2Cj7i+yHShSt3XJdhBVTqtNF7YiSGuEkb9uzz0j43Zb6yGooWAWkSSXP0h4TfhRpt+MW th5PfMcwnTjDACMymdaSicSUAPp+bXnM/7174OPo+0ymYu8Ik1CUbJlHW0tvvKQQEbxP gluannlmAHFUzNBPtu7qsr19xfb3Laudi5/diOlIpw4tgplKZx1jdHMjeZSpkoCDfg11 4EfQ==
MIME-Version: 1.0
X-Received: by 10.229.232.1 with SMTP id js1mr52392482qcb.20.1409642720174; Tue, 02 Sep 2014 00:25:20 -0700 (PDT)
Received: by 10.140.51.233 with HTTP; Tue, 2 Sep 2014 00:25:20 -0700 (PDT)
In-Reply-To: <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com>
Date: Tue, 02 Sep 2014 00:25:20 -0700
Message-ID: <CABqy+srA6KmTcKZ39jbWOibd0-5ZhvjCuRDiWh1qBTor2q=qoA@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Brian LaMacchia <bal@microsoft.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/CYRf9YkWG1f7OY3tLyRk9h2HBKs
Cc: "cfrg@ietf.org" <cfrg@ietf.org>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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: Tue, 02 Sep 2014 07:25:23 -0000
On 9/1/14, Brian LaMacchia <bal@microsoft.com> wrote: > See responses inlined below > > -----Original Message----- > From: Andy Lutomirski [mailto:luto@amacapital.net] > Sent: Monday, September 1, 2014 11:55 AM > To: Brian LaMacchia > Cc: cfrg@ietf.org > Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement > >>> 1. Requiring a Montgomery form curve for key agreement and for a >>> particular security level means that implementations of protocols with >>> both key agreement and digital signatures must implement both >>> Montgomery curve arithmetic and additionally curve arithmetic for >>> another curve form. From an engineering perspective there is thus a >>> clear drawback to requiring different curve forms for key agreement >>> and digital signature at the same security level. > >>You can do arithmetic on a curve points given in Montgomery form without a >> Montgomery ladder >implementation by converting to a different coordinate >> system. I'm not sure why you'd want to in >anything other than the >> tiniest embedded implementation, but you could. > > Yes, technically you could do that, but I haven’t seen anyone suggest that > was in any way practical or interesting. I've suggested that (<http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html>). To summarize: * If the point format contains an Edwards-form y coordinate instead of a Montgomery-form x coordinate, implementations which use the Montgomery ladder, for whatever reason, must incur a significant extra cost. (The Montgomery ladder is far simpler than the algorithms you recommend, and can be implemented with far less RAM than any tolerably efficient scalar-multiplication routine based on Edwards form, so many implementations will use the Montgomery ladder in practice, and some implementations must use it.) * If the point format consists of a Montgomery-form x coordinate (possibly together with a sign bit for an Edwards-form x coordinate), point decompression to projective Edwards (or twisted Edwards) form costs only trivially more. There is a small added cost over Dr. Bernstein's ‘Curve41417’ ECDH implementation (but only because it is sub-optimal), and essentially no added cost for your algorithms (which must double their input before table construction). (I do believe that using Edwards-form point formats in the Ed25519 signature system and the Curve41417 ECDH system was a bad decision -- in particular, if Ed25519 had used a Montgomery-form point format instead, it would have been far more convenient for many applications -- but I disagree strongly with your claim that using a different point format for a signature system's nonces is inherently bad. I'll post more details about that at some point, hopefully soon.) > To be clear, the reason you would > want to change to another form in ECDHE is for significant performance gains > in the fixed-base key generation. This is false, and you clearly know that: your own research group's paper gives performance figures for a ‘hybrid’ ECDHE implementation which uses Edwards form internally for key generation, and uses the Montgomery ladder for the variable-base scalar multiplication. (For everyone else, the added cost (during key generation) of encoding a projective Edwards-form point to a Montgomery-form point format rather than an Edwards-form point format is trivial: two additions.) Robert Ransom
- [Cfrg] On the use of Montgomery form curves for k… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… D. J. Bernstein
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tony Arcieri
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Michael Hamburg
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Jim Schaad
- Re: [Cfrg] On the use of Montgomery form curves f… Markulf Kohlweiss
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Manuel Pégourié-Gonnard
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov