Asymmetric Encryption - Learning Module

Loading content...

0/228

Encryption and Decryption

Turning Mathematics into Secrecy

We've established that asymmetric encryption uses mathematically related key pairs, and we've explored how these keys are generated. Now comes the central question: How do we actually use these keys to encrypt and decrypt data?

The answer lies in mathematical operations that are easy to perform in one direction but computationally infeasible to reverse without the private key. When Alice encrypts a message using Bob's public key, she's performing a mathematical transformation that only Bob—possessing the corresponding private key—can undo.

But there's a catch: asymmetric encryption is slow—roughly 1000x slower than symmetric encryption. It also has strict limits on how much data it can encrypt at once. These limitations might seem crippling, but they've been elegantly addressed through hybrid encryption, which combines the best properties of both asymmetric and symmetric cryptography. Understanding this design pattern is essential for grasping how real-world systems like TLS, PGP, and SSH actually work.

What You Will Learn

By the end of this page, you will understand the mathematical operations behind asymmetric encryption and decryption, why padding schemes are critical for security, the limitations that make raw asymmetric encryption impractical for large data, and how hybrid encryption elegantly solves these problems.

RSA Encryption Mathematics

RSA's elegance lies in its mathematical simplicity. The encryption and decryption operations are straightforward modular exponentiations—the security derives entirely from the difficulty of factoring the modulus.

The Core Mathematical Operations:

Given:

Public key: (n, e) where n = p × q (product of two primes)
Private key: (n, d) where e × d ≡ 1 (mod φ(n))
Message m (converted to an integer where 0 ≤ m < n)

Encryption:

c = m^e mod n

Decryption:

m = c^d mod n

Why This Works:

The mathematical foundation is Euler's theorem, which states:

For any integer a coprime to n: a^φ(n) ≡ 1 (mod n)

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

Then:

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

The encryption/decryption operations are inverses precisely because of this modular arithmetic relationship.

rsa_encryption_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
RSA Encryption/Decryption Example
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Example with small numbers (INSECURE - for illustration only):
 
Key Generation:
├── Choose primes: p = 61, q = 53
├── Compute n = 61 × 53 = 3233
├── Compute φ(n) = (61-1)(53-1) = 60 × 52 = 3120
├── Choose e = 17 (coprime to 3120)
└── Compute d = 2753 (because 17 × 2753 = 46801 = 15 × 3120 + 1)
 
Public Key: (n=3233, e=17)
Private Key: (n=3233, d=2753)
 
Encryption:
├── Message: m = 123
├── Ciphertext: c = 123^17 mod 3233
└── Result: c = 855
 
Decryption:
├── Ciphertext: c = 855
├── Plaintext: m = 855^2753 mod 3233
└── Result: m = 123 ✓
 
The message is recovered exactly!

Computational Efficiency:

The exponentiation m^e mod n would be impossibly slow if computed naively—m^65537 would require 65,537 multiplications. Instead, modular exponentiation by squaring reduces this to O(log e) multiplications:

1. Initialize: result = 1
2. While e > 0:
   a. If e is odd: result = result × m mod n
   b. m = m × m mod n
   c. e = e / 2 (integer division)
3. Return result

This transforms 65,537 multiplications into just 17 (since 65537 = 2^16 + 1).

CRT Optimization for Decryption

Using the Chinese Remainder Theorem (CRT), decryption can be performed modulo p and q separately, then combined. This is ~4x faster than standard decryption and is used in all practical implementations. The private key stores precomputed CRT values: dp = d mod (p-1), dq = d mod (q-1), qinv = q^-1 mod p.

Elliptic Curve Encryption (ECIES)

Unlike RSA, elliptic curve cryptography doesn't natively provide an encryption operation. Instead, it provides key agreement—two parties can derive a shared secret. This shared secret is then used with symmetric encryption.

ECIES (Elliptic Curve Integrated Encryption Scheme) is the standard approach for encryption using elliptic curves:

Setup:

Bob has key pair (d_B, Q_B = d_B × G)
Alice knows Bob's public key Q_B

Encryption (Alice encrypts to Bob):

Generate ephemeral key pair: (r, R = r × G)
Compute shared secret: S = r × Q_B = r × d_B × G
Derive symmetric key from S: k = KDF(S)
Encrypt message with symmetric key: c = Encrypt_k(m)
Send (R, c) to Bob

