纸质钱包是一种过时和不安全的储存比特币的方法,在2011到2016年间很受欢迎。它的工作方式是有一个单独的私钥和比特币地址,打印在纸上。假设你找到了中本聪的钱包。然而,一些文件被撕破,特别是最后72位丢失。
发布于 2019-11-27 16:43:20
在ECC上,私钥是范围k中的值[0,q-1],其中q是由点G生成的组的顺序,q是素数,Q = kG是公钥。
解决这一问题的最著名算法是Pollard's rho算法,它在O(\sqrt{q})中渐近运行。
在您的情况下,k的一部分是已知的,除了72最不重要的位。用0 \leq k_0 < 2^{72}编写D11,然后k_1表示已知的位元,k_0表示正在寻找的未知部分。
我们有\begin{array}{rcl} Q & = & kG \\ & = & (k_12^{72} + k_0) G \\ & = & k_12^{72}G + k_0 G \end{array},所以k_0G = Q',在那里Q'= Q - k_12^{72}G是已知的。现在,不是在range [0, q-1]中查找D18,而是在range [0, 2^{72} - 1]中查找k,后者的大小要小得多。
为此,您可以查看波拉德袋鼠算法,它可以在渐近复杂度O(\sqrt{2^{72}})中搜索子集[0, 2^{72} - 1]中的离散对数,这是O(2^{36}),是可行的。
https://crypto.stackexchange.com/questions/76044
复制相似问题