Public Key Encryption in Cryptography: RSA, ECC, and Asymmetric Cryptography Explained

The first time asymmetric cryptography made sense to me, I was thinking about mailboxes. Imagine a mailbox with a slot anyone can drop letters into, but only I have the key to open it. That’s public key encryption in a nutshell — anyone can encrypt a message using my public key, but only I can decrypt it using my private key. In this article, I’m going to walk through how RSA and ECC actually work under the hood, the number theory that makes them possible, and how asymmetric cryptography fits into the systems I rely on every day.

What Is Public Key (Asymmetric) Encryption?

Unlike symmetric encryption, where a single shared key handles both encryption and decryption, asymmetric encryption uses a mathematically linked key pair: a public key that can be shared openly, and a private key that must remain secret.

$$C = E_{PubK}(P)$$ $$P = D_{PrivK}(C)$$

The security of this entire system rests on trapdoor functions — mathematical operations that are easy to compute in one direction but computationally infeasible to reverse without a specific piece of secret information (the private key).

Table: Symmetric vs Asymmetric Encryption

Because asymmetric algorithms are computationally expensive, I almost never see them used to encrypt large amounts of data directly. Instead, they typically encrypt a symmetric session key, which then handles the bulk data — this hybrid approach is exactly what TLS does.

RSA: The Foundational Public Key Algorithm

RSA, named after its inventors Rivest, Shamir, and Adleman, was published in 1977 and remains one of the most widely deployed public key algorithms. Its security is based on the integer factorization problem — multiplying two large primes together is easy, but factoring the resulting product back into its original primes is computationally infeasible for sufficiently large numbers.

How RSA Key Generation Works

I walk through RSA key generation in these steps:

1. Choose two large, distinct prime numbers, p and q (typically 1024+ bits each for 2048-bit RSA).
2. Compute the modulus:

$$n = p \times q$$

3. Compute Euler’s totient function:

$$\phi(n) = (p-1)(q-1)$$

4. Choose a public exponent e such that:

$$1 < e < \phi(n), \quad \gcd(e, \phi(n)) = 1$$

Commonly, e = 65537 is used because it balances security with efficient computation.

5. Compute the private exponent d, the modular multiplicative inverse of e mod φ(n):

$$d \equiv e^{-1} \pmod{\phi(n)}$$

The public key is the pair (n, e), and the private key is the pair (n, d).

Encryption and Decryption

Encryption of a message m (represented as an integer less than n):

$$c \equiv m^e \pmod{n}$$

Decryption:

$$m \equiv c^d \pmod{n}$$

This works because of Euler’s theorem, which guarantees that raising m to the power e*d mod φ(n) returns m itself, since e and d were constructed to be modular inverses.

A Small Worked Example

I find RSA easier to understand with tiny numbers, even though real implementations use numbers hundreds of digits long.

• Let p = 61, q = 53
• n = 61 × 53 = 3233
• φ(n) = 60 × 52 = 3120
• Choose e = 17 (coprime with 3120)
• Compute d such that 17d ≡ 1 (mod 3120), which gives d = 2753

Public key: (n=3233, e=17). Private key: (n=3233, d=2753).

If I encrypt m = 65: c = 65^17 mod 3233 = 2790. Decrypting: 2790^2753 mod 3233 = 65, recovering the original message.

Why RSA Is Secure

RSA’s security depends entirely on the difficulty of factoring n back into p and q. For a 2048-bit RSA key, this means factoring a number that’s roughly 617 decimal digits long — a task believed to require more computational resources than exist on Earth using classical computers. The best known classical algorithm for this, the General Number Field Sieve, has sub-exponential but still infeasible time complexity for keys of this size.

Elliptic Curve Cryptography (ECC)

ECC takes a completely different mathematical approach, based on the algebraic structure of elliptic curves over finite fields. I find ECC more abstract than RSA, but its practical benefit is huge: it achieves equivalent security to RSA using dramatically smaller key sizes.

Table: RSA vs ECC Key Size Comparison

An elliptic curve over a finite field is defined by the equation:

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

Where a and b are curve parameters and p is a large prime defining the finite field.

The Elliptic Curve Discrete Logarithm Problem

Points on the curve can be “added” together using a defined geometric/algebraic rule, and this point addition operation forms the basis of ECC’s security. Given a base point G on the curve, I can compute:

$$Q = kG$$

Where k is a private integer (the private key) and Q is the resulting point (the public key), computed by adding G to itself k times. This is called scalar multiplication.

