RSA Cryptography
How RSA works, key sizes, padding schemes, and secure usage
Skills taught: crypto.rsa
How RSA Works
RSA security is based on the Integer Factorisation Problem: multiplying two large primes is trivial, but factoring their product is computationally infeasible. Generating an RSA key pair involves choosing two large secret primes p and q. Breaking RSA means factoring n = p × q.
- Pick two large primes: p and q (each ~1024 bits for RSA-2048)
- Compute n = p × q (the modulus; published in the public key)
- Compute φ(n) = (p-1)(q-1) (kept secret)
- Choose public exponent e = 65537 (standard choice)
- Compute private exponent d such that e × d ≡ 1 (mod φ(n))
- Public key = (n, e); Private key = (n, d)
RSA Signatures in Python
RSA signatures are the most common use of RSA. The signer uses the private key to sign a document hash. Anyone with the public key can verify the signature.
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes, serialization
# --- Key generation ---
private_key = rsa.generate_private_key(
public_exponent=65537,
key_size=2048 # minimum; use 4096 for long-lived keys
)
public_key = private_key.public_key()
# --- Sign with PSS padding (recommended for signatures) ---
document = b"Software release v2.1.0 — hash: abc123..."
signature = private_key.sign(
document,
padding.PSS(
mgf=padding.MGF1(hashes.SHA256()),
salt_length=padding.PSS.MAX_LENGTH
),
hashes.SHA256()
)
print("Signature length:", len(signature), "bytes") # 256 bytes for RSA-2048
# --- Verify (anyone with public key can do this) ---
try:
public_key.verify(
signature,
document,
padding.PSS(
mgf=padding.MGF1(hashes.SHA256()),
salt_length=padding.PSS.MAX_LENGTH
),
hashes.SHA256()
)
print("Signature VALID")
except Exception:
print("Signature INVALID — document was modified or key is wrong")
Warning: Never use PKCS1v15 padding for RSA encryption (vulnerable to Bleichenbacher's attack) or textbook RSA without any padding. Always use OAEP for encryption and PSS for signing.
Saving and Loading RSA Keys
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
# --- Save private key (password-protected PEM) ---
pem_private = private_key.private_bytes(
encoding=serialization.Encoding.PEM,
format=serialization.PrivateFormat.PKCS8,
encryption_algorithm=serialization.BestAvailableEncryption(b"strong-passphrase")
)
with open("private.pem", "wb") as f:
f.write(pem_private)
# --- Save public key (no password needed) ---
pem_public = private_key.public_key().public_bytes(
encoding=serialization.Encoding.PEM,
format=serialization.PublicFormat.SubjectPublicKeyInfo
)
with open("public.pem", "wb") as f:
f.write(pem_public)
# --- Load keys ---
from cryptography.hazmat.primitives.serialization import load_pem_private_key
with open("private.pem", "rb") as f:
loaded = load_pem_private_key(f.read(), password=b"strong-passphrase")
RSA vs ECDSA for Signatures
- RSA-2048 with PSS: Classic integer factorisation-based signature
- ECDSA P-256 / Ed25519: Elliptic curve-based signature
Tip: For new systems, prefer Ed25519 over RSA for signing. It produces 64-byte signatures (vs 256 bytes for RSA-2048), is significantly faster, and is constant-time by design (no timing side channels).
Frequently Asked Questions
Should I implement RSA myself?
Never implement cryptography yourself. Use a well-audited library (Python's cryptography package, OpenSSL). Home-grown RSA will almost certainly have timing vulnerabilities or padding oracle flaws.
What is Bleichenbacher's attack?
A 1998 attack on RSA-PKCS1v15 encryption. If a server reveals whether the RSA padding is valid, an attacker can send crafted ciphertexts and use the error responses to decrypt arbitrary messages — without knowing the private key. OAEP padding prevents this.
Should I use RSA-2048 or RSA-4096?
RSA-2048 is safe today. RSA-4096 is better for keys that must remain secure for 10+ years. For new systems, consider Ed25519 instead — 64-byte signatures with equivalent security to RSA-3072.