Number Theory and Mathematical Foundations of Cryptography Questions
The classical mathematics underpinning cryptographic hardness assumptions: modular arithmetic, prime generation and primality testing, the structure of the discrete logarithm and integer factorization problems, group and finite field theory, elliptic curve arithmetic, and pairings and bilinear groups. Covers deriving why a scheme's underlying hard problem is believed hard, the classical algorithms (index calculus, the Number Field Sieve, Pollard's rho, baby step giant step, BKZ) used to estimate its concrete difficulty as an input to parameter sizing, and how that difficulty maps to classical parameter sizes (RSA moduli, DH/DSA group sizes, EC curve sizes, pairing group balance). Every question should ground the math in an actual cryptographic scheme (RSA, Diffie-Hellman, (EC)DSA/Schnorr, ECC, or a primality testing pipeline), not bare textbook number theory. Distinct from the constructive lattice-, code-, and multivariate-based post-quantum schemes and their concrete-security estimation, which post-quantum-and-lattice-cryptography owns; this topic retains a small set of foundational lattice-object definitions (a lattice and its basis, the Gaussian heuristic, BKZ's root-Hermite relation, NTRU decryption-failure bounds, discrete-Gaussian sampler proofs, new-assumption vetting methodology) and the isogeny hardness assumption that the closed topic's own curation does not ship, kept here rather than deleted, plus a three-question footnote on why Shor collapses these classical assumptions together. Also distinct from formal security-reduction proofs and cryptanalytic attack methodology, owned by cryptanalysis-and-security-proofs. The theory layer distinguishing a cryptographer from a library user.
Given the GNFS asymptotic complexity and recent parameterized practical factoring results, explain how cryptographers map GNFS runtimes to required RSA key sizes for a target classical security level (for example, 128-bit security). Provide a reasoned derivation or numerical argument, translating the asymptotic cost into an estimated concrete adversary cost (CPU, GPU, or dedicated sieving hardware, and how you would model parallel resources), that leads to the commonly cited NIST recommendation of roughly 3072-bit RSA for 128-bit security, and discuss the assumptions and uncertainties in that mapping.
You are handed a candidate elliptic curve for a new signature scheme and asked to sign off on it before it ships to production. What mathematical properties of the curve's order, trace, embedding degree, and field would you check to rule out a weak instance, and what could go wrong if you skipped each check? Then apply your checklist to the curve y^2 = x^3 + x + 1 over F_23 and justify whether it is safe to use.
Show how the Number Field Sieve (NFS) asymptotic complexity L_n[1/3, c] for factoring influences the recommended sizes of modulus n for RSA. Given the L-notation, derive how increasing modulus bits by Δ influences expected runtime and why security scaling is sub-exponential rather than exponential.
Explain the risks of using multiplicative groups modulo a composite N (i.e., Z_N^*) and using elements from composite-order groups in discrete-log based schemes. Show with math how small-order factors or elements outside a prime-order subgroup enable small-subgroup attacks or allow an attacker to glean information. Then describe the safe parameter checks and protocol-level mitigations you would put in place to prevent it.
You are tasked with selecting safe parameters for a 2048-bit Diffie-Hellman group used in TLS. Describe mathematically how you would choose the prime p and generator g (or subgroup order r and generator) and what checks you would perform to ensure group security against small-subgroup and Pohlig-Hellman attacks.
That is every published Number Theory and Mathematical Foundations of Cryptography question for Security Architect so far. Browse the other topics in this category, or practice this one interactively.