Computational Number Theory

& Cryptography
Mid-Term Examination Study Guide
[Link] CSE — 8th Semester
1. Solving Modular Linear Equations

Theory
A modular linear equation has the form:

General Form ax ≡ b (mod n) Find integer x satisfying this

The equation ax ≡ b (mod n) has a solution if and only if gcd(a, n) | b (i.e., gcd(a,n) divides b). If d =
gcd(a, n) divides b, then there are exactly d distinct solutions modulo n.

Step-by-Step Solution Method

• Compute d = gcd(a, n) using Euclid's Algorithm.
• If d does not divide b → No solution exists.
• If d divides b → Divide the entire equation by d: (a/d)x ≡ (b/d) (mod n/d).
• Find modular inverse of (a/d) modulo (n/d) using Extended Euclidean Algorithm.
• x₀ = (a/d)⁻¹ · (b/d) mod (n/d) gives the base solution.
• All d solutions: xᵢ = x₀ + i·(n/d) for i = 0, 1, ..., d−1

💡 Key Insight
Why gcd(a,n) | b must hold: ax ≡ b (mod n) means ax − b = kn for some integer k.
So b = ax − kn. Since gcd(a,n) divides both ax and kn, it must divide b.
This condition is both necessary and sufficient for solutions to exist.

📝 Worked Example
Solve: 14x ≡ 30 (mod 35)

Step 1: d = gcd(14, 35) = 7

Step 2: Does 7 | 30? → 30 / 7 = 4.28... → NO, 7 does not divide 30.
∴ No solution exists.

─── Let's try another: Solve 6x ≡ 4 (mod 8) ───

Step 1: d = gcd(6, 8) = 2
Step 2: Does 2 | 4? → Yes (4 = 2 × 2) ✓
Step 3: Divide by 2: 3x ≡ 2 (mod 4)
Step 4: Find inverse of 3 mod 4:
3 × 1 = 3, 3 × 2 = 6 ≡ 2, 3 × 3 = 9 ≡ 1 (mod 4) → inverse is 3
Step 5: x₀ = 3 × 2 mod 4 = 6 mod 4 = 2
Step 6: d=2 solutions: x = 2, 2 + 4 = 6 (mod 8)
Verify: 6×2 = 12 ≡ 4 (mod 8) ✓ and 6×6 = 36 ≡ 4 (mod 8) ✓
2. Chinese Remainder Theorem (CRT)

Theory
The Chinese Remainder Theorem (CRT) states that given a system of simultaneous congruences:

System x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

x ≡ aₖ (mod nₖ) ...and so on

If all nᵢ are pairwise coprime (gcd(nᵢ, nⱼ) = 1 for i ≠ j), then there exists a unique solution modulo N =
n₁ · n₂ · ... · nₖ.

Construction Algorithm
• Compute N = n₁ × n₂ × ... × nₖ (product of all moduli).
• For each i, compute Nᵢ = N / nᵢ.
• Find yᵢ = Nᵢ⁻¹ (mod nᵢ) using Extended Euclidean Algorithm.
• Solution: x = (Σ aᵢ · Nᵢ · yᵢ) mod N

💡 Key Insight
CRT is extensively used in RSA to speed up decryption — operating on smaller moduli
separately and combining results is much faster than working directly with the large N.
Cryptographic importance: CRT reduces a hard problem on Z_N to easier problems on Z_p and
Z_q.

📝 Worked Example
Solve the system:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

Step 1: N = 3 × 5 × 7 = 105
Step 2: N₁ = 105/3 = 35, N₂ = 105/5 = 21, N₃ = 105/7 = 15
Step 3: Find inverses:
y₁ = 35⁻¹ mod 3: 35 ≡ 2 (mod 3), 2×2=4≡1 (mod 3) → y₁ = 2
y₂ = 21⁻¹ mod 5: 21 ≡ 1 (mod 5) → y₂ = 1
y₃ = 15⁻¹ mod 7: 15 ≡ 1 (mod 7) → y₃ = 1
Step 4: x = (2×35×2) + (3×21×1) + (2×15×1) mod 105
= 140 + 63 + 30 = 233 mod 105
= 233 − 2×105 = 23
Answer: x = 23
Verify: 23 mod 3 = 2 ✓ | 23 mod 5 = 3 ✓ | 23 mod 7 = 2 ✓
3. Euclid's Algorithm

