请注意，必须在$ [1，q-1] $范围内统一生成$ k $（其中$ q $是子组顺序）。关于$ k $的任何信息，即使是
部分信息（例如：$ 1 $和$ 2 ^ {160} -q $之间的值，
可能性也比$ 2 ^ {160} -q $和$ q $），可以被攻击者利用。 Vaudenay（PS）的“标准椭圆曲线认证方案”，其中提到Bleichenbacher发现了这次攻击，并在与作者的私人交流中提到了该攻击。给出了偏差的近似方程，并说
Bleichenbacher实际使用它是为了更近似地估计密钥，并更精确地带有签名。 />
现在我的问题是：如何在更详细的描述中进行这种攻击？或用不同的方式表达：如何利用这种微小的偏见来恢复密钥，以及为此需要多少个签名（即oracle查询）以及大概的计算工作量（如果不可忽略的话）？
本文的相关部分是（为了您方便起见）：位伪随机数以$ q $为模减少。 Bleichenbacher
观察到在$ [0，2 ^ {160}-q] $范围内$ k $的概率是其他概率的两倍。这会导致偏差
$$ E \ left（e ^ {\ frac {2i \ pi k} q} \ right）\ approx \ frac {q
e ^ {i \ pi \ frac {N-1} q}} {\ pi N} \ times \ sin \ left（\ frac {\ pi N} q \ right）$$
其中$ N = 2 ^ {160} $。由于$ q \ approx N $，这可能很大，具体取决于
$ \ frac {\ pi N} q $角度。 Bleichenbacher实际使用它是为了
通过签名越来越精确地估计密钥。
#1 楼
Nguyen和Shparlinski在具有部分已知随机数的椭圆曲线数字签名算法的不安全性中详述了该方法。我将在很大程度上遵循该论文中的标记。其想法是将对私钥的确定从多个ECDSA签名中的有偏$ k $随机数转换为隐藏数问题（HNP）的实例，然后求解HNP作为最接近向量问题的约简。
因此，您收集了很多签名并从中构造出一个格，并使用LLL或BKZ缩小了该格，然后可以从精简基向量中提取私钥。
需要估算的计算量
我在一个手工制作的LLL Python实现中进行了测试（它是如此之慢，它肯定必须构成性能的上限...）一个具有2GB RAM的Ubuntu 16.04 VM，我可以运行以下示例：
96位偏差，5个签名：（失败）31秒
64位偏差， 10个签名：（成功）4分钟
32位偏差，12个签名：（成功）12分钟
16位偏差，17个签名：（成功）49分钟
8位偏差，19个签名：（失败）79分钟
8位偏差，（21个签名）（成功）244分钟
8位偏差，20个签名：（成功）177分钟
>我停在那里。 Nguyen和Shparlinski显然能够仅用3个具有100个签名的偏差来恢复密钥，并认为仅知道2位就可以进行恢复。
更多问题的详细信息和设置
因此，假设您知道$ k $的低$ \ ell $位。 （本文介绍了一种恢复这些位的方法。）然后，您可以将$ k $编写为
$$ k = a + 2 ^ \ ell b $$
换句话说，您在[0，2 ^ \ ell -1] $中知道$ a \。为简单起见，令$ a = 0 $。然后ECDSA签名$（r，s）$中$ s $的等式变为
$$ s =（h + rx）\ cdot（2 ^ \ ell b）^ {-1} $$
其中$ h $是您的散列消息，$ x $是您的私钥，所有内容都以$ q $为模，这是基点的顺序。将其重写为
$$ xr \ cdot（2 ^ \ ell s）^ {-1} = -h \ cdot（2 ^ \ ell s）^ {-1} + b $$
定义$ t \ equiv r \ cdot（2 ^ \ ell s）^ {-1} $和$ u \ equiv -h \ cdot（2 ^ \ ell s）^ {-1} $并且您有
$$ xt = u + b $$
记住$ 0 \ lt b \ lt q / 2 ^ \ ell $，您有
$$ xt-u \ lt q / 2 ^ \ ell $$
所以这基本上是HNP。 $ b $比$ x $，$ t $和$ u $小一个因数$ 1/2 ^ \ ell $，因此可以近似得出以下等式：
$$ xt-u \ approx 0 \ longrightarrow xt-u-jq \ approx 0 $$
，因为所有内容均为mod $ q $。因此，首先收集$ n $个签名，为您提供$ t_i $，$ u_i $和$ j_i $的几个元组，然后您可以根据基本向量构造一个矩阵： pmatrix}
q＆0＆0＆\ cdots＆0 \\
0＆q＆0＆\ cdots＆0 \\
\ vdots＆\ vdots＆\ vdots＆\ ddots＆ \ vdots \\
0＆0＆0＆\ cdots＆q \\
t_0＆t_1＆t_2＆\ cdots＆t_n \\
\ end {pmatrix}
（前$ n $行包含全零和一个$ q $，每个未知$ j_i $ 。）这是一个$（n + 2）\ times n $矩阵。现在让$ T \ equiv（t_0，t_1，\ cdots，t_n）$和$ U \ equiv（u_0，u_1，\ cdots，u_n）$。那么感兴趣的简短向量$ X $将类似于
$$ U-xT + \ text {（其他内容）} $$
修改矩阵，使其包含“前哨值” $ s_T $和$ s_U $，以便您可以标识$ X $；如果您看到以$ s_T $作为最后一个时隙的缩减向量$ T'$，则很可能会看到倒数第二个包含$ -x \ cdot s_U $的条目，您可以从中恢复$ x $。免责声明：我首先在密码迷问题中看到了这个窍门，这使事情比仅仅猜测容易得多。修改后的矩阵如下：
$$ \ begin {pmatrix}
q＆0＆0＆\ cdots＆0＆0＆0 \\
0＆q＆0＆\ cdots＆0＆0＆0 \\
\ vdots＆\ vdots＆\ vdots＆\ ddots＆\ vdots＆0＆0 \\
t_0＆t_1＆t_2＆\ cdots＆t_n＆s_T＆0 \\
u_0＆u_1＆u_2＆\ cdots＆u_n＆0＆s_U \\
\ end {pmatrix}
$$
现在您可以使用从NTL或fplll进行LLL，找到前哨值，然后提取$ x $。
评论
如果您还想知道如何找到近似方程，我已经在Math.SE上发布了相应的问题。最近的两篇论文对这种攻击进行了更详细的描述：Mulder等。和Aranha等人。