我们应该信任NIST推荐的ECC参数吗？

#1 楼

编辑：我做了一些测试，发现有些奇怪。参见结尾。


初始答案：

至少Koblitz曲线（在NIST术语中为K-163，K-233 ...）不能具有因为整个过程非常透明，所以我们专门对它们进行了“烹饪”：


以二进制字段$ GF（2 ^ m）$开始。对于每个m，只有一个这样的字段（您可以有几种表示形式，但是它们都是同构的。）
将自己限制为m的质数，以免陷入子字段中而导致弱点。
考虑一下曲线$ Y ^ 2 + XY = X ^ 3 + aX ^ 2 + b $其中$ b \ ne 0 $;这是二进制字段中非超奇异曲线的正常形式。
您只需要$ a = a ^ 2 $和$ b = b ^ 2 $的曲线，这样您就可以利用Frobenius同构来加快计算速度（基本上，您只需简单地对两个坐标进行平方运算就可以替换双点，这非常快）。当$ a = 1 $时，必须是2的倍数。 p $（取决于$ a = 1 $还是$ 0 $）。对于介于“有趣范围”（例如160到768）中的$ m $，您不会找到很多合适的曲线（我不记得确切的计数，但是它类似于6或7条曲线）。 NIST只是简单地将其中的5个与$ m $值相对应，这些值最接近（但不低于）它们的“安全级别”（80、112、128、192和256位“等效强度”）。这里没有“烹饪”的空间。当然，其他人则认为Koblitz曲线具有一些特殊的结构，可以利用它们来进行更快的攻击。而且有两种方式是正确的：


更快的计算意味着更快的机械攻击；
可以解决离散对数“模制Frobenius内同态”的问题，这意味着K-233的强度大约等于225位的曲线（因为233是8位数字）。

我仍然认为这样曲线是认真进行密码工作的合理候选者。它们已经“野外生存”了至少15年，而且仍然毫发无损，就这些事情而言，这还不错。列举$ GF（2 ^ m）$中$ m $的所有Koblitz曲线，范围从3到1200。对于每个$ m $，有两个曲线要测试，$ a = 0 $和$ a = 1 $。如果曲线的阶次等于$ 4p $（对于$ a = 0 $）或$ 2p $（对于$ a = 1 $），且其质数为$ p $，则认为该曲线是“适当的”（这是因为曲线始终是$ GF（2）$中同一条曲线的扩展，因此曲线顺序必定是$ GF（2）$中曲线的倍数，取决于$ a $）为4或2。对于$ m $在160到768之间的“有趣范围”，有14条适当的曲线：


$ m = 163 $，$ a = 1 $
$ m = 233 $，$ a = 0 $
$ m = 239 $，$ a = 0 $
$ m = 277 $，$ a = 0 $
$ m = 283 $，$ a = 0 $
$ m = 283 $，$ a = 1 $
$ m = 311 $，$ a = 1 $
$ m = 331 $，$ a = 1 $
$ m = 347 $，$ a = 1 $
$ m = 349 $，$ a = 0 $
$ m = 359 $，$ a = 1 $
$ m = 409 $，$ a = 0 $
$ m = 571 $，$ a = 0 $
$ m = 701 $，$ a = 1 $

NIST的目标是它们的五个“安全级别”分别为80、112、128、192和256位，并且曲线只有在其大小至少为该级别的两倍时才会与该级别匹配。因此，每个级别的标准曲线应该是最小的曲线，该曲线对于该级别足够大。这应该分别在大小为163、233、277、409和571位的字段中产生Koblitz曲线。

奇怪的是，这与NIST的选择匹配，除了“ 128位”级别外，在该级别中，他们选择$ m = 283 $而不是$ m = 277 $。我不知道原因。对于这两个字段大小，最小的可能约简多项式是五项式（$ X ^ {277} + X ^ {12} + X ^ {6} + X ^ {3} + 1 $ for $ m = 277 $，$ X ^ {283} + X ^ {12} + X ^ {7} + X ^ {5} + 1 $ for $ m = 283 $），因此两个字段都不具有计算优势，而另一个字段使用多项式基，则277位字段要短一些，因此要快一些）。如果使用普通基数，则277位字段实际上更有效，因为它接受“ 4类”高斯普通基，而283位字段是“ 6类”（较小的类型可提高性能）。所有合适的Koblitz曲线的列表都很容易重建，事实上，NIST / NSA确实做到了（例如，从NSA雇用的JA Solinas看到这篇文章-搜索“ 277”）。

为什么它们选择283位字段对我来说是个神秘事物。我仍然认为这不太可能构成“烹饪”；仅当NIST（或NSA）知道如何在283位字段而不是277位字段中打破Koblitz曲线时，这才是后门程序，这不仅需要假设“未发表的大密码分析进展”，而且还要求认为新颖的突破技术很怪异。

