Public Key Cryptography

Modern encryption technologies securing the internet today

← Previous: Symmetric vs Asymmetric Next: Quantum Cryptography β†’

Introduction to Public Key Cryptography

Public key cryptography, also known as asymmetric cryptography, revolutionized secure communication by solving one of the oldest problems in cryptography: how to share secret keys securely over an insecure channel.

i

Public key cryptography was invented in the 1970s and is the foundation of secure internet communications, including HTTPS, email encryption, and digital signatures.

The Key Exchange Problem

Traditional symmetric encryption requires both parties to share the same secret key. But how do you securely share this key when the communication channel itself is insecure? This is known as the key distribution problem.

The Problem:

Alice wants to send Bob a secret message, but they've never met. With symmetric encryption:

  1. Alice needs to send Bob the secret key
  2. But if Eve intercepts the key, she can read all future messages
  3. There's no way to securely share the key over an insecure channel

Visualizing the Problem

πŸ‘©

Alice

πŸ”‘ Secret Key
πŸ‘€

Eve (Eavesdropper)

Insecure Channel

πŸ‘¨

Bob

Problem: Eve can intercept the key!

The Public Key Solution

Public key cryptography solves this with a brilliant insight: use two different keysβ€”one for encryption (public key) and one for decryption (private key).

How It Works:

  • Public Key: Can be shared with anyone, used to encrypt messages
  • Private Key: Kept secret, used to decrypt messages
  • Mathematical Relationship: The keys are mathematically related but you can't derive the private key from the public key

Public Key Communication

πŸ‘©

Alice

πŸ”‘ Bob's Public Key
πŸ”’ Encrypted Message
πŸ‘€

Eve

Can't decrypt!

πŸ‘¨

Bob

πŸ” Private Key

Solution: Only Bob's private key can decrypt the message!

RSA Encryption

RSA (Rivest–Shamir–Adleman) is one of the first and most widely used public-key cryptosystems. It's based on the mathematical difficulty of factoring large numbers.

The Mathematics Behind RSA

RSA security relies on the fact that while it's easy to multiply two large prime numbers, it's extremely difficult to factor their product back into the original primes.

Simple Example with Small Numbers

  1. Choose two prime numbers: p = 61, q = 53
  2. Calculate n: n = p Γ— q = 61 Γ— 53 = 3233
  3. Calculate Ο†(n): Ο†(n) = (p-1) Γ— (q-1) = 60 Γ— 52 = 3120
  4. Choose e: e = 17 (must be coprime with Ο†(n))
  5. Calculate d: d = 2753 (the modular multiplicative inverse)
  6. Public Key: (e, n) = (17, 3233)
  7. Private Key: (d, n) = (2753, 3233)

RSA Encryption and Decryption

Encryption: C = Me mod n

Decryption: M = Cd mod n

where M is the message, C is the ciphertext, e is the public exponent, d is the private exponent, and n is the modulus.

Interactive RSA Demo

Note: This uses small numbers for demonstration. Real RSA uses numbers with hundreds of digits!

Step 1: Generate Keys

Step 2: Encrypt a Message

Step 3: Decrypt the Message

Digital Signatures

Public key cryptography also enables digital signatures, which verify the authenticity and integrity of messages.

How Digital Signatures Work:

  1. Alice creates a hash of her message
  2. Alice encrypts the hash with her private key (this is the signature)
  3. Alice sends both the message and signature to Bob
  4. Bob decrypts the signature using Alice's public key
  5. Bob hashes the message and compares it with the decrypted signature
  6. If they match, the message is authentic and unmodified

Digital Signature Process

1. Signing (Alice)

Message β†’ Hash β†’ Encrypt with Private Key β†’ Signature

↓

2. Verification (Bob)

Signature β†’ Decrypt with Public Key β†’ Compare with Message Hash

↓

βœ“ Verified: Message is authentic and unmodified

Try Digital Signatures

Real-World Applications

Public key cryptography is everywhere in modern technology:

🌐

HTTPS/SSL/TLS

Secures web browsing, ensuring that websites you visit are authentic and your data is encrypted.

πŸ“§

Email Encryption

PGP and S/MIME use public key cryptography to encrypt emails and verify sender identity.

πŸ”

SSH

Secure Shell uses public key authentication for secure remote server access.

β‚Ώ

Cryptocurrencies

Bitcoin and other cryptocurrencies use public key cryptography for wallet addresses and transaction signing.

πŸ“±

Code Signing

Software developers sign their applications to prove authenticity and prevent tampering.

πŸ†”

Digital Certificates

X.509 certificates verify the identity of websites, servers, and individuals.

Diffie-Hellman Key Exchange

Another groundbreaking public key protocol is Diffie-Hellman key exchange, which allows two parties to establish a shared secret over an insecure channel without ever transmitting the secret itself.

The Paint Mixing Analogy

Imagine Alice and Bob want to create a shared secret color:

  1. They agree on a common base color (public, known to everyone)
  2. Alice picks a secret color and mixes it with the base
  3. Bob picks a secret color and mixes it with the base
  4. They exchange their mixed colors (public)
  5. Alice adds her secret color to Bob's mix
  6. Bob adds his secret color to Alice's mix
  7. They both end up with the same final color!

Eve can see all the public information but can't "unmix" the colors to find the secret.

Diffie-Hellman Visualization

Alice

Secret Color

Public Base

Bob

Secret Color

Shared Secret

Strengths and Limitations

Strengths:

  • Solves the key distribution problem
  • Enables secure communication without prior key exchange
  • Provides authentication through digital signatures
  • Supports non-repudiation (signer cannot deny signing)
  • Foundation of modern internet security

Limitations:

  • Much slower than symmetric encryption (100-1000x slower)
  • Requires larger key sizes for equivalent security
  • Vulnerable to quantum computers (Shor's algorithm)
  • Requires trusted certificate authorities for authentication
  • More complex to implement correctly
i

In practice, public key cryptography is often used to securely exchange a symmetric key, which is then used for the actual data encryption (hybrid cryptosystem).

Key Sizes and Security

The security of public key cryptography depends on key length:

RSA Key Size Security Level Status
1024 bits ~80 bits ❌ Deprecated (unsafe)
2048 bits ~112 bits βœ“ Current minimum
3072 bits ~128 bits βœ“ Recommended
4096 bits ~152 bits βœ“ High security

Summary

Key Points

  • Public key cryptography uses two mathematically related keys: public and private
  • The public key encrypts, the private key decrypts
  • RSA security is based on the difficulty of factoring large numbers
  • Digital signatures provide authentication and non-repudiation
  • Diffie-Hellman enables secure key exchange over insecure channels
  • Public key cryptography is slower but solves the key distribution problem
  • It's the foundation of HTTPS, email encryption, and secure internet communication
  • Hybrid systems combine public key and symmetric encryption for optimal security and performance
Previous: Symmetric vs Asymmetric Next: Quantum Cryptography