Theory
Euclid's Algorithm efficiently computes the Greatest Common Divisor (GCD) of two integers. It is
based on the key property:

Core Property gcd(a, b) = gcd(b, a mod b) Repeatedly apply until b = 0

When b becomes 0, the GCD is the remaining value of a. The algorithm terminates in
O(log(min(a,b))) steps, making it extremely efficient even for cryptographic-scale numbers.

Algorithm Pseudocode
📝 Worked Example
EUCLID(a, b):
while b ≠ 0:
temp = b
b = a mod b
a = temp
return a ← this is gcd(a, b)

📝 Worked Example
Compute gcd(252, 105):

Step 1: gcd(252, 105) → 252 = 2×105 + 42 → gcd(105, 42)

Step 2: gcd(105, 42) → 105 = 2×42 + 21 → gcd(42, 21)
Step 3: gcd(42, 21) → 42 = 2×21 + 0 → gcd(21, 0)

b = 0 → Answer: gcd(252, 105) = 21

💡 Key Insight
GCD is fundamental in number theory — two numbers are coprime if gcd(a,b) = 1.
RSA key generation requires choosing primes p, q such that gcd(e, φ(n)) = 1.
Euclid's algorithm runs in O(log min(a,b)) divisions — efficient for large numbers.
4. Extended Euclid's Algorithm

Theory
The Extended Euclidean Algorithm not only finds gcd(a, b) but also finds integers x and y (called
Bezout coefficients) satisfying:

Bezout's ax + by = gcd(a, b) x, y can be negative integers

Identity

This is crucial in cryptography for computing modular inverses. The modular inverse of a modulo n
exists iff gcd(a, n) = 1, and when it does:
Modular Inverse a · x ≡ 1 (mod n) x is the inverse, found via
Extended GCD

Tabular Method (exam-friendly)

• Initialize: r₀ = a, r₁ = b; s₀ = 1, s₁ = 0; t₀ = 0, t₁ = 1
• Each step: rᵢ₊₁ = rᵢ₋₁ − qᵢ · rᵢ, where qᵢ = ⌊rᵢ₋₁ / rᵢ⌋
• Apply same recurrence to s and t values.
• Stop when rᵢ₊₁ = 0. Then gcd = rᵢ, and a·sᵢ + b·tᵢ = gcd.

📝 Worked Example
Find modular inverse of 17 mod 43 (i.e., solve 17x ≡ 1 mod 43)

Extended GCD(43, 17):

q r s t
— 43 1 0
— 17 0 1
2 9 1 -2 (43 - 2×17 = 9; s: 1-2×0=1; t: 0-2×1=-2)
1 8 -1 3 (17 - 1×9 = 8; s: 0-1×1=-1; t: 1-1×(-2)=3)
1 1 2 -5 (9 - 1×8 = 1; s: 1-1×(-1)=2; t: -2-1×3=-5)
8 0 ... ... (stop)

gcd(43, 17) = 1, and: 43×2 + 17×(−5) = 86 − 85 = 1 ✓

So 17 × (−5) ≡ 1 (mod 43)
→ Inverse = −5 mod 43 = 38
Verify: 17 × 38 = 646 = 15×43 + 1 ≡ 1 (mod 43) ✓

💡 Key Insight
The modular inverse is used everywhere: decryption keys in RSA, solving congruences,
CRT construction. If gcd(a, n) ≠ 1, the inverse does NOT exist.
Extended GCD is O(log n) — the same complexity as the basic algorithm.
5. Modular Exponentiation

Theory
Computing aᵉ mod n for large e is a fundamental operation in cryptography (RSA, Diffie-Hellman,
ElGamal all depend on it). Naively multiplying a by itself e times is infeasible when e is hundreds of
bits long. The solution is the Repeated Squaring (Binary Exponentiation) method.

Principle aᵉ mod n e can be 1024+ bits long

Right-to-Left Binary Method

• Write exponent e in binary.
• Initialize result = 1, base = a mod n.
• For each bit of e from LSB to MSB:
◦ If bit = 1: result = (result × base) mod n
◦ base = (base × base) mod n (square for next bit)

