| Science Forum Index » Cryptography Forum » CRT for RSA... |
|
Page 1 of 1 |
|
| Author |
Message |
| Rob Blank... |
 Posted: Wed Oct 28, 2009 2:04 pm |
|
|
|
Guest
|
Hi,
A popular technique to improve RSA performance is to use the Chinese
remainder theorem. Basically, a computation of y mod N is split into two
shorter exponentiations y mod p and y mod q and these results are then
combined for the final output. I am wondering why this approach improves
performance by a factor of 4 and not only of 2 as we can only perform
two half-length modular exponentations in parallel. Could the rest of
the performance gain come from the fact that the modular reduction
routine is simpler? |
|
|
| Back to top |
|
|
|
| Paul Rubin... |
| Posted: Wed Oct 28, 2009 2:55 pm |
|
|
|
Guest
|
Rob Blank <Rob.Blank at (no spam) gmx.de> writes:
[quote]A popular technique to improve RSA performance is to use the Chinese
remainder theorem. Basically, a computation of y mod N is split into two
shorter exponentiations y mod p and y mod q and these results are then
combined for the final output. I am wondering why this approach improves
performance by a factor of 4 and not only of 2 as we can only perform
two half-length modular exponentations in parallel. Could the rest of
the performance gain come from the fact that the modular reduction
routine is simpler?
[/quote]
n-bit modular exponentation takes O(n**3) operations, so (n/2)-bit
modular exponentiation takes 1/8th as long. Since you're doing
two (n/2)-bit exponentations you get a 4x speedup compared to an
n-bit exponentiation. That assumes no parallelism; if you can
do the two half-length exponentiations in parallel, you can get
even more speedup. Note that you can also use parallelism on the
n-bit exponentiation in various ways without having to break it
into half-length exponentiations. |
|
|
| Back to top |
|
|
|
| Mike Scott... |
| Posted: Wed Oct 28, 2009 3:06 pm |
|
|
|
Guest
|
Rob Blank wrote:
[quote]Hi,
A popular technique to improve RSA performance is to use the Chinese
remainder theorem. Basically, a computation of y mod N is split into two
shorter exponentiations y mod p and y mod q and these results are then
combined for the final output. I am wondering why this approach improves
performance by a factor of 4 and not only of 2 as we can only perform
two half-length modular exponentations in parallel. Could the rest of
the performance gain come from the fact that the modular reduction
routine is simpler?
[/quote]
The modular exponentiations are with respect to half-sized moduli. Thats
4 times faster (using standard school-boy multiplication). The exponents
are half-sized as well, so thats 2 times faster as well. So thats 8
times faster altogether, but you need two of them for p and q, so its 4
times faster overall on a single threaded processor.
However on a dual-core processor both exponentiations can be carried out
in parallel, so its back to 8 times faster.
Mike Scott |
|
|
| Back to top |
|
|
|
|
