A paper wallet is the name given to an obsolete and unsafe method of storing bitcoin which was popular between 2011 and 2016. It works by having a single private key and bitcoin address, being printed out onto paper. Assume you have found the paper wallet of Satoshi Nakamoto. However, some of the paper is torn, specifically the last 72 bits are missing.

  1. Is there any better solution than brute force?
  2. If you get access to his wallet, how will you transfer money from his wallet to yours without raising suspicion?
  • $\begingroup$ Is this a homework exercise? What have you tried and where did you get stuck? $\endgroup$ – Squeamish Ossifrage Nov 27 '19 at 15:00
  • $\begingroup$ Actually I don't know any other way to solve this than brute force $\endgroup$ – Chetan Warke Nov 27 '19 at 15:25
  • $\begingroup$ Hint: look up Pollard's kangaroo algorithm. $\endgroup$ – Squeamish Ossifrage Nov 27 '19 at 16:41

On ECC, the private key is a value $k$ in the range $[0,q-1]$ where $q$ is the order of the group generated by a point $G$, with $q$ a prime number, and $Q = kG$ is the public key.

The best known algorithm to solve this is Pollard's rho algorithm which runs asymptotically in $O(\sqrt{q})$.

In your situation, part of $k$ is known, except the $72$ least significant bits. Writing $k = k_12^{72} + k0$ with $0 \leq k_0 < 2^{72}$, then $k_1$ represent the known bits and $k_0$ the unknown part you are looking for.

We have \begin{array}{rcl} Q & = & kG \\ & = & (k_12^{72} + k_0) G \\ & = & k_12^{72}G + k_0 G \end{array} So $k_0G = Q'$ where $Q'= Q - k_12^{72}G$ is known. Now, instead of looking for $k$ in the range $[0, q-1]$, you are looking for $k$ in the range $[0, 2^{72} - 1]$ which has a much much smaller size.

For that, you can look at Pollard's kangaroo algorithm which can search for the discrete logarithm in the subset $[0, 2^{72} - 1]$ in an asymptotically complexity $O(\sqrt{2^{72}})$ which is $O(2^{36})$ and is feasible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.