[Cryptech Tech] modexp: operands > 1024 (probably) fixed

[Rob Austein]

> At Tue, 30 Jun 2015 16:47:18 +0200, Joachim Strömbergson wrote:
> > 
> > Found the culprits that caused operands > 1024 bits to not work. I've
> > tested with 2048 bit operands in simulation and it works. The fixes and
> > new testcases have been checked into master.
> > 
> > Would appreciate if you could update and see if your tests goes through.

Today's core gets correct answers for 1024, 2048, and 4096 bit RSA.

Runtime  for this core (pure ModExp operations only, exponent unpadded
so we get the fast path benefit for short exponent):

    1024-bit short exponent (encrypt)           0.450888 seconds
    1024-bit long exponent (decrypt)            3.553510 seconds

    2048-bit short exponent (encrypt)           0.000728 seconds
    2048-bit long exponent (decrypt)            23.387081 seconds

    4096-bit short exponent (encrypt)           1.365269 seconds
    4096-bit long exponent (decrypt)            178.863616 seconds


No, I don't know why 2048-bit encrypt shows up as faster than 1024-bit
encrypt.  Troubling, as it smells like a potential timing attack, but
too early to tell whether it's real or a measurement artifact (keep in
mind that these numbers are just the difference between two calls to
gettimeofday(), thus at best no more precise than that system call).

These figures are from the better of two runs: numbers from the first
one were weird enough that I'm pretty sure something else was keeping
the main CPU busy at the time, thus messing up the measurements.

Will be conducting further tests, this time with C profiling enabled
to see if that sheds any further light.  Am particularly interested in
where the time is going during key generation (not shown here).