2 ms·
It's very easy to make sqrt(n) DLP solvers for known subranges. Here is a trivial one: In advance, make a table of all the pubkeys xG for secret key s = (0,2^
by nullc 2y ago
It's very easy to make sqrt(n) DLP solvers for known subranges.
Here is a trivial one:
In advance, make a table of all the pubkeys xG for secret key s = (0,2^33].
When you get a target key T, compute T - (2^33)xG for x = (0,2^33] and look up the result in the table.
When you get a hit, you've found the private key for T it's (2^33)x + s.
Of course, this is a trivialized example, many optimizations are possible and you can specialize any generic DL solver to work in a known range.
- the_clarence 2y agoBut that's not the range in question, this one has 66 bits. You're describing a meet in the middle attack but the runtime would be too high
- nullc 2y agoMy example is specifically for a 66-bit range. There are two loops in my post, one removes 2^33 multiples of 2^33, the other builds a table to check for values with a 33-bit range. My example will find a solution in a 66-bit range using only 2^34 point operations and 2^33 table lookups. Work thought it, I think it'll be more informative than me simply repeating myself further. If you're still confused, ask specific questions and I'll be glad to answer.
- the_clarence 2y agoOh right nevermind. For about 300GB of data. I would assume this is what they did them