8
$\begingroup$

Using an Intel Core i5 CPU, how long does it take to crack RSA using a key size of 1024 bit (generated using a secure key pair generation function)?

Suppose for instance that we have thousands of zombies or a big network of computers. To calculate all the combinations or possibilities, can we distribute the process through a big network of computers?

$\endgroup$
  • 2
    $\begingroup$ I think the standard estimate is $2^{40}$ work for 512-bit moduli and $2^{80}$ work for 1024-bit. A very optimistic guesstimate would probably be "1 day" for the 512-bit modulus, so $2^{40}$ (1 trillion) days for 1024-bit moduli. Of course I didn't use actual performance numbers (so no proper answer). $\endgroup$ – SEJPM May 26 at 14:56
  • $\begingroup$ Would you please tell me where or by which formula did you get 2^{80}? $\endgroup$ – R1w May 26 at 19:26
  • 1
    $\begingroup$ it's basically rounded from crypto.stackexchange.com/a/8692/24949 $\endgroup$ – Z.T. May 26 at 19:38
  • 2
    $\begingroup$ What CPU family? What clock speed? How much RAM? $\endgroup$ – forest May 26 at 23:20
  • 1
    $\begingroup$ @R1w Sure, but precise hardware information is necessary to make accurate estimates. However you should assume that RSA 1024 can be broken with sufficient computing power (whether a huge number of consumer PCs or a specialized ASIC). $\endgroup$ – forest May 27 at 8:15
15
$\begingroup$

RSA-768 took 2000 years of 2.2Ghz single core Opteron from year 2009 [1].

DJB et al wrote in 2013 [2] that RSA-1024 would take $2^{70}$ differences with $2^{24}$ per machine per second in 2009, so 2 million years. Hardware improved since then, and GNFS can use GPUs, so maybe better, but about a million years I guess.

Absolutely the computation can be parallelized to use many devices, for example to use a botnet, which is what DJB recommends. Whether one can have a botnet with a million devices with strong CPU/GPU that use up a lot of power and not get noticed for a year, is another matter entirely.

1 - https://en.wikipedia.org/wiki/RSA_numbers#RSA-768

2 - https://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf (see page 30 or slide 87 of 112 or about 10 minutes of this video https://youtu.be/95N2KXqH5cs?t=2100)

$\endgroup$
  • $\begingroup$ So it makes Decryption-As-Service possible either for a legal issue or illegal. $\endgroup$ – R1w May 26 at 16:00
  • 2
    $\begingroup$ Yes, Nadia Heninger (co-author of that presentation I linked, cseweb.ucsd.edu/~nadiah) tried to run such a service on the public cloud. AFAIK this service doesn't exist, but anyone can create it using open source software (cado-nfs.gforge.inria.fr) and specialists can optimize the software for new hardware or to best use cloud spot instances, etc. $\endgroup$ – Z.T. May 26 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.