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