Left-to-Right Method (Exam style — trace the powers)

• Start with result = 1.
• For each bit of e from MSB to LSB: result = result² mod n
• If the current bit is 1: result = result × a mod n

📝 Worked Example
Compute 3⁴⁷ mod 97 using repeated squaring

47 in binary = 101111

Build powers of 3 (squaring each time):

3¹ = 3
3² = 9
3⁴ = 81
3⁸ = 81² mod 97 = 6561 mod 97 = 6561 − 67×97 = 6561−6499 = 62
3¹⁶ = 62² mod 97 = 3844 mod 97 = 3844 − 39×97 = 3844−3783 = 61
3³² = 61² mod 97 = 3721 mod 97 = 3721 − 38×97 = 3721−3686 = 35

47 = 32 + 8 + 4 + 2 + 1 (binary: 101111)
3⁴⁷ = 3³² × 3⁸ × 3⁴ × 3² × 3¹ mod 97
= 35 × 62 × 81 × 9 × 3 mod 97

Compute step by step:

35 × 62 = 2170 mod 97 = 2170 − 22×97 = 2170−2134 = 36
36 × 81 = 2916 mod 97 = 2916 − 30×97 = 2916−2910 = 6
 6 × 9 = 54
54 × 3 = 162 mod 97 = 65

Answer: 3⁴⁷ mod 97 = 65

💡 Key Insight
Repeated squaring reduces O(e) multiplications to O(log e) multiplications.
For a 1024-bit exponent: from 2¹⁰²⁴ multiplications down to just 1024 — astronomically faster.
This efficiency is WHY public-key cryptography is practical on real hardware.
6. Primitive Roots & Finding Generators

Theory: Primitive Roots

A primitive root (or generator) g modulo n is an element whose powers generate all elements of the
multiplicative group ℤ*ₙ.

Definition ord(g) = φ(n) Order of g equals Euler's

totient

For a prime p, φ(p) = p−1. An element g is a primitive root mod p if and only if g^((p−1)/q) ≢ 1 (mod
p) for every prime factor q of (p−1).

Why Primitive Roots Matter

• They guarantee that every non-zero element can be expressed as a power of g.
• This is the basis for the Discrete Logarithm Problem — the security foundation of Diffie-
Hellman and ElGamal.
• The number of primitive roots modulo prime p is φ(p−1).

Finding Generators in Finite Fields

Algorithm to test if g is a primitive root mod p:
• Compute n = p − 1.
• Factorize n: find all distinct prime factors q₁, q₂, ..., qₖ.
• For each prime factor qᵢ: compute g^(n/qᵢ) mod p.
• If g^(n/qᵢ) ≡ 1 (mod p) for ANY qᵢ → g is NOT a primitive root.
• If g^(n/qᵢ) ≢ 1 (mod p) for ALL qᵢ → g IS a primitive root.

📝 Worked Example
Is g = 2 a primitive root mod 11?

p = 11, so p−1 = 10 = 2 × 5
Prime factors of 10: {2, 5}

Test g^(10/2) = 2⁵ mod 11 = 32 mod 11 = 10 ≠ 1 ✓

Test g^(10/5) = 2² mod 11 = 4 ≠ 1 ✓

Neither test gave 1, so 2 IS a primitive root mod 11.

Verify by listing powers:

2¹=2, 2²=4, 2³=8, 2⁴=5, 2⁵=10, 2⁶=9, 2⁷=7, 2⁸=3, 2⁹=6, 2¹⁰=1
All 10 elements {1,2,3,...,10} appear! ✓ (g=2 generates the entire group)
7. Discrete Logarithm Problem (DLP)

Theory
The Discrete Logarithm Problem is the computational foundation of many public-key cryptosystems.
Given a cyclic group G with generator g, and an element y ∈ G, the DLP asks:

DLP Definition Find x such that gˣ ≡ y (mod p) x is called log_g(y)

While computing gˣ mod p (modular exponentiation) is computationally easy — O(log x)

multiplications — the reverse operation (finding x given g, y, p) is believed to be computationally
infeasible for large primes p.

Why DLP is Hard

