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

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
> 