Re: [Cfrg] Curve manipulation, revisited
Peter Dettman <peter.dettman@bouncycastle.org> Thu, 01 January 2015 10:17 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 08C151A0383 for <cfrg@ietfa.amsl.com>; Thu, 1 Jan 2015 02:17:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.498
X-Spam-Level: **
X-Spam-Status: No, score=2.498 tagged_above=-999 required=5 tests=[BAYES_50=0.8, 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 zOcK9AyY3E5A for <cfrg@ietfa.amsl.com>; Thu, 1 Jan 2015 02:17:32 -0800 (PST)
Received: from tauceti.org.au (mail.tauceti.org.au [203.32.61.25]) by ietfa.amsl.com (Postfix) with ESMTP id E07251A0381 for <cfrg@irtf.org>; Thu, 1 Jan 2015 02:17:31 -0800 (PST)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS)) x-ip-name=ppp-49-237-143-239.revip6.asianet.co.th;
Message-ID: <54A51E97.5060508@bouncycastle.org>
Date: Thu, 01 Jan 2015 17:16:55 +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: <CAMfhd9W684XMmXn3ueDmwrsQ_ZdiFG+VqYLxkvs7qDwiJdpk6w@mail.gmail.com> <1725646678.805875.1419539885135.JavaMail.yahoo@jws100115.mail.ne1.yahoo.com> <CAMfhd9Ua5fFZk46Xx1AN2VgyJ=Yng6fnO8aN-_ZfzXQn0Xbxhg@mail.gmail.com> <CA+Vbu7zqFcu8d1053mZ_eEm0q=np6T3snSQ4rfY0k1-4hBVDsA@mail.gmail.com> <CAMfhd9XEqMwFzJ4sK4aHGbke6REZb26uaEEv9gbM5v_goDzwUA@mail.gmail.com>
In-Reply-To: <CAMfhd9XEqMwFzJ4sK4aHGbke6REZb26uaEEv9gbM5v_goDzwUA@mail.gmail.com>
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/7DyYY6gg32wDgHAhgSb6XxMDlJA
Cc: Adam Langley <agl@imperialviolet.org>
Subject: Re: [Cfrg] Curve manipulation, revisited
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: Thu, 01 Jan 2015 10:17:34 -0000
On 29/12/2014 8:31 pm, Adam Langley wrote: > (An implementation that wants to use a windowed method with a > Montgomery-X *input* will need to perform a square-root first, but > that's the same cost as a design where compressed Edwards points are > sent. Note: smarter people than I might be able to eliminate the > square-root but I don't see it) I believe I can give an example of how to eliminate the square-root for a random-base scalar-mult. I'll use short Weierstrass to describe it though, as I'm less familiar with Edwards and Montgomery. I assume we can convert easily enough between forms, and that twist security carries across. - Given input X0, use curve equation to calculate {Y0}^2, let K = {Y0}^2. - Initial point P0 is (X0,{Y0}) where {Y0} is unevaluated. - Change of variables to an isomorphic curve: x' = u^2.x, y' = u^3.y, a' = u^4.a, with u = {Y0} (b' = u^6.b, but not typically needed). - Can now write P0' as (K.X0, K^2) without unknowns. - Proceed with scalar multiplication of P0' to result point Pn'. - Recover output Xn from Pn' as Xn'/(K.Zn^2). Note that the doubling formula is affected by the changed a' curve parameter (unless a==0); assume modified-Jacobian coordinates are used. In the case where the original curve has a==-3, the extra cost of the windowing using the isomorphism in modified-Jacobian coordinates is +2S(quares) per addition (doubling cost is unchanged). The total extra cost using width 5 windows is therefore < 40% of the best-case cost of a sqrt. However, there are actually good performance reasons to already be using an isomorphism: to allow mixed addition with precomputed points without needing an inversion in the precomputation. In that case, there is very little additional overhead for the scheme above. Regards, Pete Dettman
- [Cfrg] Curve manipulation, revisited D. J. Bernstein
- Re: [Cfrg] Curve manipulation, revisited Adam Langley
- Re: [Cfrg] Curve manipulation, revisited Watson Ladd
- Re: [Cfrg] Curve manipulation, revisited David Gil
- Re: [Cfrg] Curve manipulation, revisited Adam Langley
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited David Gil
- Re: [Cfrg] Curve manipulation, revisited Adam Langley
- Re: [Cfrg] Curve manipulation, revisited David Gil
- Re: [Cfrg] Curve manipulation, revisited Adam Langley
- Re: [Cfrg] Curve manipulation, revisited Alyssa Rowan
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited Adam Langley
- Re: [Cfrg] Curve manipulation, revisited Watson Ladd
- Re: [Cfrg] Curve manipulation, revisited Yoav Nir
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited Michael Hamburg
- Re: [Cfrg] Curve manipulation, revisited Yoav Nir
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited Watson Ladd
- Re: [Cfrg] Curve manipulation, revisited Yoav Nir
- Re: [Cfrg] Curve manipulation, revisited Watson Ladd
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Mike Hamburg
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Rob Stradling
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited Benjamin Black
- Re: [Cfrg] Curve manipulation, revisited Tony Arcieri
- Re: [Cfrg] Curve manipulation, revisited Adam Langley
- Re: [Cfrg] Curve manipulation, revisited Rob Stradling
- Re: [Cfrg] Curve manipulation, revisited Watson Ladd
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited Paul Hoffman
- Re: [Cfrg] Curve manipulation, revisited Nico Williams
- Re: [Cfrg] Curve manipulation, revisited Watson Ladd
- Re: [Cfrg] Curve manipulation, revisited Salz, Rich
- Re: [Cfrg] Curve manipulation, revisited Paul Hoffman
- Re: [Cfrg] Curve manipulation, revisited Alyssa Rowan
- Re: [Cfrg] Curve manipulation, revisited Peter Dettman
- Re: [Cfrg] Curve manipulation, revisited Harry Halpin
- Re: [Cfrg] Curve manipulation, revisited Michael Hamburg
- Re: [Cfrg] Curve manipulation, revisited Peter Dettman