• No polynomial-time classical algorithm is known for general groups.
• Best known classical algorithm: Number Field Sieve — sub-exponential but still impractical
for 2048-bit primes.
• This asymmetry (easy forward, hard reverse) is the one-way function underlying DH and
ElGamal.

Known Attacks on DLP

• Baby-Step Giant-Step (Shanks): O(√p) time and space — impractical for large p.
• Index Calculus: Sub-exponential for multiplicative groups over finite fields.
• Pohlig-Hellman: Efficient if p−1 has only small prime factors (reason to use safe primes).
• Quantum (Shor's Algorithm): Polynomial time — threatens current DH/ElGamal on quantum
computers.

📝 Worked Example
Small example: Find x such that 2ˣ ≡ 8 (mod 11)

Compute powers of 2 mod 11:

2¹=2, 2²=4, 2³=8 ← found it!

So x = 3, i.e., log₂(8) = 3 in ℤ*₁₁

For large p (e.g., 2048-bit), this table approach has 2²⁰⁴⁸ entries → infeasible.

💡 Key Insight
Security parameter: For DLP-based systems, p should be at least 2048 bits (NIST 2030+
recommendation).
Safe prime: p = 2q + 1 where q is also prime ensures p−1 has a large prime factor,
defeating Pohlig-Hellman attack. Always use safe primes in Diffie-Hellman!
8. Diffie–Hellman Key Exchange

Theory
Diffie-Hellman (1976) was the first public-key protocol, solving the key distribution problem. It allows
two parties to establish a shared secret over an insecure channel without any prior shared secret —
even if an eavesdropper sees all messages.

Protocol Setup (Public Parameters)

• Both parties agree publicly on: large prime p and generator g (primitive root mod p).
• These parameters can be known to everyone — they are NOT secret.

Key Exchange Protocol

• Alice chooses secret a ← {2, ..., p−2} and sends A = gᵃ mod p to Bob.
• Bob chooses secret b ← {2, ..., p−2} and sends B = gᵇ mod p to Alice.
• Alice computes shared secret: K = Bᵃ mod p = g^(ab) mod p.
• Bob computes shared secret: K = Aᵇ mod p = g^(ab) mod p.
• Both arrive at the same K = g^(ab) mod p — used as symmetric key.

Shared Secret K = g^(ab) mod p Same for both parties

💡 Key Insight
Security relies on the Computational DH Problem: given g, gᵃ, gᵇ, compute g^(ab).
An eavesdropper sees g, p, gᵃ, gᵇ — but cannot compute g^(ab) without solving DLP.
DH is vulnerable to Man-in-the-Middle (MITM) attacks — it provides no authentication!

📝 Worked Example
DH Key Exchange with p=23, g=5:

Alice: a = 6 (secret)
A = 5⁶ mod 23 = 15625 mod 23 = 8 → sends 8 to Bob

Bob: b = 15 (secret)
B = 5¹⁵ mod 23 = 19 → sends 19 to Alice

Alice: K = 19⁶ mod 23 = 2 (shared secret)

Bob: K = 8¹⁵ mod 23 = 2 (shared secret) ✓

Eavesdropper knows: p=23, g=5, A=8, B=19 — must solve DLP to find K.
9. ElGamal Cryptosystem

Theory
ElGamal (1985) is an asymmetric encryption scheme based on the Discrete Logarithm Problem.
Unlike RSA, ElGamal ciphertext is probabilistic — the same plaintext encrypts differently each time
because a fresh random k is chosen per encryption.

Key Generation
• Choose large prime p and generator g (primitive root mod p).
• Choose private key x ← {2, ..., p−2} at random.
• Compute public key: y = gˣ mod p.
• Public key: (p, g, y). Private key: x.

Encryption
• To encrypt plaintext M (where 1 ≤ M ≤ p−1):
• Choose random ephemeral key k ← {2, ..., p−2}.
• Compute C₁ = gᵏ mod p.
• Compute C₂ = M · yᵏ mod p.
• Ciphertext: (C₁, C₂).

Decryption
• Given ciphertext (C₁, C₂) and private key x:
• Compute s = C₁ˣ mod p (this equals gᵏˣ = yᵏ).
• Recover M = C₂ · s⁻¹ mod p.

Decrypt M = C₂ · (C₁ˣ)⁻¹ mod p Uses private key x

📝 Worked Example
ElGamal with p=23, g=5, private key x=6, public key y=5⁶ mod 23 = 8

Encrypt M = 10 with random k = 3:

C₁ = 5³ mod 23 = 125 mod 23 = 10
C₂ = 10 × 8³ mod 23 = 10 × 512 mod 23
= 10 × (512 mod 23) = 10 × 6 = 60 mod 23 = 14
Ciphertext: (10, 14)

Decrypt (C₁=10, C₂=14) with x=6:

s = C₁ˣ = 10⁶ mod 23
10² = 100 mod 23 = 8
10⁴ = 8² mod 23 = 64 mod 23 = 18
 10⁶ = 10⁴ × 10² = 18 × 8 mod 23 = 144 mod 23 = 6
s = 6
s⁻¹ mod 23: 6 × 4 = 24 ≡ 1 (mod 23) → s⁻¹ = 4
M = 14 × 4 mod 23 = 56 mod 23 = 10 ✓

💡 Key Insight
ElGamal ciphertext is TWICE the size of plaintext (two values C₁, C₂) — a bandwidth cost.
Randomized encryption means same M encrypted twice gives different ciphertexts → CPA
secure.
Security: Breaking ElGamal ≡ Solving DLP. Choose p ≥ 2048 bits for security.
10. RSA — Key Generation, Encryption & Decryption

Theory
RSA (Rivest, Shamir, Adleman, 1977) is the most widely used public-key cryptosystem. Its security
rests on the Integer Factorization Problem: given n = p × q (product of two large primes), finding p
and q is computationally infeasible.

RSA Key Generation

• Step 1: Choose two large distinct primes p and q (each ≥ 1024 bits for security).
• Step 2: Compute n = p × q (the modulus, made public).
• Step 3: Compute φ(n) = (p−1)(q−1) — Euler's totient of n.
• Step 4: Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. Common choice: e = 65537.
• Step 5: Compute d = e⁻¹ mod φ(n) using Extended Euclidean Algorithm.
• Public Key: (n, e). Private Key: (n, d). Destroy p, q, φ(n).

Key Relation e · d ≡ 1 (mod φ(n)) d is modular inverse of e

RSA Encryption & Decryption

Encrypt C = Mᵉ mod n M is plaintext (M < n)

Decrypt M = Cᵈ mod n d is private key

Correctness follows from Euler's Theorem: M^(ed) ≡ M^(1 + k·φ(n)) ≡ M · (Mᶠ⁽ⁿ ⁾)ᵏ ≡ M · 1 ≡ M (mod
n).

