Information Security

1. Mathematical Foundations¶

1.1 Number Theory¶

Basic Properties¶

Prime Numbers: Integers greater than 1 divisible only by 1 and themselves
Greatest Common Divisor (GCD): $gcd (a, b)$ is the largest integer that divides both $a$ and $b$
Extended Euclidean Algorithm: Computes $gcd (a, b)$ and coefficients $s, t$ such that $a s + b t = gcd (a, b)$
Coprime: Integers $a$ and $b$ are coprime if $gcd (a, b) = 1$

Modular Arithmetic¶

Congruence: $a \equiv b (\mod n)$ means $n$ divides $(a - b)$
Modular Addition: $(a + b) mod n = ((a mod n) + (b mod n)) mod n$
Modular Multiplication: $(a \times b) mod n = ((a mod n) \times (b mod n)) mod n$
Modular Inverse: $a^{- 1} mod n$ is a number $b$ such that $a b \equiv 1 (\mod n)$
Exists only when $gcd (a, n) = 1$
Can be computed using the extended Euclidean algorithm

Groups, Fields, and Cyclic Groups¶

Group: Set with an operation that is closed, associative, has identity, and inverses
Field: Set with two operations (addition and multiplication) that form abelian groups
Cyclic Group: Group where every element can be expressed as powers of one element
Generator: Element $g$ such that ${g^{0}, g^{1}, g^{2}, . . .}$ generates the entire group
Order of an element: Smallest positive integer $r$ such that $g^{r} = 1$

1.2 Computational Complexity¶

Asymptotic Notation¶

Big-O Notation: $f (n) = O (g (n))$ means $f$ grows no faster than $g$
Polynomial Time: Algorithm runs in time $O (n^{k})$ for some constant $k$
Negligible Function: Function $μ (n)$ that decreases faster than the inverse of any polynomial
Formally: $\forall c > 0, \exists n_{0} : \forall n > n_{0}, μ (n) < \frac{1}{n^{c}}$

Computational Models¶

Probabilistic Polynomial Time (PPT): Algorithms that run in polynomial time with access to random bits
Uniform vs. Non-uniform Computation: Distinction between algorithms (uniform) and circuit families (non-uniform)

1.3 Computational Hardness Assumptions¶

One-way Functions¶

Functions easy to compute but difficult to invert
Formally: $f$ is one-way if for any PPT adversary $A$ :

Pr [f (A (f (x), 1^{n})) = f (x)] \leq negl (n)

where $x$ is chosen uniformly from ${0, 1}^{n}$

Discrete Logarithm Problem¶

Given $g$ and $h = g^{x}$ in a group $G$ , find $x$
Believed to be hard in:
Multiplicative groups of prime fields $Z_{p}^{*}$ with large $p$
Elliptic curve groups over finite fields
Best known classical algorithm: Index calculus, sub-exponential time for $Z_{p}^{*}$
Best known quantum algorithm: Shor's algorithm, polynomial time

Integer Factorization Problem¶

Given $N = p q$ (product of two large primes), find $p$ and $q$
Best known classical algorithm: General Number Field Sieve (GNFS)
Running time: $\exp ((\sqrt[3]{\frac{64}{9}} + o (1)) (\ln N)^{1 / 3} (\ln \ln N)^{2 / 3})$
Best known quantum algorithm: Shor's algorithm, polynomial time

Decisional Diffie-Hellman (DDH) Assumption¶

The distributions $(g, g^{a}, g^{b}, g^{a b})$ and $(g, g^{a}, g^{b}, g^{c})$ are computationally indistinguishable
Where $a, b, c$ are randomly chosen from the appropriate range

RSA Assumption¶

