Re: [Cfrg] Curve selection revisited

Watson Ladd <> Sat, 26 July 2014 17:59 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id CDDFF1A00FE for <>; Sat, 26 Jul 2014 10:59:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id VvUd8W_VVdnv for <>; Sat, 26 Jul 2014 10:59:30 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4002:c01::230]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 63B6B1A00BE for <>; Sat, 26 Jul 2014 10:59:30 -0700 (PDT)
Received: by with SMTP id i57so3813241yha.21 for <>; Sat, 26 Jul 2014 10:59:29 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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 with SMTP id j42mr35760602yhj.138.1406397569649; Sat, 26 Jul 2014 10:59:29 -0700 (PDT)
Received: by with HTTP; Sat, 26 Jul 2014 10:59:29 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <> <> <> <>
Date: Sat, 26 Jul 2014 10:59:29 -0700
Message-ID: <>
From: Watson Ladd <>
To: Robert Ransom <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: "" <>
Subject: Re: [Cfrg] Curve selection revisited
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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.

Watson Ladd

> Robert Ransom

"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin