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

Watson Ladd <watsonbladd@gmail.com> Tue, 20 January 2015 00:21 UTC

Return-Path: <watsonbladd@gmail.com>
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 5F3671B2C12 for <cfrg@ietfa.amsl.com>; Mon, 19 Jan 2015 16:21:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3
X-Spam-Level: ***
X-Spam-Status: No, score=3 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, 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 943v_Gare3E6 for <cfrg@ietfa.amsl.com>; Mon, 19 Jan 2015 16:21:01 -0800 (PST)
Received: from mail-yk0-x22e.google.com (mail-yk0-x22e.google.com [IPv6:2607:f8b0:4002:c07::22e]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CEE171B2B45 for <cfrg@irtf.org>; Mon, 19 Jan 2015 16:21:00 -0800 (PST)
Received: by mail-yk0-f174.google.com with SMTP id 131so3333300ykp.5 for <cfrg@irtf.org>; Mon, 19 Jan 2015 16:21:00 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=tnY3Il/E9yl12D92YBU3gYa7++3o4xG+GGspHmtb7/4=; b=wKG6FzuugJCcm7fA3J24lhw9WK/fY40u8XFCcI9gpBk0j7DnH1mHo7zCxWv8iyL/qj RVx4oWr1X9nmL49PLsB13EVGZPFZnCMmSsokijOQ0d30w0iDJeWzMVaNuqnloqbT+vvH bIyaGTxGqynkq5Vnni3JyXLYabukbJ/ieY123Dpq3bbY9byplNMd0op3TMJ+meWwHUsn 3++XA44/1fik542/WwXaNyceLfPGyCLyTrTE4La2E7PVY/d/q6DOSQy7UZH5dvkpG2Gl 0ufogbymu9IeLYfSbEftaetCPP3Jfw/MaBLO0ZxQMHlGdQ0T6WBi9AndRbNzBl4g6fjw T0pQ==
MIME-Version: 1.0
X-Received: by 10.236.30.168 with SMTP id k28mr8565453yha.163.1421713260034; Mon, 19 Jan 2015 16:21:00 -0800 (PST)
Received: by 10.170.115.77 with HTTP; Mon, 19 Jan 2015 16:20:59 -0800 (PST)
In-Reply-To: <54BCAE24.6020408@brainhub.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> <54BCAE24.6020408@brainhub.org>
Date: Mon, 19 Jan 2015 16:20:59 -0800
Message-ID: <CACsn0ckb6t_bsAocYnBhiqRkaJ3HExF4QNDf83riQqc=uHdQ0A@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/y8eHo1fdB_1kYC3m8N2owIH27OI>
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: Tue, 20 Jan 2015 00:21:02 -0000

On Sun, Jan 18, 2015 at 11:11 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> On 01/12/2015 11:30 AM, Watson Ladd wrote:
<snip>
> 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.

Combs are better for fixed base mults, not variable base: it takes too
long to do the precomputation.

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

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?

Sincerely,
Watson Ladd