Asymmetric Encryption - Learning Module

Loading content...

0/240

Key Generation

The Genesis of Cryptographic Keys

Every secure connection on the internet begins with key generation. When a certificate authority issues an SSL certificate, when you create an SSH key for server access, when a bank generates keys for transaction signing—key generation is the foundational act that enables all subsequent cryptographic operations.

But key generation is far more than calling generateKeyPair() in your favorite library. It's a process that must satisfy rigorous mathematical constraints while drawing from unpredictable sources of randomness. A single weak key—generated from a flawed random number generator, using insufficient entropy, or following a predictable pattern—can compromise an entire cryptosystem.

History is littered with catastrophic failures caused by broken key generation. In 2012, researchers discovered that 0.2% of TLS certificates shared private keys with at least one other certificate—because devices with poor random number generators had produced identical 'random' primes. In 2008, Debian's OpenSSL package had a bug that reduced the entropy of generated keys to just 15 bits—making them trivially brute-forceable. Understanding key generation isn't academic; it's essential for security.

What You Will Learn

By the end of this page, you will understand how asymmetric key pairs are generated—from prime number selection in RSA to curve point generation in ECC. You'll learn why randomness is critical, how entropy is measured and gathered, and what can go wrong when key generation is implemented poorly.

The Key Generation Process Overview

Key generation in asymmetric cryptography follows a general pattern, though the specifics vary by algorithm:

Step 1: Gather Entropy Collect random data from unpredictable sources (hardware events, user input, system state). This entropy is the foundation of key security.

Step 2: Seed Cryptographic RNG Use gathered entropy to initialize a cryptographically secure pseudo-random number generator (CSPRNG) that will produce the random values needed for key creation.

Step 3: Generate First Key Component Create the primary mathematical object—large primes for RSA, a random scalar for ECC, or other algorithm-specific values.

Step 4: Derive Additional Components Compute related values that form the complete key pair. These are mathematically linked to the first component.

Step 5: Validate Key Properties Verify the generated key meets security requirements (sufficient size, passes primality tests, not a weak key, etc.).

Step 6: Output Key Pair Encode and output the public and private keys in standard formats (PEM, DER, JWK, etc.).

Converting Mermaid diagram...

Critical Insight: The security of the entire key generation process rests on the quality of randomness. Every other step is deterministic given the random inputs. If an attacker can predict or reproduce the random values, they can regenerate your private key.

This is why cryptographic key generation must use cryptographically secure random number generators rather than standard library random functions like Math.random() or random.random().

Never Use Standard Random Functions

JavaScript's Math.random(), Python's random module, and similar standard library functions are NOT cryptographically secure. They use predictable algorithms and insufficient seed entropy. Always use crypto.getRandomValues() (JS), secrets module (Python), or /dev/urandom (Unix) for cryptographic operations.

Entropy and Random Number Generation

Entropy is the measure of unpredictability in a system. In cryptography, we measure entropy in bits—the number of binary decisions needed to guess a value. True security requires that attackers cannot predict or reduce the space of possible keys.

Sources of Entropy:

Modern operating systems gather entropy from multiple sources and maintain an entropy pool that is continuously replenished:

Hardware and Software Entropy Sources

•Hardware RNG (HRNG) — Dedicated chips that measure physical phenomena like thermal noise, shot noise in semiconductors, or radioactive decay. Intel's RDRAND instruction provides CPU-level random bits.
•Interrupt Timing — Variations in interrupt delivery timing from disk I/O, network packets, and user input. These microsecond-level fluctuations are unpredictable.
•Mouse/Keyboard Input — The exact timing and coordinates of user actions are impossible to predict, providing high-quality entropy.
•Disk Access Patterns — Seek times and rotational latency in HDDs vary slightly with physical conditions. SSDs have less entropy but still contribute timing variations.
•Network Traffic — Packet arrival times and contents from external sources contribute unpredictability.
•System State — Memory contents, process IDs, timestamps, and other state can provide initial entropy during boot.

