Number Theory for Cryptography Questions

Comprehensive mastery of the number theoretic and algebraic foundations that underpin modern cryptography. Core topics include modular arithmetic and modular exponentiation, prime number theory and primality testing, integer factorization problems, the discrete logarithm problem in multiplicative groups, quadratic residues and Legendre and Jacobi symbols, Euler theorem, group theory, ring theory, finite fields, and elliptic curve groups. Candidates should be able to apply these concepts to analyze and explain public key systems such as Rivest Shamir Adleman, Diffie Hellman key exchange, ElGamal, and elliptic curve cryptography, and to show why security reduces to the hardness of integer factorization or discrete logarithm in the appropriate group. The scope covers algorithmic tools and their practical complexity including the extended Euclidean algorithm, fast modular exponentiation, Chinese remainder theorem, Miller Rabin and deterministic primality tests, trial division, Pollard rho and Pollard p minus one factorization methods, elliptic curve method for factorization, quadratic sieve, general number field sieve, baby step giant step, Pollard rho for discrete logarithm, and index calculus approaches. Candidates should be comfortable solving representative problems by hand or with small code examples such as computing modular inverses, performing modular exponentiation, applying the Chinese remainder theorem, solving small discrete logarithm instances, and reasoning about how algorithmic advances translate into concrete key size and security recommendations.

EasyTechnical

57 practiced

RSA fundamentals: given p = 61, q = 53 and public exponent e = 17, compute N = p * q, phi(N), find the private exponent d (the modular inverse of e mod phi(N)), encrypt plaintext m = 65 to obtain c = m^e mod N, and then decrypt c to recover m. Show all intermediate calculations and explain why decryption recovers the original message.

Sample Answer

**Answer (step-by-step)**

**1. Compute N and phi(N)**

text

N = p * q = 61 * 53 = 3233

text

phi(N) = (p - 1) * (q - 1) = 60 * 52 = 3120

**2. Find private exponent d (modular inverse of e mod phi(N))**We need d such that

text

e * d ≡ 1 (mod phi(N))  =>  17 * d ≡ 1 (mod 3120)

Using the extended Euclidean algorithm gives d = 2753 because 17 * 2753 = 46801 and 46801 mod 3120 = 1.

**3. Encrypt plaintext m = 65**Ciphertext c = m^e mod N:

text

c = 65^17 mod 3233 = 2790

(Compute with modular exponentiation to avoid huge intermediate numbers.)

**4. Decrypt ciphertext c**Recover m' = c^d mod N:

text

m' = 2790^2753 mod 3233 = 65

**5. Why decryption recovers the original message**Because e and d are chosen so e * d ≡ 1 (mod phi(N)), there exists k with e*d = 1 + k*phi(N). For m coprime to N, Euler's theorem implies

text

m^{phi(N)} ≡ 1 (mod N)

text

m^{e*d} = m^{1 + k*phi(N)} ≡ m * (m^{phi(N)})^k ≡ m (mod N)

Thus decryption returns the original m. For completeness, special-case reasoning via Chinese Remainder Theorem handles m not coprime to N.

HardTechnical

77 practiced

Compare the Quadratic Sieve (QS) and the General Number Field Sieve (GNFS) in detail: explain core ideas of each algorithm, their asymptotic complexities, and the practical crossover point where GNFS becomes more efficient than QS. Use numeric examples to indicate roughly where QS is still used and where GNFS dominates for factoring integers relevant to cryptographic key sizes.

Sample Answer

**Core idea — Quadratic Sieve (QS)**- QS is a special-case sieving method over Z: find many smooth values of f(x) = x^2 − n, collect exponent vectors over a factor base, and solve a linear system modulo 2 to get a product of squares → nontrivial factor.- Works best when the polynomial values are moderately sized so smoothness probability is reasonable; relatively simple, low-overhead, memory-light.

**Core idea — General Number Field Sieve (GNFS)**- GNFS lifts the problem to number fields: choose a polynomial f with a root mod n, sieve relations of the form a − b·α in two domains (rational and algebraic), collect relations, map to exponents, and combine to get squares mod n. More complicated arithmetic but yields much larger smoothness probabilities per relation for very large n.- Requires polynomial selection, lattice sieving, and expensive linear algebra with large memory.

**Asymptotic complexities (L-notation)**- QS:

text

L_n[1/2, 1] = exp( (1+o(1)) sqrt( ln n · ln ln n ) )

- GNFS:

text

L_n[1/3, (64/9)^{1/3} ] ≈ L_n[1/3, 1.923] = exp( ( (64/9)^{1/3} + o(1) ) (ln n)^{1/3} (ln ln n)^{2/3} )

- Intuition: QS has subexponential exponent 1/2, GNFS improves to exponent 1/3, so GNFS grows much slower for very large n.

