这篇讲一下如何使用中国剩余定理CRT来对RSA加密运算进行加速。
RSA运算
当我们使用RSA私钥(n,d)对密文c进行解密(或者计算数字签名时)，我们需要计算模幂。私钥指数
并不像公钥指数
那样方便。一个k比特的模n，对应的私钥指数d差不多跟它一样长。计算的工作量同长度k成正比，所以对于RSA私钥的运算，有更多的计算量。
我们可以使用CRT模式更有效的计算
- 使用
提前计算以下值:
- 使用
表示模逆，表达式
y也会写成
。x是任意整数满足
。
。
- 使用密文c计算明文消息m
我们把作为私钥保存。
下面需要了解两个数论的原理，分别是中国剩余定义的一个特殊情况和欧拉定理。
中国剩余定理-特殊情况
中国剩余定理的特殊情况可以表述如下：
%EF%BC%8C0%20%5Cleq%20x_1%20%5Clt%20p%20%E4%B8%94%200%20%5Cleq%20x_2%20%5Clt%20q%EF%BC%8C%E5%AD%98%E5%9C%A8%E5%94%AF%E4%B8%80%E7%9A%84%E6%95%B0x%EF%BC%8C0%20%5Cleq%20x%20%5Clt%20n)
所以任意整数x都可以使用CRT表示方法唯一的表示成。
欧拉定理 Euler's Theorem
欧拉定理是费马小定理(Fermat's Little Theorem)的推广，也称作欧拉-费马定理(Euler-Fermat Theorem)。
如果n是一个正整数，a是任意整数，且
，那么
一个质数p，
CRT表示法中的运算
我们需要计算。如果我们知道
那么CRT告诉我们存在唯一的值
在范围[0,n-1]。
使用CRT表示方法恢复出x，我们使用Garner's方程式。
(q%5E%7B-1%7D%20%5C%20mod%20%5C%20p))%20%5C%20mod%20%5C%20p)
CRT系数可以提前计算。模幂的运算量随着模的比特数k的立方增加而增加。所以做两次幂运算mod p和mod q，比做一次幂运算mod n效率要高。
计算，可以使用欧拉定理来减少指数d modulo (p-1):
对于q使用相同的算法。
