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

Andrey Jivsov <> Mon, 12 January 2015 06:36 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id A19301A89F2 for <>; Sun, 11 Jan 2015 22:36:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.399
X-Spam-Status: No, score=0.399 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 5Nn77qHqUckj for <>; Sun, 11 Jan 2015 22:36:01 -0800 (PST)
Received: from ( [IPv6:2001:558:fe21:29:69:252:207:42]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id CD8211A88A7 for <>; Sun, 11 Jan 2015 22:36:00 -0800 (PST)
Received: from ([]) by with comcast id eubz1p0042N9P4d01ubzdi; Mon, 12 Jan 2015 06:35:59 +0000
Received: from [] ([]) by with comcast id euby1p00G4uhcbK01ubyjG; Mon, 12 Jan 2015 06:35:59 +0000
Message-ID: <>
Date: Sun, 11 Jan 2015 22:35:58 -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: Michael Hamburg <>
References: <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=q20140121; t=1421044559; bh=6OpaLxqqyHpYrKDB+sBdC3AxrYwWqzHamJqyS3rSyQc=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=QH+r9xP8X4Fcsa2bbzvIqSN7GVizzPAqrBFxl9Ev9tIe0F9cEk2CqP8CsiDROSOxU 5Bxhw62BLCRPrwiRzZph14ZQT0z72f9T/cAjpUIROs2nXAk/Fb/If07U7Sgp14bk8O EI87p8Eg8KGjkMr5qwMJpQdha2H3YBOwuJtQ32iD0zeiDJXo0kIdd21frFlK+xnuVO 4Jma9FUSMQpsJ1zPI1ADVSs7YrvGwTwR9sZIQ0BJltwb79WvvOUo020e4Afm+MW1rO H5iSpZiZQ6plPPU2ScXYZaJEDlzh2qgW1bgrlGPDvG/N4CkZQDj/05p7dxoM2VNnxg Gf/36V6/KUOcg==
Archived-At: <>
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, 12 Jan 2015 06:36:02 -0000

On 01/11/2015 06:52 PM, Michael Hamburg wrote:
> Thanks for your analysis!  However, please note that with lazy extended homogeneous coordinates on a twisted Edwards curve with a=-1, the cost of an Edwards addition to an accumulator is 8M and not 10M+1S, and the cost of a doubling is still 3M+4S, perhaps with an additional 1M to convert from this form to a suitable one for the window table.
You are welcome. I would appreciate a pointer to the method.

> Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.

Right, I was ignoring additions and multiplication by a constant.

Assuming M/4 for a24 (e.g. 4-limb F(p) operations) and full M for d in 
t.Edwards (corresponding to the 37095705...283555 in 

M: n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S
tE: 2^(w-2)*(10*M+S+M) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M)+11*M + 245*S=1423*M + 

5.4%, 5.5% (M, S). Montgomery is better.

With small curve constants (A, d), M/4 for the multiplication by these 
M: currently optimal, same 1350*M + 1265*S
tE: 2^(w-2)*(10*M+S+M/4) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M/4)+11*M + 245*S=1380*M 
+ 1335*S

2.2%, 5.5%. Montgomery is better.