I'm thinking about doing this as a project, but I'm not sure how I'm supposed to proceed.
So I have an 128-bit ECDSA, which would provide about 128 bits of security (if we do not use special methods like the baby-step giant-step algorithm or Pollard Rho's algorithm). I generate a list of 2^64 public keys, and I want to find the private keys to any one of them.
So essentially this is a multi-target attack on ECDSA private keys. With 2^64 targets (public keys), I would require 2^128/2^64=2^64 attempts on average to find a private key to any one of these targets.
I have a few questions:
(1) How long would it take for a computer to perform 2^64 ECDSA operations? Is 2^64 within the realm of possibility using commonly-available GPUs?
(2) I need to generate a list of 2^64 public keys (targets). Then I need to create a database for these keys, and index them (based on their x coordinate number size, in order to perform a structured search/lookup). Therefore, the size of this database would be bordering on several exabytes, which is completely infeasible using commonly-available resources. Is there any way to reduce the size of this database?