注：本文章中内容和图片主要来源于 Oded Regev 的课堂讲义。
初识 RSA
众所周知的
公钥密码体制现在被广泛应用于从网络浏览器到智能卡的各种应用中。 自
年首次发表以来，许多研究人员试图寻找系统中的漏洞。 发现了一些巧妙的攻击。 然而，已知的攻击都不是毁灭性的，
系统仍然被认为是安全的。
在这次课程中，提出了一个这样的攻击，最初源自 Hastad，然后由 Coppersmith 改良。 当
与低公共指数一起使用时，可以开展此攻击。攻击基于一种寻找低次多项式小解的算法，而这种算法又基于
算法。 这种寻根算法本身很有趣，也用于对
系统的其他攻击。
由于很多同学对 RSA 算法不是特别熟悉，我下面简单的介绍下 RSA 算法，还有对加解密算法做一个证明，以帮助大家更好的阅读下面的文章。
让我们描述一个简单版本的RSA密码系统。 设
是两个大小大致相同的大素数的乘积。设
是满足
的两个整数，其中
是乘法群
的阶数。 我们称
为
的模，
为公共指数，
为私有指数。
是公钥。 顾名思义，它是公开的，用于加密消息。
称为私钥，只有加密消息的接收方知道。 私钥可以解密密文。 消息是整数
。 为了加密
，计算
。 为了解密密文，合法接收方计算
。 事实上，
，其中最后一个等式遵循欧拉定理。
首先让我们看一下欧拉定理。在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若 
为正整数，且
互质，则:
。
对于密钥的生成和加密阶段，都很好理解，现在我们主要来看下解密过程。
回顾一下，
分别为算法中的公钥和私钥，根据算法性质知
(这里的等号为模等)，下同。
证明：
- 因
，所以
，
;
- 设
- 则解密过程
- 因
为素数，根据欧拉定理有
，故
可证
。
- 同理可证
- 因为
都为素数， 所以
, 即
证毕
。
RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的 下面介绍下RSA的低公共指数问题。
Low Public Exponent RSA
在许多实际应用中，加密过程是由一些有限的设备来完成的，例如智能卡。在这种情况下，将
提高到 high power 可能会在电池电量、时间等方面付出相当大的代价。为了简化加密过程，人们可能会尝试修改
密码系统，将公有指数固定为一些比较小的数，比如
。所以现在加密过程只需要将一个数字提高到 power
，这可以使用两次乘法来完成。
起初，这种修改似乎不会损害系统的安全性。 事实上，在不知道
的因式分解的情况下，如何逆置函数
并不明显。然而，正如我们将看到的，这种修改允许一些巧妙的攻击。 让我们首先回忆一下中国剩余定理 (Chinese Remainder Theorem)。
Lemma 1 (中国剩余定理，CRT) ：给定
等值
，使得
是之间成对互素，存在一个唯一的
满足这些等值，并且可以有效地找到这个
。
要演示使用低公共指数的危险，请考虑以下场景。
希望给
、
和
发同样的信息。她用他们的每个公钥
加密她的信息。 密文是
我们现在表明，接收
的窃听者可以很容易地恢复
。在不失去通用性的情况下，我们可以假设
是成对的相对素数（否则窃听者会找到一个公钥的 non-trivial 因子，并可以直接解密消息）。 通过使用中国剩余定理，窃听者计算一个数
，使
。 由于
，我们有
，因此
，这是整数的等式。 现在可以通过计算整数上
的立方根来轻松地恢复消息
。
似乎可以避免这个问题，从来不发送相同的信息给一个以上的人。 例如，考虑以下解决方案。 每个人，作为他的公钥的一部分，都有一些独特的
。不去加密
，而加密
，其中
是消息
的长度，以位为单位，
是收件人的身份。 这样，我们对每个人发送的消息都将不同。
在下一节中，我们证明了这种修改遭受了类似的攻击。 事实上，我们展示了一个更一般的攻击：假设公钥是形式
，其中
是
中的一些多项式。为了加密消息
，我们发送
，其中
是接收方的多项式。 在上述特殊情况下，我们有
。
在介绍攻击之前，我们声明：低公共指数
在仔细使用时仍然被认为是安全的。 也就是说，目前认为，应该使用一个适度的公共指数，例如
，并用一些随机位来填充消息。 最后，我们还提到，使用不同的技术，在低私有指数
上已知更强的攻击。
The Attack
定理 2. 假设
为
个互素的整数。设
，
为
个最大阶为
的多项式，假设存在唯一的
，使得
。故，如果
，可以有效的从
中找到
。
证明中的主要工具是以下定理，其证明在下一节中给出。
定理 3. 设
是整数，
是
阶的一元多项式(即
的系数为
)。 那么我们可以有效找到所有的
，使
和
，其中
。
Remark 1. 这个定理是相当强大的，并且在
系统的其他攻击中使用。
Remark 2. 注意
的分解是未知的。 否则，就更好的寻根算法。
证明：(定理2) 定义
。然后，我们寻找
，使
。我们可以假设所有的
都是一元的 (否则用它们的leading 系数的逆模
乘以它们；如果这个系数不是可逆的，那么我们有一个
的因子，我们就完成了)。 我们也可以在不失去一般性的情况下假设所有的
都是
阶的( 对于某些
，用
乘以)。
接下来，我们使用中国剩余定理将多项式
组合成多项式
，即我们定义
其中
的选择使用中国剩余定理，以满足对于每个
，
和对于每个
，
。 则多项式
为
- 阶为
- 首一的，因为它的
系数是
模任何
，
我们现在可以应用 定理3 来求
，因为
证毕。
Finding Roots of Low Degree Polynomials
在这一部分中，我们证明了 定理3。 我们分几步进行。 首先，我们证明了
的定理，其中
隐藏了一个只依赖于
的常数。然后，我们将其改进为
，并提到如何将其改进为
。 为了简单起见，可以认为
是一个小常数，例如
。
我们的目标是找到解
到
，使
，有
注意，如果发生这种情况，则多项式
的系数满足
因此，
因此，模方程
的
的任何小解也是整数上
的解。 使用标准技术可以有效地找到这些解决方案(例如，我们可以找到所有真正的根，因为它们中最多有
个，然后抛出所有非整数的根)。
然而，公式 (1) 没有理由在一般情况下成立。 主要的想法是，即使 (1) 对
不成立，它也可能对
的某个整数倍数减模
成立。 直观地讲，
的每一个倍数都会 "reshufflfles" 系数，由于有大约
个可能的倍数可供考虑，我们可能期望其中一个倍数会产生一个 "全部系数都很小" 的多项式。
更正式地说，我们的想法是找到一个多项式
，它具有性质 (1) ，并且具有与
相同的根。然后，我们可以直接找到
的所有根，因此也可以找到
的所有小根。为了找到这样的
，请考虑以下多项式集合：
注意，这些多项式的任何整数组合都有与
模
相同的根。因此，找到满足性质 (1) 的这些多项式的整数组合就足够了。 这自然导致我们考虑格
每列对应于
中的一个多项式。 第
行，
，对应于
乘以
的系数。
我们想证明我们可以在这个晶格中找到一个短向量。 所以首先，让我们计算
，
利用
，我们找到了长度满足的列
（即格向量）的整数组合
其中
隐藏了一个只依赖于
的常数，第二个不等式来自于 Minkowski 定理。 如果我们取
作为一个足够小的
，且只依赖于
，则小于
。特别是，
的每个坐标都小于
。 因此，如果我们取
中多项式的对应组合，我们得到一个多项式
这样，
和
具有与
相同的根。现在，我们可以用标准方法在整数上找到
的小根。 这就完成了对基本思想的描述。
接下来，我们想改进约束
。 主要思想是，我们可以考虑一个更大的多项式的集合。考虑多项式的集合
对于这些多项式的任何整数组合
，
的根包含了
的所有根，考虑格
与以前一样，使用
，我们得到了一个向量
，其长度满足
对于
，这正是
。 注意，对于这些多项式的任何整数组合
和任何
，使得
，
。 按照类似的论证，对于任何常数
，只要将
设为一个足够大的常数，就可以得到
。将
作为
的一个缓慢增长的函数，对于某个常数
，可以得到一个
的形式的边界。利用这一点，可以很容易地找到一个稍大的范围内的所有根，比如说
，把这个范围分割成
个小范围，然后对每个范围使用前面的算法。
Remark 3. 我们的证明也给出了以下纯数学问题的答案：在
的范围内，一个
阶多项式能有多少根模
？ 第一个证明给出了的
阶 上界
，第二个证明给出了
阶上界
。
Remark 4. 这种技术似乎不能在
之外得到很大的改进。 例如，考虑
和
。 在
的范围内
这个多项式有大致
的根，所以我们不能希望输出它们。
好了，这就是本节课所有的内容了，预告一下，下面我们将一起学习
《Lecture 5 Some basic complexity results》
惯例，给出参考文献
[1] Dan Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society (AMS), 46(2):203–213, 1999.
[2] Don Coppersmith. Finding small solutions to small degree polynomials. Lecture Notes in Computer Science, 2146:20–31, 2001.
