ISE Cryptography — Reference

Modular Arithmetic for Cryptography

Modular Reduction

The integers, but wrapped around.

What is Modular Arithmetic?

• \(a \bmod n\) is the remainder when \(a\) is divided by \(n\)
  • \(17 \bmod 5 = 2\), because \(17 = 3 \times 5 + 2\)
  • \(100 \bmod 7 = 2\), because \(100 = 14 \times 7 + 2\)
• We write \(a \equiv b \pmod{n}\) to mean \(n\) divides \(a - b\)
  • \(17 \equiv 2 \pmod{5}\), because \(5 \mid 15\)
• Negative numbers wrap forward: \(-3 \bmod 7 = 4\)
  • \(-3 \equiv 4 \pmod{7}\), because \(7 \mid (-3 - 4) = -7\)
  • Think of a clock: counting 3 steps backwards from 0 lands on 4

The Set \(\mathbb{Z}_n\)

• \(\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}\) is the complete residue system modulo \(n\)
  • Every integer maps to exactly one element of \(\mathbb{Z}_n\) via the remainder
• Addition and multiplication are performed mod \(n\)
  • The result always stays in \(\{0, 1, \ldots, n-1\}\)
  • We say \(\mathbb{Z}_n\) is closed under both operations
• RSA works entirely in \(\mathbb{Z}_n\) where \(n = pq\) is the product of two large primes
  • Encryption: \(c = m^e \bmod n\)
  • Decryption: \(m = c^d \bmod n\)
  • Numbers never exceed \(n\), even though \(n\) is 2048+ bits

Modular Addition and Multiplication

• \((a + b) \bmod n\) and \((a \cdot b) \bmod n\) are the basic operations
• Example with \(n = 12\) (clock arithmetic):
  • \(7 + 8 = 15 \equiv 3 \pmod{12}\)
  • \(7 \times 8 = 56 \equiv 8 \pmod{12}\)
• Both operations are associative and commutative, just like ordinary arithmetic
  • \((a + b) + c \equiv a + (b + c)\) and \(a + b \equiv b + a\)
  • \((a \cdot b) \cdot c \equiv a \cdot (b \cdot c)\) and \(a \cdot b \equiv b \cdot a\)
• Multiplication distributes over addition:
  • \(a \cdot (b + c) \equiv a \cdot b + a \cdot c \pmod{n}\)
• The one-time pad generalises to \(\mathbb{Z}_{26}\): \(E(k, m) = (m + k) \bmod 26\)

Groups and Inverses

The algebra behind “undo”.

Groups: The Abstraction Behind Mod Arithmetic

• In Lecture 01, we saw that XOR is a group operation on bitstrings
  • Now we need the same idea for multiplication in \(\mathbb{Z}_n\)
• A group is a set \(G\) with an operation \(\cdot\) satisfying four properties:
  • Closure: if \(a, b \in G\), then \(a \cdot b \in G\)
  • Associativity: \((a \cdot b) \cdot c = a \cdot (b \cdot c)\)
  • Identity: there exists \(e \in G\) such that \(a \cdot e = e \cdot a = a\)
  • Inverses: for every \(a \in G\), there exists \(a^{-1}\) with \(a \cdot a^{-1} = e\)
• \((\mathbb{Z}_n, +)\) is a group: identity is 0, inverse of \(a\) is \(n - a\)
• \((\mathbb{Z}_n, \times)\) is almost a group… but which elements have inverses?
  • \(5 \times 5 = 25 \equiv 1 \pmod{12}\), so 5 has an inverse in \(\mathbb{Z}_{12}\)
  • But \(4 \times ? \equiv 1 \pmod{12}\)… try them all and you’ll never find one

Why Do We Need Inverses?

• RSA decryption computes \(d = e^{-1} \bmod \phi(n)\)
  • If this inverse doesn’t exist, RSA doesn’t work at all
• Diffie-Hellman works in a group where every element has an inverse
  • If some elements lack inverses, the discrete log problem becomes structured and attackable
