Cryptography is the mathematical and computational study of techniques for secure communication in the presence of adversaries. It encompasses the design and analysis of protocols that prevent unauthorized access to information, ensure data integrity, and authenticate identities. Rooted in number theory, algebra, and probability, applied cryptography translates abstract mathematical principles into practical systems for encryption, decryption, digital signatures, and key exchange. Its applications range from everyday internet security and financial transactions to national defense and blockchain technology.

1 Foundations of Cryptography

1.1 Historical Context

1.1.1 Classical Ciphers (e.g., Caesar, Vigenère)

The earliest known ciphers include the Caesar cipher, used by Julius Caesar, which shifts letters of the alphabet by a fixed number (key). The Vigenère cipher, a polyalphabetic substitution, uses a keyword to determine multiple Caesar shifts, offering improved security over monoalphabetic ciphers. Both are now easily broken by frequency analysis and brute force.

1.1.2 Enigma and World War II Cryptanalysis

The German Enigma machine, a rotor-based electromechanical cipher, was used during World War II for secure military communications. Allied cryptanalysts, notably at Bletchley Park led by Alan Turing, developed techniques (e.g., Bombe machines) to exploit operator errors and weak key spaces, eventually breaking Enigma’s messages and contributing significantly to the Allied victory.

1.2 Core Mathematical Concepts

1.2.1 Modular Arithmetic and Prime Numbers

Modular arithmetic operates on integers modulo a positive integer \(n\) (e.g., \(a \bmod n\)). Prime numbers are integers greater than 1 with no positive divisors other than 1 and themselves. Properties of primes, such as the difficulty of factoring large composites, underpin many cryptographic systems (e.g., RSA). Modular exponentiation and Euler’s theorem are also fundamental.

1.2.2 Group Theory and Finite Fields

A group is an algebraic structure with a binary operation satisfying closure, associativity, identity, and inverses. Finite fields (Galois fields) of order \(p^k\) (for prime \(p\)) provide arithmetic systems essential for elliptic curve cryptography and AES. Cyclic groups, where every element is a power of a generator, are central to Diffie-Hellman key exchange.

1.2.3 Computational Complexity Theory

1.2.3.1 One-Way Functions and Trapdoors

A one-way function is easy to compute but hard to invert on average. A trapdoor one-way function remains hard to invert without a secret “trapdoor” (auxiliary information). These concepts formalize the security of public-key cryptosystems: encrypting is easy, decrypting requires the trapdoor (private key).

1.2.3.2 Computational Hardness Assumptions

Security proofs rely on assumptions such as the difficulty of integer factorization (RSA), the discrete logarithm problem (Diffie-Hellman, DSA), or the elliptic curve discrete logarithm problem. These problems are believed to be intractable for classical computers when parameters are chosen appropriately.

1.3 Cryptographic Primitives

1.3.1 Encryption

Encryption is the process of converting plaintext into ciphertext using a key and an encryption algorithm, rendering the message unintelligible to unauthorized parties. It is a core building block of secure communication.

1.3.2 Decryption

Decryption is the inverse process of converting ciphertext back to plaintext using the corresponding decryption algorithm and key. In symmetric cryptography, the encryption and decryption keys are identical; in asymmetric cryptography, they differ.

1.3.3 Key Generation

Key generation is the procedure for producing a key (or key pair) for a cryptographic algorithm. It must be unpredictable and based on a secure random source. Standardized algorithms (e.g., ANSI X9.17) and random number generators ensure cryptographic quality.

2 Symmetric-Key Cryptography

2.1 Stream Ciphers

2.1.1 RC4 and Modern Alternatives (e.g., ChaCha20)

RC4 is a widely used stream cipher from the 1980s that generates a pseudorandom keystream combined with plaintext via XOR. Its known biases led to practical attacks (e.g., on WEP). Modern alternatives like ChaCha20 (designed by Daniel Bernstein) offer high security and performance, and are used in TLS and SSH.

2.1.2 Linear Feedback Shift Registers

LFSRs generate binary sequences based on linear recurrence over \(GF(2)\). While efficient in hardware, their linearity makes them insecure alone. They are often combined with non-linear functions in cipher designs (e.g., A5/1, Trivium) to resist algebraic attacks.

2.2 Block Ciphers

2.2.1 Feistel Networks (DES, Blowfish)

A Feistel network splits the data block into halves and applies a round function, mixing the halves over many rounds. The Data Encryption Standard (DES, 56-bit key) uses a 16-round Feistel structure; its small key size is now vulnerable to brute force. Blowfish (key up to 448 bits) also uses a Feistel network and remains secure for legacy use.

2.2.2 Substitution-Permutation Networks (AES)