📝 Worked Example
RSA Key Generation with p=61, q=53:

n = 61 × 53 = 3233
φ(n) = (61−1)(53−1) = 60 × 52 = 3120
Choose e = 17 (gcd(17, 3120) = 1 ✓)
Find d = 17⁻¹ mod 3120:
Using Extended GCD: 17 × 2753 = 46801 = 15×3120 + 1
→ d = 2753

Public Key: (3233, 17)

Private Key: (3233, 2753)

Encrypt M = 65:
C = 65¹⁷ mod 3233 = 2790 (computed via repeated squaring)
Decrypt C = 2790:
M = 2790²⁷⁵³ mod 3233 = 65 ✓
11. Attacks on RSA & Countermeasures

Mathematical / Algebraic Attacks

A. Small Public Exponent Attack (Low e Attack)

If e is too small (e.g., e = 3) and the same message M is sent to 3 different recipients with the same e
but different moduli n₁, n₂, n₃, an attacker collects C₁ = M³ mod n₁, C₂ = M³ mod n₂, C₃ = M³ mod
n₃. Using CRT, the attacker reconstructs M³ over ℤ_{n₁n₂n₃}. If M³ < n₁n₂n₃ (likely for small M and
e=3), taking the real cube root gives M directly.

💡 Key Insight
Countermeasure: Use proper padding (OAEP) before encryption. This adds randomness,
making even the same M encrypt differently each time. Also, e = 65537 is preferred.

