| RSA (cryptosystem) | |
|---|---|
| Name | RSA |
| Inventor | Ron Rivest, Adi Shamir, Leonard Adleman |
| Introduced | 1977 |
| Based on | Integer factorization problem |
| Type | Public-key cryptosystem |
RSA (cryptosystem)
RSA (cryptosystem) is a public-key encryption and digital signature system invented by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977. It relies on the computational difficulty of the integer factorization problem for security, and it matters to Quantum physics because quantum algorithms such as Shor's algorithm threaten the classical assumptions that underpin modern secure communications like TLS and PGP.
RSA underpins large parts of contemporary digital security including secure web browsing (HTTPS/TLS), secure email (OpenPGP), and many authentication systems used by governments, financial institutions, and civil society. The advent of scalable quantum computers developed by organizations such as IBM, Google, Rigetti Computing, IonQ, and research labs including IBM Quantum and Google Quantum AI creates a direct link between experimental quantum computing progress and the practical viability of RSA. The interaction between RSA and quantum technology has catalyzed interdisciplinary work across computer science, mathematics, and experimental quantum physics, as seen in collaborations at institutions like Massachusetts Institute of Technology, University of Waterloo (including the Institute for Quantum Computing), and University of Oxford.
RSA's mathematical basis is modular arithmetic and number theory: choosing large primes p and q, computing n = pq, selecting an encryption exponent e, and a private exponent d satisfying ed ≡ 1 (mod φ(n)). The classical security assumption is that factoring n into p and q is infeasible for sufficiently large key sizes (commonly 2048–4096 bits), a hardness related to algorithms such as the general number field sieve and analytic results in number theory. Cryptanalytic efforts have involved researchers at centers like NIST and conferences such as CRYPTO and Eurocrypt; landmark papers include works by Carl Pomerance and the development of subexponential factoring techniques. Security also depends on proper implementation practices described in standards from organizations like the IETF and the Internet Engineering Task Force.
The primary quantum threat to RSA is Shor's algorithm (1994), which solves integer factorization in polynomial time on an ideal quantum computer. Shor's demonstration bridged abstract quantum algorithm theory with a tangible threat model for public-key systems, motivating experimental implementations that used small-scale quantum processors to factor numbers in proof-of-principle studies by groups at IBM, University of California, Santa Barbara, and University of Cambridge. The feasibility of breaking real-world RSA keys depends on engineering advances in quantum error correction (e.g., surface codes), qubit coherence, and quantum gate fidelity; programs like the National Quantum Initiative and investments by European Union quantum flagship projects accelerate progress. Cryptographers and physicists jointly model timelines for "cryptographically relevant quantum computers" (CRQCs) and publish guidelines through agencies including National Institute of Standards and Technology.
Responses to the quantum threat include designing post-quantum cryptography (PQC) schemes believed secure against quantum attacks, such as lattice-based systems (NTRU, CRYSTALS-Kyber), code-based systems (McEliece cryptosystem), hash-based signatures (XMSS), and multivariate quadratic equations. NIST ran a standardization competition that selected algorithms like CRYSTALS-Kyber and CRYSTALS-Dilithium for standardization. Hybrid strategies combine RSA or Elliptic-curve cryptography with PQC to hedge transition risk. Transition planning involves standards bodies (e.g., IETF, ISO/IEC), major vendors (Microsoft, Google, Apple Inc.), and infrastructure providers to update protocols, software stacks, and certificate authorities such as Let's Encrypt.
The potential compromise of RSA has broad social implications: threats to privacy, financial systems, electoral infrastructure, and human-rights communications. Vulnerable populations—activists, journalists, and marginalized groups—depend disproportionately on secure communications; thus equitable transition strategies are a justice concern. National security actors (NSA) and intelligence communities have historically driven cryptographic policy, sometimes at odds with civil liberties advocates and organizations like the Electronic Frontier Foundation and Privacy International. Policymakers in bodies such as the European Commission and legislatures must balance rapid migration to PQC with access, auditability, and global interoperability to avoid digital inequality between high-resource and low-resource regions.
Implementation practices for RSA—secure random number generation, side-channel mitigations, and key lifecycle management—remain critical during transition. Key management infrastructure (KMI) involving Public key infrastructure (PKI), certificate authorities, and hardware security modules (HSMs) must accommodate algorithm agility. Cryptanalysis groups at universities (e.g., Stanford University, ETH Zurich), national labs (Los Alamos National Laboratory), and companies publish vulnerability analyses combining classical and quantum threat modeling. Practical defenses include proactive re-encryption, forward secrecy mechanisms in TLS 1.3, and archival risk mitigation for long-term secrets (e.g., "harvest now, decrypt later" threat models). International coordination through entities like NIST and the Internet Engineering Task Force is essential to ensure an equitable, transparent migration away from RSA where necessary.
Category:Public-key cryptography Category:Quantum cryptography