MultiPrime
218 RSA BSAFE Crypto-C Developer’s Guide
MultiPrime
This section provides an overview of the MulitPrime enhancement to Crypto-C
including information on how to generate an RSA MultiPrime key.

What is MultiPrime?

In classic RSA, you create a modulus (called "n") by multiplying two large primes
together. The public and private exponents are then "e" (generally a Fermat number
such as 3, 17, or 65,537) and
where
is the Euler "phi-function".
One problem with RSA has always been performance of private-key operations. One
advance in performance was to use an algorithm based on the "Chinese Remainder
Theorem" (or "CRT") to perform the private key operations. This required performing
modular e xponen tiatio n with t he prime s as mod uli ins tead of "n". It i s faste r to do t wo
modular exponentiations with smaller moduli (and exponents) than one modular
exponentiation with a large modulus (and exponent).
Recently, Compaq acquired a patent on MultiPrime RSA. Under this scheme, a
modulus is the product of three (or more) primes. The public and private keys are
computed as before.
Now when performing private key operations, it is possible to use the Chinese
Remainder Theorem to make three modular exponentiations using the three primes.
Since each of the primes is smaller than each of the two primes of classic RSA, the
overall time is reduced.
For example, using 1024-bit RSA key pairs on a 450 MHz Pentium processor, the
following table illustrates the performance gains of CRT over non-CRT and
MultiPrime (using three primes) over 2-prime.
(milliseconds) Private non-CRT CRT public (expo = 3)
de
1–mod ϕn()()=
ϕ