• The rule: \(a\) has an inverse mod \(n\) if and only if \(\gcd(a, n) = 1\)
  • When \(n\) is prime, every nonzero element is coprime to \(n\), so everything is invertible
  • When \(n\) is composite (\(n = pq\) for RSA), some elements lack inverses
• To find inverses efficiently, we need an algorithm for computing GCDs…

GCD and the Euclidean Algorithm

The workhorse of modular arithmetic.

Greatest Common Divisor

• \(\gcd(a, b)\) is the largest integer that divides both \(a\) and \(b\)
  • \(\gcd(12, 8) = 4\), \(\gcd(15, 28) = 1\), \(\gcd(100, 75) = 25\)
• When \(\gcd(a, b) = 1\), we say \(a\) and \(b\) are coprime (or relatively prime)
  • \(\gcd(17, 60) = 1\), so 17 and 60 are coprime
• RSA key generation requires \(\gcd(e, p-1) = 1\)
  • The public exponent \(e\) must be coprime to both \(p - 1\) and \(q - 1\)
  • Otherwise, the decryption exponent \(d = e^{-1} \bmod (p-1)(q-1)\) wouldn’t exist

The Euclidean Algorithm

• The key identity: \(\gcd(a, b) = \gcd(b, a \bmod b)\)
  • Keep replacing the larger number with the remainder until you hit 0
• Worked example: \(\gcd(252, 105)\)
  • \(252 = 2 \times 105 + 42\), so \(\gcd(252, 105) = \gcd(105, 42)\)
  • \(105 = 2 \times 42 + 21\), so \(\gcd(105, 42) = \gcd(42, 21)\)
  • \(42 = 2 \times 21 + 0\), so \(\gcd(42, 21) = 21\)
• Runs in \(O(\log(\min(a, b)))\) divisions
  • Fast even for 1024-bit primes used in RSA
  • One of the oldest known algorithms (Euclid, ~300 BCE)

The Extended Euclidean Algorithm

• The extended version finds integers \(x, y\) such that \(ax + by = \gcd(a, b)\)
  • This is Bezout’s identity: such \(x, y\) always exist
• When \(\gcd(a, n) = 1\), this gives us \(ax + ny = 1\)
  • Reducing mod \(n\): \(ax \equiv 1 \pmod{n}\)
  • So \(x = a^{-1} \bmod n\), the modular inverse of \(a\)
• RSA key generation uses this to compute \(d = e^{-1} \bmod (p-1)(q-1)\)
  • Given \(e = 17\) and \((p-1)(q-1) = 3120\), find \(d\) with \(17d \equiv 1 \pmod{3120}\)
  • The extended Euclidean algorithm gives \(d = 2753\)

Extended Euclidean Algorithm: Worked Example

• Finding \(17^{-1} \bmod 3120\) via the extended Euclidean algorithm:

\[ \begin{aligned} &\textbf{Forward pass (Euclidean algorithm):} \\ &\quad 3120 = 183 \times 17 + 9 \\ &\quad 17 = 1 \times 9 + 8 \\ &\quad 9 = 1 \times 8 + 1 \\ &\quad 8 = 8 \times 1 + 0 \\[6pt] &\textbf{Back-substitution:} \\ &\quad 1 = 9 - 1 \times 8 \\ &\quad 1 = 9 - 1 \times (17 - 1 \times 9) = 2 \times 9 - 1 \times 17 \\ &\quad 1 = 2 \times (3120 - 183 \times 17) - 1 \times 17 = 2 \times 3120 - 367 \times 17 \\[6pt] &\textbf{Result: } 17 \times (-367) \equiv 1 \pmod{3120} \\ &\quad d = -367 \equiv 2753 \pmod{3120} \end{aligned} \]

Verify: \(17 \times 2753 = 46801 = 15 \times 3120 + 1\). This is the exact \(d\) value from the RSA worked example in Lecture 06.

