Re: [Cfrg] Curve manipulation, revisited

Peter Dettman <peter.dettman@bouncycastle.org> Thu, 08 January 2015 15:00 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 06BEA1A8A55 for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 07:00:24 -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 5N7pjPxHlx0A for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 07:00:21 -0800 (PST)
Received: from tauceti.org.au (mail.tauceti.org.au [203.32.61.25]) by ietfa.amsl.com (Postfix) with ESMTP id 630F41A8979 for <cfrg@irtf.org>; Thu, 8 Jan 2015 07:00:20 -0800 (PST)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS)) x-ip-name=ppp-49-237-170-4.revip6.asianet.co.th;
Message-ID: <54AE9B71.5030409@bouncycastle.org>
Date: Thu, 08 Jan 2015 22:00:01 +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: Michael Hamburg <mike@shiftleft.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> <54A51E97.5060508@bouncycastle.org> <FE4218BA-0CE1-4971-8A7B-4E3440088560@shiftleft.org>
In-Reply-To: <FE4218BA-0CE1-4971-8A7B-4E3440088560@shiftleft.org>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Authenticated-User: peter.dettman@bouncycastle.org
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/ohWCJuDa0Gg1EgHXwo6QKgU4nQM>
Cc: cfrg@irtf.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, 08 Jan 2015 15:00:24 -0000

On 8/01/2015 1:33 am, Michael Hamburg wrote:
>> On Jan 1, 2015, at 2:16 AM, Peter Dettman <peter.dettman@bouncycastle.org>; wrote:
>>
>> 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.
<snip>
> This is neat. Have you tested it? Does it work, and do you know if 
> it’s better than a Montgomery ladder? From your high-level description 
> it looks like it should be competitive with the short Weierstrass XZ 
> Montgomery ladder (8M + 7S + 5m IIUC). Cheers, — Mike 

I did some basic tests of the sqrt-avoiding isomorphism using secp256k1 
(a==0 makes the testing easier) and it works, yes.

Regarding performance, I can give numbers from a modified version of the 
Granger/Scott P-521 implementation; there I changed the precomputation 
so that all the precomputed points would have a common Z, then used an 
isomorphism on which those points are affine, and switched to 
modified-Jacobian coordinates. That scheme is 3M + 5S for doubling, 7M + 
6S per point addition, 9M + 3S per precomputed point, plus a handful of 
ops to shift to/from the isomorphic curve. So, with width 5 windows, I 
make that roughly (4.7M + 6.2S)/bit for P-521, or for something around 
256 bits, (5M + 6.3S)/bit.

The sqrt-avoiding scheme would have the same per-bit cost as above, with 
a few extra ops at the start/end.

Regards,
Pete Dettman