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

Michael Hamburg <mike@shiftleft.org> Mon, 12 January 2015 02:52 UTC

Return-Path: <mike@shiftleft.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 EAFE11A8850 for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 18:52:19 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, 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 rMQNF9S3JdRh for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 18:52:18 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EA3EA1A1A7C for <cfrg@irtf.org>; Sun, 11 Jan 2015 18:52:17 -0800 (PST)
Received: from [192.168.1.117] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 9B7F93AA12; Sun, 11 Jan 2015 18:49:21 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1421030961; bh=NBFnPVeUuIT0YxUuOCxpiLU4txYDZy+jlA5GJkU8qIk=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=H+rvdoLnXJGWJzzwp+jPYP6S+N6q03WvBLBpkRDP7lgvbj80jo1mxEjuhoJYS0DTf BpauICSkFFN8qhipEHZ1AIV/GvrRLCB97UTSPe5c2h8glOdKCETVajT2R1NIvKyQYj eZwVjuv0gZa8FvpmonBbRr00sQhEdtVA1MJ3o4eM=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.1\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <54B315CA.6040900@brainhub.org>
Date: Sun, 11 Jan 2015 18:52:14 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org>
To: Andrey Jivsov <crypto@brainhub.org>
X-Mailer: Apple Mail (2.2070.1)
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/l8BGaPoHyLkb0b5pOslf1snYP7A>
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 02:52:20 -0000

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.

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.

Cheers,
— Mike

> On Jan 11, 2015, at 4:31 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> 
> Counting multiplications (M) and squares (S) in F(p), ECC formulas use at least 5% more operations v.s. Montgomery.
> 
> The lowest non-Montgomery count is reached with twisted Edwards, signed window, w=5, which yields 6%/5.5% more M/S.
> 
> I pasted my notes below.
> 
> It's possible that my initial results in this thread are due to the difference in F(p) operations between the two implementations.
> 
> See also http://www.ietf.org/mail-archive/web/cfrg/current/msg05857.html
> 
> Thanks to Mike and Watson for pointers and comments.
> 
> 
> -----------------------------------------------------------------
> Montgomery method:
> -----------------------------------------------------------------
> 
> From http://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html (8.2M for differential addition and doubling) with Z1=1: 5M+4S.
> 
> 256*(5*M+4*S)=1275*M + 1020*S
> Inverse: 11*M + 245*S
> 
> (also checked curve25519-donna-c64.c)
> 
> Total: 1285*M + 1265*S
> 
> -----------------------------------------------------------------
> t.Edwards window method:
> -----------------------------------------------------------------
> 
> Write the windows size as w and n-bit E(F(p)) curve (e.g. n=255). 2^(w-1) signed elements need to be calculated.
> 
> The half of 2^(w-1) is filled with doubles, half with additions
> 
> 2^(w-2) additions, 2^(w-2) doubles, z!=1
> 
> addition: 10M+1S
> double: 3M+4S
> from http://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html
> 
> Window filling:
> 2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S)
> 
> For windowed scalar multiplication there are w(ceil(n/w)-1) doubles and ceil(255/w)-1 additions
> 
> w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)
> 
> The formula is 2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)
> 
> w=3: 1622*M + 1102*S
> w=4: 1438*M + 1091*S
> w=5: 1354*M + 1090*S
> w=6: 1384*M + 1130*S
> 
> Inverse: 11*M + 245*S
> 
> Total (w=5) with inverse:
> 1354*M + 1090*S +11*M + 245*S = 1365*M + 1335*S
> 
> So we have
> 
> Montgomery (M):     1285*M + 1265*S
> t.Edwards w=5 (tE): 1365*M + 1335*S
> ( tE needs 6% more M, 5.5% more S )
> 
> Unifying S+M, this is:
> 
> for S=M cost:
> M: 2550*M
> tE: 2700*M
> 
> for S=0.625M cost:
> M: 2075M
> E: 2200M
> 
> Watson's estimate is:
> Montgomery: 2491M
> t.Edwards w=5: 2714M
> 
> -----------------------------------------------------------------
> "Jacobian coordinates with a4=0 for short Weierstrass curves", window method
> -----------------------------------------------------------------
> http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html
> 
> doubling: 2M+5S
> addition:  11M+5S
> 
> 2^(w-2)*(11*M+5*S) + 2^(w-2)*(2*M+5*S) + w*(ceil(n/w)-1)*(2*M+5*S)+(ceil(n/w)-1)*(11*M+5*S) + 11*M + 245*S
> 
> w=5: 1165*M + 1825*S
> 
> for S=M cost
> 2990*M
> 
> for S=0.625M cost
> 2305*M
> 
> -----------------------------------------------------------------
> variable curve size n, window method
> -----------------------------------------------------------------
> 
> Hand-waive (extrapolate from Curve25519) the inverse as
> 0.95*n*S+0.05*n*M
> 
> Montgomery:
> (n+1)*(5*M+4*S)+0.95*n*S+0.05*n*M
> 
> t.Edwards:
> F=2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)+ 0.95*n*S+0.05*n*M
> 
> n=384:
> M: 1944*M + 1904*S
> w=5:
> tE: 2023*M + 2000*S
> w=6:
> tE: 1991*M + 2019*S
> 
> n=255, w=5  (compare to the actual, above):
> M: 1292*M + 1266*S
> tE: 1366*M + 1332*S
> 
> n=400:
> M: 2025*M + 1984*S
> w=5:
> tE: 2099*M + 2079*S
> w=6:
> tE: 2076*M + 2110.*S
> w=7:
> tE: 2203*M + 2193*S
> 
> n=512:
> M: 2590*M + 2538*S
> w=5:
> tE: 2679*M + 2668*S
> w=6:
> tE: 2613*M + 2691*S
> 
> -----------------------------------------------------------------
> Comb method
> -----------------------------------------------------------------
> The method is described here: http://eprint.iacr.org/2005/222.pdf, but always add O:
> 
> precomp: (w-1)*ceil(n/w)(3M+4S) + ((2^w)-w-1)*(10M+1S)
> mult: (ceil(n/w)-1)*(3M+4S+10M+1S)
> inverse (n=255): 11*M + 245*S
> 
> total: (w-1)*ceil(n/w)*(3*M+4*S) + ((2^(w-1))-w-1)*(10*M+S) + (ceil(n/w)-1)*(3*M+4*S+10*M+S)+11*M + 245*S
> 
> n=255:
> w=3:
> 1653*M + 1349*S
> w=4:
> 1516*M + 1339*S
> w=5:
> 1533*M + 1337*S
> w=6:
> 1772*M + 1372*S
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg