Number Theory for Cryptography

Corresponds to Katz & Lindell, Introduction to Modern Cryptography, Chapters 7–8.

Motivation: concrete hard problems

IntuitionWhy number theory now

Completing the top-down story. Private-key cryptography came from PRFs and PRPs, which come from one-way functions. Here one-way functions finally get concrete candidates: hard mathematical problems that have been studied for centuries.
Public-key cryptography needs structure. Private-key primitives can be built heuristically with no number theory. Public-key schemes have no unifying primitive and can’t (yet) be built “from scratch”: they rely on specific algebraic hardness, where some trapdoor makes a problem easy and its absence makes it hard.

Efficiency is measured in the bit length $\lVert N\rVert = \Theta(\log N)$ . An algorithm taking $\Theta(N)$ steps is exponential. Algorithmic number theory cares about both sides: what is efficiently computable (exponentiation, inverses, gcd) and what seems hard (factoring, discrete log).

Assumption	Problem	Best known attack (classical)
Factoring	given $N = pq$ , find $p, q$	number field sieve, $2^{O(n^{1/3}(\log n)^{2/3})}$
RSA	given $N, e, y$ , find $y^{1/e}\bmod N$	factor $N$
Discrete log in $\mathbb Z_p^*$	given $g, h$ , find $\log_gh$	index calculus / NFS, subexponential
Discrete log on elliptic curves	same, in $E(\mathbb Z_p)$	generic only, $\Theta(\sqrt q)$
CDH / DDH	compute / recognise $g^{xy}$	via discrete log

Primes, divisibility and modular arithmetic

DefinitionDivisibility and primes

$a\mid b$ if $ac = b$ for some integer $c$ . If $a\mid b$ and $a\mid c$ , then $a\mid Xb + Yc$ . A prime $p > 1$ has only the divisors 1 and $p$ ; 1 is neither prime nor composite. Fundamental theorem of arithmetic: $N = \prod_ip_i^{e_i}$ uniquely. Division with remainder: $a = qb + r$ with $0\le r < b$ , computable in polynomial time.

TheoremProposition 7.2 — Bézout

For positive $a, b$ , there exist integers $X, Y$ with $Xa + Yb = \gcd(a,b)$ , and $\gcd(a,b)$ is the smallest positive such combination. Euclid’s algorithm computes $\gcd$ , and extended Euclid computes $X, Y$ , both in polynomial time.

ProofThe smallest positive combination divides everything

Let $d$ be the least positive element of $I = \{\hat Xa + \hat Yb\}$ . Any $c\in I$ gives $c = qd + r$ with $r = c - qd\in I$ and $0\le r < d$ , so $r = 0$ and $d\mid c$ . In particular $d\mid a$ and $d\mid b$ . Any common divisor divides $Xa + Yb = d$ , so $d$ is the greatest common divisor.

∎

TheoremConsequences (Propositions 7.3–7.4)

If $c\mid ab$ and $\gcd(a,c) = 1$ , then $c\mid b$ . In particular, $p\mid ab\Rightarrow p\mid a$ or $p\mid b$ . (Multiply $1 = Xa + Yc$ by $b$ .)
If $p\mid N$ , $q\mid N$ and $\gcd(p,q) = 1$ , then $pq\mid N$ .

DefinitionModular arithmetic

$[a\bmod N]\in\{0,\ldots,N-1\}$ is the remainder, and $a = b\bmod N$ iff $N\mid(a - b)$ . Congruence respects $+$ , $-$ , $\times$ , so reduce first, then compute: $1093028\cdot190301\equiv28\cdot1 = 28\pmod{100}$ . It does not respect division: $3\cdot2 = 15\cdot2\bmod24$ , yet $3\ne15\bmod24$ .

TheoremProposition 7.7 — Invertibility

$a$ is invertible modulo $N$ iff $\gcd(a,N) = 1$ . The inverse is the $X$ in $Xa + YN = 1$ . Example: $(-3)\cdot11 + 2\cdot17 = 1$ , so $11^{-1} = [-3\bmod17] = 14$ . Division by $b$ means multiplication by $b^{-1}$ , and cancellation then works. Addition, multiplication, inversion and exponentiation (repeated squaring) mod $N$ are all polynomial time.

Groups

DefinitionGroup (Def. 7.9)

A set with a binary operation satisfying closure, an identity, inverses, and associativity; abelian if also commutative. The order $\lvert G\rvert$ is the number of elements. The identity and inverses are unique (Exercise 7.1). A subgroup is a subset that is a group under the same operation.

Notation: additive ( $g + h$ , identity 0, inverse $-g$ , repetition $mg$ ) or multiplicative ( $gh$ , identity 1, inverse $g^{-1}$ , repetition $g^m$ ). Results are stated multiplicatively; this is notation only.

ExampleGroups and non-groups

$\mathbb Z$ under $+$ is a group; under $\times$ it is not (2 has no inverse).
$\mathbb R\setminus\{0\}$ under $\times$ is a group.
$\mathbb Z_N = \{0,\ldots,N-1\}$ under addition mod $N$ : order $N$ , inverse $[N - a\bmod N]$ .
Cancellation (Lemma 7.13): $ac = bc\Rightarrow a = b$ .

TheoremTheorem 7.14 — $g^{\lvert G\rvert} = 1$

In a finite group of order $m$ , $g^m = 1$ for every $g$ .

ProofMultiplying by

g

permutes the group (abelian case)

With $G = \{g_1,\ldots,g_m\}$ , the elements $gg_1,\ldots,gg_m$ are distinct by cancellation, so they are $G$ again. Then $\prod_ig_i = \prod_i(gg_i) = g^m\prod_ig_i$ , and cancelling gives $g^m = 1$ .

∎

TheoremCorollaries 7.15 and 7.17 — Exponent arithmetic

