By

Navigating The Post-Quantum Future

Hero Image Attribution: Shanghai University, CC BY-SA 4.0 <https://creativecommons.org/licenses/by-sa/4.0>, via Wikimedia Commons

Shanghai University Cracks RSA Encryption, Paving the Way for
Post-Quantum Cryptography

 

Researchers at Shanghai University recently broke RSA encryption using a D-Wave quantum computer with a 5,760-qubit capacity. This technological breakthrough raises many questions about the future of encryption and security.

Quantum computing is a revolutionary form of computation that leverages the principles of quantum mechanics, the fundamental theory that governs the behavior of particles at atomic and subatomic levels. Unlike classical computers, which process information in bits (0 or 1), quantum computers use qubits that can exist in multiple states simultaneously because of phenomena like superposition and entanglement.

With their advanced technology, quantum computers can solve complex problems much faster than classical computers by performing many calculations in parallel. For example, tasks like factoring large numbers—crucial for current encryption systems—can be achieved exponentially faster, posing a threat to conventional cryptography. Quantum computing has the potential to outperform the most powerful classical systems, bringing immense benefits but also significant risks, especially to cybersecurity.

Quantum computing poses a significant threat to classical cryptography, particularly to widely used public-key encryption systems like RSA and Elliptic Curve Cryptography (ECC). The researchers mentioned above used quantum computers, and Shor’s Algorithm, to attack and break RSA encryption protocols. Here’s how they were able to disrupt these systems:

 

Shor’s Algorithm: Breaking RSA and ECC
  • RSA encryption relies on the difficulty of factoring large prime numbers. ECC is based on the hardness of solving discrete logarithms over elliptical curves.
  • Classical computers would take thousands of years to solve these problems, making them secure today. Shor’s algorithm, however, allows a sufficiently advanced quantum computer to solve this encryption exponentially faster.
  • This method of computing renders RSA and ECC encryption keys obsolete, exposing encrypted communications, certificates, and signatures to attack.

 

The experiment at Shanghai University is astounding, but the cybersecurity industry has plenty of time to prepare and respond to this news. First, the researchers were only able to crack a 50-bit RSA key. Typically the default required by organizations that follow standards such as NIST (National Institute and Standards for Technology)-800-53 Rev. 5 or FIPS (Federal Information Processing Standards) 186-4, Digital Signature Standard (DSS) typically require a 1024- or 2048-bit length for hash length. To break standard RSA or ECC public keys would require significant advancements in quantum computing, including a substantial increase in qubit capabilities and the development of better algorithms to process the data.

Navigating The Post-Quantum Future

This breakthrough suggests that the approach of the post-quantum world, or “Y2Q”—a nod to the Y2K bug at the turn of the century—may be nearer than previously projected. Experts originally estimated that Y2Q would not occur until well into the 2030s, as suggested by Ars Technica in January 2030. The article states that “those resources are about 20 million qubits and about eight hours of them running in superposition” from a research paper in 2021. The researchers in China, however, were able to conduct a proof of concept with processing power several levels of magnitude smaller. This breakthrough could bring about the advent of post-quantum computing much sooner. Our recommendation is that cybersecurity leaders begin to consider how to implement quantum computing as early as 2026. This consideration will lead to a much sooner date on which we need to implement post-quantum computing.
It is increasingly clear that over the next few years classical computations will not meet our requirements for protecting our most sensitive data, access, or identities. The question on the minds of many security researchers, leaders, and practitioners is how to implement a solution.

Post-Quantum Encryption (PQE) refers to a new class of cryptographic algorithms designed to be resistant to attacks from both classical and quantum computers. Unlike traditional encryption methods, PQE leverages complex mathematical problems that even the most powerful quantum computers cannot solve efficiently.
In 2016, NIST submitted a call to create a post-quantum encryption method to develop the most secure and fastest algorithms. There were several new submissions and NIST began the process of conducting evaluations in 2022. By August 2024, NIST released the first of three finalized standards that are:

