Asymmetric Encryption

Imagine you need to send a secret message to someone you've never met, across an insecure channel where anyone can eavesdrop. Before 1976, this problem seemed unsolvable—you would need to somehow share a secret key first, but how do you share a secret securely when you don't already have a secure channel?

This was the key distribution problem, and it plagued cryptographers for centuries. Armies sent couriers with codebooks, banks used armored trucks to transport keys, and diplomatic pouches carried cipher materials across borders. Every secure communication required first solving the logistical nightmare of key exchange.

Then came one of the most profound breakthroughs in the history of cryptography: asymmetric encryption, also known as public-key cryptography. This revolutionary idea allows two parties to establish secure communication without ever sharing a secret, fundamentally transforming everything from e-commerce to email security.

To understand why asymmetric encryption was revolutionary, we must first appreciate the fundamental limitation of symmetric encryption.

In symmetric encryption (covered in the previous module), the same key is used for both encryption and decryption. If Alice wants to send a secret message to Bob using AES, they must both possess the identical secret key. This arrangement works perfectly well for encrypting data—but creates a profound logistical problem:

How does Alice securely share the key with Bob in the first place?

This O(n²) growth in key requirements makes symmetric-only cryptosystems impractical for modern internet scale. Consider e-commerce: every time you visit a new website, you would need to have previously established a shared secret with that site. The logistical impossibility is immediately apparent.

The cryptographic community needed a fundamentally different approach—one that didn't require sharing secrets at all.

In 1976, Whitfield Diffie and Martin Hellman published "New Directions in Cryptography," arguably the most influential paper in the history of modern cryptography. They proposed an audacious idea:

What if encryption and decryption used different keys?

This seems counterintuitive—almost paradoxical. If one key locks the box, how can a different key unlock it? The genius lay in recognizing that certain mathematical functions have this exact property: trapdoor one-way functions.

The Paint-Mixing Analogy:

Imagine cryptography as mixing paint colors:

1. Alice and Bob each pick a secret color (their private keys)
2. They also agree on a common base color (a public parameter)
3. Each mixes their secret color with the base and shares the result publicly
4. Alice takes Bob's mixture and adds her secret color
5. Bob takes Alice's mixture and adds his secret color
6. Both arrive at the same final color—their shared secret!

An eavesdropper sees only the individual mixtures, not the secret colors. Separating mixed paint is computationally infeasible, just like reversing the mathematical operation without the private key.

This is the conceptual foundation of all asymmetric cryptography: operations that are easy in one direction but hard to reverse without special knowledge.

At the heart of asymmetric encryption is the key pair: two mathematically related keys that serve complementary purposes.

The Public Key:

• Can be freely distributed to anyone
• Published in directories, embedded in certificates, shared openly
• Used to encrypt data intended for the key owner
• Used to verify digital signatures created by the key owner
• Cannot be used to decrypt data or create signatures

The Private Key:

• Must be kept absolutely secret
• Never leaves the owner's control
• Used to decrypt data encrypted with the corresponding public key
• Used to create digital signatures
• Compromise of this key breaks all security guarantees

The Mathematical Relationship:

The public and private keys are not random—they are mathematically bound together. This binding guarantees:

1. Encryption-Decryption Duality: Data encrypted with a public key can only be decrypted with the corresponding private key
2. Signature-Verification Duality: Signatures created with a private key can only be verified with the corresponding public key
3. One-Way Derivation: The public key is derived from the private key, but not vice versa

This asymmetric relationship is why the system works. If deriving the private key from the public key were feasible, the entire security model would collapse.

Let's trace through exactly how key pairs solve the key distribution problem. Consider Alice wanting to send a confidential message to Bob:

Traditional Symmetric Approach (The Problem):

1. Alice creates a message
2. Alice needs Bob's secret key to encrypt
3. But Bob can't send the key securely—Eve is watching
4. Deadlock: can't establish secure channel without already having one

Asymmetric Approach (The Solution):

1. Bob generates a key pair and publishes his public key openly
2. Alice obtains Bob's public key (from a directory, website, or Bob directly)
3. Alice encrypts her message using Bob's public key
4. Alice sends the ciphertext over the insecure channel
5. Eve intercepts but cannot decrypt—she doesn't have Bob's private key
6. Bob decrypts using his private key

The critical insight: Bob's public key can be transmitted in the clear without compromising security.

Why Eve Cannot Attack This System:

The security doesn't rely on hiding any part of the communication except the private key, which never leaves Bob's possession. This is fundamentally different from symmetric encryption, where the shared secret must somehow be exchanged.

Key pairs enable another crucial capability: digital signatures. While encryption uses the public key to protect confidentiality, signatures use the private key to provide authenticity and non-repudiation.

The Signing Process:

