@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, 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?