@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
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, 64 GByte.
With some other optimizations (the search space is actually 2^59 and not 2^60 + other properties of the secp256 k1 curve), with 32 GB 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 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.
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.
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, 64 GByte.
With some other optimizations (the search space is actually 2^59 and not 2^60 + other properties of the secp256 k1 curve), with 32 GB 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 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.
I do not quite understand if I interpret your answer well, and if so, not really ... So how does your output code look like that you can compile without using that amount of RAM?
Now the person who claimed the prize will make sure to swipe the bch too before revealing the private key here!