[curves] Curve19119: A legacy-level little brother of Curve25519

[Mike Hamburg]

> On Aug 1, 2017, at 2:35 PM, Björn Haase <bjoern.m.haase at web.de> wrote:
>> In addition to FourQ and Curve19119, other fast-ish options include
>> NIST’s 2^192-2^64-1 (but again maybe not on the M0?);
> 
> The problem in my opinion is to implement the many conditional additions for the solinas prime in constant time. At least, I did try it and I did not find a way to implement that efficiently.

Right, that’s why not on the M0.  On the M4 with all the DSP extensions it might work better.

>> and the Goldi-like 2^216-2^108-1 or 2^252-2^232-1 (but maybe not on tiny micros);
> Here I expect that the fact that the field is not really much smaller than for 2^255 - 1 will be the reason that prevents significant speedups in comparison to Curve25519.

Like the P192 field, it depends on the microcontroller.

I’m not very familiar with optimizations for the M0 or M3, so I can’t really comment there.  The M0 has no widening multiplier and the M3 has a non-constant-time widening multiplier.

On the M4, you are probably using packed arithmetic with UMAAL, so the 216-bit field doesn’t help much.

On other 32-bit microcontrollers (eg PowerPC, ARC, RV32G or maybe ARM with NEON), the 216-bit field should be much faster than a “ref10”-style Curve25519 implementation: it uses 48 multiply-accumulates per field mul instead of 100, with a smaller speedup on squaring.  Considering you also have fewer scalar bits, you might reach a 2:1 speedup overall.

Cheers,
— Mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170801/99bcbd63/attachment.bin>