**Practical crossover & numeric examples**- In practice the crossover occurs around ~100–110 decimal digits (≈330–365 bits). Below that QS (and its variants: MPQS/SiQS) can be competitive; above that GNFS is generally faster.- Historical/operational markers: - QS used commonly up to ~60–100 decimal digits for fastest runs on modest hardware. - GNFS used for large public‑key relevant sizes: RSA-768 (232 decimal digits, 768 bits) was factored with GNFS; GNFS is standard for 1024-bit (≈309 d) and 2048-bit keys.- Rule of thumb for a cryptographer: any key size used in practice for RSA (≥1024 bits) is in GNFS territory; QS is only relevant for small, non‑cryptographic sizes or research/teaching benchmarks.

**Practical considerations & tooling**- GNFS has higher implementation complexity, larger memory and precomputation costs, but parallelizes well (sieving) and has dedicated tools (CADO-NFS, msieve, GGNFS).- For security estimates use GNFS asymptotics and tuned benchmarks; always account for improvements in polynomial selection and sieving hardware when projecting break times.

**Bottom line**- QS: simpler, good for small (tens of digits to ~100 digits).- GNFS: asymptotically and practically superior for cryptographic sizes (hundreds to thousands of bits); use GNFS-based cost models when assessing RSA key strength.

EasyTechnical

60 practiced

Solve the simultaneous congruences using the Chinese Remainder Theorem (CRT): x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Show the construction using the CRT formula (explicitly compute the N_i and inverses) and give the unique solution modulo the product of the moduli.

Sample Answer

**Solution outline (CRT formula)**

We want x satisfying:- x ≡ 2 (mod 3)- x ≡ 3 (mod 5)- x ≡ 2 (mod 7)

Let N = 3·5·7 = 105. For each modulus n_i let N_i = N / n_i and find y_i with N_i·y_i ≡ 1 (mod n_i). Then

x ≡ Σ a_i·N_i·y_i   (mod N)

**Compute N_i and inverses**

- n1 = 3, a1 = 2: N1 = 105/3 = 35. Compute 35 mod 3 = 2. Inverse y1 of 2 mod 3 satisfies 2·y1 ≡ 1 (mod 3) ⇒ y1 = 2.- n2 = 5, a2 = 3: N2 = 105/5 = 21. 21 mod 5 = 1 ⇒ inverse y2 = 1.- n3 = 7, a3 = 2: N3 = 105/7 = 15. 15 mod 7 = 1 ⇒ inverse y3 = 1.

**Assemble solution**

Compute contribution terms:- a1·N1·y1 = 2·35·2 = 140- a2·N2·y2 = 3·21·1 = 63- a3·N3·y3 = 2·15·1 = 30

Sum:

x ≡ 140 + 63 + 30 = 233  (mod 105)

Reduce modulo 105: 233 ≡ 23 (mod 105).

**Answer**

x ≡ 23 (mod 105). This is the unique solution modulo 105.

**Cryptographic note**

CRT constructions like this are fundamental in optimizing RSA private-key operations (using prime-power moduli and recombination), so correctly computing N_i and modular inverses is a routine cryptographic primitive.

MediumTechnical

69 practiced

Write a Python function compute_rsa_private(p, q, e) that computes the RSA private exponent d (i.e., modular inverse of e modulo phi(N)). The function should raise an exception if e is not invertible. Demonstrate the function with p = 61, q = 53, e = 17 and include basic input validation and comments explaining each step.

Sample Answer

**Approach**- Compute phi = (p-1)*(q-1). Use Extended Euclidean Algorithm to compute modular inverse of e mod phi. Validate inputs and raise if inverse doesn't exist.

**Code**

python

def compute_rsa_private(p, q, e):
    # Basic input validation
    if not (isinstance(p, int) and isinstance(q, int) and isinstance(e, int)):
        raise TypeError("p, q, e must be integers")
    if p <= 1 or q <= 1 or e <= 0:
        raise ValueError("p and q must be >1; e must be >0")

    phi = (p - 1) * (q - 1)

    # Extended Euclidean Algorithm returning (g, x, y) with ax + by = g = gcd(a,b)
    def egcd(a, b):
        if b == 0:
            return (a, 1, 0)
        g, x1, y1 = egcd(b, a % b)
        return (g, y1, x1 - (a // b) * y1)

    g, x, _ = egcd(e, phi)
    if g != 1:
        raise ValueError("e is not invertible modulo phi (gcd != 1)")

    # x is the modular inverse but may be negative; normalize to [0, phi-1]
    d = x % phi
    return d

# Demonstration
if __name__ == "__main__":
    p, q, e = 61, 53, 17
    d = compute_rsa_private(p, q, e)
    print("Private exponent d =", d)  # Expected: 2753

**Explanation & Notes**- egcd computes gcd and Bezout coefficients; if gcd != 1 no inverse exists.- Complexity: O(log phi) time (Euclidean algorithm), O(1) extra space.- Edge cases: non-prime p/q allowed for calculation but will weaken RSA; ensure e coprime to phi.

MediumTechnical

59 practiced

Describe the baby-step giant-step algorithm for solving the discrete logarithm problem. Then apply it to solve 2^x ≡ 5 (mod 101) by explicitly building the baby-step table and performing giant steps. Analyze the algorithm's time and memory complexity and discuss practical memory-time trade-offs.

Unlock Full Question Bank

Get access to hundreds of Number Theory for Cryptography interview questions and detailed answers.

Join thousands of developers preparing for their dream job.