我知道如何计算RSA模数的相对对称强度：计算现场筛的运行时间。这就是NIST在其出版物中给出非对称算法的近似对称大小的方式：对于RSA，您可以计算字段筛的运行时间：
$$ \ exp \ left（\ left（\ sqrt [3] {\ frac { 64} {9}} + o（1）\ right）（\ ln n）^ {\ frac {1} {3}}（\ ln \ ln n）^ {\ frac {2} {3}} \ right ）$$
ECDHE等价于什么？例如。攻击给定ECC曲线的最著名算法的运行时间是多少？
RFC 4492状态：
基于用于攻击它们的最著名算法的密码系统。




对称
ECC（二进制曲线）
ECC（原始曲线）
DH / DSA / RSA



80
163
160
1024


112
224
2048


128
283
3072






521（不是错字）
15360




如何复制ECC列的编号？
编辑：一些研究，RFC现在404s中提到的论文，但在http://infoscience.epfl.ch/record/164526/files/NPDF-22.pdf上找到的副本提到：

2.6。 3。进攻。攻击EC
系统的等效DLNFS或其他次指数方法从未发布。攻击EC
的最有效方法是Pollard的可并行rho方法，预期运行时间为0.88√q组操作。

但是我仍然不知道如何复制结果：椭圆曲线具有P和Q，但是我怎么知道Q是什么，例如secp521r1？
编辑：Twitter上的Deirdre Connolly提到了一个近似值：
$ log_2（0.88 \ cdot \ sqrt {2 ^ {n}}）$
匹配RFC结果。如果她不愿意的话，会做更多的研究，并在接下来的几天内将其发布为答案。

评论

谢谢@otus。即使阅读本文，我仍然不知道如何获得NIST的结果。如果您知道我会很乐意为您提供答案！
我很确定他们只是采用了一个（或一些）数据点来找到隐藏在$ \ mathcal O（\ sqrt {n}）$复杂度后面的常数（0.88），或者他们只是分析了最佳的Pollard Rho版本，以至于难以估计为0.88。
注意：视频中的“ Q”用于表示要添加的任意第二点。通常可以是P或其倍数。
仅供参考，RFC图表中的ecc大小显示的是Koblitz曲线大小，其安全级别与主要字段曲线不同

#1 楼

椭圆曲线组的安全级别约为$ \ log_2 {0.886 \ sqrt {2 ^ n}} $。您可以使用它来近似$ n $位密钥的安全级别，例如：

$ \ log_2 {0.886 \ sqrt {2 ^ {571}}} = 285.32537860389294 $

实际计算（至少对于由质数$ p $定义的有限域上的曲线）为$ \ log_2 {\ sqrt {\ pi / 4} \ sqrt {ℓ}} $，其中$ℓ$为公共基点在曲线上的点子组的顺序（点数）。 $ p $的大小确定了$ℓ$的上限，尽管它本身并不完全是上限，但通常非常接近。因此，例如，Curve25519的$ℓ$约为$ 2 ^ {252} $，因此：

$ \ log_2 {\ sqrt {\ pi / 4} \ sqrt {2 ^ {252}} } = 125.82537860389293 $

我们基于ECC密钥大小的近似值使我们非常接近：

$ \ log_2 {0.886 \ sqrt {2 ^ {256}}} = 127.82537860389293 $

如下文所述，Koblitz曲线略有不同。

任何ECC密钥的强度都与基础曲线和域参数的强度绑定在一起，并且通常，为特定曲线生成的所有有效密钥对都应具有相同的大小/强度。有一些点是无效的，不应使用，但您的ECC实现应为您处理这些问题。安全曲线：http://safecurves.cr.yp.to/rho.html

评论

$ \ begingroup $
从等式中取出$ n $可能是一个好主意，因此最终得到的内容类似于$ \ frac {l} {2}-0.17 $。
$ \ endgroup $
– CodesInChaos
15/12/23在11:14


$ \ begingroup $
pi / 4来自哪里？ Pollard的Rho复杂度不是sqrt（pi / 2 * l）吗？
$ \ endgroup $
–user13741
15年12月23日在19:49
$ \ begingroup $
@ user13741，这是由于优化使搜索空间减少了一半。
$ \ endgroup $
–otus
15年12月24日在14:04

#2 楼

先前的答案具有估算原始场椭圆曲线安全级别的正确公式。但是，正如Richie Frame指出的那样，该表似乎只是列出了所使用的最接近的Koblitz曲线尺寸。左栏中的值。例如，使用K-571曲线，以上公式将为您提供284，而不是256。此外，使用Koblitz曲线，Pollard的rho算法可以提高（pdf）约$ \ sqrt {m} $，其中$ m $是字段的大小（表中的数字）。因此，实际上K-571的安全级别约为280位。

那为什么数字与您计算它们的方式都不匹配？

那是因为Koblitz曲线具有被选择有一个主要的$ m $来避免其他攻击。他们基本上选择了能够给出椭圆曲线的最小参数，并为其目标水平提供了足够的安全性。相比之下，左列只是与以字节表示的对称密钥相对应的常见“不错”安全级别。