#2 楼

FIPS 186-3本身至少部分回答了您的问题……

附录A描述了如何从种子开始并使用涉及SHA-1的迭代过程，直到找到有效的椭圆曲线。
因此，相信NSA会煮熟这些常数，相信以下两点之一：要么可以反转SHA-1，要么必须有足够比例的曲线满足其隐藏条件，才能通过蛮力搜索找到合适的SEED值。 ，“什么也不想干”的构造从简单的东西开始，例如小整数的$ sin $（对于MD5）或$ sqrt $（对于SHA-1）。据我所知（我错了吗？），NIST曲线的SEED值不太容易描述，这本身可疑。获得FIPS认证，允许其被美国政府机构购买并用于保护机密数据。他们有信心其他人不会很快发现漏洞。 br />
这就是...

来自最新披露的大量证据表明，NSA知道与SSL / TLS有关的密码学知识。也许这意味着ECDHE，也许不是。 （哎呀，也许这只是意味着某些通用的实现。）但是，鉴于我们有Dan Bernstein（Curve25519）之类的替代产品，即使您想使用NIST曲线也没有令人信服的理由忽略Schneier的直觉，完全避免ECC。

[更新]

Bernstein / Lange的演讲说NIST椭圆曲线是由“ NSA的Jerry Solinas”创建的。我在一读时就错过了。

我已将此问题发送到Perry Metzger的密码学列表：

http://www.metzdowd.com/pipermail/cryptography/2013 -September / 017446.html

也许有人可以与Solinas先生取得联系，并问他如何选择种子价值以及为什么。即使没有人相信它，也可以从源头上听到答案。

[更新2]

另请参阅http://safecurves.cr .yp.to / rigid.html

评论

---

$ \ begingroup $
“或者足够多的曲线必须满足其隐藏条件，才能通过蛮力搜索找到合适的SEED值。”如果使用此方法创建弱化的曲线，我不会感到惊讶。
$ \ endgroup $
– Richie车架
2013年9月9日5:48

---

$ \ begingroup $
据我了解，ECDHE并未在TLS中大量部署，因此不会导致大量数据被拦截。詹姆斯·班福德（James Bamford）认为，“巨大的突破”肯定不是布莱夫代尔所必需的。
$ \ endgroup $
– imichaelmiers
2013年9月11日下午5:29

---

$ \ begingroup $
@imichaelmiers：ECDHE是当前OpenSSL的默认值，这意味着它是所有现代Linux Web服务器的默认值（在浏览器允许的情况下）。 （转到Chrome中的self-evident.org，然后单击锁定图标。我正在使用该服务器的默认设置。）我不了解当前的IIS和IE。我提出了一个问题，但到目前为止还没有答案。我认为“突破”是EC知识（可能只是关于NIST曲线）的结合，并且说服所有人开始转向ECC。但是那时我只是个曲柄...
$ \ endgroup $
– Nemo
2013年9月11日15:32

---

$ \ begingroup $
我删除了有关杰里·索利纳斯（Jerry Solinas）的评论，该评论声称种子是由HSM生成的，因为我找不到它了（不再吗？），所以我将其删除。没有可用的资源，对不起。请注意，即使不是不可能，也很难证明是否使用了HSM。
$ \ endgroup $
–马腾·博德威斯♦
17年1月3日，18：22

---

#3 楼

如果NSA知道足够大的椭圆曲线的弱曲线类别，那么他们就有可能选择弱曲线并对其进行标准化。

据我所知，没有任何暗示足以暗示椭圆曲线

关于选择曲线：如果NIST使用“明显”的字符串作为种子，那会更好。 “ P-256编号1的种子”，“ P-256编号2的种子”等，递增计数器直到找到一个好（根据指定的标准）。 （我们知道NSA和NIST从（例如）SHA-1中的常量知道并使用了“显而易见的”字符串。）

我们是否应该以他们没有像这样做为事实呢？他们知道一大类弱曲线吗？当一个诚实的人生成曲线时，选择随机种子与“显而易见的”字符串一样好。诚实的人没有预料到当前的妄想症水平，因此没有选择“显而易见的”字符串，而是产生了一些随机性，这似乎是合理的。因此，由于更简单的解释（这是一个错误），因此这不能证明NSA知道大量的弱椭圆曲线。我们现在已有13年以上的经验，这些泄漏带来了不确定性。 Bernstein-Lange幻灯片表明，NIST曲线不是最佳选择（曲线存在于较容易正确且安全地实现较快算法的位置）。我们现在就应该毫不犹豫地做出更好的选择。

#4 楼

这个侦探卫星旁边的公告机构“无所不能”（例如NROL-39）。答案为“否”的原因得到了分类。