Cryptography – Complete Reference Guide

Symmetric • Public Key • RSA • ECC • Hash Functions • Digital Signatures • Key Exchange • Attacks

Symmetric Encryption Basics

Definition

Same key for encryption & decryption: $E_k(m) = c$, $D_k(c) = m$

Classical Ciphers

Caesar: Shift letters by $k$ positions

Vigenère: Polyalphabetic with repeating key

One-Time Pad (OTP): $c = m \oplus k$, perfect secrecy

OTP Requirement: Key must be truly random, used only once, and $|k| \geq |m|$

Block Ciphers & Modes

AES (Rijndael)

Block size: 128 bits

Key sizes: 128, 192, or 256 bits

Rounds: 10, 12, or 14 (depends on key)

DES/3DES

Block: 64 bits, Key: 56 bits (DES)

3DES: $c = E_{k_3}(D_{k_2}(E_{k_1}(m)))$

Status: DES broken (2^56 weak), 3DES deprecated

Operation Modes

ECB: Each block independent (INSECURE)

CBC: $c_i = E_k(m_i \oplus c_{i-1})$ (needs IV)

CTR: Stream mode with counter, parallelizable

GCM: Auth encryption, provides integrity

ECB deterministic: same plaintext → same ciphertext!

Stream Ciphers

Concept

$c_i = m_i \oplus \text{keystream}[i]$

Examples

RC4: Fast, variable-length key (deprecated)

ChaCha: Modern, 256-bit key, 64/96-bit nonce

Salsa20: Stream cipher, high speed

LFSR (Linear Feedback)

$s_{i+n} = c_{n-1}s_{i+n-1} \oplus ... \oplus c_0 s_i$

Caution: LFSR alone is cryptographically weak

Number Theory Foundations

Modular Arithmetic

$a \equiv b \pmod{n}$ means $n | (a-b)$

