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

Andrey Jivsov <> Sun, 25 January 2015 21:35 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 094BC1A86EF for <>; Sun, 25 Jan 2015 13:35:16 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id tf65wS3nOzGi for <>; Sun, 25 Jan 2015 13:35:13 -0800 (PST)
Received: from ( [IPv6:2001:558:fe16:19:96:114:154:171]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 971D01A000C for <>; Sun, 25 Jan 2015 13:35:13 -0800 (PST)
Received: from ([]) by with comcast id kMaV1p0045Geu2801MbDHg; Sun, 25 Jan 2015 21:35:13 +0000
Received: from [] ([]) by with comcast id kMbC1p0064uhcbK01MbCVp; Sun, 25 Jan 2015 21:35:12 +0000
Message-ID: <>
Date: Sun, 25 Jan 2015 13:35:12 -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 <>, Andrey Jivsov <>
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=1422221713; bh=2MPOgHvNQ4N8yNBYURwvDnMTkePI/hwXnbR6aIZsbOQ=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=qf0vJT1/osFx+NRARPoYgKQsDkdS0/jMNSFUciyHsobjIzKhnj19ocm+lRkksSIJV otxWXMzfGKvgpGcVt9p93nyEOYBGhOYCQ5Jwie0DsVkPxSHu2pcHgBXJcuiSnO+4b3 FBXxM/r+324x05lAwQJtkKkFx9Pxn73myB7jRByCV6mrVHJoMrAoKD3ocfB5V/GAb3 k8Y3s+Dyb9mstjKB0Ug+Mz4OdXYXG91VaqsgkL2wMumy32piJ7vQ1kPs+4SvZohvpp QtKd8IVwe/xhyBzeMRebyySILG9gJx2c4ilnXe2E2thXtp0BSFqw2pkB/s0vvw9QO6 bKwD7vnZEIOEw==
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: Sun, 25 Jan 2015 21:35:16 -0000

On 01/21/2015 05:39 PM, Watson Ladd wrote:
> On Wed, Jan 21, 2015 at 1:04 AM, Andrey Jivsov <> wrote:
>> On 01/19/2015 04:20 PM, Watson Ladd wrote:
>>> And once again, the Montgomery ladder is extremely small in codesize,
>>> one the field operations are implemented. Or is there some other
>>> benefit I don't understand you are thinking of?
>> The benefits of using extended twisted Edwards coordinates would be:
>> * An order of magnitude faster key generation (this is a part of signature
>> generation or ECDH ephemeral key generation)
>> * Ability to add points (needed for signatures and many other protocols)
>> * The same code can do what Montgomery ladder does (variable case
>> scalarmult) at the same speed.
>> It plausible that a library that needs more then ECDH variable base
>> scalarmult would implement the above operations without the Montgomery
>> ladder.
>> However, if there there is a penalty to recover 'y', that unified
>> implementation is less likely to happen.
> And the cost here is what? Note that your first bullet point is false:
> the comb method on twisted Edwards can deliver a point on a Montgomery
> curve, with minimal change in performance. I agree we would be using
> twisted Edwards for signatures and protocols that require addition
> (although Mike Hamburg has some ideas on safer point formats, based on
> Jacobi quartics). But that doesn't mean we should use the same method
> for ECDH: there are security advantages which your proposal doesn't
> have.
> Once again this got discussed extensively over the summer.

You are proposing to use a Montgomery ladder for second flight of ECDH 
(variable base). There is a benefit of simplicity of code here and 
protection against timing attacks for free, but not much of performance. 
This makes sense.

The first flight of ECDH (fixed-base) is too slow with same 
implementation used for variable base (or any key generation), and so 
you propose to use a discussed over the summer idea to have another type 
of Montgomery ladder (which I couldn't locate). It won't be as simple as 
the first Montgomery ladder and it will probably be more complex as a 
simple ~20 additions of points from a pre-computed read-only table.

This, however, still doesn't solve the problem of digital signatures and 
SPAKE, which need to add points.

For example, in each 
peer does 1 fixed-base, 2 variable-base, 2 addition. I would do this 
with a single implementation of a curve formula (e.g. using extended 
twisted Edward).

IMO a library like OpenSSL that anticipates to implement most of these 
algorithms *may* consider a single implementation that can add points 
with no performance loss.