B. Small Private Exponent Attack (Wiener's Attack)

If d is too small (d < n^(1/4) / 3), Wiener's attack uses continued fraction expansion of e/n to recover
d efficiently in polynomial time.

💡 Key Insight
Countermeasure: Ensure d > n^(1/2). Never artificially reduce d for performance;
use CRT-based speedup instead (which keeps d large but computes faster).

C. Common Modulus Attack

If two users share the same modulus n but different exponents e₁, e₂ (with gcd(e₁, e₂) = 1), and the
same message M is encrypted as C₁ = Mᵉ¹ mod n and C₂ = Mᵉ² mod n, an attacker uses Extended
Euclidean to find a, b with ae₁ + be₂ = 1, then M = C₁ᵃ · C₂ᵇ mod n.

💡 Key Insight
Countermeasure: Each user must have a UNIQUE modulus n = pq.
Never share moduli between entities under any circumstances.

D. Factoring Attacks
If n can be factored into p and q, the attacker computes φ(n) = (p−1)(q−1) and then d = e ⁻¹ mod φ(n),
completely breaking RSA. Best known algorithm: General Number Field Sieve (GNFS) runs in sub-
exponential time L_n[1/3, 1.923].

💡 Key Insight
 Countermeasure: Use n ≥ 2048 bits (NIST recommendation). Choose p, q with |p−q| large
(so p and q are far apart). Use safe primes p = 2p' + 1 where p' is also prime.

Implementation / Protocol Attacks

E. Chosen Ciphertext Attack (CCA)

A textbook RSA encryption C = Mᵉ mod n is malleable: given C, an attacker picks random r,
computes C' = rᵉ · C mod n, submits C' for decryption to get M' = r · M mod n, and recovers M = M' ·
r⁻¹ mod n. This is a valid attack if the decryption oracle can be queried.

💡 Key Insight
Countermeasure: Use RSA-OAEP (Optimal Asymmetric Encryption Padding) — this is the
standardized approach (PKCS#1 v2.x). OAEP adds randomization that defeats malleable
attacks.

F. Timing Attacks (Side-Channel)

By carefully measuring the time RSA decryption takes for different ciphertexts, an attacker can
deduce bits of the private key d. This attack targets the implementation, not the math.

💡 Key Insight
Countermeasure: Blinding — multiply ciphertext by a random rᵉ before decryption,
decrypt, then unblind. This randomizes timing without affecting correctness.

G. Meet-in-the-Middle & Birthday Attacks

Although not RSA-specific, these apply to key-size choices. Birthday paradox: collisions in hash-
based schemes occur in O(2^(n/2)) operations, not O(2ⁿ).

Quick Reference: Attacks Summary Table

Attack Condition / Vulnerability Countermeasure

Low e (Hastad) e=3, same M to 3 recipients Use OAEP padding; larger e

Wiener's d < n^(1/4)/3 Keep d > n^(1/2)
Common Modulus Shared n, different e Unique n per entity
Factoring Small n or weak primes n ≥ 2048 bits, safe primes
CCA / Malleability Textbook RSA, no padding RSA-OAEP (PKCS#1 v2)
Timing Attack Non-constant time impl. Blinding; constant-time code
Fault Attack Induced hardware errors CRT verification; error check
12. Quick Revision — Key Formulas

GCD gcd(a,b) = gcd(b, a mod b) Euclid's Algorithm

Bezout ax + by = gcd(a,b) Extended Euclidean

Mod Inverse a·x ≡ 1 (mod n) iff gcd(a,n)=1

CRT x = Σ aᵢNᵢyᵢ mod N N = ∏nᵢ, Nᵢ=N/nᵢ, yᵢ=Nᵢ⁻¹

mod nᵢ

RSA Encrypt C = Mᵉ mod n Public key (n,e)

RSA Decrypt M = Cᵈ mod n d = e⁻¹ mod φ(n)

ElGamal Enc C₁=gᵏ, C₂=M·yᵏ mod p Random k per message

ElGamal Dec M = C₂·(C₁ˣ)⁻¹ mod p x is private key

DH Shared Key K = g^(ab) mod p Alice: Bᵃ, Bob: Aᵇ

φ(p) = p − 1 p is prime

φ(n) = (p−1)(q−1) n = p·q, p,q prime

Good luck with your mid-term! Remember: understand the WHY behind each algorithm —
exams often test reasoning, not just formula recall.