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

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
>