How it works

imagine you have:

a) a partial private key d:
f461d7473a944648de9630a2062fc29f676fab0c6e9c344a472f70bef31dca17 (you lost the last digit, 7)

b) the public key P:
x : 4461130191898d8b22c00c474a5903a679afcf7988c2db3636223ab4ce7883e2
y:  50abf843d037afdb1a40ae565c8c72b7b29740282bd335a63d369e6eeced21a2

You lost the last hex digit, 7,  16 is then the search space size.
How can you retrieve the correct value?

Option:
 
1) brute force, there are max 16 tries to do:  from f461....dca10 to f461....dca1e, for each private key you compute the public key and compare the result with P.


2) 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 (giant steps list) in a hash table stored in Ram and the second one (baby steps list) dynamic:

a) (giant steps list): each giant step is equal to the sqrt(space size), in our case sqrt(16) = 4, namely the distance between 2 elements is 4*G .  

Then we create the list:
k*G, (k+4)*G, (k+8)*G, (k+12)*G   where k is the first possible key to check (k = f461....dca10)

b) now we generate the baby-steps list (the distance beween 2 consecutive elements is 1*G) on fly, starting from

P  

and we check if it is equal to an element in the giant-steps list, if not try with

P - 1*G, P - 2*G and so on (P-3*G is the last element).

In our case, P - 3*G =  (k+4)*G

--> P = (k+7)*G  --> private key k+7


If you don't know the last 2 hex digits, the search space is 256 elements, then you need to create a list of 16 elements (baby-steps: k*G, (k+16)*G, (k+2*16)*G, ...,(k+15*16)*G) and the baby-steps list (P, P - 1*G, P - 2*G, ...., P - 15*G).

16 elements * 16 elements = 256 comparisons



A software (not mine) that works in this way: https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89