读<跨越千年的RSA算法>

原文链接 跨越千年的RSA算法

在当今这个由互联网构筑的世界里, RSA算法几乎无处不在. 例如:

  • 访问任何一个https证书加密的网站
  • 通过SSH登录一台服务器
  • 从GitHub上clone一个项目

说来惭愧, 作为一个每天和RSA算法打交道的程序员, 直到最近学习了Matrix67大神讲解RSA算法的博客我才终于理解RSA算法到底是怎么一回事. 在真正介绍RSA算法之前作者用了大量的篇幅为读者填补了必要的数学基础, 文章共分为六个小节, 真正提到RSA算法的只有最后一个小节, 我之前也看过一两篇其他介绍RSA算法的文章, 但唯有这一次让我有种豁然开朗的感觉.

(一)可公度线段

文章介绍了在<几何原本>中一种求取最大公约数的方法(Euclid 算法): 假设刚开始的两个数是 a 和 b ,其中 a > b ,那么把 a 除以 b 的余数记作 c ,把 b 除以 c 的余数记作 d ,c 除以 d 余 e , d 除以 e 余 f ,等等等等,不断拿上一步的除数去除以上一步的余数。直到某一次除法余数为 0 了,那么此时的除数就是最终结果。因此, Euclid 算法又有一个形象的名字,叫做 辗转相除法

(二)中国剩余定理

给出 m 个两两互质的整数,它们的乘积为 P, 假设有一个未知数 M, 如果我们已知 M 分别除以这 m 个数所得的余数, 那么在 0 到 P – 1 的范围内, 我们可以唯一地确定这个 M, 这可以看作是 M 的一个特解. 其他所有满足要求的 M ,则正好是那些除以 P 之后余数等于这个特解的数。

Bézout 定理 是中国剩余定理的另一种形式. 如果 a 和 n 互质, 那么

  a * x mod n = 1
  a * x mod n = 2 
  ...
  a * x mod n = n-1 

以上所有方程都是有解的

如果将第一个等式换成 中国剩余定理 的表达, 则可以表达描述为: a 和 n 互质, 那么在 0 到 a*n - 1 的范围内一定存在唯一的M, 使:

M mod a = 0
M mod n = 1

这里的 M 相当于上面的 a * x

(三)扩展的辗转相除

根据中国剩余定理, 我们可以指定在 0 到 P-1 之间 M 一定有唯一解, 那么如何在已知m和余数的条件下求出这个M呢 ? 这就是 扩展的辗转相除法

现在, 让我们尝试求解 115x mod 367 = 1, 根据中国剩余定理(或者说Bézout 定理), 由于 115 和 367 是互质的, 因此方程在 0 到 115 * 367 - 1 之间一定存在唯一解.

我们解方程的基本思路是,不断寻找 115 的某个倍数以及 367 的某个倍数, 使得它们之间的差越来越小,直到最终变为 1.

由 367 除以 115 得 3 余 22, 
即 3 个 115 只比 367 少 22, 
于是 15 个 115 就要比 5 个 367 少 110, 
从而 16 个 115 就会比 5 个 367 多 5.

好了,真正巧妙的就在这里了:

由 16 个 115 比 5 个 367 多 5, 
可得 64 个 115 比 20 个 367 多 20
结合 3 个 115 比 1 个 367 少 22,
可得 67 个 115 比 21 个 367 少 2. 

再结合 "少 2" 和 "多 5" 两个式子,

由 67 个 115 比 21 个 367 少 2, 
可得 134 个 115 比 42 个 367 少 4, 
结合 16 个 115 比 5 个 367 多 5, 
可得 150 个 115 比 47 个 367 多 1. 

这样,我们就解出了一个满足 115x mod 367 = 1 的 x , 即 x = 150.

在求解过程, 我们相当于对 115 和 367 做了一遍辗转相除: 我们不断给出 115 的某个倍数和 367 的某个倍数, 通过辗转对比最近的两个结果, 让它们的差距从"少 22"缩小到"多 5", 再到"少 2", "多 1", 其中 22, 5, 2, 1 这几个数正是用辗转相除法求 115 和 367 的最大公约数时将会经历的数. 因而, 算法的步骤数仍然是对数级别的, 即使面对上百位上千位的大数, 计算机也毫无压力.