Entropy Quality by Source
Entropy Source	Bits/Event	Rate	Quality
Hardware RNG (RDRAND)	~256 bits	~500 MB/s	Excellent
Keyboard timing	~4-8 bits	Sporadic	Good
Mouse movement	~8-12 bits	Sporadic	Good
Disk I/O timing	~4-6 bits	Moderate	Good
Network packet timing	~2-4 bits	Variable	Moderate
System clock (at boot)	~32-40 bits	One-time	Moderate

Cryptographically Secure PRNGs (CSPRNGs):

Pure random sources often can't generate bits fast enough for cryptographic needs. CSPRNGs solve this by:

Seeding with true random entropy
Using a deterministic algorithm to expand the seed into a long sequence
Ensuring the output is indistinguishable from true random to any polynomial-time attacker
Continuously mixing in fresh entropy when available

Common CSPRNGs:

Algorithm	Used By	Description
ChaCha20	Linux kernel (since 4.8)	Stream cipher adapted as RNG
Fortuna	macOS, FreeBSD	Entropy accumulation with multiple pools
CTR_DRBG	NIST standard	AES in counter mode with reseeding
Yarrow	Older macOS	Predecessor to Fortuna
/dev/urandom	Unix systems	Kernel interface to CSPRNG

/dev/random vs /dev/urandom

On Linux, /dev/random blocks when entropy is low, while /dev/urandom never blocks. For most cryptographic purposes, /dev/urandom is preferred—it's properly seeded after boot and blocking gives no security advantage while causing availability issues. The distinction matters mainly for early-boot scenarios before sufficient entropy is gathered.

RSA Key Generation

RSA key generation is perhaps the most well-known asymmetric key generation process. It creates a key pair based on the difficulty of factoring large numbers.

The RSA Key Generation Algorithm:

rsa_key_generation.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
RSA Key Generation Algorithm (simplified)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
INPUT: key_size (e.g., 2048 bits)
OUTPUT: (public_key, private_key)
 
1. CHOOSE e (public exponent)
   ├── Typically e = 65537 (0x10001)
   ├── Must be odd and > 1
   └── Small e enables fast encryption
 
2. GENERATE prime p
   ├── Generate random odd number of key_size/2 bits
   ├── Test if prime using Miller-Rabin
   ├── Ensure gcd(p-1, e) = 1
   └── Repeat until valid prime found
 
3. GENERATE prime q
   ├── Same process as step 2
   ├── Ensure q ≠ p
   └── Ensure |p - q| is sufficiently large
 
4. COMPUTE modulus n
   └── n = p × q
 
5. COMPUTE totient φ(n)
   └── φ(n) = (p-1) × (q-1)
 
6. COMPUTE private exponent d
   └── d = e⁻¹ mod φ(n)  (modular inverse)
 
7. OUTPUT key pair
   ├── Public Key: (n, e)
   └── Private Key: (n, d, p, q)  [p, q often stored for optimization]

Deep Dive into Each Step:

Step 1: Choosing the Public Exponent (e)

The public exponent e is typically fixed at 65537 (2¹⁶ + 1) because:

It's prime (satisfies gcd requirements)
It has only two 1-bits in binary (10000000000000001), making exponentiation fast
It's large enough to prevent certain attacks on small e

Other values like 3 or 17 work mathematically but increase vulnerability to certain padding attacks.

Step 2-3: Prime Generation

This is the computationally expensive part. To generate a random prime of n bits:

Prime Generation Process

•Generate Candidate — Create a random odd number of the required bit length. Set the top two bits to 1 to ensure the product n has the correct size.
•Trial Division — Quick check against small primes (2, 3, 5, 7, 11...) eliminates ~80% of composites cheaply.
•Miller-Rabin Test — Probabilistic primality test repeated multiple times. With 40 rounds, probability of false positive is < 2⁻⁸⁰.
•Additional Checks — Ensure gcd(p-1, e) = 1 and that p passes any algorithm-specific requirements.
•Iterate if Failed — On average, ln(n) candidates must be tested to find a prime near n.

