RSA (Asymmetric) Encryption

RSA (Rivest–Shamir–Adleman) is the first widely adopted public-key cryptosystem, introduced in 1977. In contrast to symmetric ciphers, which use the same secret key for encryption and decryption, RSA employs a pair of mathematically linked keys: one public and one private. The public key can be distributed freely to encrypt messages or verify signatures, while the private key remains secret for decryption or signature generation. This dual-key approach enables secure communication without sharing a secret in advance and underpins many modern protocols including TLS, digital signatures, and secure email.

At its core, RSA relies on the computational difficulty of factoring large integers that are the product of two prime numbers. Users generate a key pair by selecting two large random primes, p and q, then computing n = p × q and φ(n) = (p−1)×(q−1). A public exponent e is chosen, typically a Fermat prime like 65537, and the private exponent d is computed as the modular inverse of e modulo φ(n). The resulting key sizes are measured in bits of n—common lengths are 2048, 3072, and 4096 bits, offering a trade-off between security and performance.

The RSA key generation process begins by generating two large, random primes of equal length. Cryptographic libraries use probabilistic primality tests such as Miller–Rabin to ensure high confidence. Once p and q are identified, n = p × q defines the modulus. The totient φ(n) is computed as (p − 1) × (q − 1), and a public exponent e is selected. Common practice is to use e = 65537 because it balances security with efficient encryption. The private exponent d is calculated with the Extended Euclidean Algorithm so that e × d ≡ 1 mod φ(n). The public key consists of (n, e), and the private key contains (n, d) plus optional CRT parameters (d mod (p−1), d mod (q−1), and the coefficient q−1 mod p) for faster decryption.

RSA encryption transforms plaintext m ∈ [0, n−1] into ciphertext c by computing c ≡ m^e mod n. Decryption reverses the operation: m ≡ c^d mod n. However, direct application of these exponentiations is insecure by itself. Practical schemes employ padding standards: PKCS#1 v1.5 for legacy support or the modern OAEP (Optimal Asymmetric Encryption Padding) scheme. OAEP combines m with random padding using hash functions to provide semantic security and resist chosen-ciphertext attacks. Libraries must carefully implement padding removal and validate input lengths to avoid padding oracle vulnerabilities.

Digital signatures with RSA work by applying the private key to a message digest rather than the full message. The signer computes a hash of the message using a secure hash function (e.g., SHA-256), then applies a padding scheme such as PSS (Probabilistic Signature Scheme) or PKCS#1 v1.5 to format the hash. The signature s is computed as s ≡ (hash_with_padding)^d mod n. Verification uses the public key: the verifier computes s^e mod n, removes padding, and compares the recovered hash to its own computed hash of the message. PSS is recommended because it provides provable security against adaptive chosen-message attacks.

RSA’s security rests on the difficulty of factoring the modulus n. Key lengths below 2048 bits are no longer recommended because advances in factoring algorithms and specialized hardware have made them vulnerable. Proper padding is critical: PKCS#1 v1.5 padding has known downgrade and oracle-based attacks, while OAEP and PSS mitigate these risks. Implementations must guard against side-channel attacks, such as timing and power analysis, by using constant-time exponentiation and blinding techniques. Protecting private key material in secure modules (HSMs or secure enclaves) further reduces risk.

RSA operations are computationally intensive due to large modular exponentiations. Encryption with a small exponent (e = 65537) is relatively fast, while decryption and signing with the large private exponent d are slower. Chinese Remainder Theorem (CRT) optimizations split exponentiations modulo p and q, roughly quadrupling decryption and signing speed. Throughput depends on key size: typical benchmarks on modern CPUs yield thousands of encryptions per second with 2048-bit keys, but only tens to hundreds of decryptions or signatures per second without parallelization or hardware support. For high-throughput systems, hybrid encryption is used: RSA encrypts a short symmetric key, and a bulk cipher (e.g., AES-GCM) processes the main data.

RSA keys and operations are defined in multiple standards: PKCS#1 describes key formats and padding; PKCS#8 defines private key syntax; X.509 and SPKI cover public key certificates and structures; JWK is a JSON-based format for web applications. Exporting keys in pkcs8 (binary DER or base64 PEM), JWK, or SPKI ensures compatibility across languages and platforms. When generating keys, users can choose the desired export format and specify encoding (PEM vs. DER) along with optional encryption of the private key using passphrase-based encryption standards (PBES2, PBKDF2).

– Always use a minimum key length of 2048 bits, and consider 3072 or 4096 bits for long-term security. – Employ OAEP for encryption and PSS for signatures; avoid PKCS#1 v1.5 unless necessary for legacy support. – Store private keys in secure hardware or encrypted storage with strong passphrases. – Use constant-time, side-channel resistant libraries. – Combine RSA with symmetric ciphers in hybrid encryption to leverage RSA’s key distribution and the performance of AES or ChaCha20.

// Pseudocode for RSA encryption in JavaScript-like syntax const { publicKey, privateKey } = generateKeyPair({ modulusLength: 2048, publicExponent: 0x10001, hashAlgorithm: 'SHA-256' }); const ciphertext = encrypt({ key: publicKey, data: plaintext, padding: 'OAEP' }); const decrypted = decrypt({ key: privateKey, data: ciphertext, padding: 'OAEP' }); // Signing const signature = sign({ key: privateKey, data: message, padding: 'PSS', hash: 'SHA-256' }); const valid = verify({ key: publicKey, data: message, signature, padding: 'PSS', hash: 'SHA-256' });