Re: parallel encryption

[Matthew Ghio <ghio@netcom.com>]

ses@tipper.oit.unc.edu (Simon Spero) wrote:
> Ok, so I've got my BeBox and so finally have an SMP of my own again;
> anyone want to suggest any cool crypto stuff that parallelises well?
> Rogaways hashs look interesting, and nDES offers an obvious process
> network for pipelining, but what about things like running multiple
> interleaved CBC streams in parallel, with each stream starting off from a
> different IV? I can't think of any practical ways of speeding up a single
> RSA operation, although twice as many processors obviously gives twice
> the thruput.

One way to speed up RSA is to compute the series m^2, m^4, m^8, m^16...
on one processor and then multiply together the values for each one bit
in the decryption exponent on the other processor.  It's only about a 33%
speedup tho.  The other possibility is to compute the two 'halves' on
seperate processors when doing decryption.  I don't know of any way to
parallelize it to more than two processors for encrypting or more than
four for decrypting.

Discrete log systems are a bit more interesting in this respect - you can
precompute the series g^2, g^4, g^8...  (I think cryptolib does this)
then the initial parameter in a Diffie-Hellman exchange is simply the 
product of some elements of that series.  The multiplications can be
carried out in parallel in a hierarchial fashion which can be completed
in O(log(log(m))) time, where m is the modulus (assuming you have enough
processors).  However, for the second half of the exchange, you can't
precompute anything so you are stuck with the same problem as with RSA.