40

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

-    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”更好？

4

1 回答 1

70

你基本上问了三个问题：

  • 这段代码在做什么？
  • 为什么1不好？
  • 为什么被替换为65537?

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

这段代码在做什么？

要理解为什么原来的值1是一个错误的选择，你必须了解一点RSA的工作原理。

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

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

  • Bob 给了 Alice 一把挂锁（他的公钥）并保留了锁的钥匙（他的私钥）。
  • 现在，如果 Alice 想向 Bob 发送消息，她将消息放入一个盒子中，将他的挂锁放在一个盒子上，然后将盒子发送给他。
  • 只有 Bob 有钥匙，所以只有 Bob 可以解锁挂锁并进入盒子。

要真正生成密钥，RSA 需要三个重要的数字：

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

RSA 的安全性的很大一部分来自这样一个事实，即很难弄清楚d给定N和e. RSA 中的公钥由两个数字组成：<N,e>，而私钥是<N,d>。

换句话说，如果我知道 Bob 的挂锁是什么样的，那么逆向工程将很难打开 Bob 的挂锁。

为什么1不好？

1是一个糟糕的选择，因为它很容易逆向设计一把打开 Bob 挂锁的钥匙，这与我们想要的相反。

完整的有问题的部分如下所示：

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 片段，它生成 RSA 密钥e = 1。

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 answer详细解释了它。

使用合适的随机填充方案，您可以选择几乎任何大于 1 的奇数而不影响安全性，e = 3否则可以最大限度地提高性能。

于 2013-07-05T14:08:31.573 回答