一、 传统方式计算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）的逆元，我们现在需要另外2个逆元（分别是对(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.toymoban.com/news/detail-472765.html
引用：
https://www.di-mgt.com.au/crt_rsa.html文章来源地址https://www.toymoban.com/news/detail-472765.html
到了这里，关于RSA的中国剩余定理（CRT）算法解密的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
