RSA 作为世界上使用最为流行的公钥密码算法，被广泛应用在数据加密和数字签名上。为了提高加密和签名验证的效率，一般会将RSA的加密指数设置的较小，一般为 65537 ，而解密或签名效率却不能够简单的通过减小私钥的长度来实现，因为过短的私钥将直接导致安全问题。于是乎，基于中国剩余定理（Chinese Remainder Theorem，简称 CRT）的 RSA 加速方案被提出。以RSA加解密为例，本文将首先讲解 RSA 基本原理，再介绍中国剩余理论和费马小定理，最后介绍 RSA-CRT算法。
1. RSA 算法流程
RSA 包括密钥生成算法和加解密算法。
1.1 RSA 密钥生成
-
-
-
-
-
-
1.2 RSA 加密与解密
假设待加密消息为 , 对 使用 RSA 加密流程如下：
-
-
得到密文 , 由于公钥公开，私钥不公开，所以任何主体都能够使用公钥进行加密。但只有拥有私钥的情况下能够对 解密。
假设待解密消息为 , 对 使用 RSA 解密流程如下：
-
-
1.3 RSA 数字签名与验证
数字签名与加密恰恰相反，由于任何主体都能够验证签名串的正确性，而只有私钥拥有者才能够生成签名串。假设待签名消息为 , 由于签名仅为了证明签名主体的行为，所以为了加快签名效率，首先对 提取数字摘要，比如使用 SHA256 等哈希算法得到数字摘要 ，对 进行签名，流程如下：
-
-
-
假设待验证签名息为 , 消息为 , 对 使用 RSA 签名验证流程如下：
-
-
-
2. 中国剩余定理
中国剩余定理（Chinese Remainder Theorem，简称 CRT) 主要讲的是数论中的一个关于一元线性同余方程组的定理。说明了一元线性同余方程组有解的准则以及求解方法。由于一元线性同余方程组问题最早出现于我国的《孙子兵法》中，原文为：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”。所以被称为中国剩余定理。
假设 两两互质，则对任意的整数： 方程组组有解，并且通解可以用如下方式构造得到：
-
-
-
方程组的通解形式为：，并且在模 的情况下，方程组只有一个解
3. 欧拉定理及费马小定理
在数论中，欧拉定理也叫做费马-欧拉定理，是一个关于同余的性质。欧拉定理表明，若 为正整数，且 互素（即 gcd() = 1）, 则
为欧拉函数，而费马小定理实际上说的是在欧拉定理的基础上，如果 是一个质数，那么
4. RSA-CRT
前文提到，由于RSA密钥中的 很大，导致在解密时的计算开销很大。令 表示明文， 表示密文， 表示 RSA 算法的模， 表示私钥。由于 和 太大以至于计算开销很大，为了简化计算，就要考虑是否存在别的方案来构造 ，而不是直接对 进行幂运算。
现假设 ， , 假定其中 和 已知， 未知，根据 CRT ，可以得到 的通解，并且在模 的意义下， 只有一个解，这个解就是我们要得到的 . 通过上述分析可以知道的是，只要知道 和 , 使用 CRT 通解方程，就能够轻松得到 。
在未知 的情况下，如何计算 和 呢。这里以 为例，推导过程如下：
不难发现， 和 的计算难度要比 的计算容易很多， 和 在长度上是一般是 的关系。
计算得到 以后，再根据 CRT 算法，就可以很快的计算出 ，根据下列公式
原文始发于微信公众号（SAINTSEC）：利用中国剩余定理加速RSA研究
评论