RSA Encryption

RSA Encryption

Mathematical Definition

The RSA algorithm works through key generation, encryption, and decryption based on modular arithmetic and Euler's totient theorem. Given two distinct prime numbers p and q:

The public key is (n, e) and the private key is (n, d). To encrypt a message M (represented as an integer where 0 ≤ M < n), the sender computes ciphertext C. The receiver then decrypts C to recover M:

Key Concepts

• Asymmetric Cryptography: Unlike symmetric key algorithms (like AES) which use the same key for encryption and decryption, RSA uses a paired system. The encryption key is public, meaning anyone can encrypt a message, but the decryption key is kept strictly private so only the intended recipient can read it.
• Prime Factorization Problem: The security of RSA hinges on the fact that while it is computationally trivial to multiply two large primes p and q to get n, there is no known efficient classical algorithm to determine p and q when given only n if the numbers are sufficiently large (e.g., 2048 or 4096 bits).
• Euler's Theorem: The fundamental mathematical principle enabling RSA decryption is Euler's theorem, which states that if a and n are coprime, then a^φ(n) ≡ 1 (mod n). Consequently, since e × d = 1 + k × φ(n), decrypting yieldsC^d ≡ (M^e)^d ≡ M^ed ≡ M^{1 + k × φ(n)} ≡ M × (M^φ(n))^k ≡ M × 1^k ≡ M (mod n).
• Digital Signatures: RSA can be run in reverse to verify authenticity. If the owner of the private key "encrypts" a message (or a hash of the message) using d, anyone can "decrypt" it using the public key e. Since only the owner could have generated this signature, it proves the message's origin and integrity.

Historical Context

The RSA algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. It represented the first practical realization of public-key cryptography, a theoretical concept introduced a year earlier by Whitfield Diffie and Martin Hellman. Diffie and Hellman had proposed the idea of a trapdoor one-way function but lacked a concrete implementation capable of both encryption and digital signatures.

Unknown to the public at the time, a similar system had been secretly developed in 1973 by Clifford Cocks, an English mathematician working for the UK intelligence agency GCHQ. Due to its classified nature, Cocks' work was not revealed until 1997. Following its publication, RSA quickly became a foundational standard for cryptography. As computing power has increased, the required key size for security has steadily grown from 512 bits in the 1990s to the current standard of 2048 or 4096 bits.

Real-world Applications

• Transport Layer Security (TLS/SSL): RSA is fundamentally used in the handshake process to establish secure HTTPS connections. It allows a client to securely exchange a symmetric session key with a web server.
• Secure Email: Protocols like PGP (Pretty Good Privacy) and S/MIME rely on RSA to encrypt email contents and provide digital signatures to verify the sender's identity.
• Software Distribution: Operating systems and package managers use RSA digital signatures to verify that updates and software packages have not been tampered with and originate from a trusted developer.
• Virtual Private Networks (VPNs): IPsec and OpenVPN utilize RSA certificates to authenticate endpoints before establishing a secure encrypted tunnel.

Related Concepts

• Hashing Algorithms — often used in conjunction with RSA to sign fixed-length digests rather than full messages.
• Finite State Machines — useful models for conceptualizing parsing and cryptographic protocol states.
• Elliptic-Curve Cryptography (ECC) — a modern alternative to RSA that provides equivalent security with much smaller key sizes.
• Quantum Computing (Shor's Algorithm) — a theoretical threat to RSA, as a sufficiently powerful quantum computer could factor large primes efficiently.