I've watched a lot of videos on Shor's Algorithm and Quantum Computers. Most of these videos say these two things undermine RSA via fast-factoring, but they never really explain how fast-factoring is used to these break things; just very hand-wavy statements.


  • I get that with fast factoring, you could(?) reconstruct the private key from a public key. But wouldn't you still need the username/password/server details? I've ssh'd into servers for work and I still have to provide credentials on top of the ssh keys. Various commands on the server are also password protected, so fast-factoring doesn't seem all that dangerous unless I'm missing something here.
  • I get that MITM can use fast-factoring to decrypt the traffic (via the trick above) allowing you to modify the traffic then re-encrypt.

I guess I have not seen/read a complete start-to-finish example story of how fast-factoring would actually undermine the internet.

  • Consider your second bullet point about MITM'ing the TLS connection between a client and a server. Alice logs into her online banking web site. She sends her credentials through the TLS connection, but Mallory MITM's the connection using fast factoring. Now, Mallory has Alice's credentials, and Mallory can login to Alice's online banking, and withdraw all of Alice's money!
    – mti2935
    Commented Nov 29, 2023 at 12:21
  • @mti2935 - understood, what about the first point? creating the private key from public; that seems insufficient to me.
    – Sam Z
    Commented Nov 30, 2023 at 11:49
  • 1
    Yes. With SSH, it's quite common for admins to login to an SSH server using public key authentication. For this, the admin sends his public key to the server, and proves that he/she is in possession of the corresponding private key. If the public key is in the server's list of authenticated public keys, then the admin is authenticated. Using fast factoring, an attacker could copy the admin's public key, then solve for the private key, then use this to impersonate the admin, and gain access to the server.
    – mti2935
    Commented Nov 30, 2023 at 16:03
  • Even if the server uses password authentication instead of (or in addition to) public key authentication, fast factoring can be used to defeat this as well. An attacker who is positioned between the client and the server (such as an ISP or a rogue wifi hotspot operator) can copy the server's public key, then use fast factoring to solve for the server's private key, Then, the attacker can impersonate the server, and use the fake server to capture the admin's login credentials (similar to my first comment above).
    – mti2935
    Commented Nov 30, 2023 at 16:06
  • Here's another scenario to consider: An attacker who has figured out how to do fast-factoring could factor a CA's public key to get the corresponding private key. Then, the attacker could use this to impersonate the CA, and sign certificates for any site. These certificates would appear as if they were signed by the CA, and would be trusted to any browser that trusts the CA.
    – mti2935
    Commented Nov 30, 2023 at 21:08


You must log in to answer this question.

Browse other questions tagged .