16
$\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?

Improve this question
$\endgroup$
8
  • 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
    Commented May 26, 2019 at 14:56
  • $\begingroup$ Would you please tell me where or by which formula did you get 2^{80}? $\endgroup$
    – R1w
    Commented May 26, 2019 at 19:26
  • 1
    $\begingroup$ it's basically rounded from crypto.stackexchange.com/a/8692/24949 $\endgroup$
    – Z.T.
    Commented May 26, 2019 at 19:38
  • 2
    $\begingroup$ What CPU family? What clock speed? How much RAM? $\endgroup$
    – forest
    Commented May 26, 2019 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
    Commented May 27, 2019 at 8:15

1 Answer 1

Reset to default
21
$\begingroup$

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

DJB et al wrote in 2013 (see page 30) (see also: 29C3: FactHacks (EN); slide 87/112; about 10 minutes) 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 uses up a lot of power and not get noticed for a year, is another matter entirely.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So it makes Decryption-As-Service possible either for a legal issue or illegal. $\endgroup$
    – R1w
    Commented May 26, 2019 at 16:00
  • 3
    $\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.
    Commented May 26, 2019 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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