[Cryptech Core] modexp optimization plans (was: Re: teleconf?)

[Randy Bush]

>> o joachim, can anybody provide useful help with modexp and
>>   underlying bignum
> There isn't really a problem with modexp or bignum functionality wise as
> I see it.

< tact = off >

i view needing an extra word for the result as the same as a double
entry bookkeeping error of one cent.  we know there is something wrong
but we do not know the magnitude of the problem or the cause.  it could
be two complementary errors, one of $1,000.01 and one of ($1,000.00).
it scares me and should, imiho, scare you.

> Shaving off cycles in the montprod inner loop has great impact on the
> performance gains without really adding hw resources. Yesterday I
> competed fusing the adder iterations into a single iteration. This
> removed 30+% of all cycles.

cool

> Currently montprod and modexp) operates on 32-bit words. Increasing the
> size to 64 bits will halve the number of cycles in an iteration. The
> current version of modexp can do 115 MHz in Spartan-6, and in
> combination with test implementations, increasing operands to 64 bits is
> possible, 128 bits is probably possible too.
> 
> Changing operands to a bigger size means changing a lot of wires and
> operations as well as counters etc all over modexp and montprod. But the
> functionality per se will be the same. A lot of details to fix, but
> basically fairly easy. This change will increase the number of block
> memories used in the FPGA. But we have a lot of those still.

i can pretend to understand.  but does verilog not give you nanguage
constucts so you do not have to rearrange everything manually?

> The montprod core is actually used in two different settings in modexp.
> In the current version of modexp a single montprod is used and muxes are
> used to allow sharing of the single instance. Instantiating a second
> montprod will allow for some parallel processing and this increased
> performance.
> 
> The cost for this is more logic and registers from a second montprod as
> well as another block memory. Some of the increased logic will
> compensated for by the removal of the logic (muxes) needed to share the
> single montprod instance.

a credible story :)

> Doing operation skipping means introducing data/operand/key dependent
> processing time and power consumption and is the source of typical side
> channel attacks on RSA. If we want to implement operation skipping I
> think it should be a compile time flag to allow an implementator to
> enable this function if he/she thinks the application is ok with side
> channel problems.

hmmmmmm

> I have been extremely bogged down with other things the last couple of
> weeks, but have now completed everything else besides Cryptech before
> summer. I have two more weeks of work before vacation and will fully
> focus on Cryptech.
> 
> We could perhaps parallelize the work, but will run into the risk of
> messing in each others changes. I feel confident that I can do these
> changes and is up to speed.

we could serialize while you are on summer holiday.  

if we do not deliver at ietf, we're toast.

randy