Modular Inverses and Euler’s Totient

When division is possible, and why RSA works.

Modular Inverses

• \(a^{-1} \bmod n\) is the unique \(b \in \mathbb{Z}_n\) with \(ab \equiv 1 \pmod{n}\)
  • It exists if and only if \(\gcd(a, n) = 1\)
• Example: \(3^{-1} \bmod 7 = 5\), because \(3 \times 5 = 15 \equiv 1 \pmod{7}\)
• Counterexample: \(4^{-1} \bmod 6\) does not exist
  • \(\gcd(4, 6) = 2 \neq 1\)
  • No matter what you multiply 4 by, the result is always even, so never \(\equiv 1 \pmod{6}\)
• Computing inverses: use the extended Euclidean algorithm
  • Or Fermat’s method (next section) when \(n\) is prime

The Group \(\mathbb{Z}_n^*\)

• \(\mathbb{Z}_n^* = \{a \in \mathbb{Z}_n : \gcd(a, n) = 1\}\) is the set of invertible elements
  • Under multiplication mod \(n\), this forms a group
  • Closed, associative, has identity (1), and every element has an inverse
• When \(n = p\) is prime: \(\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}\)
  • Every nonzero element is coprime to \(p\), so everything is invertible
  • \(|\mathbb{Z}_p^*| = p - 1\)
• When \(n = pq\) for distinct primes (the RSA case):
  • \(\mathbb{Z}_n^*\) excludes multiples of \(p\) and multiples of \(q\)
  • \(|\mathbb{Z}_n^*| = (p-1)(q-1)\)

Euler’s Totient Function

• \(\phi(n) = |\mathbb{Z}_n^*|\) counts the integers in \(\{1, \ldots, n\}\) coprime to \(n\)
  • For prime \(p\): \(\phi(p) = p - 1\)
  • For \(n = pq\) with distinct primes: \(\phi(pq) = (p-1)(q-1)\)
• RSA example from Lecture 06: \(p = 61\), \(q = 53\)
  • \(n = 61 \times 53 = 3233\)
  • \(\phi(3233) = 60 \times 52 = 3120\)
  • The decryption exponent \(d = e^{-1} \bmod \phi(n)\)
• For prime powers: \(\phi(p^k) = p^{k-1}(p - 1)\)
• General formula: if \(n = p_1^{a_1} \cdots p_r^{a_r}\), then \(\phi(n) = n \prod_{p \mid n} (1 - 1/p)\)

Euler’s Theorem and Fermat’s Little Theorem

• Euler’s theorem: for any \(a\) with \(\gcd(a, n) = 1\)
  • \(a^{\phi(n)} \equiv 1 \pmod{n}\)
• Fermat’s little theorem (special case for prime \(p\)):
  • \(a^{p-1} \equiv 1 \pmod{p}\) for any \(a \not\equiv 0\)
• This is the reason RSA decryption works:
  • \(ed \equiv 1 \pmod{\phi(n)}\), so \(ed = 1 + k\phi(n)\)
  • \((m^e)^d = m^{ed} = m^{1 + k\phi(n)} = m \cdot (m^{\phi(n)})^k \equiv m \cdot 1^k = m\)
• Fermat also gives an alternative way to compute inverses when \(p\) is prime:
  • \(a^{-1} \equiv a^{p-2} \pmod{p}\)

Modular Exponentiation

Making \(x^e \bmod n\) fast.

The Problem with Big Exponents

• RSA computes \(x^e \bmod n\) where \(e = 65537\) and \(n\) is 2048+ bits
  • Naive: compute \(x^e\) first, then reduce mod \(n\)
  • \(x^{65537}\) has roughly \(65537 \times 2048 \approx 134\) million bits
  • Way too large to store, let alone compute
