Breadcrumbs Section. Click here to navigate to respective pages.

Chapter

Chapter

# CRT-RSA

DOI link for CRT-RSA

CRT-RSA book

# CRT-RSA

DOI link for CRT-RSA

CRT-RSA book

## ABSTRACT

The ﬁrst 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 deﬁned 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 ﬁrst 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 ﬁrst 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

) .