这种求解方程 a · x mod n = b 的算法就叫做“扩展的辗转相除法”。

(四)Fermat 小定理

1640 年, 法国业余数学家 Pierre de Fermat(通常译作"费马")发现, 如果 n 是一个质数的话, 那么对于任意一个数 a, a 的 n 次方减去 a 之后都将是 n 的倍数. 例如, 7 是一个质数, 于是 2^7 – 2, 3^7 – 3, 4^7 – 4, 甚至 100^7 – 100, 统统都能被 7 整除. 关于费马小定理的证明, 读者可以参见原文.

Fermat 小定理有一个等价的表述: 如果 n 是一个质数的话, 那么对于任意一个数 a, 随着 i 的增加, a 的 i 次方除以 n 的余数将会呈现出长度为 n – 1 的周期性.

为什么呢?

根据费马小定理, a^n 与 a 的差能够被 n 整除, 这相当于 a^n 和 a 分别都除以 n 之后将会拥有相同的余数. 另一方面, a^i 除以 n 的余数, 完全由 a^i-1 除以 n 的余数决定, 比方说, 假如我们已经知道 33 除以 7 等于 3 余 6, 这表明 33 里包含 3 个 7 以及 1 个 6. 因此, 34 里就包含 9 个 7 以及 3 个 6, 或者说 9 个 7 以及 1 个 18. 为了得到 34 除以 7 的余数,实际上只需要看看 18 除以 7 余多少就行了. 可见, 要想算出 a^i-1 · a 除以 n 的余数,我们不需要完整地知道 a^i-1 的值, 只需要知道 a^i-1 除以 n 的余数就可以了

重点 相乘之前事先对乘数取余不会对结果造成影响, 可用数学表达式表示为:

(a * b) % p = (a % p * b % p) % p

这也是取模运算的基本运算法则

值得注意的是, n – 1 并不见得是最小的周期. 如 2^i 除以 7 的余数情况, 余数序列确实存在长度为 6 的周期现象, 但实际上它有一个更小的周期 3.

假如某个整数 n 等于两个质数 p, q 的乘积,那么对于任意一个整数 a ,写出 a^i 依次除以 n 所得的余数序列, p – 1 和 q – 1 的最小公倍数将成为该序列的一个周期. 事实上, p – 1 和 q – 1 的任意一个公倍数, 比如表达起来最方便的 (p – 1) × (q – 1), 也将成为该序列的一个周期.

(五)公钥加密的可能性

加密算法和解密算法有可能是不对称的吗?

小时候我经常在朋友之间表演这么一个数学小魔术: 让对方任意想一个三位数, 把这个三位数乘以 91 的乘积的末三位告诉我, 我便能猜出对方原来想的数是多少. 如果对方心里想的数是 123, 那么对方就计算出 123 × 91 等于 11193, 并把结果的末三位 193 告诉我. 看起来, 这么做似乎损失了不少信息, 让我没法反推出原来的数. 不过, 我仍然有办法: 只需要把对方告诉我的结果再乘以 11, 乘积的末三位就是对方刚开始想的数了. 你可以验证一下, 193 × 11 = 2123 ,末三位正是对方所想的秘密数字! 其实道理很简单, 91 乘以 11 等于 1001, 而任何一个三位数乘以 1001 后, 末三位显然都不变(例如 123 乘以 1001 就等于 123123 ). 先让对方在他所想的数上乘以 91, 假设乘积为 X, 我再在 X 的基础上乘以 11, 其结果相当于我俩合作把原数乘以了 1001, 自然末三位又变了回去.

不过, 加密和解密的过程不对称并不妨碍我们根据加密方法推出解密方法来, 虽然这可能得费些功夫. 比方说, 刚才的加密算法就能被破解: 猜出对方心里想的数相当于求解形如 91x mod 1000 = 193 的方程, 这可以利用扩展的辗转相除法很快求解出来.

为了得到一个可以公开加密钥匙的算法, 我们需要一种在只知道加密钥匙的情况下, 构造出解密钥匙非常非常困难的算法。

