Goal

Understand the public-key cryptography revolution and generate your first GPG keypair. This is the foundation for everything else in the course.

Prerequisites: Week 2 (Cryptography Fundamentals)

This is Part 1 of 4 - Covers history, concepts, and key generation.

Introduction: The Public Key Revolution

Week 2 taught you symmetric encryption - Alice and Bob share the same secret key. But how do they exchange that key securely?

The problem:

Alice wants to send Bob a secret → Need shared key → How to share key securely?

Before 1976, this was unsolved. Then Diffie and Hellman published their revolutionary paper introducing public-key cryptography.

The solution:

Bob generates keypair → Publishes PUBLIC key → Alice encrypts with Bob's public key
→ Only Bob's PRIVATE key can decrypt

This changes everything:

  • No secret key exchange needed
  • Can encrypt to strangers you’ve never met
  • Digital signatures prove authorship
  • Foundation of modern internet security (HTTPS, SSH, etc.)

GPG (GnuPG) implements this revolution in a practical, battle-tested tool you’ll use for the rest of this course and beyond.

1. PGP and GPG: History and Architecture

The Birth of PGP

1991: Phil Zimmermann creates PGP (Pretty Good Privacy) to protect activists and journalists.

Zimmermann’s motivation:

“If privacy is outlawed, only outlaws will have privacy.”

What happened next:

  • PGP spreads globally via the internet
  • US government investigates Zimmermann (export of “munitions”)
  • Charges dropped in 1996 after 3-year battle
  • Proof: Cryptography is free speech, code is speech

PGP becomes a standard:

  • OpenPGP protocol standardized (RFC 4880)
  • Commercial PGP sold to companies
  • Free implementation needed for the people

Enter GPG (GnuPG)

1997: Werner Koch begins developing GnuPG - free software implementation of OpenPGP standard.

Why GPG matters:

  • Free and open source - Anyone can audit the code
  • No proprietary lock-in - Owned by the community
  • Actively maintained - Still the standard in 2025
  • Cross-platform - Linux, macOS, Windows
  • Battle-tested - Used by Snowden, journalists, activists worldwide

GPG is:

  • Command-line first (GUIs exist but we’ll master the CLI)
  • Compatible with all OpenPGP implementations
  • Your introduction to asymmetric cryptography

How GPG Works: The Math (Simplified)

RSA Algorithm (what GPG uses by default):

  1. Key Generation:

    • Pick two large prime numbers (p, q)
    • Compute n = p × q (public modulus)
    • Choose public exponent e (usually 65537)
    • Compute private exponent d (mathematical inverse)
    • Public key: (n, e)
    • Private key: (n, d)

  2. Encryption:

    • Ciphertext = Message^e mod n

  3. Decryption:

    • Message = Ciphertext^d mod n

Why this works:

  • Easy to compute e and d if you know p and q
  • Impossibly hard to compute d if you only know n (would need to factor n back into p and q)
  • Factoring large numbers is computationally infeasible (takes thousands of years)

Security margin:

  • 2048-bit RSA: Secure for now, borderline for long-term
  • 4096-bit RSA: Recommended - Should remain secure for decades
  • Post-quantum threat: RSA may be broken by quantum computers (decades away)

You don’t need to understand the math deeply - just know:

  • Public key encrypts, private key decrypts
  • Math ensures only private key holder can decrypt
  • Security relies on difficulty of factoring large numbers

2. Generating Your GPG Keypair

Installation Check

# Verify GPG is installed
gpg --version

# Should show GnuPG 2.x or newer
# If not installed:
# Debian/Ubuntu: sudo apt install gnupg
# Arch: sudo pacman -S gnupg
# macOS: brew install gnupg

Interactive Key Generation

# Full-featured key generation
gpg --full-generate-key

Walk through the prompts:

1. Key type:

Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
   (9) ECC and ECC
  (10) ECC (sign only)
  (14) Existing key from card
Your selection? 1

Choose (1) RSA and RSA - Most compatible, widely supported

2. Key size:

RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (3072) 4096

Choose 4096 - Maximum security for RSA

3. Expiration:

Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 2y

Choose 2y (2 years) - Good practice to rotate keys

Why expiration matters:

  • Limits damage if key compromised years from now
  • Forces periodic security reviews
  • Can extend expiration if key still secure
  • Industry best practice

4. Identity:

Real name: Alice Cypherpunk
Email address: [email protected]
Comment: GPG key for course exercises

Important:

  • Use real identity for professional/public key
  • Use pseudonym for privacy-focused communications
  • Email will be attached to all signatures
  • Can have multiple identities (UIDs) on same key

5. Passphrase:

CRITICAL: Choose a strong passphrase!

Enter passphrase: [Type strong passphrase]
Repeat passphrase: [Type again]

Passphrase protects your private key:

  • Even if someone steals your private key file, they can’t use it without passphrase
  • Should be 20+ characters (use diceware or password manager)
  • DO NOT FORGET THIS - No recovery mechanism

Good passphrase examples:

  • correct-horse-battery-staple-quantum-resistance-2025 (Diceware)
  • MyGPG!Key@Protects#My%Privacy&2025 (Symbolic)
  • I love cypherpunk philosophy and practice it daily since 2025! (Sentence)

Key Generation Output

gpg: key A1B2C3D4E5F6G7H8 marked as ultimately trusted
gpg: revocation certificate stored as '/home/alice/.gnupg/openpgp-revocs.d/ABCD1234.rev'
public and secret key created and signed.

pub   rsa4096 2025-10-14 [SC] [expires: 2027-10-14]
      ABCD1234ABCD1234ABCD1234ABCD1234ABCD1234
uid           Alice Cypherpunk <[email protected]> GPG key for course exercises
sub   rsa4096 2025-10-14 [E] [expires: 2027-10-14]

Understanding the output:

  • pub - Public primary key (4096-bit RSA)
  • [SC] - Key capabilities: Sign and Certify
  • [E] - Subkey capability: Encrypt
  • Fingerprint - Long hex string (ABCD1234…)
  • uid - User ID (name, email, comment)
  • sub - Subkey for encryption

IMPORTANT: Revocation certificate automatically created in ~/.gnupg/openpgp-revocs.d/

  • Use this to revoke key if compromised
  • Back it up separately from your key

Up Next

Week 3b covers understanding your keyring, encrypting files, and creating digital signatures.

Key Takeaways

  • Public-key cryptography solved the key exchange problem in 1976
  • GPG is the free, open-source implementation of OpenPGP standard
  • RSA 4096-bit keys are recommended for long-term security
  • 2-year expiration is good practice for key rotation
  • Strong passphrase (20+ characters) protects your private key
  • Revocation certificate should be backed up immediately after key generation