Fundamental Cryptographic Algorithms

Why This Matters

Cryptographic algorithms are the mathematical backbone of digital security—every secure login, encrypted message, and verified transaction depends on the computational hardness of specific mathematical problems. You're being tested on understanding why these algorithms work, not just what they do. The core concepts include number-theoretic hardness assumptions (factoring, discrete logarithms), symmetric vs. asymmetric paradigms, and the tradeoffs between security strength, key size, and computational efficiency.

Don't just memorize algorithm names and key lengths. Know which mathematical problem each algorithm relies on, whether it's symmetric or asymmetric, and when you'd choose one over another. Exam questions often ask you to compare algorithms solving similar problems or explain why a particular hardness assumption provides security. Master the underlying mathematics, and you'll be able to reason through any cryptographic scenario they throw at you.

---

Asymmetric Encryption: Public-Key Systems

Asymmetric cryptography uses mathematically related key pairs—a public key anyone can use and a private key only the owner knows. The security relies on mathematical problems that are easy to compute in one direction but computationally infeasible to reverse.

RSA (Rivest-Shamir-Adleman)

• Integer factorization hardness—security depends on the difficulty of factoring the product of two large primes $n = p \cdot q$
• Key generation involves computing $\phi(n) = (p-1)(q-1)$ and finding $e, d$ such that $ed \equiv 1 \pmod{\phi(n)}$
• Encryption/decryption uses modular exponentiation: $c = m^e \mod n$ and $m = c^d \mod n$

Elliptic Curve Cryptography (ECC)

• Elliptic curve discrete logarithm problem (ECDLP)—given points $P$ and $Q = kP$ on a curve, finding $k$ is computationally infeasible
• Smaller key sizes provide equivalent security to RSA (256-bit ECC ≈ 3072-bit RSA), reducing computational overhead
• Curve equation typically takes the form $y^2 = x^3 + ax + b$ over a finite field $\mathbb{F}_p$

ElGamal Encryption

• Discrete logarithm hardness—based on the same problem as Diffie-Hellman, computing $x$ from $g^x \mod p$
• Semantic security through randomization—the same plaintext encrypts to different ciphertexts using random $k$
• Ciphertext expansion—output is twice the size of plaintext $(c_1, c_2) = (g^k, m \cdot h^k)$

---

Symmetric Encryption: Shared-Key Systems

Symmetric algorithms use the same secret key for encryption and decryption. They're faster than asymmetric methods but require secure key distribution. Security depends on key length and resistance to cryptanalytic attacks.

AES (Advanced Encryption Standard)

• Block cipher operating on 128-bit blocks with key sizes of 128, 192, or 256 bits
• Substitution-permutation network (SPN)—alternates SubBytes, ShiftRows, MixColumns, and AddRoundKey operations
• Current standard for symmetric encryption, resistant to all known practical attacks when properly implemented

DES (Data Encryption Standard)

• 56-bit effective key length—now considered insecure; can be brute-forced in hours with modern hardware
• Feistel network structure with 16 rounds of permutation and substitution operations
• Historical significance—first widely adopted encryption standard, replaced by AES in 2001

Blowfish

• Variable key length from 32 to 448 bits, encrypting 64-bit blocks
• Feistel network with 16 rounds and key-dependent S-boxes generated during initialization
• Fast performance in software, though 64-bit block size limits security for large data volumes

Twofish

• 128-bit block size with keys up to 256 bits—designed as Blowfish's successor and AES finalist
• Complex key schedule using MDS matrices and pseudo-Hadamard transforms for diffusion
• Precomputed key-dependent S-boxes provide strong resistance to differential and linear cryptanalysis

---

Key Exchange Protocols

Key exchange algorithms solve the fundamental problem of establishing shared secrets over insecure channels. The mathematics ensures that eavesdroppers cannot compute the shared key even after observing all public communications.

Diffie-Hellman Key Exchange

• Discrete logarithm problem—given $g$, $p$, and $g^a \mod p$, computing $a$ is computationally infeasible
• Protocol mechanics: Alice sends $A = g^a \mod p$, Bob sends $B = g^b \mod p$, both compute $K = g^{ab} \mod p$
• Foundation for TLS/SSL—enables secure communication without prior key sharing, though vulnerable to man-in-the-middle attacks without authentication

---

Cryptographic Hash Functions

Hash functions map arbitrary-length inputs to fixed-length outputs. A secure hash must be preimage-resistant (can't find input from output), second preimage-resistant (can't find different input with same hash), and collision-resistant (can't find any two inputs with same hash).

SHA (Secure Hash Algorithm) Family

• Fixed output sizes—SHA-1 produces 160 bits (deprecated), SHA-256 produces 256 bits, SHA-3 uses different internal structure (Keccak sponge)
• Collision resistance is critical—SHA-1 was broken in 2017; SHA-256 remains secure for all known attacks
• Applications include Bitcoin mining (SHA-256), digital certificates, and data integrity verification

---

Digital Signature Schemes

Digital signatures provide authentication, integrity, and non-repudiation. The signer uses a private key to create a signature that anyone can verify using the corresponding public key.

Digital Signature Algorithm (DSA)

• Discrete logarithm security—based on the hardness of computing $x$ from $g^x \mod p$ in a prime-order subgroup
• Signature generation requires random $k$ for each signature—reusing $k$ completely breaks security
• Standardized by NIST—widely used in government and financial applications alongside RSA signatures

---

Quick Reference Table

---

Self-Check Questions

1. Both RSA and ElGamal are asymmetric encryption schemes. What mathematical hardness assumption does each rely on, and how does this affect their key generation processes?

2. Compare AES and DES: What structural difference (beyond key length) distinguishes their internal operations, and why is AES considered more secure against modern cryptanalysis?

3. If you need to establish a shared secret over an insecure channel without any prior key exchange, which algorithm would you use? What additional mechanism would you need to prevent man-in-the-middle attacks?

4. ECC provides equivalent security to RSA with much smaller keys. Explain the mathematical reason for this efficiency advantage in terms of the best-known attacks against each hardness assumption.

5. FRQ-style: A system uses SHA-1 for digital signatures and DES for encrypting session keys. Identify two specific vulnerabilities in this design and recommend replacement algorithms with justification.