1970 年左右,科学家们开始认真地思考“公钥加密系统”的可能性。 1977 年,来自 MIT 的 Ron Rivest 、 Adi Shamir 和 Leonard Adleman 三个人合写了一篇论文,给出了一种至今仍然安全的公钥加密算法。随后,该算法以三人名字的首字母命名,即 RSA 算法。

RSA 算法用到了一种非常犀利的不对称性——大数分解难题.

这种不对称性的点在于, 我们可以很容易的判断一个数是否是质数(稍后会讲到), 进而可以很容易的生成一个很大的质数, 但是到目前为止, 我们却没有一种高效的方法, 判断将一个大数分解成两个质数的乘积.

判断一个数是否是质数的方法, 可以搜索以下内容:

 Fermat 素性测试
 Miller-Rabin 素性测试
 AKS 素性测试

(六)RSA 算法

所有工作都准备就绪, 下面我们可以开始描述 RSA 算法了.

首先, 找两个质数, 比如说 13 和 17 (实际使用时, 我们会选取大得多的质数). 把它们乘在一起, 得 221. 再计算出 (13 – 1) × (17 – 1) = 192. 根据前面的结论, 任选一个数 a, 它的 i 次方除以 221 的余数将会呈现长度为 192 的周期(虽然可能存在更短的周期). 换句话说, 对于任意的一个 a, a, a^193, a^385, a^577 ... 除以 221 都拥有相同的余数. 注意到, 385 可以写成 11 × 35 ... 嘿嘿,这下我们就又能变数学小魔术了. 叫一个人随便想一个不超过 221 的数,比如 123. 算出 123 的 11 次方除以 221 的余数, 把结果告诉你. 如果他的计算是正确的, 你将会得到 115 这个数. 看上去, 我们似乎很难把 115 还原回去, 但实际上你只需要计算 115 的 35 次方, 它除以 221 的余数就会变回 123. 这是因为, 对方把他所想的数 123 连乘了 11 次, 得到了一个数 X, 你再把这个 X 乘以自身 35 次, 这相当于你们合作把 123 连乘了 385 次, 根据周期性现象, 它除以 221 的余数仍然是 123. 然而, 计算 35 个 X 连乘时, 反正我们要取乘积除以 221 的余数, 因此我们不必完整地获知 X 的值, 只需要知道 X 除以 221 的余数就够了. 因而, 让对方只告诉你 X 取余后的结果, 不会造成信息的丢失.

让我们试想一下, 现在可以公开获取到的信息有 211 和 11, 如果攻击者想要解密数据就必须知道原数据的i次方对211取模的循环周期是多少(即192). 假设 211 是一个很大的数, 我们几乎没有办法把 221 分解成 13 和 17 的乘积.

而作为生成秘钥对的一方, 我们知道 211 = 13 * 17, 进而知道原数据的i次方对211取模的循环周期是192, 那么现在, 我们要找出两个数 e 和 d ,使得 e 乘以 d 的结果除以 192 余 1 应该怎么做呢 ?

还记得 中国剩余定理 吗?

上面的问题可以写成数学表达式 e · d mod 192 = 1

首先, 我们随便找一个和 192 互质的数 (这是可以做到的, 比方说, 可以不断生成小于 192 的质数, 直到找到一个不能整除 192 的为止),把它用作我们的 e (比如 11). 我们知道, 因为 11 和 192 互质, d 的解一定是存在的.

让我们用 扩展的辗转相除法 再推导一次吧 !

因为 192 除以 11 商 17 余 5,
即 17个11 比 1个192 少 5,
且 18个11 比 1个192 多 6,
那么, 35个11 比 2个192 多 1, 即 11 * 35 除以 192 商 2 余 1

这正是我们需要的结果! d = 35

现在, e 和 n 就可以作为加密钥匙公之于众, d 和 n 则是只有自己知道的解密钥匙. 因而,加密钥匙有时也被称作公钥, 解密钥匙有时也被称作私钥. 这就是RSA算法背后的数学原理了, 更多关于RSA算法计算过程中的优化细节可以阅读原文, 也非常我们值得仔细思考.

<几何原本> 约于公元前300年由古希腊数学家 欧几里得 所著. 伟大的数学思想穿越2300多年的时空, 在今天这个互联网的时代大放异彩.

Show Comments