为什么这个将 RSA 公共指数设置为 1 的提交会有问题？

Question

我在 Hacker News 的 SaltStack 中看到了 this commit，但我不明白它到底做了什么，也不明白为什么原始版本是密码学错误。 （我也不太了解密码学的具体工作原理。）

-    gen = RSA.gen_key(keysize, 1, callback=lambda x, y, z: None)
+    gen = RSA.gen_key(keysize, 65537, callback=lambda x, y, z: None)

有人可以详细说明为什么选择“1”被替换吗？为什么“65537”更好？

Answer 1

您基本上问了三个问题：

• 这段代码是做什么的？
• 为什么

  1

  不好？
• 为什么被替换为

  65537

  ？

听起来你没有太多的密码学背景，所以我也会尝试填补一些空白。

这段代码是做什么的？

要理解为什么

1

的原始值是一个错误的选择，您必须了解一点 RSA 的工作原理。

RSA 是一种加密系统——一种执行密钥生成、加密和解密的方式——以便您可以安全地向其他人发送消息。 RSA 是称为公钥密码系统的类别的成员，因为用于加密消息的密钥是public并且每个人都可以自由地知道。您用来解密用公钥加密的消息的密钥是秘密的，只有您知道，因此我们将其称为 私钥。

如果您将挂锁和钥匙想象为公钥和私钥的模拟，您可以看到这如何与现实世界的消息一起使用：

• 鲍勃给了爱丽丝一把挂锁（他的公钥）并保留了锁的钥匙（他的私钥）。
• 现在，如果 Alice 想向 Bob 发送消息，她会将消息放入一个盒子中，将他的挂锁放在盒子上，然后将盒子发送给他。
• 只有鲍勃拥有钥匙，因此只有鲍勃可以打开挂锁并进入盒子。

要实际生成密钥，RSA 需要三个重要的数字：

• “N”，两个非常大的素数 p 和 q 的乘积
• “e”，“公共指数”
• “d”，“私人指数”

RSA 安全性的很大一部分来自于这样一个事实：鉴于

d

和

N

，要弄清楚

e

是什么应该非常困难。 RSA 中的公钥由两个数字组成：

<N,e>

，而私钥是

<N,d>

。

换句话说，如果我知道鲍勃的挂锁是什么样子，那么逆向工程一把可以打开鲍勃挂锁的钥匙应该是“非常困难”。 为什么

1

不好？

1

是一个糟糕的选择，因为它使得

非常容易

对一把可以打开鲍勃挂锁的钥匙进行逆向工程，这与我们想要的相反。 有问题的部分完整如下所示：

def gen_keys(keydir, keyname, keysize, user=None):
    # Generate a keypair for use with salt
    # ...
    gen = RSA.gen_key(keysize, 1, callback=lambda x, y, z: None)

这是一个 Python 片段，它使用 

e = 1

生成 RSA 密钥。

N

、

e

和

d

之间的关系由下式给出：d*e = 1 mod (p-1)(q-1)

但是等等：如果你选择 

e = 1

，就像 SaltStack 所做的那样，那么你就会遇到问题：

d = 1 mod (p-1)(q-1)

现在您拥有私钥了！安全性被破坏了，因为你可以弄清楚 

d

是什么。所以你可以解密每个人的传输——你已经做到了，这样你就可以通过鲍勃的挂锁轻松获得他的钥匙。哎呀。

实际上情况比这更糟。在 RSA 中，加密意味着您有一条要传输的消息

m

，您希望使用公钥

<N,e>

进行加密。加密消息

c

计算如下： c = m^e (mod N)

所以，如果 

e = 1

，那么

m^e = m

，你就有了

c = m mod N

。

但是如果

m < N，那么

m mod N

就是

m

。

所以你有：

c = m

加密文本与消息文本相同，

因此根本没有发生加密！

双重哎呀。 希望清楚为什么

1

是一个糟糕的选择！

为什么

65537

更好？65537 似乎是一个不寻常的、任意的选择。例如，您可能想知道为什么我们不能只选择

e = 3

。

e

越低，加密速度就越快，因为要加密我们必须执行的任何内容： c = m^e (mod N)

当

m^e

很大时，

和

e

可以是一个非常大的数。事实证明，65537主要是出于与现有硬件和软件的兼容性原因，以及其他一些原因。

这个 Cryptography StackExchange 答案

详细解释了它。 使用合适的随机填充方案，您可以选择几乎任何高于 1 的奇数整数，而不影响安全性，因此

e = 3

是一个可以最大化性能的选择。