• The fix: reduce at every step, keeping numbers small
  • \((a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n\)
  • Intermediate results never exceed \(n^2\), regardless of the exponent
• But even with modular reduction, computing \(x \cdot x \cdot x \cdots\) takes \(e - 1\) multiplications
  • For \(e = 65537\), that’s 65536 multiplications
  • We can do much better

Square-and-Multiply

• Write the exponent in binary: \(e = (e_{k-1}, e_{k-2}, \ldots, e_1, e_0)_2\)
• Scan bits from left to right, maintaining an accumulator \(r\):
  • Start with \(r \leftarrow 1\)
  • For each bit: \(r \leftarrow r^2 \bmod n\) (always square)
  • If the bit is 1: \(r \leftarrow r \cdot x \bmod n\) (also multiply by \(x\))
• Only \(O(\log e)\) multiplications instead of \(O(e)\)
  • \(e = 65537 = 10000000000000001_2\) has 17 bits
  • Only 17 squarings and 2 multiplications needed
• This algorithm is also called repeated squaring or binary exponentiation

Square-and-Multiply: Worked Example

• Computing \(3^{13} \bmod 7\), where \(13 = 1101_2\):

The exponent 13 = 1101 in binary. We scan left to right. At each step we square the accumulator. If the current bit is 1, we also multiply by the base (3). The magenta-highlighted boxes are the “multiply” steps. Verify: \(3^{13} = 1594323\) and \(1594323 \bmod 7 = 3\).

Cyclic Groups, Generators, and Order

The algebra behind Diffie-Hellman.

Cyclic Groups

• A group is cyclic if one element generates every other element
  • For \(\mathbb{Z}_p^*\) under multiplication: \(g\) is a generator if \(\{g^1, g^2, \ldots, g^{p-1}\} = \mathbb{Z}_p^*\)
  • Also called a primitive root modulo \(p\)
• \(\mathbb{Z}_p^*\) is always cyclic when \(p\) is prime
  • But not every element is a generator
• Generators exist for \(\mathbb{Z}_n^*\) only when \(n\) is 1, 2, 4, \(p^k\), or \(2p^k\) for odd prime \(p\)
  • In particular, \(\mathbb{Z}_n^*\) is NOT cyclic when \(n = pq\) (the RSA modulus)
  • This is why DH uses \(\mathbb{Z}_p^*\) with a prime modulus, not \(\mathbb{Z}_n^*\)

Generators of \(\mathbb{Z}_{11}^*\)

• \(p = 11\), so \(\mathbb{Z}_{11}^* = \{1, 2, 3, \ldots, 10\}\) with \(|\mathbb{Z}_{11}^*| = 10\)
• Try \(g = 2\): powers hit all 10 elements (a generator!)
  • \(2^1 = 2,\; 2^2 = 4,\; 2^3 = 8,\; 2^4 = 5,\; 2^5 = 10\)
  • \(2^6 = 9,\; 2^7 = 7,\; 2^8 = 3,\; 2^9 = 6,\; 2^{10} = 1\)
• Try \(g = 3\): only hits 5 elements (not a generator)
  • \(3^1 = 3,\; 3^2 = 9,\; 3^3 = 5,\; 3^4 = 4,\; 3^5 = 1\)
  • Generates only the subgroup \(\{1, 3, 4, 5, 9\}\)
• Try \(g = 10\): only hits 2 elements
  • \(10^1 = 10,\; 10^2 = 1\), cycles back immediately

Order of a Group Element

• The order of \(g\) is the smallest positive \(d\) such that \(g^d \equiv 1 \pmod{p}\)
  • Written \(\text{ord}(g) = d\)
• Lagrange’s theorem: the order of any element divides the group size
  • \(|\mathbb{Z}_{11}^*| = 10 = 2 \times 5\)
  • Possible orders: 1, 2, 5, and 10 (the divisors of 10)
  • Look at the table above: the orders we observe are 10, 5, and 2. Orders like 3, 4, 7 are impossible.
  • Intuition: the powers of \(g\) cycle with period \(d\). If \(d\) didn’t divide \(|G|\), the group couldn’t partition evenly into cosets of size \(d\).
• An element is a generator if and only if its order equals \(p - 1\)
  • \(\text{ord}(2) = 10 = p - 1\), so \(g = 2\) generates \(\mathbb{Z}_{11}^*\)
  • \(\text{ord}(3) = 5 \neq 10\), so \(g = 3\) does not generate the full group
• The number of generators of \(\mathbb{Z}_p^*\) is \(\phi(p - 1)\)
  • For \(p = 11\): \(\phi(10) = 4\) generators out of 10 elements

Exponents Live Mod \(d\)

• Once \(\text{ord}(g) = d\), powers of \(g\) only depend on the exponent mod \(d\)
  • \(g^a \equiv g^{a \bmod d} \pmod{p}\), so exponents live in \(\mathbb{Z}_d\), not \(\mathbb{Z}\)
• In DH’s prime-order subgroup \(\mathbb{G}\) of order \(q\), all secrets \(\alpha\) are sampled from \(\mathbb{Z}_q\)
  • Anything larger reduces mod \(q\) before exponentiation, no information lost
  • This is why DH and Schnorr both treat \(\mathbb{Z}_q\) as the exponent space, not \(\mathbb{Z}\)

Subgroups

• An element of order \(d\) generates a subgroup of size \(d\)
  • \(g = 3\) has order 5 in \(\mathbb{Z}_{11}^*\), generating \(\{1, 3, 4, 5, 9\}\)
  • \(g = 10\) has order 2, generating \(\{1, 10\}\)
• Every element of the subgroup has order dividing \(d\)
• Subgroups cause security problems for Diffie-Hellman:
  • If the adversary can confine the secret to a small subgroup, discrete log is easy
  • Order-5 subgroup? Only 5 values to try. Order-2? Trivial.
  • This is the Pohlig-Hellman attack: decompose DLP into small-subgroup pieces

Safe Primes and Prime-Order Subgroups

• The fix: choose \(p\) so that \(p - 1\) has no small odd factors
• A safe prime is \(p = 2q + 1\) where \(q\) is also prime (\(q\) is a Sophie Germain prime)
  • \(p - 1 = 2q\), so the only subgroup orders are 1, 2, \(q\), and \(2q\)
  • No small subgroups to exploit
• Diffie-Hellman works in \(\mathbb{G}\), the subgroup of order \(q\)
  • \(\mathbb{G} = \{g^a \bmod p : a \in \mathbb{Z}_q\}\), with exactly \(q\) elements
  • Every non-identity element generates all of \(\mathbb{G}\) (because \(q\) is prime)
• Our example: \(p = 11 = 2 \times 5 + 1\) is a safe prime with \(q = 5\)
  • \(\{1, 3, 4, 5, 9\}\) is the order-\(q\) subgroup
• In practice, \(p\) is 2048+ bits and \(q\) is roughly the same size

The Chinese Remainder Theorem

Decomposing \(\mathbb{Z}_n\) when \(n\) factors.

Statement and Intuition

• Suppose \(n = m_1 m_2\) with \(\gcd(m_1, m_2) = 1\)
• Chinese Remainder Theorem (CRT): there is a bijection
  • \(\mathbb{Z}_n \;\longleftrightarrow\; \mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2}\)
  • \(a \;\longleftrightarrow\; (a \bmod m_1,\; a \bmod m_2)\)
