密码学系列｜3.2 RSA公钥密码系统

3.2 

The RSA Public Key Cryptosystem

Bob 和 Alice 通常需要在一个不安全信道交换敏感信息。在第二章中，我们已经了解了 一些基于解决离散对数问题困难度的方法。在本节中，我们将介绍 RSA公钥密码系统，它是最早发明的，也是最著名的公钥密码系统。RSA 是以其（公开）发明者：Ron Rivest, Adi Shamir, 和 Leonard Adleman 姓氏命名的。

RSA 的安全性取决于以下 dichotomy：

• 构建：设大素数 ，，设整数 
• 问题：解关于  的同余式 
• 容易：知道  值的 Bob 根据命题 3.5 可以轻易的解出 
• 困难：不知道  值得 Eve 不能轻易得解出 
• dichotomy：解关于  的同余式  ，对一个掌握了某些额外信息的人来说很容易，但对其他人来说很难。

表3.1总结了RSA公钥密码系统：Bob 的密钥是一对大素数  。他的公钥是一对 ，其中  ， 和  互素。Alice 将其明文转换为 1 到  之间的整数 。然后计算加密  得到密文 。

虽然 Alice 将密文发送给 Bob。而对于 Bob 来说，解同余式  然后恢复 Alice 的消息  是简单的，因为 Bob 知道  的因子 。而对于敌手 Eve 来说，尽管他可能中途拦截获取了密文消息 ，但是由于他不知道  的分解，因此他也很难解出同余式  从而破获 Alice 发给 Bob 的秘密消息 。

例 3.9 接下来我们用一个小的例子来说明 RSA公钥密码系统。当然，这个例子并不安全，因为用的数字很小，所以 Eve 能够很容易的将  的因子  计算出来。安全的 RSA 密码系统需要使用具有数百位比特的模数 。

RSA Key Creation

• Bob首先选择两个秘密素数 ，然后计算模数 

• Bob 选择公开加密指数 ，其满足

RSA Encryption

• Alice 将他们的明文转化为整数 

• Alice 使用 Bob 的公钥  计算密文

• Alice 将密文  发送给

RSA Decryption

• Bob 已知 ，所以他可以计算

解得 

• Bob 使用密文 ，然后计算

解得 Alice 得明文消息 

注 3.10 Bob 的公钥对  ，其中  被称为模数， 称为加密指数。而 Bob 用来解密 Alice 消息的整数  ，且满足

称为解密指数。显然，如果加密指数  比较小，那么加密过程就会比较快。同样的，如果解密指数比较小，那么解密过程也会更有效率。当然，Bob 没法同时使得他们两个都很小，因为他只能指定其中一个，另外一个是根据同余式 3.4 计算出来的（当然这也不是严格正确的，Bob 可以同时使得 ，但是这就意味着明文和密文一致了。）

注意到 Bob 也不能选择 ，因为  需要和  互素，所以  最小只能选择 ，就目前而言， 取 3 和比起取其他更大的值还是一样安全的。对于那些想要快速加密，但是又担心  太小的人，通常采用，因为通过1.3.2一节中描述的平方和乘法算法，计算  只需要进行16次平方运算和一个乘法运算。

对于 Bob 来说，另外一个选择是选择一个比较小的 ，然后根据同余式  计算公钥 ，那么  应该会很大。然而，事实证明，这可能会导致 RSA 不安全。更准确地说，如果  ，那么根据连分数理论 Eve 就能够破解RSA。

注 3.11 Bob 的公钥对包括模数 , 其中  是两个秘密素数。通过命题 3.5 我们知道，如果 Eve 知道  的值，那么它可以轻易的解决 ，并解密发送给 Bob 的消息。

我们展开  得到

Bob 已经公开了 N，因此如果 Eve 能够知道  的和，那么根据式子 3.5，就可以计算出能够解密消息的  了。

事实上，如果 Eve 知道了  和  的值，那么他也能很轻易的计算出  来。只需要找到二次多项式

的根就好了。注意到这个多项式可以合并为 ，所以  就是这个多项式的根。因此如果 Bob 公开了  的值，对于 Eve 来说，找到  的值并不比找到  本身来说更容易。

接下来我们通过一个例子来说明，如果 Eve 知道

首先它根据式  计算

然后他就可以用二次多项式来进行分解

因此得到 

注 3.12 最后一个非常重要的点。我们已经证明，Eve 计算出  的值并不比分解  简单，但这并不能证明 Eve 为了解密 Bob 的信息必须分解 。重点是 Eve 真正需要做的是解决形为  同余方程（即在模  求  的  次根）。可以想象，也许有一种有效的算法可以在不知道  的值的情况下求解此类同余方程，不过暂且还没有人知道这种方法的存在。尽管求模  下的  次根可能比分解  要容易，详情请参见 D. Boneh, R. Venkatesan, Breaking RSA may not be equivalent to factoring (extended abstract), in Advances in Cryptology—EUROCRYPT ’98, Espoo. Volume 1403 of Lecture Notes in Computer Science (Springer, Berlin, 1998), pp. 59–71