Public-Key Cryptography: RSA and ECC

A trapdoor one-way function is easy to compute in one direction and infeasible to invert without a secret piece of information (the trapdoor). Every public-key cryptosystem is built on one:

• RSA: multiplying large primes is fast; factoring the product is infeasible without knowing the factors.
• Diffie-Hellman / DSA: exponentiation in a cyclic group is fast; the discrete logarithm is infeasible.
• ECC: scalar multiplication of a point ($kP$) is fast; recovering $k$ from $kP$ (the elliptic curve discrete log problem, ECDLP) is infeasible.

Public key = applying the function (no trapdoor needed). Private key = the trapdoor that enables inversion. Security rests on hardness assumptions — not proven unbreakable, but no polynomial-time classical algorithm is known. Shor's algorithm solves all three on a quantum computer, which is why post-quantum cryptography is a priority.

RSA key generation:

1. Choose two large distinct primes $p, q$ (each ~1536 bits for RSA-3072).
2. Compute modulus $n = pq$ and Euler's totient $\phi(n) = (p-1)(q-1)$.
3. Choose public exponent $e$ (almost always $65537 = 2^{16}+1$, prime, few 1-bits for fast exponentiation).
4. Compute private exponent $d \equiv e^{-1} \pmod{\phi(n)}$ via extended Euclidean.

Public key = $(n, e)$. Private key = $(n, d)$ (and usually $p, q, d_p, d_q, q_{inv}$ for CRT speedup).

Encryption: $C = M^e \bmod n$. Decryption: $M = C^d \bmod n$.

Signing: $S = H(M)^d \bmod n$. Verification: check $S^e \bmod n = H(M)$.

Key sizes: RSA-2048 gives ~112-bit security. RSA-3072 gives ~128-bit security. NIST recommends at least RSA-2048 through 2030, and RSA-3072 beyond that.

"Textbook RSA" ($C = M^e \bmod n$, $M = C^d \bmod n$) is deterministic and multiplicatively homomorphic: $E(M_1) \cdot E(M_2) = E(M_1 M_2) \bmod n$. Both properties are exploitable:

• Chosen-ciphertext attack: an attacker can submit a related ciphertext $C' = r^e C$ to an oracle and recover $M$ from the decryption of $C'$.
• Small-message attacks: if $M$ is small and $e = 3$, then $M^e < n$ and $C = M^3$ is just a cube — take the integer cube root directly.
• Bleichenbacher '98 (PKCS#1 v1.5 oracle): millions of real TLS servers were vulnerable; the attack decrypts ciphertexts with a few million adaptive queries.

Required padding schemes:

• Encryption: OAEP (Optimal Asymmetric Encryption Padding, PKCS#1 v2.2 / RFC 8017). Adds random seed; ciphertext is semantically secure.
• Signing: PSS (Probabilistic Signature Scheme). Adds randomness; tightly secure under the RSA assumption.

from cryptography.hazmat.primitives.asymmetric import padding, rsa, hashes

key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
ciphertext = key.public_key().encrypt(plaintext, padding.OAEP(
    mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None))

An elliptic curve over $\mathbb{F}_p$ (a prime field) is the set of points satisfying:

$y^2 \equiv x^3 + ax + b \pmod{p}$

together with a point at infinity $\mathcal{O}$. A chord-and-tangent rule defines point addition $P + Q$ — the group law. Scalar multiplication $kP = P + P + \cdots + P$ ($k$ times) is computed efficiently with double-and-add in $O(\log k)$ operations.

Standard curves:

• P-256 (secp256r1): NIST-chosen; used in TLS, FIDO2. 256-bit field, ~128-bit security.
• secp256k1: Bitcoin/Ethereum curve. Same field size as P-256 but different $a, b$.
• Curve25519: Bernstein 2006. Designed for high performance and side-channel resistance; cofactor-4 Montgomery form. Used in X25519 (key exchange) and Ed25519 (signatures).

All three offer roughly 128-bit security — equivalent to RSA-3072, but with much smaller keys and faster operations.

ECDSA signing for message hash $e = H(m)$ with private key $d$ and base point $G$ of order $n$:

1. Choose random (or deterministic) $k \in [1, n-1]$.
2. Compute $R = kG$; let $r = R_x \bmod n$.
3. Compute $s = k^{-1}(e + rd) \bmod n$.
4. Signature = $(r, s)$.

The security of ECDSA is catastrophically sensitive to the nonce $k$:

• Same $k$ for two signatures: $k$ is recoverable from $(r, s_1, s_2, e_1, e_2)$ algebraically; private key $d$ follows immediately.
• Biased $k$: if $k$ is only partially random (e.g., top bits always zero), lattice attacks recover $d$ from ~dozens of signatures.

The Sony PlayStation 3 breach (2010) was caused by using a constant $k$ in ECDSA — private key extracted from firmware signatures. Use RFC 6979 (deterministic $k$ derived from hash of key + message) or switch to Ed25519.

Ed25519 (Edwards-curve Digital Signature Algorithm over Curve25519) fixes ECDSA's nonce problem by design:

• $k$ is derived deterministically: $k = H(\text{private\_seed} \| m)$ — no external randomness needed, no nonce-reuse risk.
• Complete addition formulas — no special-cases that lead to timing attacks.
• Batch verification: $n$ signatures can be verified faster than $n$ individual verifications.
• Small keys: 32-byte private key, 32-byte public key, 64-byte signature.

from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey

private_key = Ed25519PrivateKey.generate()
public_key = private_key.public_key()

signature = private_key.sign(message)
public_key.verify(signature, message)  # raises if invalid

Ed25519 is the default in OpenSSH, Signal, Tor, and WireGuard. For new code, prefer Ed25519 over RSA or ECDSA unless interoperability constraints force otherwise.

Classical security bit levels and corresponding key sizes across algorithms:

For new systems: use Ed25519 for signatures, X25519 for key exchange, RSA-3072+ only if mandated by a compliance regime (FIPS 140-2 historically; FIPS 186-5 now includes Ed25519). Both RSA and ECC are broken by quantum computers — start tracking NIST PQC standards (ML-KEM, ML-DSA) for post-quantum migration plans.

Asymmetric crypto is where developers make the most consequential mistakes:

1. Using PKCS#1 v1.5 padding for encryption (not OAEP): still the default in many libraries. Bleichenbacher-style attacks still work against many TLS 1.2 implementations.
2. Signing the raw message instead of its hash: RSA/ECDSA math operates on integers; signing long messages directly is either truncated or padded incorrectly. Always hash first (the library does this if you use the high-level sign API).
3. Generating RSA keys in-process for every request: RSA-3072 keygen takes ~100 ms. Cache keys; generate at startup.
4. Storing private keys in code or version control: use an HSM, KMS (AWS KMS, GCP KMS), or at minimum environment variables with restricted permissions.
5. Confusing encryption and signing: they use the same key pair but in opposite directions — never use the encryption key to sign or vice versa. They have different security proofs and padding requirements.