但是，已经证明（Wiener，1990年），如果$ \ log d \ leq \ frac14 \ log N $，则私有指数$ d $可以可以从公用密钥$（N，e）$重构。
Smart，Inc.使用特殊的专用密钥，其设计如下：威纳（Wiener）推荐的最小范围，并且
由于汉明重量轻而仍然非常有效
这样的密钥是否可以安全使用？ ？
我做了一些研究，认为维纳的攻击可能是在正确的轨道上。
#1 楼
首先，您有一个错字。如果$ \ log（d）<0.25 \ log（N）$，则Wiener的攻击有效。这不是最好的攻击方法。 “ Boneh and Durfee”将结果提高到$ \ log（d）<0.292 \ log（N）$。
我不知道会有更好的结果，但这并不意味着结果
特别是，目前尚不清楚是否能帮助攻击者知道私钥的汉明权重很小。切角技术。通过已经以特定方式生成私钥来加速RSA的提议不计其数。
亚历山大·梅（Alexander May）的论文很好地概述了这一主题。该论文已有几年历史了，但是很好地显示了可能的攻击方式，更重要的是，该问题的复杂性。通过摆弄密钥。
评论
$ \ begingroup $
如果d <1/3 * N ^（1/4），维纳的攻击就起作用
$ \ endgroup $
–SecureFish
2011年3月21日在21:17
#2 楼
维纳的结果已经提高了好几倍，而且很难说出私有指数必须有多大才能保证其不会进一步发展。此外，假设$ d> n ^ {1 / 3} $，至少需要$ {1 \ over3} \ cdot log_2（n）$模乘法才能实现最稀疏的$ d $（二的幂），相比之下，说$ {7 \ over6} \ cdot log_2 （n）$用于使用滑动窗口幂运算的经典RSA。
，因此，当不使用中国余数定理时，该技术最多可以将$ 7 \ over2 $的速度提速，这小于CRT允许的系数接近4；当将该技术与CRT结合使用时，CRT的节省之一（指数大小的一半）就消失了，因此与采用CRT的传统RSA相比，提速提高了$ 7 \ over4 $。这不是一个很大的加速。如果需要这种速度折衷，则ECDSA可能是一个更好的选择。
，但这使问题没有得到解决。
#3 楼
其他答案则说明了为什么您不应该使用这样的快捷方式，以及为什么无论如何它都不会提供很大的提速。对于实际攻击，这是一个明显的攻击：蛮力。使用您提供的参数，只有$ \ binom {309} {3} = 4869634 $ d的可能值，即足够小，可以轻松检查每个值。#4 楼
如果私有指数$ d $的汉明权重很低，则很容易破坏该方案。假设$ d $的权重为$ w $，且宽度为$ m $。 @Antimony已经解释了如何在$ m \ w \ w时间中打破它。我将展示如何使用生日风格的技术更快地打破它。我的算法大约需要花费$ 2.5 \ sqrt {w} {m / 2 \ choose w / 2} $时间，这要快得多。例如，如果$ d $是汉明权重为10的1024位指数，则@Antimony的方法将执行大约$ 2 ^ {78} $个计算步骤，而我的方法将执行大约$ 2 ^ {41} $个计算步骤。
首先编写$ d = d'+ d''$，其中$ d'$的低位$ m / 2 $位全为零，$ d''$的高位$ m / 2 $位全为零。我们希望$ d'$和$ d''$都具有汉明权重$ w / 2 $（这种情况发生的可能性约为$ {w \ choose w / 2} / 2 ^ w $，这是相当大的；稍后我将描述如何删除此要求。
选择一个随机值$ x $，然后让$ y = x ^ e $。请注意，
$$ y ^ d = x。$$
随之而来的是
$$ y ^ {d'} = x / y ^ {d''}。$$
我的算法将迭代$ d'$的所有可能值，并将$ y ^ {d'} $的对应值存储在哈希表中。然后，它将遍历$ d''$的所有可能值，并在哈希表中查找$ x / y ^ {d''} $。如果它在哈希表中找到匹配项，则它同时找到了$ d $和$ d''$，从而恢复了私有指数$ d = d'+ d''$。
运行时间为$ m / 2 \选择w / 2 $步骤填充哈希表，另外$ m / 2 \\ choose w / 2 $步骤查找条目，总运行时间为$ 2 {m / 2 \ choose w / 2} $。
成功几率是多少？如果$ d $的1位中的一半落入其高$ m / 2 $位，而一半落入低$ m / 2 $位，则此操作成功。这种情况的发生概率为$ {w \选择w / 2} / 2 ^ w $，因此该算法成功恢复$ d $的概率约为$ {w \ choose w / 2} / 2 ^ w $。使用斯特林公式，成功概率约为$ 1 / \ sqrt {\ pi w / 2} $。
如果算法不成功怎么办？好吧，我们再试一次，但是用一种不同的方式将$ m $位位置分成两组。上面，我将其描述为一个拆分，一组包含高位$ m / 2 $位，而另一组包含低位$ m / 2 $位。但是，我们可以使用任何将$ m $位位置划分为两组（每组大小为$ m / 2 $）的方法来推广并应用该算法。每个这样的分区大约有$ 1 / \ sqrt {\ pi w / 2} $才可能显示$ d $，因此我们可以重复尝试许多随机分区，在经过大约$ \ sqrt {\ pi w / 2} $次试验之后，我们期望找到一个揭示$ d $的数字。因此，总运行时间为$ 2 \ sqrt {\ pi w / 2} {m / 2 \选择w / 2} \约2.5 \ sqrt {w} {m / 2 \选择w / 2} $。
评论
这是一个复杂的问题，最好将其分解。@Rook-这有点复杂，但我认为可以在这里客观地得到答案。
是的。第一个问题是大但具有较小汉明重量的私钥是否足够安全？
@SecureFish是的，idk人，也许您应该阅读教科书。另外，如果您想与我联系，也应该输入@rook，否则我不会收到您的消息。
@GregS，什么是Smart，Inc并不重要。海明码为3/309位