RSA Key Sizes and Generation Time
Key Size	Prime Size	Typical Generation Time	Security Level
1024 bits	512 bits each	~100ms	Deprecated (≈80-bit)
2048 bits	1024 bits each	~500ms	Minimum recommended (≈112-bit)
3072 bits	1536 bits each	~2 seconds	Good until 2030 (≈128-bit)
4096 bits	2048 bits each	~10 seconds	High security (≈140-bit)

Why Store p and q?

While only (n, d) are needed for decryption, storing p and q enables Chinese Remainder Theorem (CRT) optimization, making decryption ~4x faster. This is standard practice in all modern implementations. The private key file typically contains the full set: (n, e, d, p, q, dp, dq, qinv).

Elliptic Curve Key Generation

Elliptic Curve Cryptography (ECC) offers equivalent security to RSA with much smaller key sizes. ECC key generation is also significantly faster because it doesn't require generating large primes.

ECC Key Generation Process:

Select a Curve — Choose a standardized elliptic curve (P-256, P-384, Curve25519, etc.). The curve defines the mathematical group for operations.
Generate Private Key — Select a random integer d in the range [1, n-1], where n is the curve's order (the number of points on the curve).
Compute Public Key — Calculate Q = d × G, where G is the curve's generator point and × denotes scalar multiplication on the curve.
Output Key Pair — Private key is d (a number). Public key is Q (a point on the curve, represented as (x, y) coordinates).

ecdsa_key_generation.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ECDSA Key Generation (P-256 example)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Curve Parameters (NIST P-256):
├── p = 2²⁵⁶ - 2²²⁴ + 2¹⁹² + 2⁹⁶ - 1  (field prime)
├── n = Order of base point G (≈ 2²⁵⁶)
├── G = Generator point (x, y coordinates)
├── a, b = Curve equation coefficients (y² = x³ + ax + b mod p)
└── h = Cofactor = 1
 
Key Generation:
1. d ← random integer in [1, n-1]     // Private key
2. Q ← d × G                           // Public key (point multiplication)
3. Verify Q ≠ O (point at infinity)
4. Verify Q is on the curve: Q_y² = Q_x³ + aQ_x + b mod p
 
Output:
├── Private Key: d (256-bit integer)
└── Public Key: Q = (Q_x, Q_y) (two 256-bit coordinates)

ECC Advantages

•256-bit ECC ≈ 3072-bit RSA security
•Key generation is ~100x faster
•Smaller keys = less storage and bandwidth
•Faster operations on mobile/IoT devices
•Better suited for constrained environments

ECC Considerations

•Curve selection matters (some curves suspect)
•Implementation errors can leak private key
•Deterministic nonce generation is critical
•Vulnerable to quantum attacks (like RSA)
•Patent concerns (mostly expired now)

Popular Elliptic Curves:

Curve	Key Size	Organization	Notes
P-256 (secp256r1)	256 bits	NIST	Most widely used, TLS default
P-384 (secp384r1)	384 bits	NIST	Higher security, government use
P-521 (secp521r1)	521 bits	NIST	Highest NIST curve
Curve25519	256 bits	Bernstein	Designed for security and speed, used in Signal, SSH
secp256k1	256 bits	Certicom	Used by Bitcoin, Ethereum
Ed25519	256 bits	Bernstein	Optimized for signatures, modern SSH

Why Curve25519 and Ed25519 Are Popular:

These curves were designed by Daniel J. Bernstein with explicit security and performance goals:

No unexplained constants (unlike NIST curves which have 'nothing up my sleeve' concerns)
Resistant to timing side-channel attacks by design
Extremely fast implementations possible
Simpler, harder to implement incorrectly

Modern Best Practice

