Cryptography Basics - Learning Module

Loading content...

0/227

Asymmetric Encryption

The Revolutionary Breakthrough

In 1976, Whitfield Diffie and Martin Hellman published a paper that fundamentally transformed cryptography and, by extension, the modern digital world. Their insight was radical: cryptographic keys need not be identical for encryption and decryption.

For millennia, all cryptography had been symmetric—the same key that locked a message also unlocked it. This created an insurmountable problem: how do you share a secret key with someone you've never met, across potentially hostile channels? Armies employed couriers. Banks used armored vehicles. The key distribution problem seemed fundamental to the nature of secrecy itself.

Diffie and Hellman proposed something that seemed almost magical: a system where you could shout your encryption key from the rooftops, publish it on billboards, broadcast it to the world—yet only you could decrypt the messages encrypted with it. This is asymmetric encryption, also called public-key cryptography, and it is the foundation upon which digital trust, secure commerce, and modern operating system security are built.

What You Will Learn

By the end of this page, you will understand the mathematical foundations of asymmetric encryption, master the RSA and Elliptic Curve algorithms, comprehend how public-key cryptography solves the key distribution problem, understand the performance tradeoffs that lead to hybrid encryption, and recognize how asymmetric encryption secures operating systems from boot to network.

The Key Insight

Asymmetric encryption rests on the mathematical concept of trapdoor one-way functions: operations that are easy to compute in one direction but computationally infeasible to reverse—unless you possess a secret "trapdoor."

The Fundamental Concept:

Each entity generates a key pair:

Public key (PK): Freely distributed, used by others to encrypt messages TO you
Private key (SK): Kept absolutely secret, used to decrypt messages FROM others

The mathematical relationship ensures:

Anyone with PK can encrypt a message
Only the holder of SK can decrypt it
Computing SK from PK is computationally infeasible

This elegant asymmetry solves the key distribution problem: to send me a secret message, you only need my public key—which I can safely email, post on my website, or include in a directory. No secure channel is needed for key exchange.

Symmetric vs. Asymmetric Encryption
Property	Symmetric Encryption	Asymmetric Encryption
Keys	Single shared secret key	Key pair: public + private
Key distribution	Requires secure channel	Public key can be broadcast openly
Speed	Very fast (hardware accelerated)	100-1000x slower
Key size for equivalent security	128-256 bits	2048-4096 bits (RSA), 256-384 bits (ECC)
Use case	Bulk data encryption	Key exchange, signatures, small data
Scalability	O(n²) keys for n parties	O(n) key pairs for n parties

The Scalability Advantage

Consider 1000 users who each need to communicate securely with every other user. With symmetric encryption, you need nearly 500,000 unique shared keys (n(n-1)/2). With asymmetric encryption, you need just 1000 key pairs. Each user generates one pair, publishes their public key, and can communicate securely with anyone. This scalability enabled the global PKI that secures the internet.

Mathematical Foundations

Asymmetric encryption relies on mathematical problems that are believed to be computationally hard—problems where no efficient algorithm is known despite decades of research by mathematicians and computer scientists.

The Integer Factorization Problem:

Given two large prime numbers p and q, their product n = p × q is easy to compute. However, given only n, finding the original primes p and q is extremely difficult for large values. This asymmetry is the foundation of RSA encryption.

Multiplying two 1024-bit primes: microseconds
Factoring their 2048-bit product: estimated millions of years on current hardware

The Discrete Logarithm Problem:

In a cyclic group G with generator g, given g^x (mod p), finding x is computationally hard. This underlies Diffie-Hellman key exchange and the Digital Signature Algorithm (DSA).

The Elliptic Curve Discrete Logarithm Problem (ECDLP):

On an elliptic curve, given a base point G and a point P = k × G (scalar multiplication), finding k is computationally hard. Elliptic curve cryptography provides equivalent security to RSA with much smaller keys.

Why "Hard" Matters:

These problems are in the complexity class believed to be outside P (polynomial time solvable). No polynomial-time algorithms are known. However:

