生成 RSA 2048 位密钥对需要多少时间/“收集的熵”?

信息安全 RSA
2021-08-30 13:29:15

我的问题的目的是更好地了解生成 RSA 公钥/私钥对应该花费的合理时间?

为了不那么含糊,让我指定问题并定义我将使用这些命令在运行最近的 3.2.xx linux 内核的笔记本电脑上生成密钥对。

$ openssl genrsa -out testkey.private 2048
$ openssl rsa -in testkey.private -pubout -out testkey.public

我已经对命令进行了计时,平均而言,这个操作大约需要 0.5 秒,这对我来说似乎非常快(确实太快了)。

知道我知道(并试图在问题标题中表达这一点)不仅仅是时间,而是熵的数量及其补充速率会影响创建密钥对所需的时间。至少我假设熵用于生成密钥(否则密钥将是可预测的,因此无用,对吧?)。

在使用 OpenPGP“GNU Privacy Guard”的同一系统gpg --gen-key上,我也可以用来创建 2048 位 RSA 密钥对,例如需要更长的时间,甚至需要我移动鼠标等。

所以我想知道这是怎么加起来的。从本质上讲,RSA 密钥对生成应该在现代系统上承担多少熵以及相应的时间。

我相信没有标准时间,但肯定可以用“不到 30 分钟”“超过 10 秒”来估计。

鉴于系统中有“熵”的存储。假设它们是空的,因此我正在寻找创建一个 RSA 2048 密钥对“经验法则”的时间应该涉及“在熵存储方面”从头开始。

为什么 OpenPGPgpg需要大约 2 分钟来创建 RSA 2048 密钥对并 openssl在半秒内完成......?

3个回答

为了安全起见,您所需要的只是该过程以 128 左右的熵作为初始种子运行。这里的熵意味着:攻击者不知道的东西。特别是,如果使用CSPRNG将相同的源熵扩展到许多密钥对的生成中,则没有问题。

核心模型如下:操作系统维护一个内部“熵池”,其中至少包含 128 位熵。加密强 PRNG 将该内部池扩展为任意长的伪随机位序列,根据定义,这些伪随机位序列是攻击者无法预测的,因为2 128对攻击者来说太高了,无法暴力破解池,并且“加密强" 真正的意思是“你不能比蛮力做得更好”。在 Linux 系统上,这称为/dev/urandom.

(注意:“加密强”的一部分还包括“前向安全性”:在密钥生成获取池内容不应允许将 PRNG“倒回”到生成之前的状态。好的 PRNG 是前向安全的。)

有一个关于熵被“用完”的普遍神话,就像它是某种燃料一样。这不是真的,除非在非常理论上的意义上,它仅适用于您仅将随机性用于One -Time Pad并且您的攻击者是上帝的情况。对于所有其他情况,包括为 RSA 等“普通算法”生成密钥,以及不招致天怒,从/dev/urandom. /dev/random事实上,Linux 上的行为存在严重缺陷(FreeBSD 的/dev/random要好得多)。这个网页很好地解释了 和 之间的区别/dev/random/dev/urandom以及为什么/dev/urandom应该首选。通读。

剩下的问题是:为什么GnuPG会使用/dev/random而不是/dev/urandom用于密钥生成?好吧,有历史原因(GnuPG 旨在支持操作系统提供的 PRNG 非常差的系统)和普遍的惰性(普遍不愿意挑战“既定智慧”,即使这种“智慧”是神话般的);但最大的原因是你自己的错GnuPG 像医学一样进行密码学:它不仅必须保护电子邮件,而且人类用户还必须确信刚刚出现了一些强大的密码学。药丸味道难闻时效果更好;同样,用户想要密钥生成看起来像是一项昂贵的工作。您自己的问题证明了这种感觉:尽管您实际上并不确切知道 CSPRNG 中发生了什么(这是密码学家的问题),但您仍然认为“0.5 秒太快了”。GnuPG 通过大量展示密钥生成过程来满足您的要求。这都是安全剧院,它发生是因为想要那样。

通过测量文件 的读取gpg似乎是使用的熵/随机源,答案似乎是openssl/dev/random/dev/urandom

对于我们需要/使用的 2048 位 RSA 密钥对

  • 300 字节的“/dev/random随机性”,以防万一gpg
  • 32字节的“/dev/urandom随机性”openssl

/dev/random因此,时间差(gpg ca. 30secs)与(openssl ca 0.5secs)的时间差可以通过当随机性耗尽时阻塞的事实来解释。

补充一下humanandpeace 所说的,/dev/urandom 是一个使用内核内部熵池的 CSPRNG(用于 /dev/random,也是一个以熵估计 == 0 进行阻塞的 CSPRNG),但由 CSPRNG 算法扩展。这意味着从 /dev/random 读取非常慢,除非你有一个硬件 RNG 提供它。

GnuPG 使用来自 /dev/random 的原始数据输入来生成密钥。它使用 /dev/random 是因为它希望确保密钥的高质量熵,而 /dev/urandom 在某些系统上不是一个好的熵源(或者至少不是,我不确定这是否仍然真的)。

另一方面,OpenSSL 使用来自 /dev/urandom 的 32 个字节来播种它自己的内部 CSPRNG,然后从那里生成密钥生成所需的数据。这解释了更快的操作。

除非在 /dev/urandom 生成的随机数据中发现不影响 /dev/random 的弱点,否则以任何一种方式生成的密钥都应该是安全的。/dev/urandom 被认为是加密安全的,并且用于许多其他操作,因此它的弱点将是一个大问题。