How RSA Encryption Works

Understanding RSA Encryption

RSA (Rivest-Shamir-Adleman) is an asymmetric cryptographic algorithm that uses a pair of mathematically related keys: a public key for encryption and a private key for decryption. It was first published in 1977 and remains the foundation of modern secure communications.

The Mathematical Foundation

RSA relies on the practical difficulty of factoring the product of two large prime numbers. The key generation process works as follows:

1. Choose two large prime numbers p and q
2. Compute n = p * q (this becomes part of both keys)
3. Compute Euler's totient: φ(n) = (p-1)(q-1)
4. Choose a public exponent e (commonly 65537)
5. Compute the private exponent d such that d * e ≡ 1 (mod φ(n))

Encryption and Decryption

Encryption:  ciphertext = message^e mod n
Decryption:  message = ciphertext^d mod n

The public key is the pair (n, e) and the private key is (n, d). Anyone can encrypt a message using the public key, but only the holder of the private key can decrypt it.

Key Sizes and Security

The security of RSA depends entirely on the size of n. As computing power increases, larger keys are required:

• 1024-bit — considered insecure since 2010
• 2048-bit — current minimum recommended standard
• 3072-bit — recommended by NIST for protection beyond 2030
• 4096-bit — used for high-security applications

Digital Signatures

RSA also enables digital signatures by reversing the process: the private key signs a message hash, and the public key verifies the signature. This provides authentication, integrity, and non-repudiation.