A Comparative Study of Classical and Post-Quantum Key Establishment: RSA vs. CRYSTALS–Kyber (ML-KEM)

Abstract

The emergence of quantum computing poses an existential threat to classical cryptographic systems that form the backbone of contemporary digital security infrastructure. RSA, the most widely deployed public-key cryptosystem, relies on the computational hardness of integer factorization, a problem efficiently solvable by quantum computers using Shor\'s algorithm. This impending vulnerability has catalyzed the development of post-quantum cryptographic alternatives designed to withstand both classical and quantum attacks. CRYSTALS-Kyber, standardized by NIST as ML-KEM, represents the forefront of lattice-based key encapsulation mechanisms, offering quantum resistance through the Module Learning With Errors (MLWE) problem. This paper presents a comprehensive comparative analysis of RSA and Kyber, examining their mathematical foundations, security architectures, operational characteristics, and performance metrics across diverse computational environments. The study investigates the fundamental trade-offs between legacy systems optimized for classical threat models and emerging quantum-resistant algorithms designed for future-proof security. Through detailed analysis of key generation, encryption/encapsulation, decryption/decapsulation operations, and security guarantees, this research establishes the technical rationale behind NIST\'s selection of Kyber as the primary post-quantum key establishment mechanism. The findings demonstrate that while RSA maintains advantages in key size efficiency, Kyber\'s superior performance profile, quantum resilience, and robust security foundation position it as the essential successor for securing digital communications in the quantum era. This comprehensive study provides critical insights for organizations transitioning from classical to post-quantum cryptographic infrastructure.

Introduction

Modern digital security relies heavily on public-key cryptography, with RSA having served for decades as the dominant algorithm for secure communication, authentication, and key exchange. RSA’s security is based on the computational difficulty of integer factorization, which has proven reliable against classical computers and enabled the growth of secure internet services. However, the emergence of quantum computing fundamentally threatens this foundation, as Shor’s algorithm can efficiently break RSA and other number-theoretic cryptosystems, enabling future “harvest now, decrypt later” attacks on today’s encrypted data.

To counter this risk, the cryptographic community has developed post-quantum cryptography (PQC), which relies on mathematical problems believed to remain hard even for quantum computers. Among these, lattice-based cryptography has emerged as the most promising approach. The NIST Post-Quantum Cryptography Standardization Process selected CRYSTALS-Kyber, now standardized as ML-KEM, as the primary quantum-resistant key encapsulation mechanism.

Kyber is based on the Module Learning With Errors (MLWE) problem, which provides strong worst-case to average-case security guarantees and resistance to known classical and quantum attacks. Unlike RSA, whose security collapses under quantum computation, Kyber’s lattice foundation shows no efficient quantum attacks beyond modest speedups. Kyber also offers excellent performance, with very fast key generation, encapsulation, and decapsulation, making it well suited for modern protocols that require ephemeral keys and forward secrecy.

The paper presents a detailed comparison between RSA and Kyber, examining their mathematical foundations, security models, vulnerabilities, performance, and deployment considerations. While RSA benefits from smaller key sizes, mature implementations, and backward compatibility, it suffers from quantum vulnerability and slower key generation. Kyber, in contrast, requires larger keys and more complex implementations but provides strong quantum resistance, efficient computation, and long-term security.

Conclusion