For new systems, prefer Curve25519/X25519 for key exchange and Ed25519 for signatures. These offer excellent security margins, fast operations, and implementations that are resistant to common vulnerabilities. Many modern protocols (WireGuard, Signal, modern SSH) have adopted these as defaults.

Key Validation and Testing

Generated keys must be validated to ensure they're secure and correctly formed. Weak or malformed keys can completely undermine security.

RSA Key Validation Checks:

RSA Key Validation Requirements

•Size Check — n must be at least 2048 bits. Smaller keys are breakable with moderate resources.
•Primality Verification — p and q should be probable primes (Miller-Rabin with sufficient rounds).
•Distance Check — |p - q| should be large. If p ≈ q, Fermat's factorization method breaks the key quickly.
•Public Exponent Check — e should be odd, > 1, and coprime to φ(n). Standard is e = 65537.
•Private Exponent Check — d = e⁻¹ mod φ(n) should satisfy e·d ≡ 1 (mod φ(n)).
•Consistency Check — For a random message m, verify that (m^e)^d ≡ m (mod n).
•Bit Length of Factors — p and q should each be approximately half the key size ± small margin.

ECC Key Validation Checks:

ECC Key Validation Requirements

•Private Key Range — d must be in [1, n-1] where n is the curve order.
•Public Key on Curve — Q must satisfy the curve equation: Q_y² ≡ Q_x³ + aQ_x + b (mod p).
•Non-identity Check — Q must not be the point at infinity (O).
•Subgroup Check — n × Q = O (verifies Q is in the correct subgroup for curves with cofactor > 1).
•Consistency Check — Verify Q = d × G for the generated pair.
•Coordinate Range — Q_x and Q_y must be in [0, p-1].

Testing for Weak Keys:

Some keys are mathematically valid but cryptographically weak:

Weakness	Description	Detection
Small factors	p or q have small prime factors	Trial division up to 10⁶
Close primes		p-q
Common primes	Same p or q reused across keys	Compare against known weak primes
Low entropy	Key derived from predictable source	Entropy analysis of generation
Small d	Private exponent is small	Verify d > n^0.25
Special structure	Keys from faulty implementations	ROCA vulnerability test

The ROCA Vulnerability

In 2017, the ROCA attack revealed that RSA keys generated by Infineon chips could be factored efficiently due to a flaw in the prime generation algorithm. Over 750,000 Estonian e-Residency cards and millions of other devices were affected. This is why key validation and source verification matter.

Key Generation Failures in Practice

Understanding past key generation failures illuminates why the theoretical requirements matter so much in practice.

Case Study 1: The Debian OpenSSL Bug (2008)

A Debian developer removed lines of code in OpenSSL that they thought were causing Valgrind warnings. Unfortunately, these lines were the primary source of entropy for key generation. The result:

Random number generator seeded only with process ID
Only 32,768 possible key values for any key size
All keys generated on Debian/Ubuntu for 2 years were trivially breakable
Required mass reissuance of SSH keys and SSL certificates

The Scariest Line of Code Ever Removed

The removed code was: MD_Update(&m, buf, j); /* This line is critical for entropy! */ The comment wasn't even there—the developer had no way to know. This single deletion compromised millions of keys worldwide.

Case Study 2: Shared RSA Primes (2012)

Researchers Lenstra et al. analyzed millions of RSA public keys from TLS certificates and found:

0.2% of keys shared a prime factor with another key
These shared-prime keys could be factored instantly (GCD computation)
Root cause: Devices generating keys with insufficient entropy during first boot
Embedded devices, routers, and IoT were most affected

Notable Key Generation Vulnerabilities
Incident	Year	Cause	Impact
Debian OpenSSL	2008	Entropy source removed	32K possible keys, mass revocation
Shared RSA Primes	2012	Low entropy at boot	0.2% of TLS keys compromised
Android SecureRandom	2013	Java RNG not seeded properly	Bitcoin private keys stolen
Juniper Dual EC	2015	Backdoored RNG constants	VPN traffic decryptable
ROCA	2017	Faulty prime generation	750K+ Estonian ID cards vulnerable
Taiwan RNG	2013	Smartcard RNG weakness	National ID cards at risk