• Addition and multiplication respect this decomposition componentwise
  • The two sides aren’t just a bijection; they’re isomorphic as rings
• The same statement restricts to invertibles: \(\mathbb{Z}_n^* \cong \mathbb{Z}_{m_1}^* \times \mathbb{Z}_{m_2}^*\)
  • Hence \(\phi(n) = \phi(m_1) \phi(m_2)\) when the factors are coprime
  • This is the deeper reason behind \(\phi(pq) = (p-1)(q-1)\)

CRT: Worked Example

• Find \(x \in \mathbb{Z}_{35}\) with \(x \equiv 2 \pmod{5}\) and \(x \equiv 3 \pmod{7}\)
• Search the residues that are \(2 \pmod 5\): \(x \in \{2, 7, 12, 17, 22, 27, 32\}\)
  • Of those, only \(x = 17\) also satisfies \(x \equiv 3 \pmod{7}\)
• Constructive recipe: write \(x = 7a + 5b\), choose \(a, b\) so each congruence holds
  • \(7 \equiv 2 \pmod{5}\), so we need \(2a \equiv 2\), giving \(a \equiv 1 \pmod 5\)
  • \(5^{-1} \equiv 3 \pmod{7}\), so \(5b \equiv 3\) gives \(b \equiv 9 \equiv 2 \pmod 7\)
  • \(x = 7 \cdot 1 + 5 \cdot 2 = 17\), matches the search