1. Alice creates a document she wants to sign
2. Alice computes a cryptographic hash of the document
3. Alice encrypts the hash with her private key (this is the signature)
4. Alice sends the document along with the signature

The Verification Process:

1. Bob receives the document and signature
2. Bob decrypts the signature using Alice's public key
3. Bob independently computes the hash of the received document
4. If the decrypted hash matches the computed hash, the signature is valid

What Digital Signatures Guarantee:

• Authentication: Only Alice could have created this signature (only she has the private key)
• Integrity: Any modification to the document invalidates the signature (hash mismatch)
• Non-repudiation: Alice cannot deny signing (no one else could have used her private key)

Why This Works:

If Bob can successfully decrypt the signature using Alice's public key, the signature must have been created using Alice's private key. Since only Alice possesses that key, Alice must have signed the document. And since any change to the document changes its hash, the signature proves the document hasn't been altered since signing.

Asymmetric encryption relies on computationally hard problems from number theory and abstract algebra. Understanding these foundations helps appreciate why the security guarantees hold.

The Core Mathematical Concepts:

Different asymmetric algorithms use different hard problems, but they share a common structure: operations that are easy to perform but computationally infeasible to reverse without special knowledge.

Example: RSA Key Relationship

In RSA, the mathematical relationship between keys is:

n = p × q           (n is the modulus, p and q are large primes)
e × d ≡ 1 (mod φ(n))    (e is public exponent, d is private exponent)

Public Key: (n, e)
Private Key: (n, d)

Encryption: c = m^e mod n
Decryption: m = c^d mod n

The security relies on the fact that computing d from (n, e) requires factoring n into p and q. For properly chosen primes (each ~1024 bits for 2048-bit RSA), this factorization is computationally infeasible.

Key Insight: The public and private keys are related by modular arithmetic over the multiplicative group of integers modulo n. This is not random—it's a precise mathematical relationship that guarantees the encryption-decryption inverse property.

To make the concept concrete, let's examine what real public and private keys look like and how they're used in practice.

SSH Key Pair Example:

When you generate an SSH key pair with ssh-keygen -t rsa -b 4096, you create two files:

~/.ssh/id_rsa (Private Key - excerpt):

-----BEGIN RSA PRIVATE KEY-----
MIIJKAIBAAKCAgEA1J5YZ...[base64-encoded private key]...==
-----END RSA PRIVATE KEY-----

~/.ssh/id_rsa.pub (Public Key):

ssh-rsa AAAAB3NzaC1yc2E...[base64-encoded public key]...== user@hostname

The public key is typically 500-800 characters. The private key is larger and contains all the mathematical components needed for both encryption and decryption.

X.509 Certificate (TLS):

When you connect to https://example.com, the server presents a certificate containing:

• The server's public key
• The domain name the key is valid for
• The issuing Certificate Authority's signature
• Validity dates

Your browser uses the CA's public key to verify the signature, then uses the server's public key to establish an encrypted connection. This entire trust chain relies on asymmetric cryptography.

PGP/GPG Keys for Email:

PGP keys work similarly—you generate a key pair, publish your public key, and correspondents encrypt emails to you using it. Only you, with the private key, can read them.

Asymmetric encryption solved key distribution but introduced a new challenge: How do you know a public key actually belongs to who it claims?

The Man-in-the-Middle Attack:

1. Alice requests Bob's public key
2. Mallory (attacker) intercepts and substitutes her own public key
3. Alice encrypts messages with Mallory's public key, thinking it's Bob's
4. Mallory decrypts, reads, re-encrypts with Bob's real public key, and forwards
5. Neither Alice nor Bob knows their communication is compromised

The encryption itself is unbroken—but Alice encrypted to the wrong person.

Solutions to the Authenticity Problem:

Several mechanisms have evolved to bind public keys to identities:

1. Certificate Authorities (CAs): Trusted third parties that sign public keys, attesting to identity. Your browser trusts ~150 root CAs pre-installed.

2. Web of Trust: Users sign each other's keys, building a decentralized trust network (PGP model).

3. Trust on First Use (TOFU): Accept the first key presented, alert on changes (SSH model).

4. Key Fingerprints: Users manually verify key fingerprints through a secure channel (phone, in-person).

5. Public Key Infrastructure (PKI): Formal hierarchical system combining CAs, certificates, and revocation mechanisms.

Each approach has tradeoffs between convenience, scalability, and security assurances. We'll explore PKI in detail in a later module.

We've covered the foundational concepts of asymmetric encryption and key pairs. Let's consolidate the key takeaways:

What's Next:

Now that we understand the concept of key pairs, the next page explores key generation—how these mathematically-linked key pairs are actually created. We'll examine the prime number selection process in RSA, the random number generation requirements, and why weak key generation has caused real-world cryptographic failures.