Re: [Cfrg] On the use of Montgomery form curves for key agreement

Brian LaMacchia <bal@microsoft.com> Tue, 02 September 2014 07:58 UTC

Return-Path: <bal@microsoft.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 04DBD1A00F6 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 00:58:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
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 BPlX8JtHDh0b for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 00:58:24 -0700 (PDT)
Received: from na01-bn1-obe.outbound.protection.outlook.com (mail-bn1blp0186.outbound.protection.outlook.com [207.46.163.186]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 07F201A00E8 for <cfrg@ietf.org>; Tue, 2 Sep 2014 00:58:23 -0700 (PDT)
Received: from BL2PR03MB242.namprd03.prod.outlook.com (10.255.231.18) by BL2PR03MB243.namprd03.prod.outlook.com (10.255.231.23) with Microsoft SMTP Server (TLS) id 15.0.1015.19; Tue, 2 Sep 2014 07:58:22 +0000
Received: from BL2PR03MB242.namprd03.prod.outlook.com ([169.254.8.218]) by BL2PR03MB242.namprd03.prod.outlook.com ([169.254.8.218]) with mapi id 15.00.1015.018; Tue, 2 Sep 2014 07:58:22 +0000
From: Brian LaMacchia <bal@microsoft.com>
To: Robert Ransom <rransom.8774@gmail.com>
Thread-Topic: [Cfrg] On the use of Montgomery form curves for key agreement
Thread-Index: Ac/GFKdVASv0pPTeROyHvj6EvV57FQAAYtoAAAwdIdAADhl2AAABG7xg
Date: Tue, 2 Sep 2014 07:58:21 +0000
Message-ID: <b7f734820451474085f91f7118d4ffad@BL2PR03MB242.namprd03.prod.outlook.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com> <CABqy+srA6KmTcKZ39jbWOibd0-5ZhvjCuRDiWh1qBTor2q=qoA@mail.gmail.com>
In-Reply-To: <CABqy+srA6KmTcKZ39jbWOibd0-5ZhvjCuRDiWh1qBTor2q=qoA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [63.229.25.58]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 0322B4EDE1
x-forefront-antispam-report: SFV:NSPM; SFS:(6009001)(377454003)(479174003)(13464003)(189002)(199003)(51704005)(24454002)(2656002)(64706001)(92566001)(86612001)(80022001)(66066001)(20776003)(76576001)(74316001)(87936001)(21056001)(90102001)(86362001)(85852003)(83072002)(46102001)(77982001)(99396002)(81342001)(4396001)(19580395003)(83322001)(33646002)(19580405001)(106356001)(76482001)(76176999)(77096002)(74662001)(85306004)(99286002)(54356999)(105586002)(50986999)(93886004)(108616004)(81542001)(107046002)(31966008)(101416001)(95666004)(74502001)(110136001)(24736002)(42262002); DIR:OUT; SFP:; SCL:1; SRVR:BL2PR03MB243; H:BL2PR03MB242.namprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: microsoft.onmicrosoft.com
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/mPJ2GCqT2ffMvHX7eIORvQpM63k
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:58:26 -0000

-----Original Message-----
From: Robert Ransom [mailto:rransom.8774@gmail.com] 
Sent: Tuesday, September 2, 2014 12:25 AM
To: Brian LaMacchia
Cc: Andy Lutomirski; cfrg@ietf.org
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement

>On 9/1/14, Brian LaMacchia <bal@microsoft.com>; wrote:
>>  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.)

Hi Robert,

I think you misread that portion of my email as being about the cost of conversion between coordinate formats, when I was in fact referring to the overall “hybrid” implementation.  If you go back and reread the entire message, you’ll see a more detailed comment on exactly this point at the bottom of my reply to Andy.  

--bal