I do not want to disclose too much,
but imagine the whole search space as a two dimensional space.
Instead of testing every single point of the search space, you just have to define a pivot point (and its modular inverse).
Then you move from two points (one random point and one private key point) in gradients to one of the pivot points.
All you have to do is, wait until the lines cross! Then you can use simple linear algera to recover the private key.
Let's summarize what's public about this approach:
1. The explanation above.
2. We know that Baby-step giant-step method is used, witch is described here:
Q is public key, n is order of G, set m = sqrt(n)
Baby-step (i) Giant-step (j) is then to find a collision:
i*G = Q − jm*G
or, in other words, find the sum of two points, i*G + jm*G, that collide with the public key point Q that you're trying to solve. The private key will be i + jm (mod n).
3. Evil-Knievel is gathering massive number of known private/public keypairs, with 32 least significant bits of the x coordinate are matching predefined rendezvous-points. For instance, let's say if one of his predefined 32 bits are 0x
e8c4cd13, and attacked public key with matching bits is:
public 04a8177aa6808d93b480f4627faff680632f1a90a017562a6f765182f6e8c4cd13ec108158c14b43ffca30c0d400c91c652eab7f659470f1f29fd3ff46a888170e
secret ?
and, for instance, 10 gathered public keys with known private keys are (can have thousands, or millions of them):
public 04d75aaf9cfef2f8322a20b72333693253d241d8a46169b8e0e5521f85e8c4cd133f41d60134196b58e6420d6e89f1bd7077113b9a6d040c03ea3ffb418c430ad0
secret 378c918ea10ce56c0b9a4a63f92d62c65b8a24e03934bfb3a34589811ccf56ec
public 0452fc595fcfc00c83a7931bf1f2aa1e354957d7e2e49365c1caecdfede8c4cd133143ce2f82a69e1428dc5a586173a66ada8698103d2c76a2a5fb224bf46818ee
secret b0233294c24b09b448348afb589b484010d5273f200eec231cbd818e7aae0280
public 0448389e36eefae47d05f18cd899ebe40f731676c2e6213d7588171c79e8c4cd13178291bdbc3cf088b853a7fd25b89a6ec321659f189f96646ef783e1e0baebeb
secret 6983dbd427787f8622c0ab0a18fd19c459a9fd8e78ea6512187750a2cdb60673
public 045bffe58a37b10ccd6b0c959809780647a941815aa6c673e294499e28e8c4cd135eafe089336ef75141a2c88f21f4b7a2b11e2a92794206d1820f81ef5584b1df
secret db47a70e12f4eaae590e8da6c3568602e4320bec60ea3812366617f96c950945
public 04a97656f1865c8dc4f969bc3480360eec8123d1fc2cefe67bb85ca97ee8c4cd139bb1d221cd90ea60034748fc0b87e8155858d1dd5c3b4e3c0320f15aa8412fc5
secret d69d3f4fa3b3199b084d0c4bea9b9a4c061e0296b5d4d7ea88c94ec7013ffc86
public 049054c05d5b9d5541b548f6bb26728b8f08b7b712e64b36f2c3b3acc0e8c4cd13da5faf23df4ce55a60bc9b6b55795e121c51b3220737c57ec97f61694ced30ac
secret 5d822497642b85eb1b76351ada43ea812963c5b9c45421cffe645df0bda3c81c
public 043169d25764343f122b9bee026f58ad654c73bff74f6b54a60c55a20ae8c4cd1339cebff780ba3654d1e9637d9a44d1faa1aa68a0468547ccd480483d1d48f1da
secret ccbf26b0d68ae6ca372aed9edd38f17d4fe886abb506b866a7b427c7506b6beb
public 04a3bccc214b53fec3a2aa1ec8d7b0e61d0033856c4f1520a06baa3dffe8c4cd137315b361e64d41f56e40c5055cfde75108ceb0c9d3bffd2b4085e5e4d3aec49f
secret 8bd7bdf8db2cbb9989474f8017ce33ff5ea27a56a7ad38fce3b24b247ea96f63
public 04f1a597f7acf407b5dfc31af461bfc0cce2edaced7ad9c01d36a5db7be8c4cd13ff1d9d7f9b6f9bea7608d27f634d1140dac078538df188b2740275111e7678c4
secret fd440695cf90e0879136bd47461f597c1bc87a902cb4ededc8f0b53dd2eacffa
public 04196f0100280e4fb61a97c6f382e049941b3ac2064255bd9a57674752e8c4cd131546ff51bcd6fcb6b422b11f002d155111a35f64e5c68d3bc9733175cefe5e51
secret a384d6afe2844ac705f8f7735b92293d887ce3d60873bc51651a1be5f467e71b
Is there any cryptographer here to whom all this makes sense? How can Baby-step giant-step be combined with these common 32 bits and the that graphical explanation?
