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

Robert Ransom <> Tue, 02 September 2014 07:25 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 404111A00AA for <>; Tue, 2 Sep 2014 00:25:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.75
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 6roylkOwiluX for <>; Tue, 2 Sep 2014 00:25:22 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400d:c04::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id DC47A1A00AD for <>; Tue, 2 Sep 2014 00:25:20 -0700 (PDT)
Received: by with SMTP id e89so6052068qgf.4 for <>; Tue, 02 Sep 2014 00:25:20 -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=MqPYW4j2xVRSzuYXTjpSclTtgaOBlC732M+Jo0taSkk=; b=Oo23bv5wEM2JZrW5NxHrE2kaw5EJOcqpe8jADfCOvv2QKOOEscXkEs8Pc1utheYd+o wrBvZLLuyms0FD0m8e+ovMeV0hxAnW8DNWtKtukEFTZBxrqYVDbJDId5Hqm3VwycK8YU 2Cj7i+yHShSt3XJdhBVTqtNF7YiSGuEkb9uzz0j43Zb6yGooWAWkSSXP0h4TfhRpt+MW th5PfMcwnTjDACMymdaSicSUAPp+bXnM/7174OPo+0ymYu8Ik1CUbJlHW0tvvKQQEbxP gluannlmAHFUzNBPtu7qsr19xfb3Laudi5/diOlIpw4tgplKZx1jdHMjeZSpkoCDfg11 4EfQ==
MIME-Version: 1.0
X-Received: by with SMTP id js1mr52392482qcb.20.1409642720174; Tue, 02 Sep 2014 00:25:20 -0700 (PDT)
Received: by with HTTP; Tue, 2 Sep 2014 00:25:20 -0700 (PDT)
In-Reply-To: <>
References: <> <> <>
Date: Tue, 02 Sep 2014 00:25:20 -0700
Message-ID: <>
From: Robert Ransom <>
To: Brian LaMacchia <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: "" <>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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: Tue, 02 Sep 2014 07:25:23 -0000

On 9/1/14, Brian LaMacchia <> wrote:
> See responses inlined below
> -----Original Message-----
> From: Andy Lutomirski []
> Sent: Monday, September 1, 2014 11:55 AM
> To: Brian LaMacchia
> Cc:
> 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

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