Speed Optimizations in Bitcoin Key Recovery Attacks

Fixed Point Multiplication Methods

double-and-add

在椭圆曲线中计算：$Q=kP$Q=kP比较容易想到的方法是：double-and-add方法。此方法的想法是将$k$k采用二进制表示：
     $k=k_0+2k_1+2^2k_2+\cdots+2^mk_m$k=k0​+2k1​+22k2​+⋯+2mkm​
其中的$[k_0,\cdots,k_m]\epsilon[0,1]$[k0​,⋯,km​]ϵ[0,1]，并且$m$m是$k$k的位长度，所以在Bitcoin中$m=256$m=256。
给出其算法：

如果直接计算$Q=kP$Q=kP，那我们要计算$k-1$k−1次点加运算，如果我们设运行一次点加运算的时间为：$A$A，那么总的时间是：$kA$kA。
在上面的算法中，$k_i=1$ki​=1的可能大约是$\frac{m}{2}$2m​，我们假设计算一次倍加所需的时间是：$D$D，所以总的运行时间是：$(\frac{m}{2})A+mD$(2m​)A+mD，显然要比之前的运行时间缩短了很多。

因为$P$P是固定不变的，所以我们可以通过预先计算一些依赖于$P$P的数据来加速点乘法的操作。例如我们可以预先计算：
     $2P,2^2P,\cdots,2^{m-1}P$2P,22P,⋯,2m−1P
这样的话在上述算法中$P:=2P$P:=2P就无需计算了，也就是说只剩了点加运算，我们再分析一些计算时间的话，现在只有：$(\frac{m}{2})A$(2m​)A，很明显又极大的缩短了计算时间。下面我们具体说明这种算法。

固定基窗口算法

它的主要特点是先计算预置表，再进行主程序的运算，以使得主程序不需要倍点运算。
假定$(K_{d-1},\cdots,K_1,K_0)_2^w$(Kd−1​,⋯,K1​,K0​)2w​是以$k$k的以$2^w$2w为基的表达式，其中$d=[\frac{m}{w}]$d=[wm​]，令$Q_j=\sum_{i:K_i=j}2^{wi}P$Qj​=∑i:Ki​=j​2wiP，对于$1\leq j\leq2^w-1$1≤j≤2w−1有：
     $kP=\sum_{i=0}^{d-1}K_i2^{wi}P=\sum_{j=1}^{2^w-1}(j\sum_{i:K_i=j}2^{wi}P)=\sum_{j=1}^{2^w-1}jQ_j=Q_{2^w-1}+(Q_{2^w-1}+Q_{2^w-2})+\cdots+(Q_{2^w-1}+Q_{2^w-2}+\cdots+Q_1)$kP=∑i=0d−1​Ki​2wiP=∑j=12w−1​(j∑i:Ki​=j​2wiP)=∑j=12w−1​jQj​=Q2w−1​+(Q2w−1​+Q2w−2​)+⋯+(Q2w−1​+Q2w−2​+⋯+Q1​)
在计算$kP$kP的过程中，仅需计算$Q_j$Qj​，然后通过$Q_j$Qj​相加即可得出$kP$kP，而$Q_j$Qj​是预置表中的点，且其值为已知，因此通过查询预置表并结合点加运算就可以得到$kP$kP，从而省略了倍点运算，在忽略预置表的计算时间的情况下，我们可以分析其运行时间，3.1步点加需要的运行时间：$(d-1)A$(d−1)A，3.2步点加所需要的运行时间：$(2^w-1-1)A$(2w−1−1)A，所以中总的运行时间为：$(2^w+d-3)A$(2w+d−3)A

作者通过查阅之前的类似算法发现，这些算法对内存的消耗十分友好，但是作者要追求的是缩短运行时间，耗费多点内存无可厚非，所以作者从这个方向出发提出了一种新的计算方法，此方法将会占用更多的内存资源，也就是在预计算中消耗的。

新方法

作者提出$P_j=jP$Pj​=jP，在这里$1\leq j\leq2^w-1$1≤j≤2w−1，对于每一个$P_j$Pj​计算$P_{i,j}=2^{wi}Pj$Pi,j​=2wiPj，整体的算法和固定窗口基算法一样，作者只是将其中一大部分提前计算了出来，虽然会占用较大的内存，但是会极大的提升计算速度。

我们可以发现如果忽略预计算的时间，则需要运行的时间大概是$(d-1)A$(d−1)A，与前面固定基窗口算法相比，可以看出明显提升了计算速度。

下面给出在不同的窗口宽度w下的测试结果：

我们可以发现在$w=20$w=20的情况下效果最好！