The comprehensive comparative analysis of RSA and CRYSTALS-Kyber illuminates the fundamental transformation in cryptographic foundations necessitated by quantum computing\'s imminent threat to contemporary security infrastructure. RSA, despite its elegant mathematical foundation and four decades of successful deployment, faces catastrophic vulnerability to Shor\'s algorithm, which renders it fundamentally insecure against quantum adversaries regardless of key size. This vulnerability extends beyond future threats through \"harvest now, decrypt later\" attacks, where adversaries capture encrypted communications today for retroactive decryption once quantum computers become available, compromising the confidentiality of information requiring long-term protection. CRYSTALS-Kyber emerges from this analysis as the essential successor to classical public-key cryptography, providing robust quantum resistance through its foundation in the Module Learning With Errors problem. Kyber\'s security architecture offers unprecedented theoretical assurance through worst-case to average-case reductions, establishing that breaking Kyber requires solving the hardest instances of lattice problems—a computational hardness property unavailable for number-theoretic cryptography. Comprehensive security analysis against lattice reduction algorithms, incorporating both classical and quantum attack models, demonstrates that Kyber\'s parameter sets provide conservative security margins well exceeding minimum requirements, ensuring robust protection even under optimistic assumptions about future algorithmic improvements. The operational performance comparison reveals Kyber\'s striking computational advantages across key generation, encapsulation, and decapsulation operations. Kyber\'s key generation completes approximately three orders of magnitude faster than RSA, enabling practical ephemeral key usage providing perfect forward secrecy without performance penalties. This rapid generation, combined with fast and balanced encapsulation and decapsulation operations, positions Kyber as superior for modern cryptographic protocols requiring per-session key establishment. While Kyber\'s substantially larger key and ciphertext sizes impose bandwidth overhead compared to RSA\'s compact representation, this trade-off proves acceptable in most contemporary deployment contexts where network bandwidth significantly exceeds computational resources. The standardization of Kyber as ML-KEM through NIST\'s rigorous Post-Quantum Cryptography process validates its technical superiority across security, performance, and implementation dimensions. NIST\'s selection reflected comprehensive evaluation of security foundations, cryptanalytic confidence, performance characteristics across diverse platforms, and practical deployment considerations. Kyber distinguished itself through excellent performance across varied environments, strong security reductions to well-studied hardness assumptions, reasonable parameter sizes enabling practical deployment, and implementation characteristics facilitating side-channel resistance. However, the transition from RSA to Kyber represents more than a simple algorithm replacement—it necessitates comprehensive transformation of cryptographic infrastructure, protocol designs, and security engineering practices. The proposed hybrid framework addresses this transition complexity by enabling gradual migration maintaining backward compatibility while establishing quantum resistance. Hybrid protocols combining RSA and Kyber provide \"quantum hedge\" protection, ensuring security if either primitive remains secure while supporting legacy systems during the extended transition period. This approach enables organizations to establish quantum protection immediately while maintaining compatibility with existing infrastructure, then progressively migrate to pure post-quantum protocols as the ecosystem evolves. Critical research gaps remain in understanding long-term security assurances for lattice-based cryptography, optimizing post-quantum implementations across diverse platforms, achieving comprehensive side-channel resistance, and accumulating operational deployment experience. While Kyber\'s theoretical foundations provide strong security confidence, the algorithm lacks RSA\'s decades of cryptanalytic scrutiny and real-world deployment validation. Continued investment in lattice-based cryptanalysis, implementation security research, and operational deployment will progressively address these gaps, building community confidence comparable to mature classical algorithms. The quantum threat to cryptographic infrastructure represents a fundamental security challenge requiring coordinated response across the cryptographic research community, standards organizations, implementation developers, and deployment organizations. The successful development and standardization of CRYSTALS-Kyber demonstrates the community\'s capacity to address this challenge, delivering practical quantum-resistant alternatives before quantum computers achieve attack capabilities. However, the extended timeline for cryptographic transitions—typically requiring a decade or more for comprehensive infrastructure migration—demands immediate action. Organizations must begin post-quantum transition planning now, evaluating hybrid deployment strategies, testing implementations in controlled environments, and preparing infrastructure for algorithm migration.Looking forward, the cryptographic community must maintain vigilance through continued security analysis, algorithm refinement based on operational experience, and development of next-generation post-quantum primitives addressing remaining limitations. The establishment of cryptographic agility—infrastructure capable of rapid algorithm transition—proves essential for long-term security, enabling swift response to security discoveries whether affecting classical or post-quantum algorithms. The successful transition to post-quantum cryptography will establish resilient security infrastructure protecting digital communications through the quantum era and beyond, securing the foundation of contemporary digital society against the most significant cryptographic threat in the field\'s history.

References

[1] Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126. [2] Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484-1509. [3] Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), 84-93. [4] Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. Advances in Cryptology - EUROCRYPT 2010, 1-23. [5] Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., ... & Stehle, D. (2018). CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. Proceedings of IEEE European Symposium on Security and Privacy (EuroS&P), 353-367. [6] National Institute of Standards and Technology (NIST). (2022). Module-Lattice-Based Key-Encapsulation Mechanism Standard. FIPS 203. [7] Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., ... & Stehle, D. (2020). CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation. NIST Post-Quantum Cryptography Standardization. [8] Fujisaki, E., & Okamoto, T. (2013). Secure integration of asymmetric and symmetric encryption schemes. Journal of Cryptology, 26(1), 80-101. [9] Wiener, M. J. (1990). Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36(3), 553-558. [10] Langlois, A., & Stehle, D. (2015). Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3), 565-599. [11] Alkim, E., Ducas, L., Pöppelmann, T., & Schwabe, P. (2016). Post-quantum key exchange—A new hope. Proceedings of the 25th USENIX Security Symposium, 327-343. [12] Micciancio, D., & Regev, O. (2009). Lattice-based cryptography. Post-Quantum Cryptography, 147-191. [13] Peikert, C. (2016). A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10(4), 283-424. [14] Chen, Y., & Nguyen, P. Q. (2011). BKZ 2.0: Better lattice security estimates. Advances in Cryptology - ASIACRYPT 2011, 1-20. [15] National Institute of Standards and Technology (NIST). (2016). Report on Post-Quantum Cryptography. NISTIR 8105. [16] Bernstein, D. J., Lange, T., & Peters, C. (2008). Attacking and defending the McEliece cryptosystem. Post-Quantum Cryptography, 31-46.

Copyright

Copyright © 2026 Dr. S. Gunasekaran, Nandu S. Nair, Ajay M., Dhananjay Krishna S., R. Gautham Krishna, Aswathy A.. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.