Mathematical Foundations for Cryptography Questions

Comprehensive understanding of the mathematical principles and computational hardness assumptions that underlie cryptographic algorithm design and security analysis. This includes number theory, abstract algebra, probability theory, and algorithmic and computational complexity concepts used to evaluate problem difficulty. Candidates should be familiar with central computational problems such as the discrete logarithm problem, the integer factorization problem, and the elliptic curve discrete logarithm problem, as well as lattice based problems such as the learning with errors problem and the shortest vector problem that are relevant to post quantum cryptography. The topic covers how hardness assumptions are evaluated using reductions, complexity estimates, cryptanalysis history, and known attack techniques, and it requires the ability to apply mathematical reasoning to algorithm design, parameter selection, and mapping hardness assumptions to concrete security levels and trade offs.

MediumTechnical

30 practiced

Given classical computing resources, estimate the classical security (in bits) of an RSA modulus N of 3072 bits. Explain how security estimates combine algorithmic complexity (GNFS) and implementation/practical considerations to produce a concrete security level.

Sample Answer

**Brief answer**Estimated classical security ≈ 128 bits for a 3072-bit RSA modulus, using GNFS asymptotics plus practical cost factors.

**Reasoning (algorithmic)**GNFS running time for factoring N is

text

L_N[1/3, c] = exp( (c + o(1)) * (ln N)^(1/3) * (ln ln N)^(2/3) )

with c = (64/9)^(1/3) ≈ 1.923. Plugging N ≈ 2^3072 gives a runtime that, when converted to equivalent CPU-bit security, is on the order of 2^128 classical operations (standard crosschecks with e.g. ECRYPT/ENISA tables).

**Practical/implementation considerations**- Constant factors: sieving throughput, relation collection, linear algebra (sparse block Lanczos) change real cost by small poly factors.- Parallelism: massive parallel and GPU/FPGA farms reduce calendar time but preserve total work -> security measured in bit-cost; specialized hardware can lower effective bits slightly.- Records & heuristics: recent GNFS records suggest 3072-bit is conservative for ~128-bit security; conservative engineering budgets may use 120–130 bits.

**Concrete recommendation**Treat 3072-bit RSA as ~128-bit classical security, allow a small safety margin (use 3072+ or move to 4096-bit / elliptic-curve schemes) depending on threat model and timeline.

EasyTechnical

39 practiced

Describe the Euclidean algorithm for computing gcd(a, b). Prove that the number of steps is O(log min(a, b)) and explain why that bound is tight in the sense of worst-case inputs. Give examples of worst-case input patterns.

Sample Answer

**Brief description (Euclidean algorithm)** Repeatedly replace (a,b) with (b, a mod b) until b = 0. The last nonzero value is gcd(a,b). In code: while b>0: (a,b) = (b, a % b).

**Proof of O(log min(a,b)) steps (sketch, Lamé’s idea)** Let r0 = a, r1 = b and ri+1 = ri-1 mod ri. The sequence of remainders is strictly decreasing: r0 > r1 > r2 > ... ≥ 0. If the algorithm takes k divisions, then r_{i-1} ≥ 1·r_i + r_{i+1} so the minimal decrease pattern satisfies the Fibonacci recurrence. More precisely one shows

text

r_{i+1} ≥ r_{i-1} - r_i  and  r_{i-1} ≥ r_i + r_{i+1}

and therefore r_{k-j} ≥ F_j where F_j is the j-th Fibonacci. Hence if b = r1 then b ≥ F_k, so

text

k ≤ C · log_phi(b) = O(log b)

(phi ≈ 1.618).

Plain-English: each division step reduces remainders at least as fast as Fibonacci numbers grow, so number of steps is logarithmic in the smaller input.

**Tightness and worst-case inputs** The bound is tight: consecutive Fibonacci pairs (F_{n+1}, F_n) achieve the maximum number of steps ≈ n. Example small worst cases: (13,8), (21,13). For large worst cases use Fibonacci numbers; these appear in cryptographic analyses when measuring algorithmic worst-case cost.

**Cryptographer’s note** Logarithmic bound ensures GCD checks in crypto (key generation, modular inverses) are efficient. Worst-case Fibonacci inputs are rare in practice but important when proving tight complexity guarantees.