• The same idea recovers \(x \bmod n\) from \(x \bmod p\) and \(x \bmod q\) when \(n = pq\)

Why \(\mathbb{Z}_n^*\) Isn’t Cyclic When \(n = pq\)

• Take \(n = pq\) with distinct odd primes \(p, q\)
• CRT gives \(\mathbb{Z}_n^* \cong \mathbb{Z}_p^* \times \mathbb{Z}_q^*\), with \(|\mathbb{Z}_n^*| = (p-1)(q-1)\)
• Each factor is cyclic, but the product is not
  • Both \(p - 1\) and \(q - 1\) are even, so each factor has an element of order 2
  • The product then has multiple elements of order 2, namely \((\pm 1, \pm 1)\)
  • A cyclic group of even order has exactly one element of order 2, so the product can’t be cyclic
• The largest order of any element is \(\text{lcm}(p - 1, q - 1)\), strictly less than \((p - 1)(q - 1)\)
• This is why DH uses \(\mathbb{Z}_p^*\) with prime \(p\), not the RSA modulus \(n = pq\)

CRT in Practice

• Pohlig-Hellman attack on DLP: if \(|\mathbb{G}|\) factors as \(q_1 q_2 \cdots q_k\) with small \(q_i\)
  • Solve discrete log mod each \(q_i\) cheaply, then recombine via CRT
  • The factorisation of the group order is exactly the security leak
• RSA decryption speedup: rather than \(y^d \bmod n\) directly
  • Compute \(y^{d_p} \bmod p\) where \(d_p = d \bmod (p - 1)\)
  • Compute \(y^{d_q} \bmod q\) where \(d_q = d \bmod (q - 1)\)
  • Recombine via CRT to recover \(y^d \bmod n\)
  • Roughly 4x faster: half-size modulus, half-size exponent, twice
• RSA correctness for \(\gcd(m, n) \neq 1\): Euler’s theorem alone only covers \(\gcd(m, n) = 1\)
  • The rare edge case is patched by applying Fermat separately mod \(p\) and mod \(q\), then CRT

Putting It Together

Connecting the algebra to the crypto.

Where Do the Primes Come From?

• RSA needs two large primes; DH needs a safe prime. How do we find them?
• Generate-and-test: pick a random odd integer of the right size, then test it for primality
  • Prime Number Theorem: a random \(b\)-bit integer is prime with probability \(\approx 1/(b \ln 2)\)
  • For 1024-bit candidates, expect to test a few hundred before finding a prime
• Miller-Rabin is the standard probabilistic primality test
  • One-sided error: a composite is detected with probability \(\geq 3/4\) per round
  • \(k\) rounds reduces failure probability to \(\leq 4^{-k}\); in practice \(k = 64\) is overkill
  • Polynomial-time, fast enough that key generation is dominated by the search, not the test
• Safe primes are rarer: need both \(p\) and \(q = (p-1)/2\) to be prime
  • Roughly \(\log p\) times rarer than typical primes
  • In practice, safe-prime DH parameters are precomputed and standardised (RFC 3526)

