Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

Andrey Jivsov <> Mon, 19 January 2015 07:11 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id A7E431ACE94 for <>; Sun, 18 Jan 2015 23:11:36 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 3.099
X-Spam-Level: ***
X-Spam-Status: No, score=3.099 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, MANGLED_SMALL=2.3, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id BdpgNHEe1jfh for <>; Sun, 18 Jan 2015 23:11:34 -0800 (PST)
Received: from ( [IPv6:2001:558:fe16:19:96:114:154:164]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 706801ACE8A for <>; Sun, 18 Jan 2015 23:11:34 -0800 (PST)
Received: from ([]) by with comcast id hjBR1p0014xDoy801jBZ3s; Mon, 19 Jan 2015 07:11:33 +0000
Received: from [] ([]) by with comcast id hjBY1p00D4uhcbK01jBZ7x; Mon, 19 Jan 2015 07:11:33 +0000
Message-ID: <>
Date: Sun, 18 Jan 2015 23:11:32 -0800
From: Andrey Jivsov <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: Watson Ladd <>, Michael Hamburg <>
References: <> <> <> <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: 8bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=q20140121; t=1421651493; bh=w9gQcqoEvqWXe3HqWEUm36azCWrKLASWcfQYM3O32Do=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=ui29zBwU8u47wfYO/jgKQZJ2eeb+LexXrDR+1Bgf44lZOSXKx8SzaDvKuzNvWV/Vw o5TRdvdWTerRr/0sIrK7/2GxYxH4KTjthJYSJ/x+WcKnr+K3fcei+Jwv14a+TS1fqO t+IIVWHBDJmQWdzN1AQa5tLqwNj9ZcglC7YFDronu+BDXsRUvfo3OpFlG3l9fyxGvH 635faUTM4AXZwKG4JMOBg1YGOfocXY9ibFj+BdfF8LyxqAmr2tbwW1o8weL6NeAVxn EBG4fi6WSOdngh/3I1znWR1ZDP5YrRgXyKzjpSVeAMPEsSt4lPENlemFBQNrjghgUj qp4g7SZv5U6Dg==
Archived-At: <>
Cc: "" <>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
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: Mon, 19 Jan 2015 07:11:36 -0000

On 01/12/2015 11:30 AM, Watson Ladd wrote:
> On Mon, Jan 12, 2015 at 9:59 AM, Michael Hamburg <> wrote:
>> On Jan 12, 2015, at 7:28 AM, Watson Ladd <> wrote:
>> The table is filled with a cost of 8M for additions and 4M+4S for
>> doublings so 2^(w-2)*8M+2^(w-2)*(4M+4S). Then we proceed for
>> ceil(255/w)-1steps, each step consisting of (w-1) 3M+4S doublings, and
>> 1 4M+4S doubling. Ergo the total cost becomes
>> 2^(w-2)*(12M+4S)+(ceil(255/w)-1)*(w*(3M+4S)+1M).
>> Don’t you need to do some additions at some point as well?  Or do the
>> additions only cost 1M?
> Doing the calculation correctly, it's effectively 9M for an addition
> after a 3M+4S doubling. The best window is 5, with 1296*M + 1032*S,
> and tossing in the inversion gives 1307*M + 1286*S, vs 1285*M + 1265*S
> for Montgomery form. Note that here I'm neglecting the multiplications
> by constants, which is why the speeds are coming out slightly
> differently.

For extended twisted Edwards coordinates (thanks, Mike) I get very 
similar result. I agree with your operation count (according to

n=255; w=5; 2^(w-2)*(8*M) + 2^(w-2)*(4*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(9*M)+11*M + 245*S =
1307*M + 1277*S

v.s. Montgomery

n=255; n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S =
1350*M + 1265*S

I believe I properly accounted for constants (d in t.Ed is large, would 
costs D=M, a=-1 D=0). The table will include points in extended twisted 
Edwards coordinates. Interestingly, the d is not used in any calculation.

The extended twisted Edwards coordinates, despite having to deal with 
large d, are slightly better (~1.5%) with a simple window exponentiation 

The comb method doesn't seem to be better.

> But the bottom line is that Montgomery ladder is competitive with the
> best known alternative methods at 255 bits, in terms of operation
> counts, and this difference can be wiped out by the need for side
> channel protection: none of the various models are saying anything too
> different.

Yes, looks like this, if my calculations are correct. The paper mentions 
additional "caching", though.

One argument remains, though. If you plan to do anything beyond ECDH, 
there is a benefit to have the same code that does ECDH, and, say, signing.