RSA algorithm: public-key encryption, key generation, and history

How RSA works in principle

At a high level, RSA uses modular arithmetic and exponentiation to transform messages so only the holder of the private key can recover the original. The public key is used to encrypt or verify, while the private key decrypts or signs. Messages are usually processed together with standardized padding schemes to prevent structural attacks and to ensure that the system is safe to use with arbitrary messages. For background on asymmetric cryptography see asymmetric encryption and for padding standards see cryptographic padding.

Key generation and the underlying mathematics

Key generation creates a public/private key pair by selecting two large prime numbers and combining them into a modulus. The basic steps are often presented as a sequence:

1. Choose two large primes and compute their product n.
2. Compute an auxiliary value related to the primes that governs the exponent arithmetic.
3. Select a public exponent that is coprime with that auxiliary value.
4. Compute the private exponent as the multiplicative inverse of the public exponent modulo the auxiliary value.

The public key consists of the modulus and the public exponent; the private key contains the private exponent (and often the primes themselves to speed computation). Implementations may include optimizations and extra parameters for performance. For a technical reference on factors and primes see prime factorization and composite numbers.

History and development

RSA was introduced in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman as one of the earliest practical public-key systems. It followed theoretical work that showed public-key cryptography was possible and provided a working method that could be implemented on contemporary computers. Over time the algorithm has been refined through research on padding, side-channel protections, and parameter recommendations. For historical context see public key history and biographical notes at Rivest–Shamir–Adleman.

Uses, examples and importance

RSA is employed in many standard protocols and products. Typical uses include establishing secure channels (often to exchange symmetric session keys), creating digital signatures that prove authenticity, and encrypting small blocks of data. In everyday systems RSA often works alongside other primitives: it may secure a key-exchange step that then yields a faster symmetric cipher for bulk data. Standards and libraries provide interoperable formats so different implementations can work together; consult standards and practical guides at implementation notes.

Security considerations and notable facts

• Security depends chiefly on the difficulty of factoring the modulus; key sizes must increase as computational power grows.
• Proper padding (e.g., OAEP for encryption, PSS for signatures) is essential to prevent chosen-ciphertext and related attacks.
• Side-channel attacks (timing, power analysis) can leak private keys unless implementations take countermeasures.
• Quantum computing poses theoretical future risk to RSA: sufficiently large quantum computers could run algorithms that break factoring-based systems.

Despite the availability of alternative public-key schemes (elliptic-curve cryptography, lattice-based systems), RSA remains widely supported because of its longstanding role in standards and its clear conceptual basis. For more detailed treatments that cover proofs and recommended parameters, follow the links above to authoritative references and standards documents.