Work mod $\lvert G\rvert$ in the exponent: $g^i = g^{[i\bmod m]}$ . Additively, $152\cdot11\equiv2\cdot11 = 7\pmod{15}$ .
$e$ -th powers are permutations: if $\gcd(e,m) = 1$ , then $f_e(g) = g^e$ is a bijection with inverse $f_d$ , $d = [e^{-1}\bmod m]$ , since $(g^e)^d = g^{[ed\bmod m]} = g$ . This is RSA’s engine.

The group $\mathbb Z_N^*$ and Euler’s $\varphi$

Definition $\mathbb Z_N^*$ (Proposition 7.18)

$\mathbb Z_N^* = \{a\in\{1,\ldots,N-1\} : \gcd(a,N) = 1\}$ is an abelian group under multiplication mod $N$ . (Closure: a prime dividing $N$ and $ab$ would divide $a$ or $b$ .) Its order is Euler’s phi function $\varphi(N)$ .

FormulaEuler’s $\varphi$ (Theorem 7.19)

$\varphi(p) = p - 1,\qquad\varphi(pq) = (p-1)(q-1),\qquad\varphi\Big(\prod_ip_i^{e_i}\Big) = \prod_ip_i^{e_i-1}(p_i - 1)$

For $N = pq$ : from $\{1,\ldots,N-1\}$ , remove the $q - 1$ multiples of $p$ and the $p - 1$ multiples of $q$ . Example: $\mathbb Z_{15}^* = \{1,2,4,7,8,11,13,14\}$ has $\varphi(15) = 8$ , and $8^{-1} = 2$ .

TheoremCorollaries 7.21–7.22 — Euler and Fermat

$a^{\varphi(N)} = 1\bmod N$ for $a\in\mathbb Z_N^*$ , and $a^{p-1} = 1\bmod p$ (Fermat). If $\gcd(e,\varphi(N)) = 1$ , then $x\mapsto x^e\bmod N$ is a permutation of $\mathbb Z_N^*$ with inverse $x\mapsto x^d$ , $d = e^{-1}\bmod\varphi(N)$ . This even holds on all of $\mathbb Z_N$ for squarefree $N = pq$ (Exercise 7.8: apply CRT; modulo $p$ either $p\mid x$ , giving $0\mapsto0$ , or use Fermat with $ed\equiv1\bmod(p-1)$ ).

The Chinese remainder theorem

DefinitionIsomorphisms and direct products

An isomorphism $f : G\to H$ is a bijection with $f(g_1g_2) = f(g_1)f(g_2)$ ( $G\simeq H$ ): the same algebraic structure in a different representation. $G\times H$ has the componentwise operation.

TheoremTheorem 7.24 — Chinese remainder theorem

If $N = pq$ with $\gcd(p,q) = 1$ , then

$\mathbb Z_N\simeq\mathbb Z_p\times\mathbb Z_q,\qquad\mathbb Z_N^*\simeq\mathbb Z_p^*\times\mathbb Z_q^*,\qquad x\leftrightarrow([x\bmod p],\ [x\bmod q])$

It extends to any pairwise-coprime factorisation.

ProofInjective plus equal sizes

