一、 传统的计算方法RSA
1.公私钥计算 （1） 计算 n = p x q ; （2） 计算Φ（n）= (p-1) x (q-1); （3） 选择 e ，且e与Φ（n）互素 ; （4） 确定d x e= 1 mod Φ（n）; （5） 确定公钥 PU = {n , d}, 私钥 PR = {n,e} 2.加解密 明文M ;加密Y= M^e mod n； 解密 M = Y^d mod n；
二、 中国剩余定理简介
p和q是独立的大素数，n为p*q，对于任意(m1, m2), (0<=m1< p, 0<=m2< p) 一定有一个独特的m ,0<=m< n 使得 m1 = m mod p m2 = m mod q
所以换句话说，给定一个(m1,m2)满足上述等式的m必须是唯一存在的。
所以解密RSA的流程c^d mod n,可以分解为 m1=c^d mod p以及m2=c^d mod q然后计算方程组m( m以下是计算方法 )。 但是等式c^d mod p 或者 c^d mod q ，虽然模数从n降到p或q但是这个指数d还是比较大的，操作还是比较消耗性能的。我们需要降低指数。
仔细看等式c^d mod p 令 d = k(p-1) r 则 c^d mod p =c^(k(p-1) r) mod p =c^r * c^(k(p-1)) mod p 因为 c^(p-1) mod p = 1 (欧拉定理) =c^r mod p
r是d除p-1的余数，即 r = d mod (p-1) 所以 c^d mod p可以降阶为 c^(d mod p-1) mod p,同理，c^d mod q可以降阶为 c^(d mod q-1) mod q。 其中 dP = d mod p-1 和 dQ = d mod q-1 可提前计算。 但是计算dP和dQ可以更简单地计算e对p-1和q-1的逆。
三、 使用中国剩余定理（CRT）RSA解密
首先，在生成私钥公钥时，我们需要生成更多的数字： 我们的d是e对Φ（n）我们现在需要另外两个逆元(分别是对的(p-1)和(q-1)的），既 1：计算dP，使得dPe = 1 mod(p-1)，即 dP = (1/e) mod (p-1) 2：计算dQ，使得dQe = 1 mod(q-1)，即dQ = (1/e) mod (q-1) 此外，第三个元素需要q对p的逆元 3：计算qInv，使得qInv * q = 1 mod p，即qInv = (1/q) mod p 私钥是 (p, q, dP, dQ, qInv)
计算： 使用公钥加密： 若要加密明文m,则需要计算c = m^e mod n，c为密文。
使用私钥解密： 1:m1=c^dP mod p 2:m2=c^dQ mod q 3:h= qInv.(m1 - m2) mod p 4:m = m2 h*q m就是明文。
引用： https://www.di-mgt.com.au/crt_rsa.html