Lessons Learned:

Hardware matters — Devices must have adequate entropy sources. Virtual machines and embedded systems are particularly vulnerable.
First-boot is dangerous — Systems have minimal entropy right after boot. Keys should not be generated until sufficient entropy is available.
Audit everything — Any change to cryptographic code can have catastrophic consequences. The Debian bug was one line.
Defense in depth — Use multiple entropy sources. Don't rely on a single hardware RNG that might be backdoored.
Validate outputs — Production key generation should include post-generation validation to catch systematic errors.

The Dual EC Backdoor

The Dual EC DRBG random number generator, standardized by NIST, contained constants that security researchers suspected might be backdoored. In 2013, Snowden documents confirmed the NSA had inserted a kleptographic backdoor. This is why curve constants with 'nothing up my sleeve' provenance (like Curve25519) are preferred.

Practical Key Generation

Let's examine how to properly generate keys in practice using modern tools and libraries.

Command-Line Key Generation:

ssh_key_generation.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Generate RSA key (4096 bits recommended for long-term use)
ssh-keygen -t rsa -b 4096 -C "user@example.com"
 
# Generate Ed25519 key (modern, recommended)
ssh-keygen -t ed25519 -C "user@example.com"
 
# Generate ECDSA key (P-256 curve)
ssh-keygen -t ecdsa -b 256 -C "user@example.com"
 
# View key fingerprint
ssh-keygen -lf ~/.ssh/id_ed25519.pub
 
# Output:
# 256 SHA256:abcd...xyz user@example.com (ED25519)

Best Practices for Key Generation:

Use established libraries — Never implement key generation yourself. Use OpenSSL, libsodium, or language-native crypto modules.
Generate on-device — Private keys should be generated where they'll be used. Never transport private keys across networks.
Protect private keys — Use passphrase encryption for stored private keys. Consider hardware security modules (HSMs) for high-value keys.
Verify system entropy — Check that /dev/random (or equivalent) has sufficient entropy before generating keys. On Linux: cat /proc/sys/kernel/random/entropy_avail.
Backup securely — Private keys are irreplaceable. Backup using encryption along with secure offline storage.
Document key metadata — Record when keys were generated, their purpose, and expiration dates.

VM and Container Warning

Virtual machines and containers often have low entropy, especially right after boot. Use virtio-rng to pass host entropy to VMs, or ensure the guest has its own hardware RNG. Never generate keys immediately on VM boot—wait for entropy to accumulate.

Summary: Key Generation Fundamentals

We've explored the critical process of asymmetric key generation. Let's consolidate the key takeaways:

Key Takeaways

•Entropy is the foundation — All key security derives from the unpredictability of the random numbers used during generation.
•RSA requires prime generation — Two large primes are selected, and the key pair is derived through modular arithmetic.
•ECC is simpler and faster — A random scalar is chosen, and the public key is computed by point multiplication on a curve.
•Key validation is essential — Generated keys must be checked for proper size, mathematical correctness, and known weaknesses.
•Real-world failures are common — Insufficient entropy, faulty RNGs, and implementation bugs have compromised millions of keys.
•Use established tools — Never implement key generation yourself. Use OpenSSL, libsodium, or native crypto libraries.
•Protect from generation to storage — Security must be maintained throughout the key lifecycle.

What's Next:

Now that we understand how key pairs are generated, the next page explores encryption and decryption with asymmetric keys—the actual process of using these key pairs to protect data, including the mathematical operations involved and why asymmetric encryption is typically used for small data or key exchange rather than bulk encryption.

Page Complete

You now understand the intricate process of asymmetric key generation—from entropy collection through prime selection to final key validation. This knowledge is essential for understanding why key security depends on far more than just key size, and why the provenance of cryptographic keys matters as much as their mathematical properties.