Re: [Cfrg] Curve selection revisited
Watson Ladd <watsonbladd@gmail.com> Sat, 26 July 2014 17:59 UTC
Return-Path: <watsonbladd@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 CDDFF1A00FE for <cfrg@ietfa.amsl.com>; Sat, 26 Jul 2014 10:59:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=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 VvUd8W_VVdnv for <cfrg@ietfa.amsl.com>; Sat, 26 Jul 2014 10:59:30 -0700 (PDT)
Received: from mail-yh0-x230.google.com (mail-yh0-x230.google.com [IPv6:2607:f8b0:4002:c01::230]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 63B6B1A00BE for <cfrg@irtf.org>; Sat, 26 Jul 2014 10:59:30 -0700 (PDT)
Received: by mail-yh0-f48.google.com with SMTP id i57so3813241yha.21 for <cfrg@irtf.org>; Sat, 26 Jul 2014 10:59:29 -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=cJj3Y5Ls76HUONr/syfA5ez6jT2qlHv3twBN58QUdag=; b=KE/Gsw/UAWPYzlgyNLouykwjzf/ih/HXWKsRxJ1ZdgaGJbjqpngi4BouY/7bFblvzK urxuR16Hd9pc3p7IAV+6a28R5NUJu44VB3No5e6e7TDqISEjA3XiPV3oIOs8B+NOZYIX ZmxpFAl+fp2idK7w8+IENY3yGcPGwgaDBOSdH8Su7dT0H+dii1Y9zVTGHG0aptTOepMF MjdbZvUYq9+cmKbAN3xbumJNzLuYKHj9mQoxlq+6p77nfu0mKpjYTdnXNekX6So9gamd U0KWw9BYzf56DKnQi14KysBLFZ1HEeYZ50575aCiuum2reFz2NRpV+7C2eit0rC4EwaO ngig==
MIME-Version: 1.0
X-Received: by 10.236.17.194 with SMTP id j42mr35760602yhj.138.1406397569649; Sat, 26 Jul 2014 10:59:29 -0700 (PDT)
Received: by 10.170.202.8 with HTTP; Sat, 26 Jul 2014 10:59:29 -0700 (PDT)
In-Reply-To: <CABqy+spNJYWyBHLY5YL3kh6PcDm_tTbqyN0tpDNs-Bme7de1hg@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> <CABqy+spNJYWyBHLY5YL3kh6PcDm_tTbqyN0tpDNs-Bme7de1hg@mail.gmail.com>
Date: Sat, 26 Jul 2014 10:59:29 -0700
Message-ID: <CACsn0cm7_d0XBz-E7trOgH_J0RcpyLJLm-uy6AmE2rL0peQ=bQ@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Robert Ransom <rransom.8774@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/EvNVlCSDjucpfIGzcUxI3Oa2qRY
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 17:59:34 -0000
<choping irrelevent stuff> > > “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. By "easy" I meant that as the field arithmetic is already done, which is the vast bulk of the difficulty, the additional code is smaller. Adding the Montgomery ladder as a routine on top of the arithmetic is not hard: it's 10 function calls and a loop more or less. > > >> (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.) Doesn't A become a ratio of small integers rather than a small integer? Although this is still pretty fast. > >>>> 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.) The numbers are right, but the conclusions are thus wrong since a common optimization is neglected. In particular, the absence of Montgomery form from the proposal is based on performance measures including a fixed based exponentiation. Sincerely, Watson Ladd > > > Robert Ransom -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin
- [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