Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
Peter Dettman <peter.dettman@bouncycastle.org> Mon, 12 January 2015 05:26 UTC
Return-Path: <peter.dettman@bouncycastle.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 BC78C1A88A7 for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 21:26:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.202
X-Spam-Level:
X-Spam-Status: No, score=-0.202 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HELO_EQ_AU=0.377, HOST_EQ_AU=0.327, RCVD_IN_DNSWL_NONE=-0.0001, RELAY_IS_203=0.994] 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 7Z99gDaOieto for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 21:26:09 -0800 (PST)
Received: from tauceti.org.au (mail.tauceti.org.au [203.32.61.25]) by ietfa.amsl.com (Postfix) with ESMTP id EADAC1A8895 for <cfrg@irtf.org>; Sun, 11 Jan 2015 21:26:08 -0800 (PST)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS)) x-ip-name=ppp-49-237-36-181.revip6.asianet.co.th;
Message-ID: <54B35ADE.8020209@bouncycastle.org>
Date: Mon, 12 Jan 2015 12:25:50 +0700
From: Peter Dettman <peter.dettman@bouncycastle.org>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org>
In-Reply-To: <54B315CA.6040900@brainhub.org>
Content-Type: text/plain; charset="windows-1252"; format="flowed"
Content-Transfer-Encoding: 7bit
X-Authenticated-User: peter.dettman@bouncycastle.org
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/6rMNRTs67fqn8k68fosr-329nUQ>
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 05:26:11 -0000
On 12/01/2015 7:31 am, Andrey Jivsov wrote: > ----------------------------------------------------------------- > "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 [NOTE: I realise GLV curves are not on the table in the current curve selection process; this is just a response to the presented numbers, not advocacy] The state-of-the-art precomputation for Weierstrass window method uses co-z arithmetic at a cost of ~(5M+2S)/point as set out in https://eprint.iacr.org/2008/051. In that paper it's shown how to convert the table to affine with a single inversion and total cost of ~(9M+2S)/point + 1I, observing that the full Montgomery trick is not needed because the Z coordinates form a multiplicative chain already. However, based on the same observation, it is straightforward to bring all precomputed points to a common Z coordinate, avoid the inversion, and proceed to calculate on an isomorphic curve where those points are affine (by dropping the Z coordinate and setting a4' = Z^4.a4). A single multiplication is needed to bring the result point back to the original curve. For a4=0, the isomorphism doesn't affect the formulae, so in the windowing, doubling costs (2M+5S), (mixed) addition costs (7M+4S). Also, a4=0 is chosen to allow use of a fast endomorphism, so numbers should really reflect its usage. It reduces the doublings by half, and (for secp256k1) adds an extra 1M per precomputed point (and doubles storage, but not lookup costs). Splitting the scalar costs a few multiplications. So, slightly more roughly than above: 2^(w-1)*(10M + 2S) + (n/2)*(2M + 5S) + (n/w)*(7M + 4S) + (15M+255S) <--[Actual cost of inversion in a secp256k1 implementation] n=256,w=5: 795*M + 1135*S (S=M: 1930*M, S=0.625M: 1505*M). Regards, Pete Dettman
- [Cfrg] On relative performance of Edwards v.s. Mo… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Mike Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Mike Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Peter Dettman
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Kurt Roeckx
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov