@zielar: it is possible, I used the baby step giant step algorithm to retrieve the key #60 in about 80 seconds. And I have 32 GB ram.
space search for each key of the puzzle transaction:
key #1 : from 1 to 1 (2^0 -> 2^1 - 1)
key #2 : from 2 to 3 (2^1 -> 2^2 - 1)
key #3 : from 4 to 7 (2^2 -> 2^3 - 1)
key #4 : from 8 to 15 (2^3 -> 2^4 - 1)
....
key #60: from 2^59 to 2^60 - 1
Let's say for semplicity that our space search in this case is 2^60 (actually is only half, 2^59).
P is the public key, we want to find the private key k. If G is the generator of the curve, the private key k is the number :
k*G = P
baby-step-giant-step (-->
http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/):
you create two lists, the first one (the baby steps list) in a hash table stored in the Ram and the second one (the giant steps list) dynamic:
a) (
baby steps list): each baby step is equal to 1 (the distance between 2 consecutive elements is 1*G) and we store all these public keys: (0G), 1*G, 2*G, 3*G, 4*G, 5*G, ..., 2^30*G (because sqrt(2^60) = 2^30) in a hash table
b) (
giant steps list): each giant step is equal to the sqrt(space size), in our case sqrt(2^60) = 2^30, namely the distance between 2 elements is 2^30*G . We generate on fly this list:
P, P - 2^30*G, P - 2*2^30*G, P - 3*2^30*G, P - 4*2^30*G, P - 5*2^30*G, ....., P - (2^30 - 1)*2^30*G
and we check if there is a element in the giant-steps list equal to an element in the baby-steps list.
If for example P - 5*2^30*G = 1000*G, then P = 5*2^30*G + 1000*G
--> P =
(5*2^30 + 1000) * G -->
private key k = (5*2^30 + 1000)2 lists, 2^30 elements * 2^30 elements = 2^60 comparisons without doing 2^60 operations, this is the trick.
Hash table: 2^30 entries, each entry has the coordinate x of the public key (256 bit) + the number of the private key (max 32 bit). I'm using only the first 32 bits of the x instead of 256 bits (there are only few false collisions looking at the first 32 bits and I check these collisions), then I need to store (32 + 32) * 2^30 bit, 2^36 bit, 8 GByte. The hash table actually has to have the double of the number of the keys in the baby steps list (to avoid collisions between two different "x" that share the same 32 bits), so I need at least 16 GByte.
With some other optimizations (the search space is actually 2^59 and not 2^60 + other properties of the secp256k1 curve), I can run the program.
When the search space is greater than 60 bit, let's say 62 bit, I can't store all the 2^31 public keys of the baby steps list at once in the Ram, then I split 2^31 in 2 lists of 2^30 elements, A e B, then first I check the entire giant steps list against the list A, and if there is no match, I generate the list B and I generate again the giant steps list.