$(a+b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$

$(a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n$

Euler's Totient Function

$\phi(n)$ = count of integers coprime to $n$

If $n=p$ (prime) $\phi(p) = p-1$

If $n=pq$ (distinct primes) $\phi(pq) = (p-1)(q-1)$

Euler's Theorem

If $\gcd(a,n)=1$: $a^{\phi(n)} \equiv 1 \pmod{n}$

Fermat's Little Theorem: If $p$ prime: $a^{p-1} \equiv 1 \pmod{p}$

Chinese Remainder Theorem

CRT Theorem

If $\gcd(n_1, n_2)=1$, then:

$x \equiv a_1 \pmod{n_1}$ and $x \equiv a_2 \pmod{n_2}$

has unique solution mod $n_1n_2$

Solution Formula

$x = a_1 M_1 y_1 + a_2 M_2 y_2 \pmod{n_1n_2}$

where $M_i = n / n_i$, $M_i y_i \equiv 1 \pmod{n_i}$

Application: RSA decryption speedup using CRT

RSA: Key Generation

Key Generation Steps

1. Choose large primes $p, q$ (1024+ bits)

2. Compute $n = pq$

3. Compute $\phi(n) = (p-1)(q-1)$

4. Choose $e$ with $\gcd(e, \phi(n)) = 1$, typically $e = 2^{16}+1$

5. Compute $d \equiv e^{-1} \pmod{\phi(n)}$ (extended GCD)

6. Public key: $(n, e)$, Private key: $(n, d)$

Encryption/Decryption

Encrypt: $c \equiv m^e \pmod{n}$

Decrypt: $m \equiv c^d \pmod{n}$

Verify: $m^{ed} \equiv m \pmod{n}$ (by Euler)

RSA Security & Attacks

Security Assumptions

Factoring Problem: Hard to factor $n=pq$

RSA Problem: Hard to compute $m$ from $c, e, n$

Common Vulnerabilities

Small $e$: Vulnerable to Hastad attack

Low Entropy: Poor randomness in $p, q$ selection

Textbook RSA: Deterministic (use OAEP padding)

Timing Attacks: Mitigated with constant-time arithmetic

Never use RSA without proper PKCS#1 v2.1 padding!

Diffie-Hellman Key Exchange

Protocol

1. Public: large prime $p$, generator $g$

2. Alice: choose random $a$, send $A = g^a \bmod p$

3. Bob: choose random $b$, send $B = g^b \bmod p$

4. Shared secret: $K = B^a = A^b = g^{ab} \bmod p$

Security

Hardness: Discrete Logarithm Problem (DLP)

Given $g, p, g^a \bmod p$, hard to find $a$

MITM Vulnerability: Unauthenticated (fix: sign exchange)

Parameters

Prime: 2048+ bits for security

Exponents: $a, b \geq 160$ bits

ECDH & ElGamal

Elliptic Curve DH

Curve: $y^2 = x^3 + ax + b \pmod{p}$

Public: curve, generator point $G$

Alice: $a \in [1, n-1]$, sends $[a]G$

Bob: $b \in [1, n-1]$, sends $[b]G$

Shared: $K = [a][b]G = [b][a]G$

256-bit ECC ≈ 3072-bit RSA in security

ElGamal

Encrypt: Choose random $r$, send $(g^r, m \cdot h^r)$ where $h = g^x$

Decrypt: $m = \frac{c_2}{c_1^x} = \frac{m \cdot g^{rx}}{g^{rx}}$

Hash Functions

Properties (Unkeyed)

One-Way: Easy $H(x) \to h$, hard $h \to x$ (preimage resistance)

Collision Resistance: Hard to find $x_1 \neq x_2$ with $H(x_1) = H(x_2)$

Second Preimage: Given $x$, hard to find $x' \neq x$ with $H(x') = H(x)$

Avalanche Effect: Small input change → large output change

Common Functions

MD5: 128-bit output (BROKEN, don't use)

SHA-1: 160-bit output (deprecated)

SHA-2: SHA-256, SHA-512 (secure)

SHA-3: Keccak-based, latest standard

Merkle-Damgård Construction

Iterative: $h_i = f(h_{i-1}, m_i)$, output $h_n$

Length extension attack possible on MD5, SHA-1, SHA-2

Message Authentication

MAC (Message Auth Code)

$\text{MAC}_k(m) = t$ provides integrity & authentication

Keyed hash: only holder of $k$ can compute valid MAC

Deterministic, not unique to message

HMAC Formula

$\text{HMAC}(k, m) = H((k \oplus \text{opad}) || H((k \oplus \text{ipad}) || m))$

opad: outer padding (0x5c repeated)

ipad: inner padding (0x36 repeated)

Output: Same size as underlying hash

Alternatives

CBC-MAC: Encrypt last block

CMAC: Variant for AES

GMAC: Galois/Counter Mode auth

Digital Signatures: RSA

RSA Signature

Sign: $s \equiv H(m)^d \pmod{n}$

Verify: Check $s^e \equiv H(m) \pmod{n}$

Properties

Authentication: Only holder of $d$ can sign

Non-repudiation: Signer cannot deny

Integrity: Any change to $m$ fails verification

PSS Padding (Secure)

Adds randomness to signature (RSASSA-PSS)

Deterministic PKCS#1 v1.5 is less secure

Always hash before signing: $s = \text{Sign}(H(m))$

DSA & ECDSA Signatures

DSA (Digital Signature Algorithm)

Params: Prime $p$, $q | (p-1)$, generator $g$

Private key: $x \in [1, q-1]$

Public key: $y = g^x \bmod p$

Signature Generation

1. Choose random $k \in [1, q-1]$

2. $r = (g^k \bmod p) \bmod q$

3. $s = k^{-1}(H(m) + xr) \bmod q$

4. Signature: $(r, s)$

ECDSA (Elliptic Curve)

Same structure as DSA but over EC group

256-bit ECDSA ≈ 3072-bit DSA security

Used in Bitcoin, TLS 1.3

Critical: $k$ must be random & unique per signature!

Elliptic Curve Cryptography

Curve Equation

Weierstrass: $y^2 = x^3 + ax + b \pmod{p}$

Must satisfy $\Delta = -16(4a^3 + 27b^2) \not\equiv 0 \pmod{p}$

Point Addition

$P + Q = R$ using geometric method

$P + O = P$ (identity element)

$P + (-P) = O$ (inverse)

Line through $P, Q$ intersects curve at $R$

Scalar Multiplication

$[k]P = P + P + ... + P$ ($k$ times)

Computed efficiently using double-and-add

Easy to compute $[k]P$, hard to find $k$ from $P, [k]P$ (ECDLP)

Standard Curves

P-256 (secp256r1): $p = 2^{256} - 2^{224} + 2^{192} + 2^{128} - 1$

Curve25519: $y^2 = x^3 + 486662x^2 + x \pmod{2^{255}-19}$

P-384, P-521: Higher security levels

Key Exchange Protocols

TLS Handshake (1.2)

Client Hello: cipher suites, random

Server Hello: chosen cipher, cert, random

Key Exchange: DH/ECDH params

Derive: Master secret from DH shared key

Session keys: encrypt/MAC keys from master

Perfect Forward Secrecy (PFS)

Ephemeral key exchange (DHE, ECDHE)

Session key independent of long-term key

Compromise of server key ≠ compromise of past sessions

TLS 1.3 Changes

Mandatory PFS (DHE/ECDHE only)

0-RTT resumption optional

Removed static RSA, weak ciphers

Security Notions

IND-CPA (Semantic Security)

Adversary cannot distinguish encryptions of two chosen messages

Implies: deterministic encryption is insecure

Requires: randomized encryption (nonce/IV)

IND-CCA2 (Chosen Ciphertext)

Adversary can request decryptions, cannot distinguish messages

Stronger than IND-CPA

Example: RSASSA-OAEP, AES-GCM

Authenticated Encryption (AEAD)

Encryption + MAC combined: $\text{Enc}_k(m) = (c, t)$

Provides confidentiality AND authenticity

Examples: GCM, ChaCha20-Poly1305

Common Cryptographic Attacks

Implementation Attacks

Timing: Execution time leaks info

Power Analysis: Power consumption patterns

Side-Channel: Cache, branch prediction, etc.

Mathematical Attacks

Factoring: Pollard's $\rho$, quadratic sieve, GNFS

Discrete Log: Baby-step Giant-step, Pohlig-Hellman

Collision: Birthday attack in $O(2^{n/2})$ time

Protocol Attacks

MITM: Intercept unauthenticated exchange

Replay: Reuse old message (fix: nonce, timestamp)

Downgrade: Force weaker cipher (SSLv3, RC4)

Padding Oracle: Attacker decrypts via error messages (fix: encrypt-then-MAC)

Protocols & Certificates

X.509 Certificates

Contains: Public key, identity, issuer, validity dates

Signed by: Certificate Authority (CA) private key

Chain: Root CA → Intermediate → End-entity

Certificate Validation

1. Check signature with issuer's public key

2. Verify dates (not before/not after)

3. Check CN/SAN matches domain

4. Verify chain to trusted root

HTTPS/TLS Flow

Client: Request cert, verify signature

Exchange: DH/ECDH key agreement

Encrypt: All subsequent traffic encrypted

HSTS: HTTP Strict-Transport-Security forces HTTPS

CRYPTOGRAPHY Complete Reference