SPNs apply substitution (S-boxes) and permutation (bit-wise shuffling) in each round. The Advanced Encryption Standard (AES) has a fixed block size of 128 bits and key sizes of 128, 192, or 256 bits. It operates on a 4×4 byte matrix, using SubBytes, ShiftRows, MixColumns, and AddRoundKey, and is the current global standard.

2.2.3 Modes of Operation

2.2.3.1 Electronic Codebook (ECB)

Each block is encrypted independently with the same key. Identical plaintext blocks yield identical ciphertext blocks, revealing patterns. ECB is insecure for most applications and is avoided except for encrypting short, random data.

2.2.3.2 Cipher Block Chaining (CBC)

Each plaintext block is XORed with the previous ciphertext block before encryption. A random initialization vector (IV) is used for the first block. CBC hides patterns but requires sequential processing and is susceptible to padding oracle attacks if not used carefully.

2.2.3.3 Counter Mode (CTR)

The cipher encrypts a counter value (incremented per block) to produce a keystream, which is XORed with plaintext. CTR is parallelizable, requires no padding, and offers good security when the counter does not repeat. It is widely used in modern protocols.

2.3 Message Authentication Codes (MACs)

2.3.1 HMAC (Hash-based MAC)

HMAC combines a cryptographic hash function with a secret key to produce a MAC. Defined as \(\text{HMAC}(K, m) = H((K' \oplus \text{opad}) \parallel H((K' \oplus \text{ipad}) \parallel m))\), it provides security against length-extension attacks and is standardized (RFC 2104). It is used in TLS, IPsec, and many other protocols.

2.3.2 CMAC and Poly1305

CMAC (Cipher-based MAC) uses a block cipher (e.g., AES) in CBC-MAC mode with modifications to handle variable-length messages. Poly1305 is a fast, universal hash-based MAC designed for use with one-time keys (e.g., in ChaCha20-Poly1305). It is highly parallelizable and secure.

3 Asymmetric-Key Cryptography

3.1 Public-Key Encryption

3.1.1 RSA (Rivest–Shamir–Adleman)

RSA encryption uses a public key \((n, e)\) where \(n = pq\) (product of two large primes) and \(e\) is a public exponent. Decryption uses the private key \(d\) such that \(ed \equiv 1 \pmod{\phi(n)}\). Security relies on the difficulty of factoring \(n\). RSA is used for encryption and digital signatures, typically with key sizes of 2048 bits or more.

3.1.2 ElGamal Encryption

ElGamal is based on the discrete logarithm problem in a cyclic group. The public key includes \((G, q, g, h)\) where \(h = g^x\). Encryption produces a pair \((c_1, c_2) = (g^y, m \cdot h^y)\). It is probabilistic and homomorphic, but ciphertexts are twice the size of the plaintext.

3.1.3 Elliptic Curve Cryptography (ECC)

ECC uses the group of points on an elliptic curve over a finite field. It offers equivalent security to RSA with smaller key sizes (e.g., 256-bit ECC ≈ 3072-bit RSA). Elliptic curve integrated encryption scheme (ECIES) is a standard approach combining ECDH with symmetric encryption.

3.2 Digital Signatures

3.2.1 RSA Signatures