EasyTechnical

29 practiced

Compare the random oracle model (ROM) and the standard model of cryptographic proofs. Give an example of a scheme with a proof in the ROM and discuss practical implications and criticisms of relying on ROM for security guarantees.

MediumTechnical

38 practiced

Prove that if you can compute phi(n) for an RSA modulus n = p*q you can factor n efficiently. Provide the algebraic reasoning showing how p and q are recovered from n and phi(n).

Sample Answer

**Answer (cryptographer's perspective)**

1) Key identities and goal- For n = p*q (p,q primes) the Euler totient is

text

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

Intuition: counts integers < n coprime to n.

2) Express sum of primes- Expand phi(n):

text

phi(n) = pq - p - q + 1 = n - (p + q) + 1

Hence the sum S = p + q is

text

S = p + q = n - phi(n) + 1

Intuition: knowing phi(n) gives the linear combination p+q.

3) Recover p and q via quadratic- p and q are roots of x^2 - S x + n = 0 because x^2 - (p+q)x + pq = 0 and pq = n.- Discriminant D:

text

D = S^2 - 4n

Intuition: D = (p - q)^2 ≥ 0; for distinct primes D is a positive perfect square.- Solve:

text

p = (S + sqrt(D)) / 2
q = (S - sqrt(D)) / 2

4) Complexity and notes- Computing S and D is polynomial-time arithmetic; extracting integer square root is polynomial-time (Newton/bit algorithms). Thus factoring reduces to computing phi(n).- Edge cases: if p = q (not RSA) then D = 0 and p = q = S/2. For valid RSA p≠q so sqrt(D) is nonzero integer.

HardTechnical

33 practiced

Explain isogeny-based cryptography (e.g., SIDH/SIKE): what mathematical objects are used, what is the computational hardness assumption, and what are the main known attack vectors? Provide reasons why isogeny problems were considered promising for compact post-quantum key exchange.

Sample Answer

**Brief answer (role: cryptographer)**

**Mathematical objects**- Supersingular elliptic curves over F_{p^2}; isogenies (separable homomorphisms) between them; torsion subgroups E[ℓ^k]; endomorphism rings (quaternion algebras for supersingular curves).- SIDH/SIKE specifically use walks of prescribed ℓ-power degree (typically ℓ=2,3) from a fixed base curve; public keys are target curves plus images of torsion basis points.

**Hardness assumption**- The underlying assumption is that given two supersingular curves (and limited auxiliary torsion-image data) it’s hard to find an explicit isogeny between them — formalized as the Computational/Decisional Supersingular Isogeny problems (CSSI/SSCDHP variants) and related path-finding problems in the supersingular isogeny graph. Quantumly, best generic attacks are subexponential in the graph size but not polynomial (prior to recent specialized breaks).

**Main attack vectors**- Classical: meet-in-the-middle / baby-step giant-step on isogeny walks (time ~sqrt of search space).- Quantum: claw-finding / search improvements (Grover/quantum walks) reduce complexities but not to poly-time for generic instances.- Structure exploits: recovering secret using auxiliary torsion-image points (SIDH provided such points in public keys), leading to algebraic attacks mapping to linear equations.- Endomorphism-ring computation: if one computes End(E) classically/quantumly, explicit isogenies can be derived via quaternion-algebra techniques.- Practical: side-channels, fault attacks, implementation pitfalls.

**Why promising for compact PQ KEX**- Very small public keys/ ciphertexts relative to lattice/code-based schemes because security is encoded in short isogeny descriptions and a few curve/point coordinates.- Different hardness foundation than lattices/codes, offering diversification.- Concrete SIDH design provided efficient Diffie–Hellman-like exchange with relatively small bandwidth.

**Caveats / current status**- SIDH/SIKE were optimistic but SIKE was broken (Castryck–Decru 2022) by exploiting torsion-point structure and computing endomorphism rings; this demonstrates structural risks when auxiliary data leaks. Current isogeny research focuses on schemes without those public torsion images (e.g., CSIDH variants, supersingular schemes with different assumptions) and on hardening implementations against algebraic and side-channel attacks.

Unlock Full Question Bank

Get access to hundreds of Mathematical Foundations for Cryptography interview questions and detailed answers.

Join thousands of developers preparing for their dream job.