The security of ECC rests on the Elliptic Curve Discrete Logarithm Problem (ECDLP): given G and Q, it’s computationally infeasible to determine k, even though computing Q from k and G is efficient. Unlike integer factorization, no sub-exponential algorithm is known for solving ECDLP on well-chosen curves, which is exactly why ECC keys can be so much smaller than RSA keys while offering equivalent security.

ECDH: Elliptic Curve Diffie-Hellman Key Exchange

I use ECDH constantly for secure key exchange. Two parties, Alice and Bob, each generate a private/public key pair:

• Alice: private key a, public key A = aG
• Bob: private key b, public key B = bG

They exchange public keys, then each computes the shared secret independently:

$$S = aB = a(bG) = abG$$ $$S = bA = b(aG) = abG$$

Both arrive at the same shared secret S without ever transmitting it directly, and an eavesdropper who intercepts A and B cannot feasibly compute S without solving the ECDLP.

ECDSA: Elliptic Curve Digital Signature Algorithm

ECDSA is the signature counterpart to ECDH, and it’s what secures Bitcoin transactions and TLS certificate signing. Signing a message hash h with private key d involves generating a random nonce k, then computing:

$$R = kG, \quad r = R_x \bmod n$$ $$s = k^{-1}(h + rd) \bmod n$$

The signature is the pair (r, s). Verification involves reconstructing a point using the public key and confirming it matches r. I want to stress one critical detail here: the nonce k must be unique and unpredictable for every signature. Reusing k across two signatures allows an attacker to recover the private key algebraically — this exact mistake compromised the PlayStation 3’s signing key in 2010.

Common Curves in Use Today

• P-256 (secp256r1) — widely used in TLS and standardized by NIST.
• Curve25519 — designed by Daniel J. Bernstein for high performance and resistance to implementation errors, used in modern protocols like Signal and WireGuard.
• secp256k1 — the curve used by Bitcoin and Ethereum.

Implementation Example

Seeing RSA in actual code helps me connect the number theory to something concrete. Here’s how I generate an RSA key pair and perform encryption/decryption using Python’s cryptography library:

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

# Key generation
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

message = b"Meet me at the usual place"

# Encryption with OAEP padding (never use raw textbook RSA)
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# Decryption
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

I deliberately used OAEP padding here rather than encrypting the raw message bytes directly. Textbook RSA without proper padding is deterministic and malleable — identical plaintexts always produce identical ciphertexts, and an attacker can manipulate ciphertexts in mathematically predictable ways. OAEP introduces randomness and a verifiable structure that closes off both of these weaknesses, which is why every production RSA implementation I’ve worked with uses it (or an equivalent padding scheme) rather than the bare mathematical operation.

For ECDH, the equivalent flow looks like this:

from cryptography.hazmat.primitives.asymmetric import ec

alice_private = ec.generate_private_key(ec.SECP256R1())
bob_private = ec.generate_private_key(ec.SECP256R1())

alice_shared = alice_private.exchange(ec.ECDH(), bob_private.public_key())
bob_shared = bob_private.exchange(ec.ECDH(), alice_private.public_key())

assert alice_shared == bob_shared  # both derive the same secret

The resulting shared secret is typically passed through a key derivation function (like HKDF) before being used directly as a symmetric key, rather than using the raw ECDH output.

Real-World Applications of Public Key Cryptography

• TLS/HTTPS handshakes — RSA or ECDHE is used to establish a shared symmetric session key.
• Digital certificates — Certificate Authorities sign certificates using RSA or ECDSA, allowing browsers to verify server identity.
• SSH authentication — public/private key pairs authenticate users without transmitting passwords.
• Cryptocurrency wallets — Bitcoin and Ethereum addresses are derived from ECDSA public keys, and transactions are signed with the corresponding private keys.
• PGP/GPG email encryption — RSA or ECC keys encrypt messages and verify sender identity.

Hybrid Encryption in Practice

Because asymmetric encryption is computationally expensive, virtually every real system I’ve studied combines both approaches:

1. The sender generates a random symmetric session key.
2. The session key is encrypted using the recipient’s public key (RSA) or derived via ECDH.
3. The actual message data is encrypted using the fast symmetric session key (typically AES-GCM).
4. The recipient decrypts the session key with their private key, then uses it to decrypt the message.

This is precisely how TLS 1.3 operates, and it’s why an HTTPS connection can encrypt gigabytes of data quickly despite relying on “slow” asymmetric cryptography for the initial handshake.

