[Cryptech Core] modexp optimization plans

[Peter Stuge]

Joachim Strömbergson wrote:
> >>>> 4.2 Implement support for short exponent. Currently the size of
> >>>> the exponent is ignored. This means that an operation with a
> >>>> public exponent (such as 65537) takes as long time as if the
> >>>> exponent is as big as the modulus. This fix is easy to do and
> >>>> will drastically reduce the time to do operations with short
> >>>> exponents.
> > 
> > What are the numbers?
> 
> For 2048 bit modulus and 17 bit e, the difference is something like
> doing 2048**2 vs 2048*32 operations. Huge.

4194304 / 65536 = factor 64 doesn't seem huge to me. Typo?

4M cycles at 40 MHz = 100ms, 64k cycles = 1.6ms


> > Would the same size-dependent optimization not be used for private 
> > operations? Would that require duplicating some logic? The
> > suggestion reads "Implement support for short exponent." and does not
> > mention the difference between public and private.
> 
> For private key operations e has the same number of words as the modulus.

Different size moduli still have different number of words. I think
completely data-independent constant-time execution is highly desirable.


> One could further optimize to find the MSB one of the exponent and set
> the size to that. And then you could end up with data dependent
> execution time.

It seems that this is already the case?


//Peter