与 RSA 密钥相比,我的 ed25519 密钥太短了,这很糟糕吗?

信息安全 RSA 电子抄送
2021-09-05 05:02:56

我最近生成了一个 ed25519 格式的新 SSH 密钥。公钥只有 69 个字节长,而我的旧 RSA 密钥是 373 个字节。

从我的看法 ed25519 是更新和安全的格式。

那么为什么这里不再更好呢?

2个回答

不,越长越好。

让我解释。对称密码学中,密钥只是比特串,所有比特序列都是有效密钥。它们没有内部结构。假设您使用了不错的算法,对对称加密密钥的最佳攻击是暴力破解:攻击者尝试所有可能的密钥,直到找到正确的密钥。如果密钥有n位,则有 2 n 个可能的密钥,平均而言,攻击者会在尝试一半后找到正确的一个,即 2 n -1因此,较长的键会使蛮力变得更加困难;在这种情况下,越长越好。

(请注意,这是有限制的;当密钥足够长以至于暴力破解不再可行时,增加密钥长度不会以任何有意义的方式使事情“更安全”。因此,对于对称密钥,越长越好,直到它们足够长,此时更长就是更长。)

RSA 和 EdDSA 与完全不同的非对称密码学有关。非对称密码学的密钥是具有特定内部结构的数学对象;破解密钥在于解开该结构,并且可以比尝试所有可能的私钥更有效地完成。注意两点:

  • 对抗暴力破解,重要的不是公钥的长度而是私钥长度,因为攻击者想要的是私钥,而不是公钥。

  • 蛮力不是针对非对称密码学中使用的密钥的最有效攻击。

对于 RSA 密钥,攻击通过分解模数来成功。整数分解是一个长期研究的问题。使用最知名的算法,破解 2048 位 RSA 密钥(即模数为 2048 位整数的 RSA 公钥)需要大约 2 110次左右的基本操作。

对于 EdDSA 密钥,公钥是椭圆曲线上的点P ,因此P = xG其中x是私钥(256 位整数),G是常规曲线点。PG中恢复x的最著名算法需要大约 2 128个基本操作,即比 2048 位 RSA 密钥还要多。一般来说,要破解一个n位椭圆曲线公钥,工作量是 2 n /2

打破任何一个关键都远远超出了现有或可预见的技术是可行的。但从“学术”的角度来看,EdDSA 密钥比 RSA 密钥强一些;此外,椭圆曲线为您提供了更高的每位安全性(从技术上讲,我们说整数分解是一个次指数问题)。

有关该主题的更多信息,请参阅此站点

我对我之前的回答不满意,这导致对 ed25519 中使用的压缩方法的混淆假设,所以我会再试一次,让那些不会跳到 EC(进一步椭圆曲线)数学上的人能够理解为什么与 RSA 密钥相比,EC 密钥是如此之短。

由于我的英语远非完美,因此我最好在恕我直言,这个主题的链接非常好。

对于那些真正想了解 EC 的“魔力”(但仍想避免深深爱上数学)并能够理解的人 - “为什么 EC 可以使用更小的密钥管理比 RSA 更强大的加密”, - 我建议阅读 arstechnica.com 上的完整文章“椭圆曲线密码学相对容易理解的入门”

作者用图像说明了 EC 的要点,这些图像有助于通过几个步骤理解概念。

欧共体

顺便说一句,关于 EC 的有趣摘录:

您可以计算破解密码算法需要多少能量,并将其与能量可以煮沸多少水进行比较。这是一种加密碳足迹。通过这种方法,破解 228 位 RSA 密钥所需的能量比烧开一茶匙水所需的能量还要少。相比之下,破解一个 228 位的椭圆曲线密钥需要足够的能量来煮沸地球上所有的水。对于 RSA 的这种安全级别,您需要一个 2,380 位的密钥。

对于那些不想深入挖掘 EC 内部结构的人,我建议至少阅读并遵循关于 SSH 加密的非常好的实用总结,值得花时间阅读。链接在这里:secure-secure-shell

准备复制/粘贴各种操作系统的解决方案(由 github 社区提供)在这里: Secure-Secure-Shell 的 WiKi (但我强烈建议您在去那里之前阅读 github 上的 previuos 文章)


上一个答案:

问:“公钥只有 69 字节长,而我的旧 RSA 密钥是 373 字节。那么为什么这里不再更好了?”

除了汤姆的解释“为什么密钥更短,同时至少同样安全” - 根据从这里创建 ed25519 的人的原始论文:http ://ed25519.cr.yp.to/ed25519-20110926.pdf :

除了“同样安全”之外,ed25519 的短密钥是“内部”压缩的。未压缩的 ed25519 密钥几乎要长两倍。

附言

为避免混淆或误解 ed25519 中使用的点压缩,它不是像 zip 存档中那样的常规压缩(!!!)。感谢@diagprov 帮助纠正我在评论中的回答,并提供了对点压缩的简单解释以及描述点压缩的链接

参考上述文件(第 2 页):

  • 小钥匙。公钥只消耗 32 个字节。再次包括压缩和解压缩的时间。