Decryption (Bob decrypts):

Receive (R, c)
Compute shared secret: S = d_B × R = d_B × r × G
Derive same symmetric key: k = KDF(S)
Decrypt: m = Decrypt_k(c)

Converting Mermaid diagram...

Why This Works:

The key insight is that both parties compute the same shared secret S:

Alice computes: S = r × Q_B = r × (d_B × G) = (r × d_B) × G
Bob computes: S = d_B × R = d_B × (r × G) = (d_B × r) × G

Since elliptic curve point multiplication is commutative, r × d_B × G = d_B × r × G.

An eavesdropper sees only R and Q_B. Computing S would require knowing either r or d_B, which requires solving the discrete logarithm problem on the curve—computationally infeasible.

Comparison with RSA:

Aspect	RSA	ECIES
Native operation	Encryption	Key agreement
Message size limit	~key_size - 42 bytes (OAEP)	Unlimited (hybrid)
Ciphertext overhead	Fixed (key size)	R + symmetric overhead
Ephemeral keys	Not required	Required per message
Forward secrecy	Possible with additional protocol	Built-in (ephemeral keys)

Forward Secrecy by Design

ECIES provides forward secrecy automatically: each message uses a fresh ephemeral key r. Even if Bob's long-term private key d_B is later compromised, past messages cannot be decrypted because the ephemeral key r was discarded after encryption. This is a significant security advantage over naive RSA encryption.

The Critical Role of Padding

Raw RSA encryption (textbook RSA) is completely insecure. Without proper padding, RSA is vulnerable to numerous attacks:

Vulnerabilities of Textbook RSA:

Why Raw RSA Fails

•Deterministic Encryption — Same plaintext always produces same ciphertext. An attacker can build a dictionary or detect repeated messages.
•Small Message Attack — If m^e < n, then c = m^e without any modular reduction, and m = c^(1/e) is trivially computable with integer roots.
•Multiplicative Property — E(m1) × E(m2) = E(m1 × m2). An attacker can forge encryptions of related messages.
•Common Modulus Attack — If the same message is encrypted with different public exponents sharing a modulus, the message can be recovered.
•Bleichenbacher Attack — Against PKCS#1 v1.5 padding, allowing decryption through error message analysis.
•Chosen Ciphertext Attacks — An attacker who can obtain decryptions of related ciphertexts can break the scheme.

OAEP: The Modern Solution

Optimal Asymmetric Encryption Padding (OAEP), specified in PKCS#1 v2.x, addresses all these vulnerabilities:

OAEP Encoding Process:

                    ┌────────────────────────────────────────┐
                    │              plaintext M               │
                    └────────────────────────────────────────┘
                                        │
      ┌─────────────────────────────────┼─────────────────────────────────┐
      │                                 ▼                                 │
      │  ┌──────────────┐    ┌────────────────────────────────┐          │
      │  │ random seed  │    │  lHash ║ PS ║ 0x01 ║ M        │          │
      │  │     (r)      │    │     (Data Block = DB)          │          │
      │  └──────────────┘    └────────────────────────────────┘          │
      │         │                           │                             │
      │         ▼                           ▼                             │
      │    ┌─────────┐                 ┌─────────┐                       │
      │    │ MGF(r)  │────────────────▶│   ⊕     │                       │
      │    └─────────┘                 └─────────┘                       │
      │                                     │                             │
      │                                     ▼                             │
      │                              maskedDB                             │
      │         ┌─────────────────────────┘                               │
      │         ▼                                                         │
      │    ┌─────────┐                                                    │
      │    │   ⊕     │◀────────────── MGF(maskedDB)                       │
      │    └─────────┘                                                    │
      │         │                                                         │
      │         ▼                                                         │
      │     maskedSeed                                                    │
      │                                                                   │
      │  Output: 0x00 ║ maskedSeed ║ maskedDB                            │
      └───────────────────────────────────────────────────────────────────┘

Why OAEP Works:

Randomization — The random seed r ensures every encryption is unique, even for identical plaintexts
All-or-Nothing Transform — Modifications to any part of the ciphertext result in random garbage when decrypted
Provable Security — OAEP has formal proofs reducing its security to the RSA problem

