[Cryptech Core] modexp optimization plans

[Joachim Strömbergson]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Aloha!

Peter Stuge wrote:
> Rob Austein 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.


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

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. But that is not planned.

- -- 
Med vänlig hälsning, Yours

Joachim Strömbergson - Alltid i harmonisk svängning.
========================================================================
 Joachim Strömbergson          Secworks AB          joachim at secworks.se
========================================================================
-----BEGIN PGP SIGNATURE-----
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBCAAGBQJVh/5QAAoJEF3cfFQkIuyNsKsP/0JnEwZIEbtpQV6sGFdAt9EV
jH0+6YfPiwhHa19+bgiqXHIw5uKOEq7Zie7IJvQfINFVt8lXnHnL+pqctXBz8rdw
wZD8RYonxGPyl3szMOfwvI8EvZgrAjC5YQCxnlgK5Z5FUfxgnSnJZPX8Zvu5u2PP
5EgqBwGllPDA78UrI6WMl0YrwtJRI6DTu6NTELlM6fSvHkAMICeFFQgomR++1Rrh
vDSab29IqY4aAuq/6Xo//N2G0k8LmTHh7Cr6mONAwxY2jXhVRKdgrbkJMhqvGDLM
i9ttuApCQX6CwRFjB01NhBTsdf87G+sOzy2xeKc3DQBgmiDePFzN21ReJqSJtbai
cVhznhnKOkXfdZx6UjpFUw7bp+AkfKIzuLPnshzAFr26X8yYphKrnTVK8YCtH2BW
4hY3JYEhsbchdc0bUxGgIlofcOVl2iDKm/OnM8907dEei4769z6BeFrQMEV5o7LY
Il9Zy3MmLfy2qLWtRg7iADrSsmE8LlohyxFpDNrDWTaRtoiJWMOA5aBzIlfgPvzM
3sWHZTvtRAls9VNKj1SVUzSqX5WoXJ422PfHayYAqOi2vWRQG9A2ov2mmNCB3cs+
VKamm8pFMjCVvDmUmg9tTgQIaVEeZjjGiZQgoK698NsktCdKYiRRfXcfzwtlN/6Q
xAAjD+lwHl8hMn+T21yT
=maBO
-----END PGP SIGNATURE-----