Given $N = p q$ , $e$ such that $gcd (e, ϕ (N)) = 1$ , and $y = x^{e} mod N$ , it's hard to compute $x$
Weaker than factoring (breaking RSA doesn't necessarily mean factoring $N$ )

2. Information-Theoretic vs. Computational Security¶

2.1 Information-Theoretic Security¶

Perfect Secrecy¶

Definition: A cryptosystem has perfect secrecy if:

\forall m \in M, \forall c \in C, Pr [M = m | C = c] = Pr [M = m]

Equivalent formulation: For any two messages $m_{1}, m_{2}$ and any ciphertext $c$ :

Pr [C = c | M = m_{1}] = Pr [C = c | M = m_{2}]

One-time Pad: Achieves perfect secrecy:
Key: Random bit string $k \in {0, 1}^{n}$
Encryption: $E (m, k) = m \oplus k$
Decryption: $D (c, k) = c \oplus k$

Shannon's Theorem¶

Any encryption scheme with perfect secrecy must have $| K | \geq | M |$
Proof sketch:
For each ciphertext $c$ , define $S_{c} = {k : \exists m such that E (m, k) = c}$
For perfect secrecy, each key in $S_{c}$ must encrypt to a different message
Therefore, $| S_{c} | \geq | M |$ for each $c$
Since sets $S_{c}$ are disjoint, $| K | \geq | M |$

Statistical Security¶

Relaxation of perfect secrecy
Distributions of ciphertexts are statistically close
Still requires keys as long as messages

2.2 Computational Security¶

Basic Concept¶

Security against computationally bounded adversaries
Based on hardness assumptions (problems believed to be difficult)
Allows for much more efficient cryptographic schemes

Advantages over Information-Theoretic Security¶

Can use keys much shorter than messages
Enables public-key cryptography
Practical for real-world applications

Limitations¶

Security is conditional on unproven computational assumptions
Vulnerable to unforeseen algorithmic breakthroughs
Potentially vulnerable to quantum computers

2.3 Key Differences¶

Adversary Power¶

Information-theoretic: Secure against unbounded adversaries
Computational: Secure only against bounded (typically polynomial-time) adversaries

Proof Techniques¶

Information-theoretic: Based on probability theory
Computational: Based on reductions to hard computational problems

Practical Applicability¶

Information-theoretic: Limited to key distribution, authentication codes
Computational: Basis for nearly all practical cryptography

3. Symmetric Cryptography¶

3.1 Computational Security Models¶

Indistinguishability Experiments¶

IND-CPA Game:
Challenger generates key $k \leftarrow Gen (1^{n})$
Adversary $A$ can make polynomial queries to encryption oracle ${Enc}_{k} (\cdot)$
$A$ selects $m_{0}, m_{1}$ of equal length
Challenger selects $b \leftarrow {0, 1}$ uniformly and sends $c = {Enc}_{k} (m_{b})$
$A$ can continue making encryption queries
$A$ outputs guess $b^{'}$
$A$ wins if $b^{'} = b$
Advantage: ${Adv}_{Π, A}^{CPA} (n) = | Pr [b^{'} = b] - \frac{1}{2} |$
CPA Security: Scheme is CPA-secure if for all PPT adversaries $A$ , ${Adv}_{Π, A}^{CPA} (n)$ is negligible

CCA Security¶

IND-CCA Game:
Same as IND-CPA, but adversary also has access to decryption oracle ${Dec}_{k} (\cdot)$
Cannot decrypt the challenge ciphertext $c$
Advantage: ${Adv}_{Π, A}^{CCA} (n) = | Pr [b^{'} = b] - \frac{1}{2} |$
CCA Security: Scheme is CCA-secure if for all PPT adversaries $A$ , ${Adv}_{Π, A}^{CCA} (n)$ is negligible

Real-vs-Random Security¶

Alternative definition equivalent to IND-CPA
Adversary cannot distinguish encryptions of chosen messages from encryptions of random messages

3.2 Pseudorandom Functions and Permutations¶

PRF (Pseudorandom Function):

A function family $F : {0, 1}^{k} \times {0, 1}^{n} \to {0, 1}^{m}$
For a key $K \in {0, 1}^{k}$ , $F_{K} (x) = F (K, x)$ where $x \in {0, 1}^{n}$
Security definition: For any probabilistic polynomial-time adversary $A$ with oracle access:

| Pr [K \leftarrow {0, 1}^{k} : A^{F_{K}} (1^{n}) = 1] - Pr [f \leftarrow {Func}_{n} : A^{f} (1^{n}) = 1] | \leq negl (n)

where ${Func}_{n}$ is the set of all functions from ${0, 1}^{n}$ to ${0, 1}^{m}$

PRG (Pseudorandom Generator):

A deterministic function $G : {0, 1}^{s} \to {0, 1}^{l}$ where $l > s$
Security definition: For any probabilistic polynomial-time adversary $A$ :

| Pr [r \leftarrow {0, 1}^{s} : A (G (r)) = 1] - Pr [y \leftarrow {0, 1}^{l} : A (y) = 1] | \leq negl (s)

PRP (Pseudorandom Permutation):

A keyed family of permutations $P : {0, 1}^{k} \times {0, 1}^{n} \to {0, 1}^{n}$
For each key $K \in {0, 1}^{k}$ , $P_{K} (\cdot)$ is a bijection on ${0, 1}^{n}$
Security definition: For any probabilistic polynomial-time adversary $A$ with oracle access:

| Pr [K \leftarrow {0, 1}^{k} : A^{P_{K}, P_{K}^{- 1}} (1^{n}) = 1] - Pr [π \leftarrow {Perm}_{n} : A^{π, π^{- 1}} (1^{n}) = 1] | \leq negl (n)

where ${Perm}_{n}$ is the set of all permutations on ${0, 1}^{n}$

Relationship construction examples:

PRG from PRF: $G (s) = F_{s} (1) ‖ F_{s} (2) ‖ . . . ‖ F_{s} (t)$ for seed $s$
PRF from PRG (GGM): For a PRG $G$ that doubles input length with $G_{0}, G_{1}$ as its output halves: $F_{K} (x_{1} x_{2} . . . x_{n}) = G_{x_{n}} (. . . G_{x_{2}} (G_{x_{1}} (K)) . . .)$
PRP from PRF (Luby-Rackoff): A 3-round Feistel network using a PRF creates a PRP

Pseudorandom Functions (PRFs)¶

Family of functions $F : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}^{n}$
Security: Computationally indistinguishable from a truly random function
Formally: For any PPT distinguisher $D$ :

| Pr [D^{F_{k} (\cdot)} (1^{n}) = 1] - Pr [D^{f (\cdot)} (1^{n}) = 1] | \leq negl (n)

where $k \leftarrow {0, 1}^{n}$ and $f$ is a random function

Pseudorandom Permutations (PRPs)¶

Family of permutations $P : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}^{n}$
Each $P_{k}$ is a bijection
Security: Computationally indistinguishable from a truly random permutation

PRF/PRP Switching Lemma¶

For any distinguisher making $q$ queries:

| Pr [D^{f (\cdot)} (1^{n}) = 1] - Pr [D^{π (\cdot)} (1^{n}) = 1] | \leq \frac{q (q - 1)}{2^{n + 1}}

where $f$ is a random function and $π$ is a random permutation

PRG from PRF¶

A pseudorandom generator can be constructed from a pseudorandom function by using the PRF to expand a seed into a longer output:

G (s) = F_{s} (1) ‖ F_{s} (2) ‖ \dots ‖ F_{s} (t)

Elaboration: - Start with a seed $s \in {0, 1}^{k}$ - Use the seed as the key for the PRF $F$ - Evaluate the PRF on successive inputs $1, 2, \dots, t$ (typically encoded as fixed-length bit strings) - Concatenate all outputs to get a longer pseudorandom string - If $F_{s}$ outputs $m$ bits and we evaluate it $t$ times, we expand $k$ bits to $t \cdot m$ bits - Security follows from the PRF property: if the outputs were distinguishable from random, the PRF could be distinguished from a random function

PRF from PRG (GGM Construction)¶

The Goldreich-Goldwasser-Micali (GGM) construction builds a PRF from a PRG:

F_{K} (x_{1} x_{2} \dots x_{n}) = G_{x_{n}} (\dots G_{x_{2}} (G_{x_{1}} (K)) \dots)

Elaboration: - Start with a PRG $G : {0, 1}^{n} \to {0, 1}^{2 n}$ that doubles input length - Split $G$ 's output into two equal halves: $G (z) = G_{0} (z) ‖ G_{1} (z)$ where $| G_{0} (z) | = | G_{1} (z) | = n$ - For input $x = x_{1} x_{2} \dots x_{n} \in {0, 1}^{n}$ and key $K \in {0, 1}^{n}$ : - Compute $K_{1} = G_{x_{1}} (K)$ - Compute $K_{2} = G_{x_{2}} (K_{1})$ - Continue for each bit of $x$ - Return $K_{n} = G_{x_{n}} (K_{n - 1})$ - This effectively creates a binary tree of depth $n$ with $2^{n}$ leaves - Each input $x$ defines a path through this tree, and $F_{K} (x)$ is the value at the end of this path - Security relies on the PRG's expansion property: any polynomial-time adversary cannot distinguish between PRG outputs and random strings

PRP from PRF (Luby-Rackoff Construction)¶

The Luby-Rackoff construction uses the Feistel network to convert a PRF into a PRP:

Elaboration: - Start with a PRF $F : {0, 1}^{k} \times {0, 1}^{n / 2} \to {0, 1}^{n / 2}$ - Use 3 or 4 rounds of a Feistel network with independent keys $K_{1}, K_{2}, K_{3}, K_{4}$ - For input $x = (L_{0}, R_{0})$ where $| L_{0} | = | R_{0} | = n / 2$ : - Round 1: $L_{1} = R_{0}$ , $R_{1} = L_{0} \oplus F_{K_{1}} (R_{0})$ - Round 2: $L_{2} = R_{1}$ , $R_{2} = L_{1} \oplus F_{K_{2}} (R_{1})$ - Round 3: $L_{3} = R_{2}$ , $R_{3} = L_{2} \oplus F_{K_{3}} (R_{2})$ - Round 4 (optional): $L_{4} = R_{3}$ , $R_{4} = L_{3} \oplus F_{K_{4}} (R_{3})$ - Output $(L_{3}, R_{3})$ or $(L_{4}, R_{4})$ - The result is a permutation because each Feistel round is invertible - Three rounds provide security against chosen-plaintext attacks - Four rounds provide security against chosen-ciphertext attacks - This construction is the theoretical foundation for block ciphers like DES and forms the basis for the security proof of block cipher modes

Other Important Relationships¶

PRP to PRF¶

A PRP can be used as a PRF directly when the input domain is large
For $n$ -bit inputs, the statistical distance is bounded by $q^{2} / 2^{n + 1}$ where $q$ is the number of queries
This is known as the PRP/PRF switching lemma

PRG from One-Way Functions¶

Håstad, Impagliazzo, Levin, and Luby showed that PRGs can be constructed from any one-way function
This is a fundamental result showing that pseudorandomness can be built from minimal cryptographic assumptions

PRP Composition¶

The composition of secure PRPs results in another secure PRP
This justifies multi-round block cipher designs that compose multiple simpler permutations

3.3 Block Ciphers¶

Fixed-length permutations parameterized by a key
Examples: DES (56-bit key, 64-bit block), AES (128/192/256-bit key, 128-bit block)
Design principles: Substitution-permutation networks, Feistel networks
Security goal: Behave as a PRP

DES (Data Encryption Standard)¶

Feistel network with 16 rounds
56-bit key (effectively 48 bits of security due to complementation property)
Vulnerable to exhaustive search

AES (Advanced Encryption Standard)¶

Substitution-permutation network with 10/12/14 rounds
128/192/256-bit key
Operations: SubBytes, ShiftRows, MixColumns, AddRoundKey

3.4 Modes of Operation¶

Electronic Codebook (ECB)¶

$c_{i} = E_{K} (m_{i})$
Insecure for multiple blocks (patterns in plaintext visible in ciphertext)

Cipher Block Chaining (CBC)¶

$c_{i} = E_{K} (m_{i} \oplus c_{i - 1})$ with $c_{0} = I V$
CPA-secure if IV is random and unpredictable
Vulnerable to padding oracle attacks

Counter Mode (CTR)¶

$c_{i} = m_{i} \oplus E_{K} (I V + i)$
Effectively turns block cipher into stream cipher
CPA-secure if $(I V, I V + 1, . . .)$ never repeats
Parallelizable

Galois/Counter Mode (GCM)¶

Combines CTR mode encryption with authentication
Provides authenticated encryption
Fast and parallelizable

3.5 Stream Ciphers¶

Generate pseudorandom keystream from seed
XOR keystream with plaintext: $c_{i} = m_{i} \oplus k s_{i}$
Examples: RC4 (insecure), ChaCha20

RC4¶

Simple key scheduling algorithm and byte generation
Various weaknesses, no longer recommended

ChaCha20¶

Based on add-rotate-XOR (ARX) operations
256-bit key, 96-bit nonce, 32-bit counter
Often paired with Poly1305 for authentication (ChaCha20-Poly1305)

4. Cryptographic Hash Functions¶

4.1 Security Properties¶

Pre-image Resistance: Given $h$ , hard to find any $m$ such that $H (m) = h$
Formally: For all PPT adversaries $A$ :

Pr [H (A (H (x), 1^{n})) = H (x)] \leq negl (n)

where $x$ is chosen uniformly

Second Pre-image Resistance: Given $m_{1}$ , hard to find $m_{2} \neq m_{1}$ such that $H (m_{1}) = H (m_{2})$
Formally: For all PPT adversaries $A$ :

Pr [A (x) = x^{'} : x^{'} \neq x and H (x) = H (x^{'})] \leq negl (n)

where $x$ is chosen uniformly

Collision Resistance: Hard to find any $m_{1} \neq m_{2}$ such that $H (m_{1}) = H (m_{2})$
Formally: For all PPT adversaries $A$ :

Pr [A (1^{n}) = (x, x^{'}) : x \neq x^{'} and H (x) = H (x^{'})] \leq negl (n)

Relationships: Collision resistance ⟹ Second pre-image resistance ⟹̸ Pre-image resistance

4.2 Birthday Attack¶

Finds collisions in $O (2^{n / 2})$ time for $n$ -bit hash
Based on birthday paradox probability:

P (n, d) \approx 1 - e^{- n^{2} / (2 d)}

where $n$ is number of elements, $d$ is range size

For 50% probability of collision:
Need approximately $1.177 \times 2^{n / 2}$ samples from $n$ -bit hash
Implications:
128-bit hash provides only 64 bits of collision resistance
256-bit hash needed for 128-bit collision resistance

4.3 Hash Function Constructions¶

Merkle-Damgård Construction¶

Foundation for many hash functions (MD5, SHA-1, SHA-2)
Message $M$ split into blocks $M = m_{1} | | m_{2} | | . . . | | m_{L}$
Compression function $f$ iteratively applied:
$h_{0} = I V$ (initialization vector)
$h_{i} = f (h_{i - 1}, m_{i})$ for $i = 1, 2, . . ., L$
$H (M) = h_{L}$
Length padding: Append message length to prevent length extension attacks
Security: If compression function is collision-resistant, so is the hash function

Sponge Construction¶

Used in SHA-3 (Keccak)
Based on permutation $f$ of fixed size
Two phases:
Absorbing: Incorporate message blocks
Squeezing: Extract hash bits
Resistant to length extension attacks

4.4 Common Hash Functions¶

MD5¶

128-bit output
Merkle-Damgård construction
Broken (collisions can be found in seconds)

SHA-1¶

160-bit output
Merkle-Damgård construction
Broken (collisions demonstrated in practice)

SHA-2 Family¶

Includes SHA-224, SHA-256, SHA-384, SHA-512
Merkle-Damgård construction
Currently secure, but similar design to SHA-1

SHA-3 (Keccak)¶

Sponge construction
More resistant to attacks that affect SHA-2
Flexible output size

5. Message Authentication¶

5.1 Message Authentication Codes (MACs)¶

Provide data integrity and authentication
Function $MAC : K \times M \to T$
Security goal: Existential unforgeability under chosen message attack (EU-CMA)

Security Definition¶

EU-CMA Game:
Challenger generates key $k \leftarrow Gen (1^{n})$
Adversary $A$ can make queries to ${MAC}_{k} (\cdot)$
$A$ outputs $(m, t)$
$A$ wins if ${Vrfy}_{k} (m, t) = 1$ and $m$ was not queried
Advantage: ${Adv}_{Π, A}^{MAC} (n) = Pr [A wins]$
Security: MAC is secure if for all PPT adversaries $A$ , ${Adv}_{Π, A}^{MAC} (n)$ is negligible

5.2 MAC Constructions¶

CBC-MAC¶

Based on block cipher in CBC mode
$t_{0} = 0^{n}$
$t_{i} = E_{K} (m_{i} \oplus t_{i - 1})$ for $i = 1, 2, . . ., L$
Output $t_{L}$ as the MAC tag
Secure only for fixed-length messages
For variable-length messages, use:
EMAC: Encrypt the final output with a different key
CMAC: Use different masks for final block, handle padding

HMAC¶

Hash-based MAC:

{HMAC}_{K} (m) = H ((K \oplus opad) | | H ((K \oplus ipad) | | m))

where $opad = 0 x 5 c . . .5 c$ and $ipad = 0 x 36. . .36$

More secure than naive $H (K | | m)$ approach
Security based on compression function properties

Poly1305¶

Based on polynomial evaluation in a finite field
Often used with ChaCha20
Strong information-theoretic security guarantees
Extremely efficient

5.3 Authenticated Encryption¶

Definition¶

Provides both confidentiality and integrity
Formally: $(Gen, Enc, Dec)$ where:
$Gen (1^{n})$ outputs key $k$
${Enc}_{k} (m)$ outputs ciphertext $c$
${Dec}_{k} (c)$ outputs $m$ or $⊥$ (invalid)

Security¶

IND-CCA security
Ciphertext integrity: Cannot forge valid ciphertexts

Generic Compositions¶

Encrypt-then-MAC: $C = E_{K} (M) | | {MAC}_{K^{'}} (E_{K} (M))$
Provably secure
Preferred approach
MAC-then-Encrypt: $C = E_{K} ({MAC}_{K^{'}} (M) | | M)$
Can be vulnerable (e.g., TLS CBC padding oracle attacks)
Encrypt-and-MAC: $C = E_{K} (M) | | {MAC}_{K^{'}} (M)$
May leak information about plaintext

AEAD Modes¶

GCM (Galois/Counter Mode):
CTR mode encryption with GHASH authentication
Uses Galois field multiplication
Fast and widely deployed
ChaCha20-Poly1305:
ChaCha20 stream cipher with Poly1305 MAC
More secure on platforms without AES hardware acceleration
CCM (Counter with CBC-MAC):
Combines CTR mode with CBC-MAC
Less efficient than GCM

5.4 Replay Attack Prevention¶

Replay Attack: Adversary captures valid message and resends later
MACs alone don't prevent replay attacks

Prevention Techniques¶

Sequence Numbers: Include monotonically increasing counter in authenticated data
Timestamps: Include timestamp in authenticated data
Nonces (Numbers Used Once): Include random/unique value in authenticated data
Challenge-Response: Server sends random challenge that must be included in authenticated response

6. Public Key Cryptography¶

6.1 Fundamental Differences from Symmetric Cryptography¶

Structural Differences¶

Symmetric: Same key for encryption and decryption
Public Key: Different keys for encryption (public) and decryption (private)

Underlying Assumptions¶

Symmetric: Based on confusion and diffusion (information-theoretic concepts)
Public Key: Based on mathematical hardness assumptions (computational concepts)

Key Distribution Problem¶

Symmetric Problem: $n$ users need $(\binom{n}{2}) = \frac{n (n - 1)}{2}$ keys for pairwise communication
Public Key Solution: $n$ users need only $2 n$ keys (public + private for each)

Performance¶

Symmetric: Typically 1000-10000x faster than public key operations
Public Key: Computationally intensive
Hybrid Systems: Use public key crypto for key exchange, symmetric for data encryption

6.2 Key Distribution Approaches¶

Key Distribution Center (KDC)¶

Trusted third party that distributes session keys
Each user shares a long-term key with the KDC
Example: Kerberos authentication protocol

Key Agreement Protocols¶

Allow two parties to derive a shared secret over an insecure channel
Example: Diffie-Hellman key exchange

Public Key Infrastructure (PKI)¶

System for distributing and validating public keys
Components: Certificate Authorities (CAs), certificates, revocation

6.3 RSA Cryptosystem¶

Key Generation¶

Generate large primes $p, q$ (typically 1024-2048 bits each)
Compute $N = p q$
Compute $ϕ (N) = (p - 1) (q - 1)$
Choose $e$ such that $gcd (e, ϕ (N)) = 1$ (typically 65537)
Compute $d$ such that $e d \equiv 1 (\mod ϕ (N))$
Public key: $(N, e)$ , Private key: $d$

Encryption/Decryption¶

Encryption: $c = m^{e} mod N$
Decryption: $m = c^{d} mod N$

Correctness¶

For any $m \in Z_{N}^{*}$ :

c^{d} \equiv (m^{e})^{d} \equiv m^{e d} \equiv m^{k ϕ (N) + 1} \equiv m \cdot (m^{ϕ (N)})^{k} \equiv m \cdot 1^{k} \equiv m (\mod N)

where $e d = k ϕ (N) + 1$ for some integer $k$

Security¶

Based on hardness of factoring $N$ or solving the RSA problem
Basic (textbook) RSA is deterministic and NOT CPA secure
Vulnerable to:
Chosen ciphertext attacks
Common modulus attacks
Low public exponent attacks
Timing attacks

6.4 RSA Padding Schemes¶

PKCS#1 v1.5 Padding¶

Format: $EB = 00 | | 02 | | PS | | 00 | | M$
Where PS is random non-zero bytes of appropriate length
Prevents certain mathematical attacks
Vulnerable to Bleichenbacher's attack

Optimal Asymmetric Encryption Padding (OAEP)¶

Combines message with random seed through hash functions
Provides provable security in the random oracle model
More complex but stronger security properties

6.5 Chinese Remainder Theorem (CRT)¶

Theorem Statement¶

If $m_{1}, m_{2}, . . ., m_{k}$ are pairwise coprime, then the system of congruences:

x \equiv a_{1} (\mod m_{1})

x \equiv a_{2} (\mod m_{2})

⋮

x \equiv a_{k} (\mod m_{k})

has a unique solution modulo $M = m_{1} \cdot m_{2} \cdot . . . \cdot m_{k}$

RSA-CRT Decryption¶

Compute $m_{p} = c^{d mod (p - 1)} mod p$
Compute $m_{q} = c^{d mod (q - 1)} mod q$
Compute $m = (m_{p} \cdot q \cdot (q^{- 1} mod p) + m_{q} \cdot p \cdot (p^{- 1} mod q)) mod N$
Approximately 4x faster than standard RSA decryption

6.6 Diffie-Hellman Key Exchange¶

Protocol¶

Setup: Public parameters $(p, g)$ where $p$ is prime and $g$ is a generator of $Z_{p}^{*}$
Alice:
Choose random $a \in {1, 2, . . ., p - 2}$
Compute $A = g^{a} mod p$
Send $A$ to Bob
Bob:
Choose random $b \in {1, 2, . . ., p - 2}$
Compute $B = g^{b} mod p$
Send $B$ to Alice
Shared secret: $K = A^{b} mod p = B^{a} mod p = g^{a b} mod p$

Security¶

Security based on Computational Diffie-Hellman (CDH) assumption
Vulnerable to man-in-the-middle attacks without authentication
Variants:
Static-Static: Both parties have long-term DH keys
Ephemeral-Ephemeral: Both parties generate new DH keys per exchange
Static-Ephemeral: One party has long-term key, other generates new key

6.7 ElGamal Encryption¶

Key Generation¶

Choose prime $p$ and generator $g$ of $Z_{p}^{*}$
Choose random $x \in {1, 2, . . ., p - 2}$
Compute $h = g^{x} mod p$
Public key: $(p, g, h)$ , Private key: $x$

Encryption/Decryption¶

Encryption:
Choose random $y \in {1, 2, . . ., p - 2}$
Compute $c_{1} = g^{y} mod p$
Compute $c_{2} = m \cdot h^{y} mod p$
Ciphertext: $(c_{1}, c_{2})$
Decryption:
Compute $s = c_{1}^{x} mod p$
Compute $m = c_{2} \cdot s^{- 1} mod p$

Properties¶

CPA secure under the Decisional Diffie-Hellman (DDH) assumption
Naturally randomized (different ciphertexts for same plaintext)
Ciphertext expansion: 2x plaintext size
Multiplicatively homomorphic: $E (m_{1}) \cdot E (m_{2}) = E (m_{1} \cdot m_{2})$

6.8 Security Definitions for Public Key Cryptography¶

CPA Security¶

Similar to symmetric CPA security
Adversary always has the public key, so can encrypt any message
Game:
Challenger generates $(p k, s k) \leftarrow Gen (1^{n})$
Adversary gets $p k$
Adversary selects $m_{0}, m_{1}$ of equal length
Challenger selects $b \leftarrow {0, 1}$ uniformly and sends $c = {Enc}_{p k} (m_{b})$
Adversary outputs guess $b^{'}$
Adversary wins if $b^{'} = b$

CCA Security¶

As above, but adversary can also query decryption oracle
Cannot decrypt the challenge ciphertext
Important for practical security
Achieved by schemes like RSA-OAEP, Cramer-Shoup

7. Digital Signatures¶

7.1 Basic Concepts¶

Digital analog of handwritten signatures
Only the signer can create valid signatures, but anyone can verify
Scheme $(G e n, S i g n, V e r i f y)$ :
$G e n (1^{n})$ : Outputs key pair $(p k, s k)$
$S i g n (s k, m)$ : Outputs signature $σ$
$V e r i f y (p k, m, σ)$ : Outputs 1 (valid) or 0 (invalid)

7.2 Security Definition¶

Existential Unforgeability under Chosen Message Attack (EU-CMA)¶

Game:
Challenger generates $(p k, s k) \leftarrow Gen (1^{n})$
Adversary gets $p k$ and access to ${Sign}_{s k} (\cdot)$
Adversary outputs $(m, σ)$
Adversary wins if $Verify (p k, m, σ) = 1$ and $m$ was not queried to signing oracle

Strong Unforgeability¶

As above, but adversary also wins if it produces a new signature for a previously signed message

7.3 RSA Signatures¶

Basic idea: "Decrypt" the message with private key
Signing: $σ = m^{d} mod N$ (uses private key)
Verification: Check if $σ^{e} \equiv m (\mod N)$ (uses public key)
In practice, sign a hash: $σ = H (m)^{d} mod N$
Need padding schemes for security (e.g., PKCS#1 v1.5, PSS)

7.4 Digital Signature Algorithm (DSA)¶

Key Generation¶

Choose prime $p$ and prime $q$ such that $q$ divides $p - 1$
Choose $g$ of order $q$ in $Z_{p}^{*}$
Choose random $x \in {1, 2, . . ., q - 1}$
Compute $y = g^{x} mod p$
Public key: $(p, q, g, y)$ , Private key: $x$

Signing¶

Choose random $k \in {1, 2, . . ., q - 1}$
Compute $r = (g^{k} mod p) mod q$
Compute $s = k^{- 1} (H (m) + x r) mod q$
Signature: $(r, s)$

Verification¶

Check that $0 < r, s < q$
Compute $w = s^{- 1} mod q$
Compute $u_{1} = H (m) \cdot w mod q$
Compute $u_{2} = r \cdot w mod q$
Compute $v = (g^{u_{1}} \cdot y^{u_{2}} mod p) mod q$
Signature is valid if $v = r$

7.5 Elliptic Curve Digital Signature Algorithm (ECDSA)¶

Variant of DSA using elliptic curve groups
Smaller key sizes for equivalent security
Basic structure similar to DSA with operations in elliptic curve group

8. Security Reductions¶

8.1 Reduction Concept¶

Proof technique to establish security based on hardness assumptions
If problem A can be reduced to problem B:
Algorithm for B can be used to solve A
Hardness of A implies hardness of B

8.2 Types of Reductions¶

Polynomial-time Reductions¶

Mapping problem instances in polynomial time
Standard for computational complexity

Concrete Security Reductions¶

Preserves exact security parameters
Example: "If attacker breaks scheme with advantage $ϵ$ , we can solve hard problem with advantage $ϵ / 2$ "

8.3 Example Reductions¶

ElGamal Security Reduction¶

CPA security of ElGamal reduces to the Decisional Diffie-Hellman (DDH) problem
Reduction transforms a DDH challenge into an ElGamal encryption

RSA-OAEP Security Reduction¶

CCA security of RSA-OAEP reduces to RSA assumption in the random oracle model
More complex reduction using properties of the OAEP transform

9. Advanced Topics¶

9.1 Quantum Effects on Cryptography¶

Shor's Algorithm¶

Polynomial-time quantum algorithm for factoring integers and computing discrete logarithms
Breaks RSA, DSA, ECDSA, and Diffie-Hellman

Grover's Algorithm¶

Quadratic speedup for brute-force search
Reduces symmetric key security by half (e.g., 128-bit keys provide 64-bit security)
Implication: Double key lengths for symmetric algorithms

9.2 Post-Quantum Cryptography¶

Lattice-based Cryptography¶

Based on hardness of lattice problems
Examples: NTRU, Ring-LWE, Module-LWE
NIST candidates: CRYSTALS-Kyber, SABER

Code-based Cryptography¶

Based on hardness of decoding random linear codes
Example: McEliece cryptosystem
NIST candidates: Classic McEliece

Multivariate Cryptography¶

Based on hardness of solving multivariate polynomial equations
Examples: HFE, UOV
NIST candidates: Rainbow

Hash-based Signatures¶

Security based solely on hash function properties
Examples: Lamport signatures, XMSS, SPHINCS+
Stateful vs. stateless designs

9.3 Zero-Knowledge Proofs¶

Definition¶

Interactive protocol between prover and verifier
Properties:
Completeness: Honest prover convinces honest verifier
Soundness: Dishonest prover cannot convince honest verifier
Zero-knowledge: Verifier learns nothing but truth of statement

Non-interactive Zero-Knowledge (NIZK)¶

Zero-knowledge proofs without interaction
Often uses a common reference string

Applications¶

Authentication without revealing secrets
Private transactions in cryptocurrencies
Secure multi-party computation

9.4 Secure Multi-party Computation¶

Definition¶

Multiple parties compute function on private inputs
No party learns anything beyond their output

Approaches¶

Garbled circuits
Secret sharing
Homomorphic encryption

Applications¶

Privacy-preserving analytics
Secure auctions
Private machine learning

9.5 Homomorphic Encryption¶

Partial Homomorphism¶

ElGamal: Multiplicative homomorphism
Paillier: Additive homomorphism

Fully Homomorphic Encryption (FHE)¶

Allows arbitrary computations on encrypted data
First construction: Gentry (2009)
Current schemes: BGV, BFV, CKKS, GSW
Still impractical for many applications but improving rapidly

10. Cryptographic Protocols¶

10.1 Secure Communication Protocols¶

Transport Layer Security (TLS)¶

Provides secure communication over computer networks
Components:
Handshake protocol (key exchange, authentication)
Record protocol (data encryption, integrity)
Versions: TLS 1.2, TLS 1.3 (removes vulnerable constructions)

Secure Shell (SSH)¶

Secure remote login and command execution
Components:
Transport layer (encryption, integrity)
Authentication protocol
Connection protocol

10.2 Authentication Protocols¶

Password-based Authentication¶

Vulnerable to various attacks
Mitigations: Salting, key derivation functions (PBKDF2, bcrypt, Argon2)

Challenge-Response Protocols¶

Server sends random challenge
Client proves knowledge of secret without revealing it

OAuth and OpenID Connect¶

Delegated authentication and authorization
Allows third-party access without sharing credentials

10.3 Key Exchange Protocols¶

Station-to-Station (STS) Protocol¶

Authenticated Diffie-Hellman
Prevents man-in-the-middle attacks

Internet Key Exchange (IKE)¶

Key exchange protocol used in IPsec
Complex with many options and modes

11. Practical Considerations¶

11.1 Implementation Security¶

Side-Channel Attacks¶

Timing attacks
Power analysis
Cache attacks
Countermeasures: Constant-time operations, masking, blinding

Fault Attacks¶

Induce errors during computation
Extract secrets from faulty outputs
Countermeasures: Verification, redundancy

11.2 Random Number Generation¶

True Random Number Generators (TRNGs)¶

Based on physical processes
Examples: Radioactive decay, atmospheric noise, circuit noise

Deterministic Random Bit Generators (DRBGs)¶

Pseudo-random generators with entropy input
Examples: HMAC-DRBG, CTR-DRBG

Catastrophic Failures¶

Debian OpenSSL vulnerability (2008)
Dual EC DRBG backdoor controversy

11.3 Standards and Best Practices¶

NIST Recommendations¶

Symmetric algorithms: AES, SHA-2/SHA-3
Asymmetric algorithms: RSA, ECDSA, DH, ECDH
Key lengths: 128-bit symmetric, 3072-bit RSA, 256-bit ECC

IETF Recommendations¶

Protocols: TLS 1.3, SSH, IPsec
Cipher suites: AES-GCM, ChaCha20-Poly1305
Key exchange: ECDHE, DHE

Cryptographic Agility¶

Design systems to easily update algorithms and parameters
Prepare for quantum computer threat