Units map to units: $\gcd(x,N) = 1\Rightarrow\gcd(x\bmod p,p) = 1$ . Injective: $f(x) = f(x')$ means $p, q\mid x - x'$ , so $pq\mid x - x'$ (Proposition 7.4), and $x = x'$ . Same size: $N = pq$ , so $f$ is a bijection. Homomorphism: $(a +_N b)\bmod p = (a +_p b)\bmod p$ (Exercise 7.6, since $p\mid N$ ), and likewise for $\times$ .

∎

Example $\mathbb Z_{15}^*\simeq\mathbb Z_5^*\times\mathbb Z_3^*$ (Example 7.25)

$1\leftrightarrow(1,1)$ , $2\leftrightarrow(2,2)$ , $4\leftrightarrow(4,1)$ , $7\leftrightarrow(2,1)$ , $8\leftrightarrow(3,2)$ , $11\leftrightarrow(1,2)$ , $13\leftrightarrow(3,1)$ , $14\leftrightarrow(4,2)$ : every pair appears exactly once. Then $14\cdot13\leftrightarrow(4\cdot3,\ 2\cdot1) = (2,2)\leftrightarrow2$ , and indeed $182\equiv2\pmod{15}$ .

AlgorithmConverting back from $(x_p,x_q)$ (when $p, q$ are known)

Extended Euclid: $Xp + Yq = 1$ .
$1_p = [Yq\bmod N]\leftrightarrow(1,0)$ and $1_q = [Xp\bmod N]\leftrightarrow(0,1)$ (precompute these once).
$x = [x_p1_p + x_q1_q\bmod N]$ .

Example ( $N = 35$ ): $3\cdot5 - 2\cdot7 = 1$ gives $1_p = 21$ and $1_q = 15$ , so $(4,3)\leftrightarrow[84 + 45\bmod35] = 24$ . Check: $24\equiv4\pmod5$ and $24\equiv3\pmod7$ .

ExampleExponentiation through CRT (Examples 7.29–7.30)

$29^{100}\bmod35$ : $29\leftrightarrow(-1,1)$ , so $(-1,1)^{100} = (1,1)\leftrightarrow1$ .
$18^{25}\bmod35$ : $18\leftrightarrow(3,4)$ . Reduce exponents mod the group orders, $25\bmod4 = 1$ and $25\bmod6 = 1$ , giving $(3,4)\leftrightarrow18$ .

Splitting into small moduli and reducing exponents mod $p - 1$ and $q - 1$ makes RSA decryption about 4× faster (RSA-CRT). It needs the factorisation, which only the key owner has.

Primes, factoring and RSA

Generating random primes

WarningRandom products are easy to factor

In “weak factoring” (multiply two random $n$ -bit integers), $N$ is even with probability $3/4$ , and small prime factors are common. The hardest numbers to factor have only large prime factors, so the factoring assumption uses random $n$ -bit primes, which must be efficiently generatable.

AlgorithmRandom $n$ -bit prime (Algorithm 7.34)

Repeat up to $n^2/c$ times: $p := 1\Vert p'$ with $p'\leftarrow\{0,1\}^{n-1}$ (so the length is exactly $n$ ); return $p$ if Miller–Rabin with parameter $n$ says “prime”.

Density (prime number theorem, weak form): at least $c\cdot2^{n-1}/n$ of the $n$ -bit numbers are prime, so each try succeeds with probability at least $c/n$ . After $n^2/c$ tries, failure is at most $(1 - c/n)^{n^2/c}\le e^{-n}$ .
Testing: one-sided randomised tests (a prime is always called prime). A deterministic polynomial test exists (AKS, 2002) but is slower, so randomised tests are used in practice.
Special forms ( $p\equiv3\bmod4$ , safe primes $p = 2q + 1$ ): modified generators work in practice, though their analyses rely on density conjectures.

Primality testing: Miller–Rabin

AlgorithmFermat test (first attempt, Algorithm 7.35)

Pick $a\leftarrow\{1,\ldots,N-1\}$ . Output “composite” if $\gcd(a,N)\ne1$ or $a^{N-1}\ne1\bmod N$ (a witness), and repeat $t$ times.

LemmaLemmas 7.36–7.37 — subgroups are small

In a finite group, a nonempty subset containing 1 and closed under the operation is a subgroup (inverses come from $a^{m-1}$ ). A strict subgroup has at most half the elements: a coset $\bar hH$ is disjoint from $H$ and the same size.

TheoremTheorem 7.38 — one witness means many

If any witness exists, the non-witnesses form a strict subgroup of $\mathbb Z_N^*$ , so at least half of $\mathbb Z_N^*$ are witnesses. Each round then catches $N$ with probability at least $\frac12$ , giving error at most $2^{-t}$ .

WarningCarmichael numbers

Infinitely many composites (for example 561) have no Fermat witnesses at all. The Fermat test is not enough.

DefinitionStrong witnesses

Write $N - 1 = 2^ru$ with $u$ odd and look at $a^u, a^{2u},\ldots,a^{2^ru}$ (each the square of the previous). $a$ is a strong witness if $a^u\ne\pm1$ and $a^{2^iu}\ne-1$ for $1\le i < r$ . A non-strong-witness’s sequence looks like $(\pm1,1,\ldots,1)$ or $(\ast,\ldots,\ast,-1,1,\ldots,1)$ . Every Fermat witness is a strong witness.

TheoremPrimes have no strong witnesses (Lemma 7.39)

Modulo an odd prime, the only square roots of 1 are $\pm1$ : $(x-1)(x+1)\equiv0$ forces $p\mid x\mp1$ . In the sequence ending at $a^{N-1} = 1$ , the term just before the first 1 is a square root of 1 other than 1, hence $-1$ .

TheoremTheorem 7.40 — Many strong witnesses for odd composites that are not prime powers

Let $i$ be the largest index for which some non-strong-witness has $a^{2^iu} = -1$ ( $i$ exists since $(-1)^u = -1$ ). Define $\overline{\mathrm{Bad}} = \{a : a^{2^iu} = \pm1\}$ .

It contains all non-strong-witnesses.
It is a subgroup (closed under products).
It is strict: write $N = N_1N_2$ with coprime factors. Take $a$ with $a^{2^iu} = -1\leftrightarrow(-1,-1)$ and set $b\leftrightarrow(a_1,1)$ . Then $b^{2^iu}\leftrightarrow(-1,1)$ , which is neither $1$ nor $-1$ .

So at least half of $\mathbb Z_N^*$ are strong witnesses.

AlgorithmMiller–Rabin (Algorithm 7.44; Theorem 7.33)

Even $N$ : composite. Perfect power: composite (check $\hat N^e = N$ for $e\le\lVert N\rVert + 1$ by binary search; Exercise 7.9). Otherwise write $N - 1 = 2^ru$ and repeat $t$ times: random $a$ ; “composite” if $\gcd(a,N)\ne1$ or $a$ is a strong witness. A prime always passes; a composite passes with probability at most $2^{-t}$ .

The factoring and RSA assumptions

DefinitionFactoring assumption (Def. 7.45)

$\mathrm{GenModulus}(1^n)$ outputs $(N,p,q)$ with $N = pq$ and $p, q$ $n$ -bit primes. Factoring is hard relative to it if every ppt $\mathcal A$ , given $N$ , outputs $p', q' > 1$ with $p'q' = N$ only with negligible probability.

DefinitionRSA assumption (Def. 7.46)

$\mathrm{GenRSA}(1^n)$ outputs $(N,e,d)$ with $\gcd(e,\varphi(N)) = 1$ and $ed\equiv1\bmod\varphi(N)$ (Algorithm 7.47: generate a modulus, choose $e$ , set $d = e^{-1}\bmod\varphi(N)$ ). RSA is hard if, given $N, e$ and uniform $y\in\mathbb Z_N^*$ , every ppt $\mathcal A$ finds $x$ with $x^e = y\bmod N$ only with negligible probability.

ImportantRSA is no harder than factoring, and maybe easier

Trapdoor: knowing $p, q$ gives $\varphi(N)$ , then $d$ , then $y^d$ . So hard RSA implies hard factoring.
Equivalences: computing $\varphi(N)$ is as hard as factoring (Exercise 7.11: $p + q = N - \varphi(N) + 1$ and $pq = N$ , so $p, q$ are roots of $z^2 - (N - \varphi + 1)z + N$ ). Knowing $d$ also reveals the factorisation (Exercise 7.12 for $e = 3$ : $3d - 1 = k\varphi(N)$ with $k\in\{1,2\}$ , so try both).
Gap: RSA might be solvable without computing $\varphi$ or $d$ , so “RSA ⟺ factoring” is unproven.

Pure factoring lacks a convenient trapdoor structure for building schemes; RSA’s asymmetry (easy with the trapdoor $\varphi(N)$ , hard without) is what public-key schemes need.

Cyclic groups and discrete-log assumptions

DefinitionOrder, generators, cyclic groups

$\langle g\rangle = \{g^0, g^1,\ldots\}$ is the subgroup generated by $g$ . The order of $g$ is the least $i > 0$ with $g^i = 1$ , and $\lvert\langle g\rangle\rvert = i$ . $G$ is cyclic if some $g$ (a generator) has order $\lvert G\rvert$ . Cyclic groups usually have several generators.

TheoremPropositions 7.49–7.52 and Theorem 7.53 — Orders

$g^x = g^y\iff x\equiv y\bmod\mathrm{ord}(g)$ .
$\mathrm{ord}(g)$ divides $\lvert G\rvert$ (Lagrange for cyclic subgroups).
Prime order ⇒ cyclic, and every non-identity element is a generator.
$\mathbb Z_p^*$ is cyclic for prime $p$ (but has non-prime order $p - 1$ ).

ExampleOrders in practice

$\mathbb Z_{15}$ (additive): 1 and 2 generate; 3 has order 5 ( $\{0,3,6,9,12\}$ ); 10 has order 3. Both orders divide 15.
$\mathbb Z_{15}^*$ : $\langle2\rangle = \{1,2,4,8\}$ , order 4, which divides 8.
$\mathbb Z_7^*$ : $\langle2\rangle = \{1,2,4\}$ , but $\langle3\rangle = \{1,3,2,6,4,5\}$ , so 3 is a generator.

WarningIsomorphic is not computationally equivalent

Every cyclic group of order $n$ is isomorphic to $\mathbb Z_n$ via $a\mapsto g^a$ . But evaluating that isomorphism backwards is the discrete-log problem. Discrete log is trivial in $(\mathbb Z_n,+)$ and believed hard in $\mathbb Z_p^*$ or on elliptic curves: hardness depends on the representation.

Discrete log, CDH and DDH

DefinitionDiscrete logarithm (Def. 7.59)

$\mathcal G(1^n)$ outputs a cyclic group $\mathbb G$ of order $q$ ( $\lVert q\rVert = n$ ) with generator $g$ and efficient operations. $\log_gh$ is the unique $x\in\mathbb Z_q$ with $g^x = h$ ; it satisfies $\log_g(h_1h_2) = \log_gh_1 + \log_gh_2\bmod q$ . Hard if, given $(\mathbb G,q,g,h)$ for uniform $h$ , every ppt algorithm finds $\log_gh$ only with negligible probability.

DefinitionDiffie–Hellman problems

$\mathrm{DH}_g(g^{x_1},g^{x_2}) = g^{x_1x_2}$ .

CDH: compute $g^{xy}$ from $g^x, g^y$ .
DDH (Def. 7.60): distinguish $(g^x,g^y,g^{xy})$ from $(g^x,g^y,g^z)$ : $\lvert\Pr[\mathcal A(\ldots,g^z) = 1] - \Pr[\mathcal A(\ldots,g^{xy}) = 1]\rvert\le\mathrm{negl}(n)$ .

Hierarchy: DL easy ⇒ CDH easy ⇒ DDH easy, so hard DDH ⇒ hard CDH ⇒ hard DL (Exercises 7.13–7.14). The converses are believed false: some groups have hard DL and CDH but easy DDH (for example $\mathbb Z_p^*$ itself, via quadratic residuosity).

ImportantWhy prime-order groups

Discrete log is hardest there. Pohlig–Hellman reduces order $q_1q_2$ to orders $q_1$ and $q_2$ .
Generators are free. Every non-identity element generates.
DH values are almost uniform (Proposition 7.61). For random $x_1, x_2$ , $\Pr[\mathrm{DH} = 1] = \frac2q - \frac1{q^2}$ (since $x_1x_2\equiv0$ iff a factor is 0, as $q$ is prime), and $\Pr[\mathrm{DH} = y] = \frac1q - \frac1{q^2}$ for $y\ne1$ (unique $x_2 = x\cdot x_1^{-1}$ ). That is within negligible distance of uniform.

This is heuristic support only: prime order is neither necessary nor sufficient for DDH hardness.

AlgorithmQuadratic residues modulo a safe prime (Algorithm 7.62)

Squaring mod $p$ is 2-to-1, so the quadratic residues $\mathcal{QR}_p$ are half of $\mathbb Z_p^*$ and form a subgroup. For a safe prime $p = 2q + 1$ with $q$ prime, $\mathcal{QR}_p$ has prime order $q$ , so DDH is believed hard there. Generate $(p,q)$ , pick $x\ne\pm1$ , and output $g = x^2\bmod p$ , a non-identity residue and hence a generator.

Elliptic-curve groups

DefinitionElliptic curve over $\mathbb Z_p$ ( $p\ge5$ )

$E : y^2 = x^3 + Ax + B\bmod p$ with $4A^3 + 27B^2\ne0$ (no repeated roots). $E(\mathbb Z_p)$ is the set of solutions together with the point at infinity $O$ . Picture the real curve, with $O$ at the top of every vertical line. A line meets the curve in exactly 3 points (counting tangency twice and $O$ for vertical lines).

ExamplePoints on $y^2 = x^3 + 3x + 3\bmod7$ (Example 7.63)

$f(x) = x^3 + 3x + 3$ takes the values $f(0..6) = 3, 0, 3, 4, 2, 3, 6$ . The quadratic residues mod 7 are $\{1,2,4\}$ .

$f(1) = 0$ gives the single point $(1,0)$ ;
$f(3) = 4$ gives $(3,2)$ and $(3,5)$ ;
$f(4) = 2$ gives $(4,3)$ and $(4,4)$ .

With $O$ , that is 6 points.

FormulaGroup law (Claims 7.64–7.65)

Rule: $P_1 + P_2 + P_3 = O$ for collinear points, $O$ is the identity, and $-(x,y) = (x,-y)$ (reflect). For $P_1 = (x_1,y_1)$ and $P_2 = (x_2,y_2)$ , neither $O$ :

$x_1\ne x_2$ : $m = \frac{y_2 - y_1}{x_2 - x_1}$ ;
doubling, $P_1 = P_2$ with $y_1\ne0$ : $m = \frac{3x_1^2 + A}{2y_1}$ ;

then

$x_3 = m^2 - x_1 - x_2,\qquad y_3 = m(x_1 - x_3) - y_1\pmod p$

(with $x_2 = x_1$ in the doubling case). If $x_1 = x_2$ with $y_1\ne y_2$ , or $P_1 = P_2$ with $y_1 = 0$ , the sum is $O$ . This is an abelian group; associativity is tedious to verify directly and follows naturally from algebraic geometry.

NoteWhy elliptic curves

No subexponential discrete-log algorithm is known for well-chosen curves, only generic $\sqrt q$ ones. In practice, parameters are chosen so that $E(\mathbb Z_p)$ (or a subgroup) has prime order. Schemes in this book treat the group generically (“any cyclic group where DDH is hard”), so the curve only matters at implementation time.

Applications

TheoremTheorem 7.68 — Factoring ⇒ one-way function

Let Gen use $p(n)$ random bits. $f_{\mathrm{Gen}}(x)$ runs $\mathrm{Gen}(1^n;x)$ , using $x$ as the random tape with $n$ such that $p(n)\le\lvert x\rvert < p(n+1)$ , and outputs $N$ . A uniform $x$ gives exactly Gen’s distribution of moduli, and any preimage $x'$ reveals the factors (rerun Gen on $x'$ ). Hence hard factoring ⇒ one-way $f$ , and hard RSA ⇒ one-way $f$ too.

