Re: [Cfrg] Curve manipulation, revisited

Peter Dettman <> Thu, 01 January 2015 10:17 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 08C151A0383 for <>; Thu, 1 Jan 2015 02:17:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id zOcK9AyY3E5A for <>; Thu, 1 Jan 2015 02:17:32 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id E07251A0381 for <>; Thu, 1 Jan 2015 02:17:31 -0800 (PST)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS));
Message-ID: <>
Date: Thu, 01 Jan 2015 17:16:55 +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
References: <> <> <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="windows-1252"; format="flowed"
Content-Transfer-Encoding: 7bit
Cc: Adam Langley <>
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, 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 

- 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 

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.

Pete Dettman