RSA with multiple primes

Typically RSA public keys are the product of two large primes,n =pq. But there's no reason they couldn't be the product of say three primes,n =pqr, or more primes, as long as (n), or (n), is calculated correctly.

Encryption is done the same way. Decryption could be done the same way, except there is the opportunity for it to be more efficient. The trick is to use the CRT (Chinese Remainder Theorem) in a way similar to Garner's algorithm. This is why RSA with multiple primes is sometimes used for digital signatures.

The difficulty of factoringn using the GNFS algorithm doesn't change depending on the number of factors n has, as long as all the factors are sufficiently large, far too large to find using trial division.

Daniel Bernstein's post-quantum RSA paper was based on keys that are the product of a large number of 4096-bit primes. This way all the arithmetic is carried out modulo 4096-bit primes, not modulo terabyte primes.

The post RSA with multiple primes first appeared on John D. Cook.