RSA signatures are produced by hashing the message and then computing the hash raised to the private exponent \(d\) modulo \(n\). Verification raises the signature to the public exponent \(e\) and compares to the hash. Padding schemes (e.g., PKCS#1 v1.5, PSS) are essential to avoid attacks.

3.2.2 Digital Signature Algorithm (DSA, ECDSA)

DSA uses a subgroup of prime order \(q\) in \(\mathbb{Z}_p^*\), relying on the discrete logarithm problem. ECDSA is the elliptic curve variant. Both produce a pair \((r, s)\) where \(r\) depends on a per-signature random nonce. Security requires unique nonces; reuse leaks the private key.

3.2.3 Schnorr Signatures

Schnorr signatures use a non-interactive zero-knowledge proof paradigm. They are provably secure in the random oracle model and offer signature aggregation (e.g., in Bitcoin Taproot). EdDSA (Ed25519) is a widely adopted Schnorr-like scheme based on twisted Edwards curves.

3.3 Key Exchange Protocols

3.3.1 Diffie-Hellman Key Exchange

The Diffie-Hellman (DH) protocol allows two parties to agree on a shared secret over an insecure channel. Using a cyclic group with generator \(g\) and public values \(g^a\) and \(g^b\), both compute \(g^{ab}\). Without the private exponents, an eavesdropper cannot feasibly derive the secret (assuming the computational Diffie-Hellman assumption).

3.3.2 Elliptic Curve Diffie-Hellman (ECDH)

ECDH operates on an elliptic curve. Parties exchange public points \(aG\) and \(bG\), then compute the shared point \(abG\). It offers the same security as traditional DH with smaller keys and faster computation. Used in TLS 1.3 and Signal protocol.

3.3.3 Authenticated Key Exchange (STS, SIGMA)

Basic Diffie-Hellman is vulnerable to man-in-the-middle attacks. Authenticated key exchange protocols include Station-to-Station (STS) and SIGMA (used in IKEv2). They incorporate digital signatures or MACs to authenticate the exchanged public keys, preventing impersonation.

4 Hash Functions and Their Applications

4.1 Properties of Cryptographic Hash Functions

4.1.1 Preimage Resistance

For a given output \(y\), it is computationally infeasible to find any input \(x\) such that \(H(x) = y\). This property ensures that hash values cannot be inverted.

4.1.2 Second Preimage Resistance

Given an input \(x_1\), it is infeasible to find a different input \(x_2 \neq x_1\) with \(H(x_1) = H(x_2)\). This protects against forgery.

4.1.3 Collision Resistance

It is infeasible to find any two distinct inputs \(x_1 \neq x_2\) with \(H(x_1) = H(x_2)\). Collision resistance is stronger than second preimage resistance and is crucial for digital signatures.

4.2 Commonly Used Hash Functions

4.2.1 SHA-2 Family (SHA-256, SHA-512)

SHA-2 (Secure Hash Algorithm 2) includes SHA-256 and SHA-512, producing 256- and 512-bit digests, respectively. Based on the Merkle–Damgård construction, they are widely used in TLS, Bitcoin, and file integrity verification. No practical collisions are known.

4.2.2 SHA-3 (Keccak)

SHA-3 is the latest NIST standard, based on the Keccak sponge construction. It does not rely on the Merkle–Damgård structure and offers resistance against length-extension attacks. Variants include SHA3-224 through SHA3-512 and extendable-output functions SHAKE128/256.

4.2.3 BLAKE2

BLAKE2 is a fast hash function designed as an alternative to SHA-3 and SHA-2. It provides high performance on software platforms, with BLAKE2s (32-bit) and BLAKE2b (64-bit). It also includes a keyed mode (MAC) and is used in protocols like Ed25519.

4.3 Applications

4.3.1 Password Hashing and Salt

To securely store user passwords, a hash function is applied to the password combined with a random “salt.” The salt prevents precomputed rainbow table attacks and ensures different users with the same password have distinct hashes. Dedicated password hashing functions (bcrypt, Argon2) add work factors to resist brute force.

4.3.2 Merkle Trees and Hash-based Signatures

A Merkle tree is a binary tree where leaves are hashes of data blocks and internal nodes are hashes of child hashes. The root provides a compact commitment to the entire data set. Hash-based signature schemes (e.g., SPHINCS+) use Merkle trees to generate and verify many one-time signatures, with security relying only on the hash function.

4.3.3 Blockchain and Proof-of-Work

Blockchains (e.g., Bitcoin) link blocks via hash pointers. Proof-of-work (PoW) requires finding a nonce such that the block’s hash is below a target difficulty. This process relies on the preimage resistance and unpredictability of hash functions, securing the distributed ledger.

5 Cryptographic Protocols and Practical Security

5.1 Transport Layer Security (TLS) and Secure Sockets Layer (SSL)

5.1.1 Handshake Protocol

The TLS handshake negotiates cryptographic parameters, authenticates the server (and optionally the client), and establishes session keys. Steps include cipher suite negotiation, exchange of certificates, key exchange (e.g., ECDHE), and verification of Finished messages. TLS 1.3 simplified the handshake and removed weak options.

5.1.2 Certificate Authorities and Public Key Infrastructure (PKI)

A public key infrastructure binds public keys to identities via digital certificates issued by Certificate Authorities (CAs). CAs are trusted third parties that verify ownership of domain names or entities. The chain of trust from root CAs to end-entity certificates enables secure authentication on the internet.

5.2 Secure Multi-Party Computation (MPC)

5.2.1 Garbled Circuits (Yao’s Protocol)

Yao’s garbled circuits allow two parties to compute a function on their private inputs without revealing them. One party (garbler) creates encrypted versions of the circuit’s gates; the other (evaluator) decrypts only the relevant outputs using oblivious transfer. This is the foundation of many practical MPC systems.

5.2.2 Secret Sharing (Shamir, Verifiable)

Shamir’s secret sharing splits a secret into \(n\) shares, such that any \(t\) shares reconstruct the secret, but fewer reveal nothing. Verifiable secret sharing (VSS) adds commitments to detect malicious dealers or shareholders. Used in distributed key generation and threshold cryptography.

5.3 Zero-Knowledge Proofs

5.3.1 Interactive Proof Systems

An interactive proof consists of a prover and verifier exchanging messages, where the prover aims to convince the verifier of a statement’s truth without revealing any additional information. Soundness and completeness are required. Classic examples include graph isomorphism and quadratic residuosity.

5.3.2 zk-SNARKs and zk-STARKs

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) allow verification of computational statements with short proofs and no interaction, but require a trusted setup. zk-STARKs (scalable transparent arguments of knowledge) are post-quantum secure and need no trusted setup, using hash functions and interactive oracles.

