RSA

RSA was the first public-key system that actually worked in practice, and it still underpins a huge amount of deployed TLS, PGP, and code-signing. Understanding it matters not because you should reach for it first (you should not, for new work), but because you will meet it everywhere and most of its real-world failures come from misuse rather than broken math.

The math at intuition level

RSA’s security rests on a lopsided problem: multiplying two large primes is trivial, but factoring the product back into those primes is infeasible when the numbers are big enough.

1. Pick two large secret primes p and q.
2. Compute the modulus n = p * q. This becomes part of the public key.
3. Derive a public exponent e (commonly 65537) and a private exponent d that are inverses with respect to the totient of n.
4. The public key is (n, e); the private key is (n, d).

Encrypting is c = m^e mod n; decrypting is m = c^d mod n. Anyone can raise to the power e, but reversing it requires d, and recovering d requires factoring n. Nobody knows how to factor a 3072-bit n in reasonable time on classical hardware.

The catch: m must be smaller than n, so RSA can only encrypt a small chunk of data (in practice, a symmetric key or a hash), not a whole message.

Padding matters

Raw modular exponentiation is deterministic and malleable, so RSA is never used bare. A padding scheme adds randomness and structure. The scheme you choose is a security decision, not a formality.

Scheme	Purpose	Status
PKCS#1 v1.5 (encryption)	Legacy encryption padding	Avoid: vulnerable to padding-oracle attacks (Bleichenbacher)
OAEP	Modern encryption padding	Use this for RSA encryption
PKCS#1 v1.5 (signatures)	Legacy signature padding	Tolerable but not preferred
PSS	Modern randomized signature padding	Use this for RSA signatures

Why textbook RSA is always wrong

“Textbook RSA” means c = m^e mod n with no padding. It is broken in ways that have nothing to do with factoring:

• Deterministic: the same plaintext always gives the same ciphertext, so an attacker can detect repeats and precompute a dictionary of likely messages.
• Malleable: multiplying two ciphertexts multiplies their plaintexts, letting an attacker forge related messages.
• Small-message weakness: a short m with small e may not wrap the modulus at all, so c = m^e can be reversed with a plain cube root.

The lesson mirrors the wider theme in this group (see the sibling Overview): the primitive is fine, the misuse is fatal. Always let a vetted library apply OAEP or PSS.

Hands-on: generate, encrypt, and sign with RSA

cd ~/crypto-lab
# Generate a 3072-bit RSA private key (minimum size for new RSA work)
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out rsa.pem
openssl pkey -in rsa.pem -pubout -out rsa.pub.pem

# Encrypt a short secret with OAEP padding
echo -n "symmetric-key-material" > secret.bin
openssl pkeyutl -encrypt -pubin -inkey rsa.pub.pem \
  -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
  -in secret.bin -out secret.enc

# Decrypt with the private key
openssl pkeyutl -decrypt -inkey rsa.pem \
  -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
  -in secret.enc -out secret.dec
diff secret.bin secret.dec && echo "roundtrip OK"

Expected output:

roundtrip OK

Now sign a message with PSS padding:

echo -n "release v2.1.0" > msg.txt
openssl dgst -sha256 -sign rsa.pem \
  -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:-1 \
  -out msg.sig msg.txt
openssl dgst -sha256 -verify rsa.pub.pem \
  -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:-1 \
  -signature msg.sig msg.txt

Expected output:

Verified OK

Practical Guidance

1. Prefer Ed25519 or ECDSA P-256 for new keys (see the sibling Elliptic Curves). Reach for RSA only when a peer or standard requires it.
2. If you use RSA, generate at least 3072-bit keys; treat 2048 as a legacy floor and never go below it.
3. Always use OAEP for encryption and PSS for signatures. Never touch textbook (unpadded) RSA.
4. Keep the public exponent at 65537. Do not choose small exponents like 3.
5. Do not encrypt bulk data with RSA. Encrypt a symmetric key and use it for the payload (hybrid encryption).
6. Protect the private key file with strict permissions and a passphrase, and rotate it on schedule (see the Key Management group).