One of the favorites in the industry is KYBER-Dilithium PQE, a name which references two of the most popular sci-fi franchises ever. KYBER-Dilithium PQE uses encryption similar to the asymmetric encryption standards that we practice today. Instead of PKE (Public Key Encryption), however, it uses KEM (Key Encapsulation Mechanism). Instead of using a private key to decrypt a message, KEM uses a private key to generate a shared secret, then decrypts the message. This additional step adds another layer of security, which makes it more difficult for quantum computers to break the encryption. Compared to traditional methods, KEM-based encryption takes advantage of harder mathematical problems, such as lattice-based cryptography and stateless hashing. These complex equations are more resistant to quantum attacks, increasing the necessary computational power for a quantum computer to break the encryption. (For more details, refer to the FIPS standards linked above.)

Highlight: Cryptography 101 with Alfred Menezes — Kyber & Dilithium

—Alfred Menezes, mathematician & cryptographer, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo (Ontario, Canada). 

For a more in-depth exploration of KYBER-Dilithium PQE, check out this series of lectures from Alfred Menezes via YouTube.

Steps to Evaluate and Implement PQE (Post-Quantum Encryption)

Implementing PQE can seem daunting or difficult, but it really isn’t much different than when we switched from TLS 1.1 to 1.2 or 1.3. Many known certificate authorities or providers already have PQC labs or guides that support the transition. Prior to conducting technology swaps, an organization will need to establish some goals and evaluations to determine their readiness. 

Step 1: Assess Your Current Cryptographic Landscape

  • Inventory cryptographic assets: Identify systems, protocols, and devices relying on public-key encryption (e.g., TLS, VPNs, PKI, digital signatures).
  • Evaluate data at risk: Prioritize protecting long-term sensitive data (e.g., financial records, personal information) from “harvest now, decrypt later” threats.
  • Review cryptographic dependencies: Check for third-party software, certificates, and libraries using vulnerable encryption algorithms (RSA, ECC).

Step 2: Understand Emerging Standards and Guidelines

  • Follow NIST recommendations: Monitor the progress of the NIST PQC Standardization Project and align with their approved algorithms.
  • Learn from pilot programs: Organizations like Google (CECPQ2) and Microsoft are testing post-quantum solutions in TLS protocols. Leveraging their experiences can guide your implementation.
  • Comply with regulatory frameworks: Ensure your PQE deployment aligns with emerging government policies and industry mandates.

Step 3: Develop a Hybrid Cryptographic Strategy

  • Implement hybrid encryption: Combine traditional algorithms (e.g., RSA or AES) with quantum-resistant algorithms (e.g., CRYSTALS-Kyber) to secure communication during the transition phase.
  • Plan phased deployments: Gradually integrate PQE into core systems like VPNs, web servers (TLS), and digital certificates while keeping traditional systems in parallel.
  • Coordinate with vendors: Work closely with your technology providers to ensure that devices and software are ready to support quantum-resistant cryptography.

Step 4: Test and Validate Solutions

  • Run internal simulations: Test how PQE algorithms perform under realistic workloads, ensuring they meet performance and scalability requirements.
  • Evaluate interoperability: Check that post-quantum algorithms work seamlessly with legacy systems and protocols without introducing bottlenecks.
  • Pilot critical systems: Start with limited deployment in non-production or low-risk environments to assess compatibility and stability.

Step 5: Implement Key Management and Security Controls

  • Update key management systems: Ensure they can handle the larger keys and certificates used by post-quantum algorithms.
  • Use KEM-based encryption: Apply Key Encapsulation Mechanisms (KEMs) to generate secure session keys and ensure efficient bulk encryption.
  • Ensure forward secrecy: PQE solutions should support forward secrecy, so even if long-term keys are compromised, previous communications remain secure.

Step 6: Monitor Performance and Security Risks

  • Audit and monitor systems: Regularly test the effectiveness of the PQE solutions through security audits and penetration testing.
  • Analyze key lifecycles: Monitor certificate expiration and renew keys regularly to prevent vulnerabilities.
  • Adjust to evolving threats: Stay aware of new quantum breakthroughs and standards to keep your defenses robust.
Sources: