ABSTRACT

The first variant of RSA that we consider is CRT-RSA. Made popular by Quisquater and Couvreur [198], CRT-RSA is currently the standard way of implementing RSA in practice.

The computational costs for RSA decryption can be decreased by exploiting the factorization of the modulus. Let (e,N) be a valid public key and (d, p, q) be its corresponding private key, where the exponents are defined modulo λ(N). For a given ciphertext c = me mod N , the standard decryption algorithm for RSA recovers the plaintext by computing

m = cd mod N,

a single exponentiation modulo an n-bit number. Since the primes in the modulus are known to the party decrypting, the plaintext can also be recovered by first computing partial decryptions of the ciphertext modulo p and modulo q and then combining these with the Chinese remainder theorem to compute the plaintext. That is, we can first compute

mp = cd mod p

mq = cd mod q,

and then, since the primes are relatively prime to each other, combine these using the Chinese remainder theorem to obtain the plaintext. Using Garner’s algorithm for example (see Menezes, van Oorschot and Vanstone [169, Section 14.5.2]), the plaintext is computed as

m = mp + p ( (mq −mp)p−1 mod q

) .