RSA Padding Schemes
Scheme	Status	Security Level	Use Case
No padding (textbook)	BROKEN	None	Never use
PKCS#1 v1.5	Deprecated	Weak (Bleichenbacher)	Legacy compatibility only
OAEP (PKCS#1 v2.x)	Recommended	Provably secure	Modern RSA encryption
PSS	Recommended	Provably secure	RSA signatures (not encryption)

Maximum Message Size

With OAEP using SHA-256, the maximum message size for RSA-2048 is 2048/8 - 2×32 - 2 = 190 bytes. This is why RSA is rarely used for bulk encryption—it's used to encrypt symmetric keys, which are only 16-32 bytes.

Performance Characteristics

Asymmetric encryption is computationally expensive compared to symmetric encryption. Understanding these performance characteristics is essential for system design.

RSA Performance:

RSA operations involve modular exponentiation with very large numbers:

Encryption: c = m^e mod n — typically fast because e is small (65537)
Decryption: m = c^d mod n — much slower because d is large (≈ size of n)

RSA Operation Performance (typical modern CPU)
Key Size	Encryption	Decryption	Decryption (CRT)
RSA-1024	~30,000/sec	~1,200/sec	~4,500/sec
RSA-2048	~15,000/sec	~200/sec	~800/sec
RSA-3072	~8,000/sec	~80/sec	~320/sec
RSA-4096	~5,000/sec	~35/sec	~140/sec

ECC Performance:

Elliptic curve operations are significantly faster than RSA for equivalent security:

ECC vs RSA Performance Comparison
Security Level	ECC (ECDSA P-256)	RSA Equivalent	ECC Speedup
128-bit	~20,000 signs/sec	RSA-3072: 80/sec	~250x faster
128-bit	~8,000 verifies/sec	RSA-3072: 8,000/sec	Similar
192-bit	~8,000 signs/sec	RSA-7680: 10/sec	~800x faster
256-bit	~3,000 signs/sec	RSA-15360: 1/sec	~3000x faster

Why Asymmetric is Slow

•Operations on 2048-4096 bit numbers
•Modular exponentiation complexity
•No hardware acceleration (historically)
•Memory bandwidth for large operands
•Complex algorithms (Montgomery mult.)

Why Symmetric is Fast

•Operations on 128-256 bit blocks
•Simple bit operations (XOR, shifts)
•Hardware acceleration (AES-NI)
•Cache-friendly memory access
•Parallelizable (AES-CTR, AES-GCM)

Comparative Performance:

Algorithm	Throughput	Relative Speed
AES-256-GCM	~5 GB/sec	1x (baseline)
ChaCha20-Poly1305	~3 GB/sec	0.6x
RSA-2048 encrypt	~3 MB/sec	0.0006x
RSA-2048 decrypt	~50 KB/sec	0.00001x
ECDSA P-256 sign	~400 KB/sec	0.00008x

Key Takeaway: Asymmetric operations are roughly 10,000 to 100,000 times slower than symmetric operations. This fundamental limitation shapes how cryptographic systems are designed.

Hardware Acceleration Changing the Picture

Modern CPUs increasingly include instructions for large integer multiplication and ECC operations. ARM's Cryptographic Extension and Intel's forthcoming acceleration will significantly improve asymmetric performance, but the fundamental gap will remain due to the mathematical complexity difference.

Hybrid Encryption

Hybrid encryption combines asymmetric and symmetric cryptography to get the best of both worlds:

Asymmetric: Solves key distribution, provides public-key capabilities
Symmetric: Fast bulk encryption of arbitrary-length data

The Hybrid Encryption Pattern:

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
Hybrid Encryption (Envelope Encryption)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
ENCRYPTION (Alice encrypts to Bob):
1. Generate random symmetric key: K = random_key(256 bits)
2. Encrypt message with symmetric key: c = AES-GCM(K, plaintext)
3. Encrypt symmetric key with Bob's public key: K_enc = RSA-OAEP(Bob_pub, K)
4. Output: (K_enc, c)
 
DECRYPTION (Bob decrypts):
1. Receive: (K_enc, c)
2. Decrypt symmetric key: K = RSA-OAEP-decrypt(Bob_priv, K_enc)
3. Decrypt message: plaintext = AES-GCM-decrypt(K, c)
4. Return plaintext
 
┌─────────────────────────────────────────────────────────────────┐
│                    Hybrid Encryption Structure                  │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌──────────────────┐          ┌───────────────────────────┐   │
│  │  Encrypted Key   │          │    Encrypted Data         │   │
│  │  (RSA-OAEP)      │    +     │    (AES-GCM)              │   │
│  │  256 bytes       │          │    any size               │   │
│  └──────────────────┘          └───────────────────────────┘   │
│                                                                 │
│         Fast to decrypt                Fast to decrypt          │
│      (one RSA operation)            (hardware-accelerated)     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Why Hybrid Encryption is Universal:

Virtually every real-world cryptographic system uses hybrid encryption:

TLS/HTTPS:

Client and server negotiate a symmetric 'session key' using asymmetric key exchange (RSA or ECDHE)
All application data encrypted with the symmetric session key (AES-GCM typically)

PGP/GPG Email Encryption:

Random 'session key' generated per message
Session key encrypted with recipient's RSA/ECC public key
Message body encrypted with session key using symmetric cipher

SSH:

Key exchange (DH or ECDH) establishes shared secret
Session keys derived and used for symmetric encryption of all traffic

S/MIME:

Content encryption key (CEK) is random symmetric key
CEK encrypted to each recipient using their public key
Message encrypted with CEK

Hybrid Encryption Benefits
Property	Asymmetric Only	Symmetric Only	Hybrid
Key distribution	✓ Solved	✗ Requires pre-shared key	✓ Solved
Bulk encryption speed	✗ Very slow	✓ Very fast	✓ Very fast
Message size limit	✗ < 256 bytes typical	✓ Unlimited	✓ Unlimited
Forward secrecy	✓ With ephemeral keys	✗ No	✓ With ephemeral keys
Recipient flexibility	✓ Multiple recipients easy	✗ Separate key per recipient	✓ Encrypt CEK to each

Key Encapsulation Mechanisms (KEMs)

Modern standards use 'Key Encapsulation Mechanisms' (KEMs) instead of directly encrypting symmetric keys. KEMs are designed specifically for the task of securely sharing a random symmetric key and have cleaner security proofs. Post-quantum algorithms like Kyber are KEMs, not encryption schemes.

Encryption in Practice

Let's see how asymmetric encryption is used in actual code and real-world systems.

RSA Encryption with OpenSSL:

rsa_encrypt_openssl.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Generate RSA key pair
openssl genrsa -out private.pem 2048
openssl rsa -in private.pem -pubout -out public.pem
 
# Encrypt a small file (must be < key_size - padding overhead)
echo "Secret message" > plaintext.txt
openssl pkeyutl -encrypt -pubin -inkey public.pem \
    -pkeyopt rsa_padding_mode:oaep \
    -pkeyopt rsa_oaep_md:sha256 \
    -in plaintext.txt -out ciphertext.bin
 
# Decrypt
openssl pkeyutl -decrypt -inkey private.pem \
    -pkeyopt rsa_padding_mode:oaep \
    -pkeyopt rsa_oaep_md:sha256 \
    -in ciphertext.bin -out decrypted.txt
 
# Verify
diff plaintext.txt decrypted.txt && echo "Success!"

Security Best Practices

Always use OAEP padding, never PKCS#1 v1.5 for new systems. Use authenticated encryption (AES-GCM) for the symmetric portion. Generate a fresh symmetric key for each message. Never reuse IVs/nonces. Consider using established libraries like libsodium rather than implementing crypto yourself.

Security Considerations

Beyond choosing the right algorithms and padding schemes, several security considerations affect practical asymmetric encryption systems.

Critical Security Considerations

•Side-Channel Attacks — Implementation timing, power consumption, or electromagnetic emissions can leak private key bits. Constant-time implementations and hardware protection (HSMs) mitigate this.
•Key Authenticity — Encryption protects confidentiality but not against using the wrong public key. Always verify the recipient's public key through certificates, fingerprint comparison, or trust frameworks.
•Chosen Ciphertext Attacks — An attacker who can obtain decryptions of chosen ciphertexts may extract the private key. Use IND-CCA2 secure schemes (OAEP) and never expose decryption error details.
•Key Protection — Private keys must be protected at rest (encrypted) and in use (memory protection). HSMs provide hardware-based protection for high-value keys.
•Random Number Quality — Weak randomness during key generation or encryption compromises security. Use cryptographically secure RNGs with proper entropy.
•Algorithm Agility — Systems should support algorithm upgrades. Quantum computers will eventually break RSA and ECC—plan for post-quantum migration.

Attack Vectors and Mitigations
Attack	Target	Mitigation
Timing attack	Private key	Constant-time implementation
Padding oracle	Plaintext	OAEP, don't leak error types
MITM	Public key	PKI, certificate validation
Low entropy	Key generation	Verified CSPRNG, entropy checks
Key theft	Private key	HSM, key encryption
Quantum attack	All keys	Post-quantum algorithms

Defense in Depth

Secure systems layer multiple protections: hardware security modules for key storage, certificate pinning for public key verification, perfect forward secrecy for session keys, and audit logging for operations. No single mechanism is sufficient; security comes from the combination.

Summary: Encryption and Decryption Mastery

We've explored the mechanics of asymmetric encryption and decryption. Let's consolidate the key takeaways:

Key Takeaways

•RSA uses modular exponentiation — Encryption is m^e mod n, decryption is c^d mod n, enabled by the mathematical relationship between e and d.
•ECC uses key agreement — ECIES derives a shared secret through point multiplication, then uses symmetric encryption.
•Padding is critical — Raw (textbook) RSA is completely insecure. Always use OAEP for encryption.
•Asymmetric is slow — 10,000-100,000x slower than symmetric encryption, limiting its use to small data.
•Hybrid encryption is universal — All real-world systems use asymmetric to exchange symmetric keys, then symmetric for bulk data.
•Security requires vigilance — Side channels, padding oracles, and key authentication all require careful attention.

What's Next:

Now that we understand how encryption and decryption work, the next page explores key exchange protocols—how parties securely establish shared keys, including the famous Diffie-Hellman protocol, ephemeral key exchange for forward secrecy, and modern protocols like ECDHE that power TLS.

Page Complete

You now understand the mathematical operations and practical patterns of asymmetric encryption and decryption—from RSA's modular exponentiation to ECC's key agreement, from padding schemes that prevent attacks to hybrid encryption that enables real-world systems. This knowledge is fundamental to understanding TLS, SSH, PGP, and virtually every secure protocol.

Encryption and Decryption

Turning Mathematics into Secrecy

What You Will Learn

RSA Encryption Mathematics

The Core Mathematical Operations:

Given:

Public key: (n, e) where n = p × q (product of two primes)
Private key: (n, d) where e × d ≡ 1 (mod φ(n))
Message m (converted to an integer where 0 ≤ m < n)

Encryption:

c = m^e mod n

Decryption:

m = c^d mod n

Why This Works:

The mathematical foundation is Euler's theorem, which states:

For any integer a coprime to n: a^φ(n) ≡ 1 (mod n)

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

Then:

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

The encryption/decryption operations are inverses precisely because of this modular arithmetic relationship.

rsa_encryption_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
RSA Encryption/Decryption Example
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Example with small numbers (INSECURE - for illustration only):
 
Key Generation:
├── Choose primes: p = 61, q = 53
├── Compute n = 61 × 53 = 3233
├── Compute φ(n) = (61-1)(53-1) = 60 × 52 = 3120
├── Choose e = 17 (coprime to 3120)
└── Compute d = 2753 (because 17 × 2753 = 46801 = 15 × 3120 + 1)
 
Public Key: (n=3233, e=17)
Private Key: (n=3233, d=2753)
 
Encryption:
├── Message: m = 123
├── Ciphertext: c = 123^17 mod 3233
└── Result: c = 855
 
Decryption:
├── Ciphertext: c = 855
├── Plaintext: m = 855^2753 mod 3233
└── Result: m = 123 ✓
 
The message is recovered exactly!

Computational Efficiency:

1. Initialize: result = 1
2. While e > 0:
   a. If e is odd: result = result × m mod n
   b. m = m × m mod n
   c. e = e / 2 (integer division)
3. Return result

This transforms 65,537 multiplications into just 17 (since 65537 = 2^16 + 1).

CRT Optimization for Decryption

Elliptic Curve Encryption (ECIES)

ECIES (Elliptic Curve Integrated Encryption Scheme) is the standard approach for encryption using elliptic curves:

Setup:

Bob has key pair (d_B, Q_B = d_B × G)
Alice knows Bob's public key Q_B

Encryption (Alice encrypts to Bob):

Generate ephemeral key pair: (r, R = r × G)
Compute shared secret: S = r × Q_B = r × d_B × G
Derive symmetric key from S: k = KDF(S)
Encrypt message with symmetric key: c = Encrypt_k(m)
Send (R, c) to Bob

Decryption (Bob decrypts):

Receive (R, c)
Compute shared secret: S = d_B × R = d_B × r × G
Derive same symmetric key: k = KDF(S)
Decrypt: m = Decrypt_k(c)

Converting Mermaid diagram...

Why This Works:

The key insight is that both parties compute the same shared secret S:

Alice computes: S = r × Q_B = r × (d_B × G) = (r × d_B) × G
Bob computes: S = d_B × R = d_B × (r × G) = (d_B × r) × G

Since elliptic curve point multiplication is commutative, r × d_B × G = d_B × r × G.

An eavesdropper sees only R and Q_B. Computing S would require knowing either r or d_B, which requires solving the discrete logarithm problem on the curve—computationally infeasible.

Comparison with RSA:

Aspect	RSA	ECIES
Native operation	Encryption	Key agreement
Message size limit	~key_size - 42 bytes (OAEP)	Unlimited (hybrid)
Ciphertext overhead	Fixed (key size)	R + symmetric overhead
Ephemeral keys	Not required	Required per message
Forward secrecy	Possible with additional protocol	Built-in (ephemeral keys)

Forward Secrecy by Design

The Critical Role of Padding

Raw RSA encryption (textbook RSA) is completely insecure. Without proper padding, RSA is vulnerable to numerous attacks:

Vulnerabilities of Textbook RSA:

Why Raw RSA Fails

•Deterministic Encryption — Same plaintext always produces same ciphertext. An attacker can build a dictionary or detect repeated messages.
•Small Message Attack — If m^e < n, then c = m^e without any modular reduction, and m = c^(1/e) is trivially computable with integer roots.
•Multiplicative Property — E(m1) × E(m2) = E(m1 × m2). An attacker can forge encryptions of related messages.
•Common Modulus Attack — If the same message is encrypted with different public exponents sharing a modulus, the message can be recovered.
•Bleichenbacher Attack — Against PKCS#1 v1.5 padding, allowing decryption through error message analysis.
•Chosen Ciphertext Attacks — An attacker who can obtain decryptions of related ciphertexts can break the scheme.

OAEP: The Modern Solution

Optimal Asymmetric Encryption Padding (OAEP), specified in PKCS#1 v2.x, addresses all these vulnerabilities:

OAEP Encoding Process:

                    ┌────────────────────────────────────────┐
                    │              plaintext M               │
                    └────────────────────────────────────────┘
                                        │
      ┌─────────────────────────────────┼─────────────────────────────────┐
      │                                 ▼                                 │
      │  ┌──────────────┐    ┌────────────────────────────────┐          │
      │  │ random seed  │    │  lHash ║ PS ║ 0x01 ║ M        │          │
      │  │     (r)      │    │     (Data Block = DB)          │          │
      │  └──────────────┘    └────────────────────────────────┘          │
      │         │                           │                             │
      │         ▼                           ▼                             │
      │    ┌─────────┐                 ┌─────────┐                       │
      │    │ MGF(r)  │────────────────▶│   ⊕     │                       │
      │    └─────────┘                 └─────────┘                       │
      │                                     │                             │
      │                                     ▼                             │
      │                              maskedDB                             │
      │         ┌─────────────────────────┘                               │
      │         ▼                                                         │
      │    ┌─────────┐                                                    │
      │    │   ⊕     │◀────────────── MGF(maskedDB)                       │
      │    └─────────┘                                                    │
      │         │                                                         │
      │         ▼                                                         │
      │     maskedSeed                                                    │
      │                                                                   │
      │  Output: 0x00 ║ maskedSeed ║ maskedDB                            │
      └───────────────────────────────────────────────────────────────────┘

Why OAEP Works:

Randomization — The random seed r ensures every encryption is unique, even for identical plaintexts
All-or-Nothing Transform — Modifications to any part of the ciphertext result in random garbage when decrypted
Provable Security — OAEP has formal proofs reducing its security to the RSA problem

RSA Padding Schemes
Scheme	Status	Security Level	Use Case
No padding (textbook)	BROKEN	None	Never use
PKCS#1 v1.5	Deprecated	Weak (Bleichenbacher)	Legacy compatibility only
OAEP (PKCS#1 v2.x)	Recommended	Provably secure	Modern RSA encryption
PSS	Recommended	Provably secure	RSA signatures (not encryption)

Maximum Message Size

Performance Characteristics

Asymmetric encryption is computationally expensive compared to symmetric encryption. Understanding these performance characteristics is essential for system design.

RSA Performance:

RSA operations involve modular exponentiation with very large numbers:

Encryption: c = m^e mod n — typically fast because e is small (65537)
Decryption: m = c^d mod n — much slower because d is large (≈ size of n)

RSA Operation Performance (typical modern CPU)
Key Size	Encryption	Decryption	Decryption (CRT)
RSA-1024	~30,000/sec	~1,200/sec	~4,500/sec
RSA-2048	~15,000/sec	~200/sec	~800/sec
RSA-3072	~8,000/sec	~80/sec	~320/sec
RSA-4096	~5,000/sec	~35/sec	~140/sec

ECC Performance:

Elliptic curve operations are significantly faster than RSA for equivalent security:

ECC vs RSA Performance Comparison
Security Level	ECC (ECDSA P-256)	RSA Equivalent	ECC Speedup
128-bit	~20,000 signs/sec	RSA-3072: 80/sec	~250x faster
128-bit	~8,000 verifies/sec	RSA-3072: 8,000/sec	Similar
192-bit	~8,000 signs/sec	RSA-7680: 10/sec	~800x faster
256-bit	~3,000 signs/sec	RSA-15360: 1/sec	~3000x faster

Why Asymmetric is Slow

•Operations on 2048-4096 bit numbers
•Modular exponentiation complexity
•No hardware acceleration (historically)
•Memory bandwidth for large operands
•Complex algorithms (Montgomery mult.)

Why Symmetric is Fast

•Operations on 128-256 bit blocks
•Simple bit operations (XOR, shifts)
•Hardware acceleration (AES-NI)
•Cache-friendly memory access
•Parallelizable (AES-CTR, AES-GCM)

Comparative Performance:

Algorithm	Throughput	Relative Speed
AES-256-GCM	~5 GB/sec	1x (baseline)
ChaCha20-Poly1305	~3 GB/sec	0.6x
RSA-2048 encrypt	~3 MB/sec	0.0006x
RSA-2048 decrypt	~50 KB/sec	0.00001x
ECDSA P-256 sign	~400 KB/sec	0.00008x

Key Takeaway: Asymmetric operations are roughly 10,000 to 100,000 times slower than symmetric operations. This fundamental limitation shapes how cryptographic systems are designed.

Hardware Acceleration Changing the Picture

Hybrid Encryption

Hybrid encryption combines asymmetric and symmetric cryptography to get the best of both worlds:

Asymmetric: Solves key distribution, provides public-key capabilities
Symmetric: Fast bulk encryption of arbitrary-length data

The Hybrid Encryption Pattern:

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
Hybrid Encryption (Envelope Encryption)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
ENCRYPTION (Alice encrypts to Bob):
1. Generate random symmetric key: K = random_key(256 bits)
2. Encrypt message with symmetric key: c = AES-GCM(K, plaintext)
3. Encrypt symmetric key with Bob's public key: K_enc = RSA-OAEP(Bob_pub, K)
4. Output: (K_enc, c)
 
DECRYPTION (Bob decrypts):
1. Receive: (K_enc, c)
2. Decrypt symmetric key: K = RSA-OAEP-decrypt(Bob_priv, K_enc)
3. Decrypt message: plaintext = AES-GCM-decrypt(K, c)
4. Return plaintext
 
┌─────────────────────────────────────────────────────────────────┐
│                    Hybrid Encryption Structure                  │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌──────────────────┐          ┌───────────────────────────┐   │
│  │  Encrypted Key   │          │    Encrypted Data         │   │
│  │  (RSA-OAEP)      │    +     │    (AES-GCM)              │   │
│  │  256 bytes       │          │    any size               │   │
│  └──────────────────┘          └───────────────────────────┘   │
│                                                                 │
│         Fast to decrypt                Fast to decrypt          │
│      (one RSA operation)            (hardware-accelerated)     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Why Hybrid Encryption is Universal:

Virtually every real-world cryptographic system uses hybrid encryption:

TLS/HTTPS:

Client and server negotiate a symmetric 'session key' using asymmetric key exchange (RSA or ECDHE)
All application data encrypted with the symmetric session key (AES-GCM typically)

PGP/GPG Email Encryption:

Random 'session key' generated per message
Session key encrypted with recipient's RSA/ECC public key
Message body encrypted with session key using symmetric cipher

SSH:

Key exchange (DH or ECDH) establishes shared secret
Session keys derived and used for symmetric encryption of all traffic

S/MIME:

Content encryption key (CEK) is random symmetric key
CEK encrypted to each recipient using their public key
Message encrypted with CEK

Hybrid Encryption Benefits
Property	Asymmetric Only	Symmetric Only	Hybrid
Key distribution	✓ Solved	✗ Requires pre-shared key	✓ Solved
Bulk encryption speed	✗ Very slow	✓ Very fast	✓ Very fast
Message size limit	✗ < 256 bytes typical	✓ Unlimited	✓ Unlimited
Forward secrecy	✓ With ephemeral keys	✗ No	✓ With ephemeral keys
Recipient flexibility	✓ Multiple recipients easy	✗ Separate key per recipient	✓ Encrypt CEK to each

Key Encapsulation Mechanisms (KEMs)

Encryption in Practice

Let's see how asymmetric encryption is used in actual code and real-world systems.

RSA Encryption with OpenSSL:

rsa_encrypt_openssl.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Generate RSA key pair
openssl genrsa -out private.pem 2048
openssl rsa -in private.pem -pubout -out public.pem
 
# Encrypt a small file (must be < key_size - padding overhead)
echo "Secret message" > plaintext.txt
openssl pkeyutl -encrypt -pubin -inkey public.pem \
    -pkeyopt rsa_padding_mode:oaep \
    -pkeyopt rsa_oaep_md:sha256 \
    -in plaintext.txt -out ciphertext.bin
 
# Decrypt
openssl pkeyutl -decrypt -inkey private.pem \
    -pkeyopt rsa_padding_mode:oaep \
    -pkeyopt rsa_oaep_md:sha256 \
    -in ciphertext.bin -out decrypted.txt
 
# Verify
diff plaintext.txt decrypted.txt && echo "Success!"

Security Best Practices

Security Considerations

Beyond choosing the right algorithms and padding schemes, several security considerations affect practical asymmetric encryption systems.

Critical Security Considerations

•Side-Channel Attacks — Implementation timing, power consumption, or electromagnetic emissions can leak private key bits. Constant-time implementations and hardware protection (HSMs) mitigate this.
•Key Authenticity — Encryption protects confidentiality but not against using the wrong public key. Always verify the recipient's public key through certificates, fingerprint comparison, or trust frameworks.
•Chosen Ciphertext Attacks — An attacker who can obtain decryptions of chosen ciphertexts may extract the private key. Use IND-CCA2 secure schemes (OAEP) and never expose decryption error details.
•Key Protection — Private keys must be protected at rest (encrypted) and in use (memory protection). HSMs provide hardware-based protection for high-value keys.
•Random Number Quality — Weak randomness during key generation or encryption compromises security. Use cryptographically secure RNGs with proper entropy.
•Algorithm Agility — Systems should support algorithm upgrades. Quantum computers will eventually break RSA and ECC—plan for post-quantum migration.

Attack Vectors and Mitigations
Attack	Target	Mitigation
Timing attack	Private key	Constant-time implementation
Padding oracle	Plaintext	OAEP, don't leak error types
MITM	Public key	PKI, certificate validation
Low entropy	Key generation	Verified CSPRNG, entropy checks
Key theft	Private key	HSM, key encryption
Quantum attack	All keys	Post-quantum algorithms

Defense in Depth

Summary: Encryption and Decryption Mastery

We've explored the mechanics of asymmetric encryption and decryption. Let's consolidate the key takeaways:

Key Takeaways

•RSA uses modular exponentiation — Encryption is m^e mod n, decryption is c^d mod n, enabled by the mathematical relationship between e and d.
•ECC uses key agreement — ECIES derives a shared secret through point multiplication, then uses symmetric encryption.
•Padding is critical — Raw (textbook) RSA is completely insecure. Always use OAEP for encryption.
•Asymmetric is slow — 10,000-100,000x slower than symmetric encryption, limiting its use to small data.
•Hybrid encryption is universal — All real-world systems use asymmetric to exchange symmetric keys, then symmetric for bulk data.
•Security requires vigilance — Side channels, padding oracles, and key authentication all require careful attention.

What's Next:

Page Complete