Re:We Cracked a 512-Bit DKIM Key for Less Than $8 in the Cloud
by DarkmSparks on Wednesday January 08, 2025 @07:51PM
(#42640355)
Pretty sure the search cost of GNFS is (bits)^2, the search cost of brute force is 2^(bits), if it was 2^(bits) GNFS would be no better than brute force.
->but only on the order of e^(cbrt(512 * 64/9))
e^(log(n)) = n
search_space(n: number_of_bits) = 2^n * k
so search_space(1024)/search_space(512)=2^512, not 2^2.
Asymptotics in GNFS are better[0], but only on the order of e^(cbrt(512 * 64/9)) times more work, not 2^2.
This would give an approximation of math.exp(math.cbrt(512 * 64/9))*$8 = $40 million for 1024 bits.
[0] https://en.wikipedia.org/wiki/General_number_field_sieve