RSA Correctness

• The RSA trapdoor permutation:
  • Public key: \((n, e)\) where \(n = pq\) and \(\gcd(e, (p-1)(q-1)) = 1\)
  • Secret key: \((n, d)\) where \(d = e^{-1} \bmod (p-1)(q-1)\)
  • Encrypt: \(F(pk, x) = x^e \bmod n\)
  • Decrypt: \(I(sk, y) = y^d \bmod n\)
• Why \(I(sk, F(pk, x)) = x\):
  • \(ed \equiv 1 \pmod{\phi(n)}\), so \(ed = 1 + k\phi(n)\) for some integer \(k\)
  • \(x^{ed} = x^{1 + k\phi(n)} = x \cdot (x^{\phi(n)})^k \equiv x \cdot 1^k = x \pmod{n}\)
  • By Euler’s theorem: \(x^{\phi(n)} \equiv 1 \pmod{n}\)
• Edge case: if \(\gcd(x, n) \neq 1\), Euler’s theorem doesn’t apply directly to \(x\)
  • This means \(x\) is a multiple of \(p\) or \(q\), probability \(\sim 2/n\), never happens in practice
  • Correctness still holds: apply Fermat separately mod \(p\) and mod \(q\), then combine via CRT

RSA: Every Concept Connects

• Every piece of this reference deck plays a role in RSA:
  • Miller-Rabin finds the primes \(p, q\)
  • Extended Euclidean algorithm computes the decryption exponent \(d\)
  • Square-and-multiply computes \(x^e\) and \(y^d\) in \(O(\log e)\) multiplications
  • Euler’s theorem (with CRT for the edge case) guarantees decryption inverts encryption
• Drop any one of these and RSA either doesn’t exist or doesn’t run
• The same toolbox supports DH (square-and-multiply, Lagrange, safe primes) and Schnorr (everything DH needs, plus a hash)

Diffie-Hellman: Why Eavesdropping is Hard

• Public parameters: safe prime \(p\), generator \(g\) of the order-\(q\) subgroup \(\mathbb{G}\)
• The eavesdropper sees \(g^\alpha \bmod p\) and \(g^\beta \bmod p\)
  • Needs \(g^{\alpha\beta} \bmod p\) (the shared secret)
• To recover \(\alpha\) from \(g^\alpha\): the discrete logarithm problem (DLP)
  • Generic attacks (work in any group): Pollard rho, \(O(\sqrt{q})\) operations
  • In \(\mathbb{Z}_p^*\) specifically: number field sieve runs sub-exponentially in \(\log p\)
  • That is why a 2048-bit prime is the modern minimum: NFS, not Pollard rho, sets the bar
• The Computational Diffie-Hellman (CDH) assumption:
  • Given \(g^\alpha\) and \(g^\beta\), computing \(g^{\alpha\beta}\) is hard
  • Assumed to be as hard as the discrete log problem (unproven, but widely believed)
• Real-world DH groups use standardised parameters from RFC 3526

Notation Summary

Notation	Meaning	Used in
\(\mathbb{Z}_n\)	Integers \(\{0, \ldots, n-1\}\) with arithmetic mod \(n\)	RSA
\(\mathbb{Z}_n^*\)	Invertible elements of \(\mathbb{Z}_n\)	RSA, DH
\(\mathbb{Z}_p^*\)	\(\{1, \ldots, p-1\}\) for prime \(p\)	DH
\(\phi(n)\)	Euler’s totient: \(\lvert\mathbb{Z}_n^*\rvert\)	RSA correctness
\(\gcd(a, b)\)	Greatest common divisor	RSA keygen
\(a^{-1} \bmod n\)	Modular inverse via extended Euclidean	RSA \(d\)
\(\text{ord}(g)\)	Smallest \(d\) with \(g^d \equiv 1\)	DH subgroups
\(\mathbb{G}\)	Prime-order subgroup of \(\mathbb{Z}_p^*\)	DH protocol