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

Andrey Jivsov <crypto@brainhub.org> Mon, 19 January 2015 07:11 UTC

Return-Path: <crypto@brainhub.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A7E431ACE94 for <cfrg@ietfa.amsl.com>; Sun, 18 Jan 2015 23:11:36 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id BdpgNHEe1jfh for <cfrg@ietfa.amsl.com>; Sun, 18 Jan 2015 23:11:34 -0800 (PST)
Received: from resqmta-po-05v.sys.comcast.net (resqmta-po-05v.sys.comcast.net [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 ietfa.amsl.com (Postfix) with ESMTPS id 706801ACE8A for <cfrg@irtf.org>; Sun, 18 Jan 2015 23:11:34 -0800 (PST)
Received: from resomta-po-05v.sys.comcast.net ([96.114.154.229]) by resqmta-po-05v.sys.comcast.net with comcast id hjBR1p0014xDoy801jBZ3s; Mon, 19 Jan 2015 07:11:33 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by resomta-po-05v.sys.comcast.net with comcast id hjBY1p00D4uhcbK01jBZ7x; Mon, 19 Jan 2015 07:11:33 +0000
Message-ID: <54BCAE24.6020408@brainhub.org>
Date: Sun, 18 Jan 2015 23:11:32 -0800
From: Andrey Jivsov <crypto@brainhub.org>
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 <watsonbladd@gmail.com>, Michael Hamburg <mike@shiftleft.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org> <CACsn0c=qxBXCkr7hCtzgY9U+5_N8hY=jShU7g=hUbqkrUMYxNw@mail.gmail.com> <3C94ED57-5089-4A6D-9CC6-2DCD452C7BCF@shiftleft.org> <CACsn0ck6q9nxioS7q66MkB6M+YmaGj=Nmqop1LQ-DuG0q78GaQ@mail.gmail.com>
In-Reply-To: <CACsn0ck6q9nxioS7q66MkB6M+YmaGj=Nmqop1LQ-DuG0q78GaQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; 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: <http://mailarchive.ietf.org/arch/msg/cfrg/2mrf7Pig9WjzQMphLemqED_flc0>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=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 <mike@shiftleft.org> wrote:
>>
>> On Jan 12, 2015, at 7:28 AM, Watson Ladd <watsonbladd@gmail.com> 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 
http://eprint.iacr.org/2008/522.pdf):

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 
method.

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.