TheoremConstruction 7.71 — The RSA one-way permutation family

$\mathrm{Gen}$ : $I = \langle N,e\rangle$ from GenRSA; $D_I = \mathbb Z_N^*$ ; Samp is uniform on $\mathbb Z_N^*$ ; $f_I(x) = x^e\bmod N$ . One-way iff RSA is hard, and a trapdoor permutation given $d$ . Discrete log also gives a one-way permutation family: $x\mapsto g^x\bmod p$ maps $\{1,\ldots,p-1\}$ bijectively onto $\mathbb Z_p^*$ (Exercise 7.17).

TheoremTheorem 7.73 — A discrete-log collision-resistant hash

With prime-order $(\mathbb G,q,g)$ and random $h$ as the public key,

$H_s(x_1,x_2) = g^{x_1}h^{x_2},\qquad x_1,x_2\in\mathbb Z_q$

is collision-resistant if discrete log is hard. (Evidence suggests collision resistance can’t be built from arbitrary OWFs or OWPs, so number theory is needed for provable CRHFs.)

ProofA collision reveals

\log_gh

$g^{x_1}h^{x_2} = g^{x_1'}h^{x_2'}$ gives $g^{x_1-x_1'} = h^{x_2'-x_2}$ . Here $\Delta = x_2' - x_2\not\equiv0$ , otherwise $x_1 = x_1'$ too and the inputs would be equal. Since $q$ is prime, $\Delta$ is invertible, so $\log_gh = (x_1 - x_1')\Delta^{-1}\bmod q$ . (If $h = 1$ , output 0.) The reduction’s view is exactly the real key distribution, so its success equals the collision probability.

∎

ExampleToy instance and compression (Example 7.74, Exercise 7.16)

$p = 47$ , $\mathcal{QR}_{47}$ has order $q = 23$ , $g = 4$ , $h = 21$ . An 8-bit input splits into two 4-bit numbers: $11111101\mapsto(15,13)$ . Then $4^{15}\cdot21^{13}\equiv34\cdot7 = 238\equiv3\pmod{47}$ , so $H_s(11111101) = 000011$ . (Checked by hand.) Inputs are $2(n-1)$ bits and outputs $n + 1$ bits (elements of $\mathbb Z_p^*$ with $\lVert p\rVert = n + 1$ ), so the hash compresses once $n > 3$ . Merkle–Damgård then extends it to arbitrary length (Theorem 4.12).

ExampleAn RSA-based CRHF (Exercise 7.18, Construction 7.75)

Key $(N,e,y)$ ; for $X\in\{0,1\}^{3n}$ , $H(X) = f^{X_1}(f^{X_2}(\cdots f^{X_{3n}}(1)))$ with $f^0(x) = x^e$ and $f^1(x) = yx^e$ . Strip equal outer layers until the first differing bit, where $a^e = y\,b^e$ . Then $y = (a/b)^e$ , so $a/b$ is the $e$ -th root of $y$ : a collision solves RSA. (Sketch.)

Algorithms for factoring (Chapter 8)

NoteWhy attacks matter

Parameter sizes come from the best known algorithms: a scheme meant to last 5 years needs $N$ large enough that the best factoring algorithm takes longer than that. Trial division takes $O(\sqrt N)$ , so anything interesting must beat that.

Pollard’s $p - 1$ method

AlgorithmPollard $p - 1$ (Algorithm 8.1)

Find $y\leftrightarrow(1,y_q)$ with $y_q\ne1$ . Then $p\mid y - 1$ but $q\nmid y - 1$ , so $\gcd(y - 1,N) = p$ .

Choose $B$ with $(p-1)\mid B$ but $(q-1)\nmid B$ , for example $B = \prod_{i\le k}p_i^{\lfloor n/\log p_i\rfloor}$ over small primes.
Set $y = x^B\bmod N$ . Modulo $p$ : $x^B = 1$ (Fermat). Modulo $q$ : $x^B\ne1$ whenever $x_q$ has order not dividing $B$ , for example when it is a generator, which happens with probability $\varphi(q-1)/(q-1)$ .

It works exactly when $p - 1$ is smooth (all prime factors small) and $q - 1$ is not. Defence: strong primes ( $(p-1)/2$ prime). Today’s consensus is that the cost isn’t worth it, since general-purpose algorithms are better anyway, though some schemes need strong primes for structural reasons.

Pollard’s rho method

AlgorithmPollard rho (Algorithm 8.3)

Look for a good pair: $x\equiv x'\bmod p$ but $x\not\equiv x'\bmod N$ . Then $\gcd(x - x',N) = p$ .

Birthday: $k\approx2^{n/2} = O(\sqrt p)$ random elements contain a collision mod $p$ with constant probability (about 1/4), but almost surely none mod $N$ . Testing all $\binom k2$ pairs would cost $O(\sqrt N)$ , no better than trial division.
Iterate $x_m = F(x_{m-1})$ , for example $F(x) = x^2 + b$ with $b\ne0,-2$ . The sequence mod $p$ is eventually periodic (a “ρ” shape). Claim 8.2: if $x_i\equiv x_j\pmod p$ with $i < j$ , then some $i' < j$ has $x_{i'}\equiv x_{2i'}$ , namely the first multiple of the period at least $i$ . So test only $\gcd(x_{2i} - x_i,N)$ (Floyd cycle-finding, as in the low-memory birthday attack).

Heuristically $O(N^{1/4}\mathrm{polylog}N)$ , about $2^{\lVert N\rVert/4}$ : general-purpose but still exponential. The sequence isn’t random, so a rigorous analysis is open.

The quadratic sieve

IntuitionCongruence of squares

If $x^2\equiv y^2\bmod N$ with $x\not\equiv\pm y$ , then $N\mid(x-y)(x+y)$ but divides neither factor, so $\gcd(x - y,N)$ is a prime factor. For $N = pq$ , each square has four square roots, so a random “equal squares” pair is nontrivial with probability about $\frac12$ .

AlgorithmQuadratic sieve (high level)

Collect relations. Fix a factor base $\mathcal B = \{p_1,\ldots,p_k\}$ of small primes. Find $\ell > k$ values $x_i > \sqrt N$ with $q_i = x_i^2\bmod N$ $\mathcal B$ -smooth: $x_i^2\equiv\prod_jp_j^{e_{i,j}}$ . (The sieving that finds them is omitted.)
Linear algebra mod 2. The exponent-parity matrix $\Gamma$ ( $\ell\times k$ , $\ell > k$ ) has a subset of rows summing to 0 over $\mathrm{GF}(2)$ . The product of those relations is then $\big(\prod x_i\big)^2\equiv\big(\prod_jp_j^{(\sum e)/2}\big)^2$ .

Running time $2^{O(\sqrt{n\log n})}$ : subexponential. Fastest until the early 1990s, still best up to about 300-bit $N$ . The general number field sieve is fastest today: heuristically $2^{O(n^{1/3}(\log n)^{2/3})}$ .

ExampleFactoring $N = 377753$ (Example 8.4)

$x$	$x^2\bmod N$	factorisation
620	6647	$17^2\cdot23$
621	7888	$2^4\cdot17\cdot29$
645	38272	$2^7\cdot13\cdot23$
655	51272	$2^3\cdot13\cdot17\cdot29$

The product is $2^{14}\cdot13^2\cdot17^4\cdot23^2\cdot29^2$ , all exponents even. So $(620\cdot621\cdot645\cdot655)^2\equiv(2^7\cdot13\cdot17^2\cdot23\cdot29)^2$ , i.e. $127194^2\equiv45335^2$ with $127194\ne\pm45335$ . Then $\gcd(127194 - 45335,\ N) = 751$ , and $N = 751\times503$ . (Squares and factorisation checked by hand.)

Algorithms for discrete log (Chapter 8)

NoteGeneric versus specific

Generic algorithms use only group operations (and the order $q$ ). Specific ones exploit the representation. Brute force is $O(q)$ . Generic algorithms provably need $\Omega(\sqrt q)$ (Nechaev; Shoup), and baby-step/giant-step meets this, but the bound says nothing about particular groups.

Baby-step/giant-step

AlgorithmShanks’ baby-step/giant-step (Algorithm 8.5)

With $t = \lfloor\sqrt q\rfloor$ :

Giant steps: compute and sort $g^0, g^t, g^{2t},\ldots,g^{\lfloor q/t\rfloor t}$ , which mark the “circle” $\langle g\rangle$ at spacing $t$ .
Baby steps: for $i = 0..t$ , compute $yg^i$ and look it up. Since $y = g^x$ lies in some gap, $yg^i = g^{kt}$ for some $i\le t$ , giving $\log_gy = kt - i\bmod q$ .

Time $O(\sqrt q\,\mathrm{polylog}\,q)$ and memory $O(\sqrt q)$ . Pollard’s rho for discrete log achieves the same time with constant memory.

Example $\log_217$ in $\mathbb Z_{29}^*$ (Example 8.6)

$q = 28$ , $t = 5$ . Giant steps: $2^0, 2^5,\ldots,2^{25} = 1, 3, 9, 27, 23, 11$ . Baby steps: $17\cdot2^i$ for $i = 0..5$ gives $17, 5, 10, 20, 11, 22$ . The match $17\cdot2^4 = 11 = 2^{25}$ gives $\log_217 = 25 - 4 = 21$ . Check: $2^{21} = 2^{20}\cdot2 = 46\equiv17$ .

Pohlig–Hellman

AlgorithmPohlig–Hellman

With $q = \prod_iq_i$ pairwise coprime and $\mathrm{ord}(g) = q$ : since $\mathrm{ord}(g^{q/q_i}) = q_i$ (Lemma 8.7),

$(g^{q/q_i})^x = y^{q/q_i}\quad\Rightarrow\quad x_i = x\bmod q_i$

in a group of order $q_i$ . Solve each subproblem (for example with baby-step/giant-step) and combine by CRT. Time $O(\mathrm{polylog}(q)\cdot\max_i\sqrt{q_i})$ . Prime powers reduce further, digit by digit in base $p$ (Exercises 8.1–8.2), to $O(\mathrm{polylog}(q)\cdot\max\sqrt{p_i})$ , where the $p_i$ are the primes dividing $q$ . Smooth group order ⇒ easy discrete log, hence prime-order groups.

Example $\log_326$ in $\mathbb Z_{31}^*$ (Example 8.8)

$q = 30 = 5\cdot3\cdot2$ .

$(3^6)^x = 16^x = 26^6 = 1$ , so $x\equiv0\pmod5$ (16 has order 5);
$(3^{10})^x = 25^x = 26^{10} = 5 = 25^2$ , so $x\equiv2\pmod3$ ;
$(3^{15})^x = 30^x = 26^{15} = 30$ , so $x$ is odd.

CRT gives $x\equiv5\pmod{30}$ , and indeed $3^5 = 243\equiv26$ .

Discrete log in $(\mathbb Z_N,+)$ is easy

ExampleRepresentation matters

In additive $\mathbb Z_N$ , " $\log_gy$ " means solving $x\cdot g\equiv y$ . With $g = 1$ , $x = y$ . With any generator $g$ , $\gcd(g,N) = 1$ , so $x = y\cdot g^{-1}\bmod N$ . This uses multiplication, a second operation beyond the group law. For non-generators, divide by $d = \gcd(g,N)$ , solve mod $N/d$ , and lift to $d$ solutions (Exercise 8.3).

Index calculus

AlgorithmIndex calculus in $\mathbb Z_p^*$

Precompute (needs only $p, g$ ; reusable): pick a factor base $\{p_1,\ldots,p_k\}$ and find exponents $x_i$ with $g^{x_i}\bmod p$ smooth. Each gives a linear relation $x_i\equiv\sum_je_{i,j}\log_gp_j\pmod{p-1}$ .
Per target $y$ : find $x^*$ with $g^{x^*}y$ smooth, giving $x^* + \log_gy\equiv\sum_je^*_j\log_gp_j$ . Solve the linear system (care is needed because $p - 1$ is composite).

Time $2^{O(\sqrt{n\log n})}$ , the same as the quadratic sieve; the NFS variant reaches $2^{O(n^{1/3}(\log n)^{2/3})}$ . Specific to $\mathbb Z_p^*$ (smoothness of integer representatives). There is no analogue for good elliptic curves.

Example $\log_387$ in $\mathbb Z_{101}^*$ (Example 8.9)

$3^{10} = 65 = 5\cdot13$ , $3^{12} = 80 = 2^4\cdot5$ , $3^{14} = 13$ , and $3^5\cdot87 = 32 = 2^5$ . So $\log13 = 14$ , $\log5 = 10 - 14 = 96$ , and $4\log2 = 12 - 96\equiv16\pmod{100}$ . That gives $\log2\in\{4,29,54,79\}$ ; checking gives 29. Then $\log87 = 5\cdot29 - 5 = 140\equiv40\pmod{100}$ . (Relations checked by hand.)

ImportantWhy elliptic curves are smaller

A 512-bit $p$ : NFS costs about $2^{512^{1/3}\cdot9^{2/3}}\approx2^{8\cdot4.3}$ , roughly $2^{32}$ – $2^{35}$ . A prime-order elliptic curve with $q\approx2^{64}$ costs about $\sqrt q = 2^{32}$ by the best (generic) attack. Comparable security with far smaller groups, hence faster honest operations. (Modern guidance: about 3072-bit RSA or $\mathbb Z_p^*$ versus about 256-bit curves for 128-bit security. 512-bit Diffie–Hellman was actually broken in practice by the 2015 Logjam attack. And all of factoring, discrete log and EC discrete log fall to Shor’s quantum algorithm.)

Exercises (selected)

ExampleShort answers

7.2: $\{1\}\cup\{2,4,6,\ldots\}\subset\mathbb R^\times$ is closed, contains 1, but has no inverses. Proposition 7.36 needs finiteness.
7.3: $\langle g\rangle$ is a subgroup in finite groups (inverses $g^{i-1}$ ). In infinite groups $\{g^0,g^1,\ldots\}$ needn’t be: $\{2^k : k\ge0\}\subset\mathbb Q^\times$ lacks $\frac12$ .
7.6: $p\mid N\Rightarrow[[X\bmod N]\bmod p] = [X\bmod p]$ , but $[[X\bmod p]\bmod N]$ needn’t equal $[X\bmod N]$ : take $X = N$ and $p\nmid N$ -free cases, e.g. $p = 3$ , $N = 6$ , $X = 4$ gives $1$ versus $4$ .
7.9: if $N = \hat N^e$ with $\hat N\ge2$ , then $e\le\log_2N\le\lVert N\rVert$ . For each $e$ , binary-search $\hat N$ , giving polynomial time overall.
7.11–7.12: see the RSA box above.
8.3: $ab\equiv c\bmod N$ with $\gcd(b,N) = d$ forces $d\mid c$ and $a(b/d)\equiv c/d\bmod N/d$ with $\gcd(b/d,N/d) = 1$ . Invert, then the $d$ lifts $a + k(N/d)$ are all solutions.

(Answers worked here.)

Quick reference

Object	Statement	Note
Bézout	$Xa + Yb = \gcd(a,b)$	extended Euclid, polynomial time
Inverse mod $N$	exists iff $\gcd(a,N) = 1$	$11^{-1}\equiv14\pmod{17}$
$g^{\lvert G\rvert} = 1$	exponents mod $\lvert G\rvert$	$e$ -th power permutes if $\gcd(e,\lvert G\rvert) = 1$
$\varphi$	$\varphi(pq) = (p-1)(q-1)$ ; $\prod p^{e-1}(p-1)$	Euler/Fermat
CRT	$\mathbb Z_N^\simeq\mathbb Z_p^\times\mathbb Z_q^*$	$x = x_p1_p + x_q1_q$
Prime generation	random $n$ -bit + Miller–Rabin, $O(n^2)$ tries	density $\ge c/n$
Miller–Rabin	strong witnesses ≥ half for non-prime-power composites	error $2^{-t}$
Factoring / RSA	find $p, q$ / find $y^{1/e}$	RSA ≤ factoring; $\varphi$ or $d$ ⇒ factors
Orders	divide $\lvert G\rvert$ ; prime order ⇒ every non-identity element generates
DL, CDH, DDH	DDH hard ⇒ CDH hard ⇒ DL hard	prime-order groups preferred
Safe-prime subgroup	$\mathcal{QR}_p$ , $p = 2q + 1$ , order $q$	$g = x^2$
Elliptic curves	chord-and-tangent law, $O$ identity	only generic attacks
Applications	factoring ⇒ OWF; RSA ⇒ OWP family; DL ⇒ CRHF $g^{x_1}h^{x_2}$
Pollard $p - 1$	$\gcd(x^B - 1,N)$	smooth $p - 1$
Pollard rho	$\gcd(x_{2i} - x_i,N)$	$O(N^{1/4})$
Quadratic sieve	smooth relations + GF(2) linear algebra	$2^{O(\sqrt{n\log n})}$
NFS	factoring and DL in $\mathbb Z_p^*$	$2^{O(n^{1/3}(\log n)^{2/3})}$
BSGS	giant steps $g^{kt}$ , baby steps $yg^i$	$O(\sqrt q)$ , generically optimal
Pohlig–Hellman	CRT over the factors of the order	$O(\max\sqrt{p_i})$
Index calculus	smooth relations for $\log$ of the factor base	subexponential, $\mathbb Z_p^*$ only

Facts to keep to hand

Modular arithmetic is efficient; structure gives trapdoors. gcd, inverses and exponentiation are polynomial time. Exponents live modulo the group order, so knowing $\varphi(N)$ (equivalently the factorisation) inverts $x\mapsto x^e$ . RSA’s trapdoor is exactly that asymmetry, and CRT makes computing with known factors fast.
Primes are plentiful and testable. About $1/n$ of $n$ -bit numbers are prime, and Miller–Rabin’s strong witnesses defeat Carmichael numbers, giving error $2^{-t}$ . So random moduli and safe-prime groups are easy to generate.
Cyclic groups host discrete log, CDH and DDH. Prefer prime order (Pohlig–Hellman, easy generators, near-uniform DH values): safe-prime residue subgroups of $\mathbb Z_p^*$ , or elliptic curves where only generic $\sqrt q$ attacks are known. Hardness depends on representation, not abstract structure.
Known attacks set the key sizes. Factoring and discrete log in $\mathbb Z_p^*$ fall to subexponential sieves (smooth relations plus linear algebra), while elliptic-curve discrete log resists all but generic attacks. That is why curves achieve the same security with much smaller parameters.

References

Katz & Lindell, Introduction to Modern Cryptography — Chapters 7–8
Shoup, A Computational Introduction to Number Theory and Algebra (2005)
Crandall & Pomerance, Prime Numbers: A Computational Perspective (2005)
Washington, Elliptic Curves: Number Theory and Cryptography (2008)

Related

Number Theory for Cryptography

Motivation: concrete hard problems

Primes, divisibility and modular arithmetic

Groups

The group $\mathbb Z_N^*$ and Euler’s $\varphi$

The Chinese remainder theorem

Primes, factoring and RSA

Generating random primes

Primality testing: Miller–Rabin

The factoring and RSA assumptions

Cyclic groups and discrete-log assumptions

Discrete log, CDH and DDH

Elliptic-curve groups

Applications

Algorithms for factoring (Chapter 8)

Pollard’s $p - 1$ method

Pollard’s rho method

The quadratic sieve

Algorithms for discrete log (Chapter 8)

Baby-step/giant-step

Pohlig–Hellman

Discrete log in $(\mathbb Z_N,+)$ is easy

Index calculus

Exercises (selected)

Quick reference

References

Mentioned in

Related

Motivation: concrete hard problems

Primes, divisibility and modular arithmetic

Groups

The group ZN∗\mathbb Z_N^*ZN∗​ and Euler’s φ\varphiφ

The Chinese remainder theorem

Primes, factoring and RSA

Generating random primes

Primality testing: Miller–Rabin

The factoring and RSA assumptions

Cyclic groups and discrete-log assumptions

Discrete log, CDH and DDH

Elliptic-curve groups

Applications

Algorithms for factoring (Chapter 8)

Pollard’s p−1p - 1p−1 method

Pollard’s rho method

The quadratic sieve

Algorithms for discrete log (Chapter 8)

Baby-step/giant-step

Pohlig–Hellman

Discrete log in (ZN,+)(\mathbb Z_N,+)(ZN​,+) is easy

Index calculus

Exercises (selected)

Quick reference

References

Mentioned in

The group $\mathbb Z_N^*$ and Euler’s $\varphi$

Pollard’s $p - 1$ method

Discrete log in $(\mathbb Z_N,+)$ is easy