RSA

RSA
Name	RSA
Type	Public-key cryptosystem
Developer	Ron Rivest, Adi Shamir, Leonard Adleman
Introduced	1977
Based on	Integer factorization problem
Use	Digital signatures, key exchange, encryption

RSA is a public-key cryptosystem widely used for secure data transmission, digital signatures, and key exchange. Invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, it relies on number-theoretic properties of large integers and modular arithmetic. RSA underpins many protocols and standards across computing and telecommunications, including implementations in cryptographic libraries and network stacks.

History

The invention of RSA emerged from work at the Massachusetts Institute of Technology where Ron Rivest, Adi Shamir, and Leonard Adleman published their algorithm in 1977. Early academic discussion intersected with contributions from Whitfield Diffie and Martin Hellman, whose 1976 work on public-key cryptography set the stage. Subsequent developments involved formalization by Michael Rabin and work on hardness assumptions by Carl Pomerance and Robert Silverman. Adoption accelerated through standards bodies such as the Internet Engineering Task Force, the National Institute of Standards and Technology, and industry consortia including the International Organization for Standardization. Legal and export considerations influenced deployment; cases involving the Electronic Frontier Foundation and governmental export regulations shaped dissemination. Landmark events affecting public perception included controversies around key escrow proposals and algorithmic patents, where the US Patent and Trademark Office and corporate entities like IBM and Microsoft played roles.

Mathematical Foundations

RSA depends on properties of prime numbers and modular arithmetic studied since Euclid and Euler. The algorithm's security is tied to the difficulty of the integer factorization problem examined by mathematicians such as Évariste Galois, Adrien-Marie Legendre, and Carl Friedrich Gauss. Euler's totient function and Fermat's little theorem provide the algebraic backbone, while results by Leonhard Euler and Joseph-Louis Lagrange inform modular exponentiation behavior. Complexity-theoretic analyses reference work by Alan Turing, John von Neumann, and later theoretical computer scientists like Richard Karp and Leslie Valiant. Number-theoretic algorithms for primality testing and factoring—developed by Gary Miller, Michael Rabin, Hendrik Lenstra, and Peter Shor—connect to RSA's foundations. Cryptanalytic frameworks built on results from Andrew Odlyzko, Daniel Bernstein, and Arjen Lenstra further contextualize hardness assumptions.

Key Generation and Algorithms

Key generation begins by selecting two large prime numbers using primality tests attributed to Carl Pomerance and Martin Davis; deterministic and probabilistic tests derive from the work of Gary Miller and Michael Rabin. The modulus is the product of the primes; the public and private exponents are chosen using modular inverses computed via procedures related to algorithms by Euclid. Encryption and decryption perform modular exponentiation, for which efficient routines trace back to algorithms by John von Neumann and modern optimizations implemented in libraries from OpenSSL, BoringSSL, and LibreSSL. Signature schemes built on RSA follow standards influenced by Ronald Rivest's PKCS series and protocols standardized by the Internet Engineering Task Force. Variants and modes, such as RSA-OAEP and RSA-PSS, incorporate padding and hashing designed with input from the cryptographic community and standards organizations like ISO and NIST.

Security and Attacks

Security assessments address factoring algorithms and implementation vulnerabilities. Classical factoring methods—trial division, Pollard's rho, Pollard's p‑1, and the quadratic sieve—were advanced by John Pollard and Carl Pomerance; the general number field sieve, a breakthrough by Arjen Lenstra and Hendrik Lenstra, remains the most effective classical approach for large composites. Quantum algorithms, chiefly Peter Shor's algorithm, pose theoretical threats; these concerns have motivated work by researchers at institutions such as IBM, Google, and the University of Cambridge on post‑quantum alternatives. Side-channel attacks exploiting timing, power, and electromagnetic leakage were demonstrated in influential studies from Paul Kocher and Daniel Bleichenbacher, prompting countermeasures standardized by organizations like NIST and the Trusted Computing Group. Protocol-level attacks—padding oracle exploits and Bleichenbacher attacks—have been applied to implementations in products by vendors like Microsoft, Oracle, and Cisco, leading to mitigation efforts across major projects.

Implementations and Applications

RSA is implemented in cryptographic libraries such as OpenSSL, LibreSSL, BoringSSL, and NSS, and is supported in operating systems by projects like Linux, Windows, and macOS. It is integrated into protocols including Transport Layer Security, Secure Shell, S/MIME, and PGP, and used by internet infrastructure services like certificate authorities (for example, Entrust and DigiCert) and public key infrastructures administered by organizations such as the Internet Corporation for Assigned Names and Numbers. Hardware implementations appear in smart cards from companies like NXP and Infineon and in secure elements used by mobile vendors including Apple and Samsung. RSA-based digital signature standards are employed in legal and financial systems overseen by institutions such as SWIFT and various central banks.

Performance and Optimizations

Performance improvements draw on algorithmic and engineering advances. Fast modular exponentiation uses exponentiation by squaring and Montgomery reduction techniques introduced by Peter Montgomery; Chinese Remainder Theorem optimizations reduce decryption cost using methods related to the work of Carl Friedrich Gauss. Multi-precision arithmetic libraries such as GMP and libgcrypt implement Karatsuba and Schönhage–Strassen multiplication algorithms attributed to Anatoly Karatsuba and Arnold Schönhage, accelerating large-integer operations. Parallel and hardware-accelerated implementations exploit GPUs and dedicated cryptographic accelerators produced by Intel, AMD, and ARM. Practical deployment balances key size, where standards bodies such as NIST and ETSI recommend minimum sizes, against performance constraints in embedded systems developed by vendors like ARM and Qualcomm.

Category:Public-key cryptography