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

Andrey Jivsov <crypto@brainhub.org> Mon, 12 January 2015 06:36 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 A19301A89F2 for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 22:36:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.399
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5Nn77qHqUckj for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 22:36:01 -0800 (PST)
Received: from resqmta-ch2-10v.sys.comcast.net (resqmta-ch2-10v.sys.comcast.net [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 ietfa.amsl.com (Postfix) with ESMTPS id CD8211A88A7 for <cfrg@irtf.org>; Sun, 11 Jan 2015 22:36:00 -0800 (PST)
Received: from resomta-ch2-13v.sys.comcast.net ([69.252.207.109]) by resqmta-ch2-10v.sys.comcast.net with comcast id eubz1p0042N9P4d01ubzdi; Mon, 12 Jan 2015 06:35:59 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by resomta-ch2-13v.sys.comcast.net with comcast id euby1p00G4uhcbK01ubyjG; Mon, 12 Jan 2015 06:35:59 +0000
Message-ID: <54B36B4E.9010006@brainhub.org>
Date: Sun, 11 Jan 2015 22:35:58 -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: Michael Hamburg <mike@shiftleft.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org>
In-Reply-To: <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; 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: <http://mailarchive.ietf.org/arch/msg/cfrg/UQFiVpESbvjrr1jK4e4iPf41hHc>
Cc: 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, 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 
draft-agl-cfrgcurve-00):

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 + 
1335*S

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

With small curve constants (A, d), M/4 for the multiplication by these 
constants:
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.