Cryptanalysis and Attacks Against Asymmetric Systems

• Factoring attacks (RSA) — the General Number Field Sieve is the best known classical factoring algorithm; RSA keys below 2048 bits are now considered insufficient.
• Weak random number generation — if the primes p and q (RSA) or the nonce k (ECDSA) aren’t generated with a truly random, secure process, private keys can potentially be recovered.
• Nonce reuse in ECDSA — as mentioned above, reusing a nonce across signatures leaks the private key.
• Side-channel attacks — timing attacks or power analysis can leak information about private key operations if implementations aren’t constant-time.
• Shor’s algorithm — a quantum algorithm that can efficiently factor large integers and solve discrete logarithm problems, which would break both RSA and ECC if large-scale, fault-tolerant quantum computers become practical. This is the driving force behind current research into post-quantum cryptography.

Best Practices I Follow

• Use RSA keys of at least 2048 bits, preferably 3072 or 4096 bits for long-term security.
• Prefer ECC (P-256 or Curve25519) over RSA for new systems where smaller key sizes and faster computation are beneficial.
• Never implement RSA or ECC primitives from scratch — rely on audited libraries like OpenSSL, libsodium, or BoringSSL.
• Always use a cryptographically secure random number generator for key and nonce generation.
• Use RSA-OAEP for encryption padding rather than the outdated PKCS#1 v1.5 padding, which is vulnerable to padding oracle attacks (like the Bleichenbacher attack).
• Monitor developments in post-quantum cryptography and plan migration paths for long-term-sensitive data.

Performance Considerations

Asymmetric operations are inherently slower than symmetric ones — RSA decryption in particular is computationally expensive due to modular exponentiation with large numbers. ECC generally outperforms RSA at equivalent security levels because its smaller key sizes translate directly into faster computations and smaller certificates, which is part of why ECDHE has become the default key exchange mechanism in modern TLS deployments.

Common Mistakes I See

• Using RSA key sizes below 2048 bits.
• Reusing nonces in ECDSA signing operations.
• Implementing custom padding schemes instead of using standardized, vetted ones like OAEP.
• Failing to validate that received public keys/certificates are legitimate before trusting them.
• Assuming asymmetric encryption alone provides authentication — encryption confirms confidentiality, but digital signatures are needed to confirm sender identity.

Frequently Asked Questions

Why can’t I just use RSA for everything instead of combining it with symmetric encryption? RSA is far too slow to encrypt large amounts of data efficiently. Hybrid encryption uses RSA or ECC only to protect a small symmetric key, letting a fast cipher like AES handle the bulk data.

Is ECC always better than RSA? ECC generally offers better performance and smaller key sizes for equivalent security, but RSA remains widely deployed, well-understood, and compatible with legacy systems, which is why both continue to coexist.

What happens to RSA and ECC if quantum computers become practical? Shor’s algorithm would break both, which is why NIST has been standardizing post-quantum cryptographic algorithms (like CRYSTALS-Kyber and CRYSTALS-Dilithium) designed to resist quantum attacks.

Can I reuse the same RSA key pair for both encryption and signing? It’s best practice to use separate key pairs for encryption and signing to avoid certain cross-protocol attacks and to simplify key management and revocation.

How do I choose between RSA and ECC for a new project? I generally default to ECC (P-256 or Curve25519) for new systems, since it offers equivalent security with smaller keys, faster computation, and reduced bandwidth for certificates and handshakes. I reach for RSA mainly when compatibility with older systems or specific compliance requirements demands it, since RSA remains more universally supported across legacy infrastructure.

Summary

Public key cryptography solved one of the oldest problems in secure communication: how to exchange secrets without ever having shared a secret beforehand. RSA achieves this through the difficulty of factoring large integers, while ECC achieves equivalent or stronger security through the elliptic curve discrete logarithm problem, using far smaller keys. Both algorithms underpin the digital certificates, key exchanges, and digital signatures that secure the modern internet, almost always working alongside symmetric encryption in hybrid systems rather than replacing it. As quantum computing advances, the field is already shifting toward post-quantum alternatives designed to withstand a fundamentally different kind of computational threat.

References

• Rivest, R., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM.
• NIST FIPS 186-5, Digital Signature Standard (DSS)
• NIST Special Publication 800-56A, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography
• RFC 8017, PKCS #1: RSA Cryptography Specifications Version 2.2
• RFC 7748, Elliptic Curves for Security (Curve25519 and Curve448)
• Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation.
• NIST IR 8413, Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process