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

Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx> Tue, 04 April 2017 01:14 UTC

Return-Path: <francisco@cs.cinvestav.mx>
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 C16721274D2 for <cfrg@ietfa.amsl.com>; Mon, 3 Apr 2017 18:14:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] 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 2gnjtOMPcCGY for <cfrg@ietfa.amsl.com>; Mon, 3 Apr 2017 18:14:37 -0700 (PDT)
Received: from delta.cs.cinvestav.mx (delta.cs.cinvestav.mx [148.247.102.21]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DB2E412702E for <cfrg@irtf.org>; Mon, 3 Apr 2017 18:14:36 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id 571735C206F; Mon, 3 Apr 2017 20:14:23 -0500 (CDT)
X-Virus-Scanned: amavisd-new at cs.cinvestav.mx
Received: from delta.cs.cinvestav.mx ([127.0.0.1]) by localhost (delta.cs.cinvestav.mx [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6bNkYDzyKtcr; Mon, 3 Apr 2017 20:14:22 -0500 (CDT)
Received: by delta.cs.cinvestav.mx (Postfix, from userid 1507) id EAA155C2087; Mon, 3 Apr 2017 20:14:21 -0500 (CDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id DD76A5C206F; Mon, 3 Apr 2017 20:14:21 -0500 (CDT)
Date: Mon, 3 Apr 2017 20:14:21 -0500 (CDT)
From: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>
To: Peter Dettman <peter.dettman@bouncycastle.org>
cc: cfrg@irtf.org
In-Reply-To: <467245bb-374c-c157-d134-1ca4d1b7057e@bouncycastle.org>
Message-ID: <alpine.LFD.2.02.1704032011360.14799@delta.cs.cinvestav.mx>
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> <467245bb-374c-c157-d134-1ca4d1b7057e@bouncycastle.org>
User-Agent: Alpine 2.02 (LFD 1266 2009-07-14)
MIME-Version: 1.0
Content-Type: MULTIPART/MIXED; BOUNDARY="-141290138-908383680-1491268461=:14799"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JBq2MZS9k1HhxUqtPd-7yfIPSzA>
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: Tue, 04 Apr 2017 01:14:39 -0000


On Sat, 1 Apr 2017, Peter Dettman wrote:

> 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.

Thanks, corrections done!

> - 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.


That is great news!, the improvements are within the range of our 
estimations :)

> - 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.

We've checked your suggestion, and indeed your trick looks quite 
interesting. We think that the best option would be to pre-compute the u 
coordinates as -uPi, because this would involve no extra programming 
effort.

Thanks again for your feedback.

Cheers!
The authors


> 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
>>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>