Public-Key Cryptography: Asymmetric Encryption, Digital Signatures, and Key Exchange

Public-Key Cryptography (PKC), or asymmetric cryptography, solves the fundamental problem of key distribution by using mathematically linked keypairs: a public key for encryption/verification and a private key for decryption/signing.

⚡ Quick Dive

Asymmetric Cryptographic Algorithms Comparison

Algorithm Underlying Hard Problem Primary Application Recommended Key Length Security Level
RSA Integer Prime Factorization Encryption & Digital Signatures $\ge 2048$ bits (3072 recommended) Standard (Legacy)
ECC (ECDSA / ECDH) Elliptic Curve Discrete Logarithm High-speed Signatures & Key Exchange $\ge 256$ bits (secp256r1) High
Ed25519 / X25519 Edwards-curve (Curve25519) Modern SSH, TLS 1.3, Signal Protocol 256 bits Maximum Modern
Diffie-Hellman (DH) Discrete Logarithm in Finite Fields Session Key Agreement $\ge 3072$ bits Standard
ML-KEM (Kyber) Module Learning with Errors (Lattice) Post-Quantum Key Encapsulation 512 / 768 / 1024 bits Quantum-Resistant

Keypair Roles Summary

Operation Alice (Sender) Action Bob (Receiver) Action Key Used
Asymmetric Encryption Encrypts message Decrypts message Bob's Public Key $\to$ Bob's Private Key
Digital Signature Signs message hash Verifies signature Alice's Private Key $\to$ Alice's Public Key
Key Agreement (ECDH) Combines Alice_priv + Bob_pub Combines Bob_priv + Alice_pub Derives identical shared secret $S$

📖 Extended Guide

1. Mathematical Foundations & Trapdoor Functions

Public-key cryptography relies on one-way trapdoor functions: mathematical operations that are computationally trivial in the forward direction but intractable to reverse without a secret "trapdoor":

Forward Direction (Public Key):
Message (m) ──────────────────────► Ciphertext (c = mᵉ mod n) [Trivial: O(log e) operations]

Reverse Direction without Trapdoor (Attacker):
Ciphertext (c) ───────────────────► Message (m) [Intractable: Requires factoring n]

Reverse Direction with Trapdoor (Private Key d):
Ciphertext (c) ───────────────────► Message (m = cᵈ mod n) [Trivial: O(log d) operations]

2. RSA Cryptosystem Mechanics

RSA Key Generation Algorithm:
1. Select two large distinct primes p and q.
2. Compute modulus n = p * q.
3. Compute Euler's Totient: φ(n) = (p - 1) * (q - 1).
4. Choose public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (Standard: e = 65537).
5. Compute private exponent d = e⁻¹ mod φ(n) using Extended Euclidean Algorithm.
   - Public Key:  (e, n)
   - Private Key: (d, n)

package main

import (
	"crypto/rand"
	"crypto/rsa"
	"crypto/sha256"
	"fmt"
)

func main() {
	// 1. Generate 2048-bit RSA Keypair
	privateKey, err := rsa.GenerateKey(rand.Reader, 2048)
	if err != nil {
		panic(err)
	}
	publicKey := &privateKey.PublicKey

	message := []byte("Sensitive Financial Transaction")

	// 2. Encrypt with OAEP padding (PKCS#1 v2.1)
	ciphertext, err := rsa.EncryptOAEP(sha256.New(), rand.Reader, publicKey, message, nil)
	if err != nil {
		panic(err)
	}

	// 3. Decrypt with Private Key
	decrypted, err := rsa.DecryptOAEP(sha256.New(), rand.Reader, privateKey, ciphertext, nil)
	if err != nil {
		panic(err)
	}

	fmt.Printf("Decrypted: %s\n", string(decrypted))
}

3. Elliptic Curve Cryptography (Curve25519 & Ed25519)

Instead of huge 4096-bit numbers, ECC operates over the algebraic structure of elliptic curves over finite fields: $$y^2 = x^3 + ax + b$$

  • Point Multiplication: Given base point $G$ and private scalar $d$, computing public point $Q = d \cdot G$ is fast via double-and-add.
  • ECDLP (Elliptic Curve Discrete Logarithm Problem): Given $Q$ and $G$, finding $d$ is computationally impossible for large fields ($O(\sqrt{p})$ using Pollard's rho).
  • A 256-bit ECC key provides equivalent cryptographic strength to a 3072-bit RSA key, consuming 90% less CPU and bandwidth.

4. Ephemeral Diffie-Hellman & Perfect Forward Secrecy (PFS)

In modern TLS 1.3, static RSA encryption is prohibited in favor of ECDHE (Elliptic Curve Diffie-Hellman Ephemeral):

Alice                                                              Bob
Generate private a ──────────────────────────────────────► Generate private b
Compute A = a * G        [ Send Public A ]                 Compute B = b * G
                    ─────────────────────────►
                         [ Send Public B ]
                    ◄─────────────────────────
Compute Secret:                                           Compute Secret:
S = a * B = a * (b * G)                                   S = b * A = b * (a * G)
                                (S is identical!)

Because private keys $a$ and $b$ are discarded immediately after the session concludes, a future compromise of the server's master identity certificate cannot decrypt past recorded network traffic (Perfect Forward Secrecy).

5. Hybrid Encryption: The Architecture of TLS

Asymmetric encryption is computationally expensive and limited to small payload sizes. Real-world systems use Hybrid Encryption:

1. Handshake Phase (Asymmetric PKC):
   Alice and Bob use ECDHE to negotiate a shared secret S and verify identity via Digital Signatures.
2. Derivation:
   Both parties derive a high-speed symmetric session key (AES-256-GCM / ChaCha20-Poly1305).
3. Data Phase (Symmetric Encryption):
   Gigabytes of payload data stream securely at hardware-accelerated symmetric speeds.
⌂ All Guides