1
$\begingroup$

I know that RSA is known to be secure in the current landscape of computing, and I know that RSA is known to be broken in the world of quantum computing and cryptography.

I have two questions, can someone tell me why super computer's with this magnitude of processing power are unable to break RSA:

Six Clicks: The six fastest computers in the world

Please be specific with maths and all.

Additionally, can someone explain why RSA is broken by quantum computers mathematically and how lattice cryptography is resistant to them?

$\endgroup$
  • 2
    $\begingroup$ This question seems a combination of 3 separate parts: 1. why is RSA not broken by supercomputers, 2. why is it broken with (currently unavailable) quantum computers and 3. how does PQC work. $\endgroup$ – Maarten Bodewes May 28 '19 at 21:16
  • $\begingroup$ Yes it kinda is. They all stem from my research into supercomputers and cryptography. $\endgroup$ – leaustinwile May 28 '19 at 22:14
  • 3
    $\begingroup$ No offence but sounds like "do my research for me" kind of question. All three topics have been covered here numerous times, have your searched? $\endgroup$ – tum_ May 28 '19 at 23:07
  • $\begingroup$ I think there are already existing answers on this site which answer each one of your questions. Factoring is hard, and even the most powerful supercomputer can only run the GNFS algorithm, whereas a sufficiently complete quantum computer can run the far more effective Shor's algorithm. As for lattice crypto and other PQC, you might want to look into what the BQP complexity class is. $\endgroup$ – forest May 29 '19 at 4:10
  • $\begingroup$ The point is that, with the current algorithms, no matter the type of "classic" computer one uses (mobile phone, laptop, supercomputer, etc), the number of operations required to break RSA is super-polynomial in the security parameter. However, with quantum computer, we know polynomial times to break it. $\endgroup$ – Hilder Vitor Lima Pereira May 29 '19 at 6:55