Offensive Security Researcher & Quantum Cryptography Analyst

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

Abdul Wahab Junaid
Public Key Encryption in Cryptography

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

FeatureSymmetricAsymmetric
Keys usedOne shared keyPublic/private key pair
SpeedFastSlow (100-1000x slower)
Key distribution problemDifficult — must share secret securelySolved — public key can be shared openly
Common usesBulk data encryptionKey exchange, digital signatures, authentication
ExamplesAES, DES, ChaCha20RSA, ECC, Diffie-Hellman

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$$

  1. Compute Euler’s totient function:

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

  1. 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.

  1. 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.

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

Security Level (bits)RSA Key SizeECC Key Size
801024 bits160 bits
1122048 bits224 bits
1283072 bits256 bits
1927680 bits384 bits
25615360 bits521 bits

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:

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

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

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

Best Practices I Follow

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

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

Exit mobile version