This is not proven—P vs NP is unsolved
Quantum computers threaten these assumptions (Shor's algorithm)
"Hard on average" is not the same as "always hard"

Hardness Assumptions Underlying Common Algorithms
Algorithm	Hardness Assumption	Quantum Threat?
RSA	Integer factorization	Yes (Shor's algorithm)
DH, DSA	Discrete logarithm (finite fields)	Yes (Shor's algorithm)
ECDH, ECDSA	Elliptic curve discrete logarithm	Yes (Shor's algorithm)
NTRU, CRYSTALS-Kyber	Lattice problems (Ring-LWE)	No (post-quantum candidate)
SPHINCS+	Hash-based signatures	No (post-quantum)

The Quantum Threat

Shor's algorithm, running on a sufficiently powerful quantum computer, can solve factorization and discrete logarithm problems in polynomial time—completely breaking RSA, DH, and ECC. While such computers don't yet exist, the threat is real enough that NIST has standardized post-quantum algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium). Long-term secrets encrypted today should consider quantum-resistant algorithms.

The RSA Algorithm

RSA, named after its inventors Rivest, Shamir, and Adleman (1977), was the first practical public-key cryptosystem and remains widely deployed. Understanding RSA illuminates the core concepts of asymmetric encryption.

Key Generation:

Choose two large prime numbers p and q (each typically 1024+ bits)
Compute n = p × q (the modulus, 2048+ bits)
Compute φ(n) = (p-1)(q-1) (Euler's totient function)
Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (commonly e = 65537)
Compute d such that d × e ≡ 1 (mod φ(n)) (modular multiplicative inverse)

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

Encryption: Ciphertext c = m^e mod n (where m is the plaintext message as an integer < n)

Decryption: Plaintext m = c^d mod n

Why It Works:

By Euler's theorem, for any m coprime to n: m^φ(n) ≡ 1 (mod n)

Since d × e ≡ 1 (mod φ(n)), we have d × e = 1 + k × φ(n) for some integer k.

Therefore: c^d = (m^e)^d = m^(ed) = m^(1 + k×φ(n)) = m × (m^φ(n))^k ≡ m × 1 ≡ m (mod n)

rsa_example.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// RSA Key Generation and Operations (Simplified)
 
// Key Generation
function RSA_KEYGEN(bits):
    // Step 1: Generate two large random primes
    p = generate_prime(bits / 2)  // e.g., 1024 bits each
    q = generate_prime(bits / 2)
    
    // Step 2: Compute modulus
    n = p * q  // 2048-bit modulus
    
    // Step 3: Compute Euler's totient
    phi_n = (p - 1) * (q - 1)
    
    // Step 4: Choose public exponent
    e = 65537  // Common choice: 2^16 + 1 (Fermat prime)
    // Must verify: gcd(e, phi_n) == 1
    
    // Step 5: Compute private exponent
    d = modular_inverse(e, phi_n)
    // d * e ≡ 1 (mod phi_n)
    
    public_key = (n, e)
    private_key = (n, d)
    
    // Securely erase p, q, phi_n from memory!
    return (public_key, private_key)
 
// Encryption (anyone can do with public key)
function RSA_ENCRYPT(message, public_key):
    (n, e) = public_key
    m = bytes_to_integer(message)
    if m >= n:
        error("Message too long for key size")
    c = modular_exponentiation(m, e, n)
    return c
 
// Decryption (only private key holder)
function RSA_DECRYPT(ciphertext, private_key):
    (n, d) = private_key
    m = modular_exponentiation(c, d, n)
    return integer_to_bytes(m)

Critical: Never Use Textbook RSA

Raw RSA as described (m^e mod n) is deterministic and vulnerable to numerous attacks. Real implementations MUST use padding schemes: OAEP (Optimal Asymmetric Encryption Padding) for encryption, PSS (Probabilistic Signature Scheme) for signatures. These add randomness and structure that prevent chosen-ciphertext attacks, preserve semantic security, and are mandatory in all standards.

RSA Key Sizes:

RSA security depends directly on key size (the modulus n). Larger keys exponentially increase factorization difficulty but also slow operations:

Key Size	Security Level	Status	Performance
1024 bits	~80 bits	Deprecated (factorable)	Fast
2048 bits	~112 bits	Minimum acceptable	Moderate
3072 bits	~128 bits	Recommended	Slower
4096 bits	~140+ bits	High security	Slow

Note that RSA key sizes are much larger than AES key sizes for equivalent security. A 256-bit AES key provides security comparable to a 15,360-bit RSA key—which is impractical. This is why we use hybrid encryption.

Elliptic Curve Cryptography (ECC)

Elliptic Curve Cryptography, proposed by Neal Koblitz and Victor Miller in 1985, provides the same security as RSA with dramatically smaller keys. This efficiency makes ECC essential for resource-constrained environments and modern protocols.

The Elliptic Curve:

An elliptic curve (for cryptography) is defined by the equation:

y² = x³ + ax + b (mod p)

Where p is a large prime and 4a³ + 27b² ≠ 0 (to ensure no singular points).

Points on this curve, along with a "point at infinity" (identity element), form a group under an operation called "point addition."

Scalar Multiplication:

Given a base point G on the curve and an integer k, we can compute P = k × G (adding G to itself k times). This is efficient.

However, given G and P, finding k is the Elliptic Curve Discrete Logarithm Problem—believed to be much harder than the finite field discrete log problem.

Key Generation (ECDH/ECDSA):

Select a standardized curve (e.g., P-256, P-384, Curve25519)
The curve defines a base point G and its order n
Generate random integer d in [1, n-1] (private key)
Compute Q = d × G (public key point)

Private key: d (256 bits for P-256) Public key: Q (point on curve, ≈512 bits uncompressed for P-256)

RSA vs. ECC Key Size Comparison
Security Level	Symmetric Equivalent	RSA Key Size	ECC Key Size
80 bits	2-Key 3DES	1024 bits	160-223 bits
112 bits	3DES	2048 bits	224-255 bits
128 bits	AES-128	3072 bits	256-383 bits
192 bits	AES-192	7680 bits	384-511 bits
256 bits	AES-256	15360 bits	512+ bits

Why ECC Matters

A 256-bit ECC key provides security equivalent to a 3072-bit RSA key, but operations are faster and keys are smaller. This matters enormously for mobile devices, IoT, and TLS handshakes where public-key operations occur frequently. Modern protocols (TLS 1.3, Signal, WireGuard) default to ECC. Curve25519 (designed by Daniel Bernstein) is particularly popular for its security properties and constant-time implementation.

Common Standardized Curves

•P-256 (secp256r1) — NIST curve, 128-bit security, widely deployed in TLS, code signing. Some concerns about parameter generation but thoroughly studied.
•P-384 (secp384r1) — NIST curve, 192-bit security, required for NSA Suite B 'TOP SECRET' level.
•Curve25519 — Designed by djb for ECDH, 128-bit security, constant-time by design, simpler to implement safely. Used in Signal, WireGuard, and increasingly in TLS.
•Ed25519 — Edwards curve related to Curve25519, optimized for signatures. Fast, deterministic, constant-time. Used in SSH, Signal.
•secp256k1 — Used by Bitcoin and Ethereum for signatures. Not a NIST curve; chosen for transparency and efficiency.

Hybrid Encryption

Asymmetric encryption is slow—100 to 1000 times slower than symmetric encryption. RSA encryption with a 2048-bit key can only encrypt about 200 bytes of data directly. Encrypting a large file byte-by-byte with RSA would take hours instead of milliseconds.

The solution is hybrid encryption: use asymmetric cryptography to exchange a symmetric key, then use fast symmetric encryption for the actual data. This combines the key distribution advantages of asymmetric cryptography with the speed of symmetric algorithms.

The Hybrid Approach:

Sender generates a random symmetric key (e.g., 256-bit AES key)
Sender encrypts the symmetric key with recipient's public key (RSA or ECC)
Sender encrypts the actual data with the symmetric key (AES-GCM)
Sender transmits both encrypted key and encrypted data
Recipient decrypts symmetric key with their private key
Recipient decrypts data with the recovered symmetric key

This pattern underlies virtually all secure communication: TLS, SSH, PGP, Signal, and more.

hybrid_encryption.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Hybrid Encryption Process
 
function HYBRID_ENCRYPT(plaintext, recipient_public_key):
    // Step 1: Generate random symmetric key
    symmetric_key = generate_random_bytes(32)  // 256-bit key
    
    // Step 2: Encrypt symmetric key with asymmetric algorithm
    // Using RSA-OAEP or ECIES
    encrypted_key = RSA_ENCRYPT_OAEP(symmetric_key, recipient_public_key)
    
    // Step 3: Encrypt data with symmetric algorithm
    nonce = generate_random_bytes(12)  // For AES-GCM
    ciphertext, tag = AES_GCM_ENCRYPT(plaintext, symmetric_key, nonce)
    
    // Step 4: Securely erase symmetric key from memory
    secure_zero(symmetric_key)
    
    // Return combined encrypted package
    return {encrypted_key, nonce, ciphertext, tag}
 
function HYBRID_DECRYPT(package, recipient_private_key):
    // Step 1: Decrypt symmetric key
    symmetric_key = RSA_DECRYPT_OAEP(package.encrypted_key, recipient_private_key)
    
    // Step 2: Decrypt data with symmetric key
    plaintext = AES_GCM_DECRYPT(
        package.ciphertext, 
        symmetric_key, 
        package.nonce,
        package.tag
    )
    
    // Step 3: Securely erase symmetric key
    secure_zero(symmetric_key)
    
    return plaintext

Key Encapsulation Mechanisms (KEMs)

Modern cryptography prefers Key Encapsulation Mechanisms (KEMs) over direct encryption for hybrid schemes. A KEM produces a random shared secret and its encapsulation in one step, avoiding the complexities of encrypting an already-random key. ECIES (Elliptic Curve Integrated Encryption Scheme) and the post-quantum CRYSTALS-Kyber are KEMs. NIST's post-quantum standards are KEM-based.

Performance Comparison

•AES-256-GCM: ~10 GB/s with AES-NI
•RSA-2048 encrypt: ~100,000 ops/sec
•RSA-2048 decrypt: ~5,000 ops/sec
•ECDH P-256: ~20,000 key exchanges/sec
•Ed25519 sign: ~50,000 signatures/sec

Best Practices

•Always use hybrid encryption for data
•Prefer ECC over RSA for new systems
•Use AEAD modes (AES-GCM) for symmetric part
•Generate fresh symmetric keys per session
•Securely erase keys after use

Key Exchange Protocols

Beyond encrypting data directly, asymmetric cryptography enables key agreement: two parties can compute a shared secret over a public channel without ever transmitting the secret itself.

Diffie-Hellman Key Exchange:

The original key exchange protocol (1976) remains foundational:

Alice and Bob agree on public parameters: prime p and generator g
Alice chooses random secret a, computes A = g^a mod p, sends A to Bob
Bob chooses random secret b, computes B = g^b mod p, sends B to Alice
Alice computes secret: s = B^a mod p = g^(ab) mod p
Bob computes secret: s = A^b mod p = g^(ab) mod p

Both arrive at the same shared secret s, but an eavesdropper seeing only A and B cannot compute s (this is the Computational Diffie-Hellman problem).

Elliptic Curve Diffie-Hellman (ECDH):

The same concept on elliptic curves:

Agree on curve parameters and base point G
Alice: private a, public A = a × G
Bob: private b, public B = b × G
Shared secret: a × B = b × A = ab × G

ECDH with Curve25519 (called X25519) is the modern standard.

ecdh_key_exchange.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// ECDH Key Exchange (e.g., X25519)
 
// Both parties agree on curve parameters
curve = Curve25519
 
// Alice generates her key pair
alice_private = generate_random_32_bytes()  // 256-bit scalar
alice_public = scalar_multiply(alice_private, curve.base_point)
 
// Bob generates his key pair
bob_private = generate_random_32_bytes()
bob_public = scalar_multiply(bob_private, curve.base_point)
 
// Exchange public keys (over insecure channel)
// Alice receives bob_public
// Bob receives alice_public
 
// Alice computes shared secret
shared_secret_alice = scalar_multiply(alice_private, bob_public)
 
// Bob computes shared secret
shared_secret_bob = scalar_multiply(bob_private, alice_public)
 
// Both compute the same shared secret!
assert(shared_secret_alice == shared_secret_bob)
 
// Derive encryption key from shared secret (using KDF)
encryption_key = HKDF(shared_secret, salt="", info="encryption key", length=32)

Authentication Required!

Plain Diffie-Hellman is vulnerable to man-in-the-middle attacks! An attacker can establish separate key exchanges with each party, relaying messages between them. Real protocols (TLS, Signal) combine DH with signatures or pre-shared public keys to authenticate the exchange. Never use unauthenticated DH.

Perfect Forward Secrecy (PFS):

A critical property achieved through ephemeral key exchange. If each session uses freshly generated DH keys (ephemeral-ephemeral), compromising long-term keys doesn't reveal past session keys.

Static-Static DH: Both parties use long-term keys. Compromising either reveals all sessions.
Ephemeral-Ephemeral DH: Fresh keys each session. Compromising long-term keys only affects future authentication, not past confidentiality.

Modern TLS (1.3) mandates ephemeral key exchange for forward secrecy. Even if an attacker records encrypted traffic today and compromises the server's key next year, they cannot decrypt the recorded sessions.

Asymmetric Encryption in Operating Systems

Operating systems leverage asymmetric cryptography throughout their security architecture, from boot verification to network connections to software updates.

Key OS Applications

•Secure Boot — UEFI firmware verifies bootloader signatures using public keys embedded in firmware. Only code signed by trusted authorities (Microsoft, distro vendors) can execute during boot, preventing rootkits from compromising the boot chain.
•Code Signing — Kernel modules, device drivers, and applications are signed by developers. The OS verifies signatures before loading/executing, ensuring integrity and authenticity. Windows requires signed drivers in 64-bit mode.
•Package Management — Linux package managers (apt, yum, pacman) verify package signatures against distribution keys. This prevents attackers who compromise mirrors from injecting malicious packages.
•TLS in Kernel — kTLS (kernel TLS) implements TLS encryption in the kernel for network sockets, using asymmetric cryptography for handshakes and symmetric for data. This enables hardware offload and zero-copy sending.
•SSH Authentication — The most common SSH authentication uses public-key cryptography. Users generate key pairs; the public key is placed on servers. Authentication proves possession of the private key without transmitting it.
•Full Disk Encryption Key Sealing — TPM chips can seal disk encryption keys to specific system states using asymmetric cryptography, preventing key access if the boot configuration changes.

ssh_key_auth.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# SSH Public Key Authentication (common OS task)
 
# Generate Ed25519 key pair (recommended)
ssh-keygen -t ed25519 -C "user@host"
# Creates: ~/.ssh/id_ed25519 (private) and ~/.ssh/id_ed25519.pub (public)
 
# Copy public key to remote server
ssh-copy-id user@server
# Appends public key to server's ~/.ssh/authorized_keys
 
# Now SSH authenticates by proving private key ownership
# Client signs a challenge from server
# Server verifies signature using stored public key
 
# RSA alternative (larger keys required for security)
ssh-keygen -t rsa -b 4096 -C "user@host"
 
# Verify server host key (protects against MITM)
# On first connection, client stores server's public key
# Future connections verify server hasn't changed
cat ~/.ssh/known_hosts  # View stored server keys

The Certificate Authority System

TLS security relies on the CA (Certificate Authority) system. CAs are trusted third parties whose root certificates are bundled with operating systems. Servers obtain certificates signed by CAs, and clients verify the certificate chain back to a trusted root. This is how your browser knows it's really connected to your bank—the bank's certificate is signed by a CA your OS trusts.

Summary: Asymmetric Encryption

We've explored the revolutionary concept of public-key cryptography—the breakthrough that solved the key distribution problem and enabled secure communication at internet scale.

Key Takeaways

•Asymmetric encryption uses key pairs: public for encryption, private for decryption — This eliminates the need for secure key distribution channels.
•Security rests on hard mathematical problems — Integer factorization (RSA), discrete logarithm (DH), elliptic curve discrete log (ECC). Quantum computers threaten all current asymmetric algorithms.
•RSA remains widely deployed but requires large keys — 2048+ bits minimum, prefer 3072+. Always use OAEP padding, never textbook RSA.
•ECC provides equivalent security with smaller keys — 256-bit ECC ≈ 3072-bit RSA. Curve25519/Ed25519 are modern, safe choices.
•Hybrid encryption combines asymmetric and symmetric cryptography — Asymmetric for key exchange, symmetric for data. This is how all real systems work.
•Diffie-Hellman enables key agreement without transmitting secrets — Ephemeral DH provides forward secrecy, protecting past sessions if long-term keys are compromised.
•Operating systems use asymmetric crypto extensively — Secure boot, code signing, package verification, SSH, TLS, TPM key sealing.

Looking Ahead:

Asymmetric encryption provides confidentiality through encryption and enables key exchange, but how can we verify that data hasn't been tampered with? How can we prove that a message was sent by a specific party? The next page explores hash functions—one-way functions that create unique "fingerprints" of data, enabling integrity verification and forming the foundation for digital signatures.

Page Complete

You now understand asymmetric encryption—from the mathematical hardness assumptions that secure it, through RSA and ECC algorithms, to hybrid encryption and key exchange protocols. This knowledge is essential for understanding secure boot, code signing, TLS, and the cryptographic trust infrastructure that secures modern computing.