RSA Security 5.2.2 manual What is MultiPrime?, Milliseconds Private non-CRT

MultiPrime

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

d = e–1mod(ϕ(n))

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 exponentiation with the primes as moduli instead of "n". It is faster to do two 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)

2 1 8 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e