Chinese Remainder Theorem synthesis algorithm
Suppose m = pq where p and q are large, distinct primes. In the previous post we said that calculations mod m can often be carried out more efficiently by working mod p and mod q, then combining the results to get back to a result mod m.
The Chinese Remainder Theorem assures us that the system of congruences
has a unique solution mod m, but the theorem doesn't say how to compute x efficiently.
H. L. Garner developed an algorithm to directly compute x [1]:
You compute the inverse of q mod p once and save it, then solving the system above for multiple values of a and b is very efficient.
Garner's algorithm extends to more than two factors. We will present the general case of his algorithm below, but first we do a concrete example with RSA keys.
RSA key exampleThis is a continuation of the example at the bottom of this post.
This shows that the numbers in the key file besides those that are strictly necessary for the RSA algorithm are numbers needed for Garner's algorithm.
What the key file calls coefficient" is the inverse of q modulo p.
What the key file calls exponent1" is the the decryption exponent d reduced mod p-1. Similarly, exponent2" is d reduced mod q-1 as explained here.
from sympy import lcm prime1 = 0xf33514...d9 prime2 = 0xfee496...51 publicExponent = 65537 privateExponent = 0x03896d...91 coefficient = 0x4d5a4c...b7 # q^-1 mod p assert(coefficient*prime2 % prime1 == 1) exponent1 = 0x37cc69...a1 # e % phi(p) exponent2 = 0x2aa06f...01 # e % phi(q) assert(privateExponent % (prime1 - 1) == exponent1) assert(privateExponent % (prime2 - 1) == exponent2)More factors
Garner's algorithm can be used more generally when m is the product of more than two primes [2]. Suppose
where the mi are pairwise relatively prime (not necessarily prime). Then the system of congruences
for i = 1, 2, 3, ..., n can be solved by looking for a solution of the form
where
Again, in practice the modular inverses of the products of the ms would be precomputed and cached.
Related posts[1] Ferguson, Schneier, Kohno. Cryptography Engineering. Wiley. 2010.
[2] Geddes, Czapor, and Labahn. Algorithms for Computer Algebra. Kluwer Academic Publishers. 1992.
The post Chinese Remainder Theorem synthesis algorithm first appeared on John D. Cook.