5.4 Quantum Cryptography

5.4.1 Quantum Key Distribution (BB84)

BB84 is a quantum key distribution protocol using four polarization states of photons. Eavesdropping disturbs the quantum states, revealing the attacker’s presence. After error correction and privacy amplification, the two parties share a secret key. BB84 is provably secure against arbitrary quantum adversaries.

5.4.2 Post-Quantum Cryptography (Lattice-based, Code-based)

Post-quantum cryptography designs algorithms believed secure against quantum computers. Lattice-based schemes (e.g., CRYSTALS-Kyber, Dilithium) rely on the hardness of learning with errors (LWE). Code-based schemes (e.g., Classic McEliece) use error-correcting codes. NIST is standardizing several such algorithms.

6 Cryptanalysis and Security Evaluation

6.1 Classical Attacks

An attacker tries all possible keys until a decryption yields meaningful plaintext. Modern secure algorithms have a key space large enough (e.g., 128 bits for AES) to make brute force infeasible with current hardware. Brute force remains viable against small key sizes (e.g., DES’s 56 bits).

6.1.2 Frequency Analysis

In substitution ciphers, letter frequencies in the ciphertext are compared to those of the natural language. Common letters (e.g., E, T in English) map to frequent symbols. Frequency analysis breaks monoalphabetic ciphers easily and was historically used against classical ciphers.

6.2 Modern Cryptanalytic Techniques

6.2.1 Differential Cryptanalysis

Differential cryptanalysis studies how differences in plaintext pairs affect differences in ciphertext pairs. By tracing high-probability differentials through rounds, an attacker can recover key bits. It was used to break DES faster than brute force, though DES was designed to resist it. Many modern ciphers are designed with provable resistance.

6.2.2 Linear Cryptanalysis

Linear cryptanalysis approximates the behavior of a cipher with linear equations in the plaintext, ciphertext, and key bits. High-correlation linear approximations allow partial key recovery. It was also applied to DES and remains an important evaluation tool for block ciphers.

6.2.3 Side-Channel Attacks (Timing, Power Analysis)

Side-channel attacks exploit physical leakage from implementations. Timing attacks measure execution time variations (e.g., due to conditional branching). Power analysis monitors power consumption during encryption. Countermeasures include constant-time code, blinding, and masking.

6.3 Provable Security

6.3.1 Reduction Proofs and Security Models (IND-CPA, IND-CCA)

Provable security uses reductions: if an adversary can break a cryptosystem, then an algorithmic problem (e.g., factoring) can be solved efficiently. Security models define adversarial capabilities: IND-CPA (indistinguishability under chosen-plaintext attack) and IND-CCA (chosen-ciphertext attack) are common goals. Schemes like RSA-OAEP achieve IND-CCA security.

6.3.2 Random Oracle Model

In the random oracle model, hash functions are idealized as truly random functions accessible via queries. Many security proofs (e.g., for RSA-OAEP, Fiat-Shamir signatures) assume this model. However, some schemes proven secure in the random oracle model have been broken when instantiated with concrete hash functions, highlighting the need for careful analysis.

7.1 Cryptography in Memes and Pop Culture

7.1.1 “PGP” and “TLS” Jokes

Cryptographic protocols become occasional subjects of internet humor. For example, “I encrypt my affection with a PGP-encrypted love note” or jokes about TLS certificate warnings (“Your connection is not private”) appear in memes. Such references reflect the growing public awareness of encryption.

7.1.2 Crypto-Clipping and CTF (Capture The Flag) Competitions

Capture The Flag competitions include challenges that require solving cryptographic puzzles (e.g., breaking weak XOR ciphers, implementing AES). Crypto-clipping refers to creating or solving short cipher challenges shared on social media. These activities promote learning cryptography in a fun, community-driven environment.

7.2 Lighthearted Cryptography Puzzles

7.2.1 Cipher Challenges (e.g., Cicada 3301)

Cicada 3301 was an online puzzle series starting in 2012, using cryptography (e.g., book ciphers, RSA, steganography) to recruit individuals. Participants solved increasingly difficult riddles, reaching real-world clues. The puzzles became a landmark in internet cryptography culture.

7.2.2 Homemade Ciphers in Online Communities

Online forums (e.g., Reddit’s r/codes) feature users creating and breaking homemade ciphers. These range from simple substitution to custom block ciphers. While often insecure, they serve as educational tools and recreational challenges, fostering a hands-on interest in cryptanalysis.