Re: [Cfrg] Curve manipulation, revisited

Peter Dettman <> Thu, 08 January 2015 15:00 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 06BEA1A8A55 for <>; Thu, 8 Jan 2015 07:00:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.202
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 5N7pjPxHlx0A for <>; Thu, 8 Jan 2015 07:00:21 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 630F41A8979 for <>; Thu, 8 Jan 2015 07:00:20 -0800 (PST)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS));
Message-ID: <>
Date: Thu, 08 Jan 2015 22:00:01 +0700
From: Peter Dettman <>
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 <>
References: <> <> <> <> <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [Cfrg] Curve manipulation, revisited
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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 <> 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.
> 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.

Pete Dettman