Computes the RSA algorithm. If
p is null, straightforward
modular exponentiation is used.
Otherwise, this method uses the Chinese Remainder Theorem (CRT) to
compute the result given the known factorisation of the public
modulus
n into two relatively prime factors
p and
q.
The arithmetic behind this method is detailed in [1] and [2].
The comments that follow, which are edited from the PGP
mpilib.c file
with p and q reversed, make
the practical algorithmic implementation clearer:
Y = X**d (mod n) = X**d (mod pq)
We form this by evaluating:
p2 = plain**d (mod p) and
q2 = plain**d (mod q)
and then combining the two by the CRT.
Two optimisations of this are possible. First, we reduce X modulo p
and q before starting, since:
x**a (mod b) = (x (mod b))**a (mod b)
Second, since we know the factorisation of p and q (trivially derived
from the factorisation of n = pq), and input is relatively prime to
both p and q, we can use Euler's theorem:
X**phi(m) = 1 (mod m),
to throw away multiples of phi(p) or phi(q) in d. Letting
ep = d (mod phi(p)) and
eq = d (mod phi(q))
then combining these two speedups, we only need to evaluate:
p2 = (X mod p)**ep (mod p) and
q2 = (X mod q)**eq (mod q).
Now we need to apply the CRT. Starting with:
Y = p2 (mod p) and
Y = q2 (mod q)
we can say that:
Y = q2 + kq
and if we assume that:
0 <= q2 <32q, then
0 <= Y <32pq for some 0 <= k <32p
Since we want:
Y = p2 (mod p),
then
kq = (p2 - q2) (mod q)
Since p and q are relatively prime, q has a multiplicative inverse
u mod p. In other words, uq = 1 (mod p).
Multiplying by u on both sides gives:
k = u * (p2 - q2) (mod p)
Once we have k, evaluating kq + q2 is trivial, and that gives
us the result.