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 the paper that introduced 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 in a practical 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”)
  • Investigation closed in January 1996 with no charges filed, after about three years
  • Courts later held source code is protected speech: Bernstein v. DOJ (9th Cir. panel, 1999, later withdrawn on rehearing) and Junger v. Daley (6th Cir. 2000)

PGP becomes a standard:

  • OpenPGP protocol standardized (RFC 4880; later revised as RFC 9580 in 2024)
  • 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
  • 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)
  • Interoperates with other OpenPGP software for standard keys like the one you’ll make here
  • Your introduction to asymmetric cryptography

How GPG Works: The Math (Simplified)

RSA Algorithm (the classic, most compatible choice; newer GnuPG defaults to ECC/Curve25519):

  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: fine today; NIST’s transition plan (draft IR 8547) deprecates it after 2030
  • 3072/4096-bit RSA: stronger against classical attacks, but a larger key does NOT protect against a future quantum computer
  • Post-quantum: NIST plans to disallow RSA and ECC by 2035. Data encrypted today can be recorded now and decrypted later, so long-lived secrets are the ones to worry about. Newer GnuPG releases are adding post-quantum (ML-KEM/Kyber) support; check the current release notes before relying on it.

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

Still have the practice key from Week 1b? That “Cypherpunk Student” key was for exercises only. The key you make here is your real one. Keep the practice key for lesson work or delete it with gpg --delete-secret-and-public-key "Cypherpunk Student", but don’t use it for anything real.

# 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
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
   (9) ECC (sign and encrypt) *default*
  (10) ECC (sign only)
  (14) Existing key from card
Your selection? 1

Choose (1) RSA and RSA - A deliberate choice for compatibility with older software; the rsa4096 output below assumes it. GnuPG 2.2 shows RSA as the default; 2.4 and later show ECC. Choosing (1) works on both. The default (9) produces ed25519/cv25519 keys instead.

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:

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)
  • No recovery mechanism

Picking a passphrase: Generate your own. Roll dice for 6-7 words from the EFF large wordlist, or let your password manager generate a random 6+ word passphrase. Don’t pick the words yourself, don’t add dates, and never reuse an example you have seen published. The shape looks like word1-word2-word3-word4-word5-word6.

Key Generation Output

gpg: key ABCD1234ABCD1234 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 (GPG key for course exercises) <[email protected]>
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
  • 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