Re: [Cfrg] A note on how to (pre-)compute a ladder

Peter Dettman <peter.dettman@bouncycastle.org> Sat, 01 April 2017 14:35 UTC

Return-Path: <peter.dettman@bouncycastle.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0ED4F129489 for <cfrg@ietfa.amsl.com>; Sat, 1 Apr 2017 07:35:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001] autolearn=ham autolearn_force=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 F0SArDgm_SB0 for <cfrg@ietfa.amsl.com>; Sat, 1 Apr 2017 07:34:57 -0700 (PDT)
Received: from tauceti.org.au (mail.tauceti.org.au [203.32.61.25]) by ietfa.amsl.com (Postfix) with ESMTP id A2DF9128C81 for <cfrg@irtf.org>; Sat, 1 Apr 2017 07:34:55 -0700 (PDT)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS)) x-ip-name=ppp-223-24-57-67.revip6.asianet.co.th;
To: cfrg@irtf.org
References: <CAHOTMVKHA-yJR1oCyPtUp4-aJVc3dTdyxQHNo4xqnJt0hU6jVQ@mail.gmail.com> <CAMm+Lwgm8XzTBarZ1eFePTZGORorBJAeF7brDkhWGQKQVT0LPQ@mail.gmail.com> <CAMm+LwggT_AVv=KjzM1r=6UnkeK+g8zkticXFBDQ0cUXs_PP0A@mail.gmail.com> <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com> <CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@mail.gmail.com> <CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@mail.gmail.com> <CAMm+LwjeZdR=ZGX0topN2w6P12jEmR-TQ8M9+anyETj43nbiqg@mail.gmail.com> <CAHOTMVL2e2UjVX6VKgHUbOHrb-gsU8kn_cxY1FdNrnj29cki9g@mail.gmail.com> <alpine.LFD.2.02.1703291804030.8996@delta.cs.cinvestav.mx>
From: Peter Dettman <peter.dettman@bouncycastle.org>
Message-ID: <467245bb-374c-c157-d134-1ca4d1b7057e@bouncycastle.org>
Date: Sat, 1 Apr 2017 21:34:42 +0700
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:45.0) Gecko/20100101 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <alpine.LFD.2.02.1703291804030.8996@delta.cs.cinvestav.mx>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 8bit
X-Authenticated-User: peter.dettman@bouncycastle.org
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/1kSTZB262HQJgCEyX3WekhxX9iY>
Subject: Re: [Cfrg] A note on how to (pre-)compute a ladder
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 01 Apr 2017 14:35:00 -0000

Hi Francisco,
Some more feedback:

- Typo: Alg. 5 line 12 has an X_R1 that should be U_R1.

- Typo: the Magma code (Appendix B) refers to "Sec. 6.2 of RFC7748", but
the Curve25519 test vectors are from 6.1.

- I've now implemented Alg. 5 in my RFC 7748 code (Java). I measure a
16% speedup for Curve25519 ECDH (i.e. 1 fixed + 1 variable) and 19% for
Curve448. Only about 100 lines of extra code per curve.

- My Curve448 implementation uses unsigned digits; subtraction is slower
than addition. The 2 subtractions involving A, B at lines 11-12 of Alg.
5 can be replaced by additions if the u_Pi coordinates are
(pre-)negated. Or instead of negating u_Pi, init Z_R1 and Z_R2 to -1,
then negate Z_R1 prior to the final doublings (line 16). It gives a
little over 1% further speedup here.

Regards,
Pete Dettman

On 30/03/2017 8:00 AM, Francisco Rodriguez- Henriquez wrote:
> Dear CFRG community,
> 
> We would like to draw your attention to our IACR pre-print entitled,
> 
> "A note on how to (pre-)compute a ladder
> Improving the performance of X25519 and X448"
> 
> https://eprint.iacr.org/2017/264.pdf.
> 
> For the point multiplication computation Q = kP, this note describes a
> right-to-left version of the Montgomery ladder, which is amenable for
> pre-computing multiples of the base point P. By requiring very modest
> memory resources and a small implementation effort, it obtains noticeable
> performance improvements with respect to the RFC 7748 classical ladder
> procedure.
> 
> We stress that our proposal fully complies with the RFC 7748
> specification, in the sense that given any arbitrary secret keys of
> Alice and Bob, our ladder generates exactly the same public keys that an
> implementation of the RFC 7748 would output.
> 
> As a way of illustration, in Appendix B of our note, we include a magma
> script, which given Alice and Bob private keys of RFC7748 Sec. 6.2, it
> computes the same public keys as specified in that document.
> 
> We would be delighted to receive feedback (including sightings of typos)
> from the CFRG community.
> 
> With best regards,
> 
> Thomaz Oliveira, Julio López and Francisco Rodríguez-Henríquez
> 
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>