Number Theory and Mathematical Foundations of Cryptography Questions

Direct answer

Euler's totient $\phi(n)$ counts the integers from 1 to $n$ that share no common factor with $n$. For $n = pq$ with distinct primes, $\phi(n) = (p-1)(q-1)$, and this quantity is exactly what RSA (the Rivest, Shamir, and Adleman public-key cryptosystem) key generation needs to compute the private exponent $d$, because Euler's theorem is what guarantees decryption undoes encryption.

Structured elaboration

$\phi(n)$ is the size of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$, the group of residues mod $n$ that have a multiplicative inverse. For a general $n$ this can be tricky to compute without knowing its factorization, but for $n = pq$ with distinct primes $p, q$, every residue that is neither a multiple of $p$ nor of $q$ is coprime to $n$. Counting directly: there are $p-1$ nonzero residues mod $p$ and $q-1$ nonzero residues mod $q$, and the Chinese Remainder Theorem lets these combine independently, giving

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

RSA key generation, at the mathematical level:

1. Choose distinct primes $p, q$; compute $n = pq$.
2. Compute $\phi(n) = (p-1)(q-1)$.
3. Choose public exponent $e$ with $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$.
4. Compute private exponent $d$ as the modular inverse of $e$ mod $\phi(n)$: $e \cdot d \equiv 1 \pmod{\phi(n)}$.

Why $\phi(n)$ is needed for $d$. Euler's theorem states that for any $m$ coprime to $n$, $m^{\phi(n)} \equiv 1 \pmod n$. Choosing $d$ so that $ed \equiv 1 \pmod{\phi(n)}$ means $ed = 1 + k\phi(n)$ for some integer $k$, and then

$m^{ed} = m \cdot \left(m^{\phi(n)}\right)^k \equiv m \cdot 1^k \equiv m \pmod n$

so raising to $e$ then to $d$ returns the original value. Without $\phi(n)$, there is no way to compute a matching $d$ for a given $e$, which is why $\phi(n)$ (equivalently, knowledge of $p$ and $q$) is the private key material, and finding $d$ from $n$ and $e$ alone is believed to require factoring $n$ first.

Worked example

Take small primes $p = 7$, $q = 11$:

$n = 7 \times 11 = 77, \qquad \phi(n) = (7-1)(11-1) = 6 \times 10 = 60$

Choose $e = 7$: check $\gcd(7, 60) = 1$, valid. Find $d$ solving $7d \equiv 1 \pmod{60}$: $d = 43$, and indeed $7 \times 43 = 301 = 5 \times 60 + 1$.

Trade-offs and pitfalls

A frequent conceptual slip is treating $\phi(n)$ as computable from $n$ alone without the factorization, it is not, for a general composite $n$ this is exactly as hard as factoring. Another is forgetting to check $\gcd(e, \phi(n)) = 1$ before proceeding; if it fails, $e$ has no modular inverse mod $\phi(n)$ and no valid $d$ exists. As with any hand-computable example, $p=7$ and $q=11$ are far too small for real security; production RSA keys use primes with hundreds of decimal digits precisely so that computing $\phi(n)$ from $n$ alone is computationally infeasible.

Direct answer

Point addition and scalar multiplication on an elliptic curve are built from ordinary modular arithmetic (a handful of additions, multiplications, and one inversion per step), so computing $k \cdot P$ for a large integer $k$ is fast. But reversing that process, recovering $k$ given only $P$ and $k \cdot P$, is the elliptic curve discrete logarithm problem (ECDLP), and no algorithm significantly better than generic square-root attacks is known for a well-chosen curve. The gap between "easy forward" and "hard backward" is what makes elliptic curve cryptography (ECC) work.

Structured elaboration

An elliptic curve over a finite field $\mathbb{F}_p$ consists of the points $(x, y)$ satisfying

$y^2 = x^3 + ax + b \pmod p$

together with a special "point at infinity" $O$ acting as the identity. These points form an abelian group under a geometric addition rule:

• Point addition ($P \neq Q$): draw the line through $P$ and $Q$; it hits the curve at a third point, and reflecting that point across the x-axis gives $P+Q$. Algebraically, with slope $\lambda = (y_Q - y_P)(x_Q - x_P)^{-1} \bmod p$:
  $x_R = \lambda^2 - x_P - x_Q, \qquad y_R = \lambda(x_P - x_R) - y_P \pmod p$
• Point doubling ($P = Q$): use the tangent line instead, with slope $\lambda = (3x_P^2 + a)(2y_P)^{-1} \bmod p$, then the same formulas for $x_R, y_R$.

Scalar multiplication $k \cdot P$ means adding $P$ to itself $k$ times, but it is never computed that way. Double-and-add (analogous to fast exponentiation) computes it in about $\log_2 k$ doublings plus additions, one per set bit of $k$, so it costs only $O(\log k)$ group operations, each a handful of modular multiplications and one inversion. That is why the forward direction is cheap even for a 256-bit $k$.

Worked example

Take the small curve $y^2 = x^3 + 2x + 2 \pmod{17}$ (parameters $a=2, b=2, p=17$, chosen only so the arithmetic fits on paper). The point $P = (5, 1)$ is on the curve, since $1^2 = 1$ and $5^3 + 2(5) + 2 = 125 + 10 + 2 = 137 \equiv 1 \pmod{17}$.

Doubling $P$: slope $\lambda = (3 \cdot 5^2 + 2)(2 \cdot 1)^{-1} \bmod 17$. This curve, run through the group law, gives

$2P = P + P = (6, 3)$

$3P = 2P + P = (10, 6)$

Continuing the same doubling-and-adding pattern out to $7P = (0, 6)$, and checking every multiple, this particular $P$ turns out to generate a subgroup of order 19 (there are 18 other affine points on this tiny curve plus the point at infinity, and $P$ reaches all of them before returning to $O$). Recovering the exponent $k$ from $kP$ here is trivial by brute force, since the whole group has only 19 elements; that is exactly the point, a cryptographically sized curve uses a field and group order around 256 bits, making the same brute-force search take on the order of $2^{128}$ steps instead of 19.

Trade-offs and pitfalls

ECDLP's hardness is not automatic: it depends on the curve avoiding a short list of known structural weaknesses. Two named examples, both rarely something you would need to re-derive in an interview, just recognize by name and know to avoid: anomalous curves (curves where the number of points on the curve happens to equal the field size $p$ exactly; that coincidence enables a specific fast algorithm that solves the discrete log in linear time instead of the usual square-root time), and curves with small embedding degree (the embedding degree is the smallest integer $k$ such that the curve's group can be mapped, via a pairing, into the multiplicative group of the extension field $\mathbb{F}_{p^k}$; a small $k$ means that mapping is cheap to compute, which lets an attacker transfer the discrete log problem out of the curve's exponentially-hard group and into a finite field's multiplicative group, where sub-exponential index-calculus attacks apply instead). This is why cryptographic curves are standardized and vetted rather than picked arbitrarily, and why "is this curve on a standard, vetted list" is usually as deep as this needs to go in practice or in an interview.

A common conceptual mistake is assuming elliptic curves have an index-calculus-style shortcut the way multiplicative groups do. Index calculus is a family of algorithms that solve discrete logs faster than brute force by building relations among a small chosen set of "easy" elements (a factor base) and combining them with linear algebra; it works well in the multiplicative group of a finite field, but elliptic curves generically do not have the extra structure it needs. That is precisely why the best known generic attack (Pollard's rho, costing about $O(\sqrt{n})$ group operations for a group of order $n$) is close to the true difficulty, and why ECC keys can be so much smaller than RSA (the Rivest, Shamir, and Adleman public-key cryptosystem) moduli for the same security level: RSA's best attack is sub-exponential, ECC's best generic attack is exponential in the group's bit-length.

Direct answer

P, NP, and NP-hard are complexity classes describing how the cost of solving a problem scales with input size, not how unpredictable to guess a specific instance is; basing cryptographic security on "this problem is NP-hard" only proves that the hardest instances of that problem are hard, which is not the same as proving that the specific instances a real scheme generates are hard on average, and average-case, instance-specific hardness is what a cryptosystem actually needs.

Structured elaboration

• P: problems solvable in polynomial time by a deterministic algorithm, considered efficiently solvable.
• NP: problems whose proposed solutions can be verified in polynomial time, even if finding one from scratch might take much longer.
• NP-hard: at least as hard as every problem in NP, meaning any NP problem can be transformed (reduced) into it in polynomial time. NP-hard problems need not themselves be in NP; some are not even decidable.

Cryptographic meaning. Basing a scheme's security on an NP-hard problem would mean: breaking the scheme efficiently implies an efficient solver for that NP-hard problem exists. That is a compelling-sounding story, but NP-hardness is a worst-case notion. It only guarantees that the single hardest instances of the problem resist efficient solution; it says nothing about a randomly generated, "typical" instance, and a cryptosystem's key generation always produces exactly such typical instances, not adversarially chosen worst cases. If most instances of an NP-hard problem are easy and only a vanishingly rare subset are hard, an NP-hardness proof is compatible with every instance a real key-generation algorithm ever produces being trivially breakable.

Limitations of NP-hardness as the sole justification

1. Worst-case versus average-case. Cryptography needs the specific instances it generates to be hard essentially all the time, not just somewhere in the space of all possible instances.
2. Decision versus search. Many NP-hardness results are proven for decision problems ("does a solution exist?"), while breaking a cryptosystem is usually a search or inversion task ("find the actual secret key"); a reduction between the two is not automatic.
3. Non-constructive or non-tight reductions. Even where a reduction exists, it may not be efficient enough in practice, an attacker needing to solve the NP-hard problem "only" $n^{50}$ times faster than the reduction assumes could still break real-world parameter sizes.
4. No protection from unrelated attack strategies. An NP-hardness proof says nothing about side channels, protocol-level attacks, or shortcuts that never go through the underlying hard problem at all.

Because of these gaps, cryptographers generally prefer problems with a direct, well-studied argument for average-case hardness over merely worst-case NP-hardness, well-known examples include factoring and the discrete logarithm problem (whose apparent average-case hardness is what actually underlies RSA (the Rivest, Shamir, and Adleman public-key cryptosystem) and Diffie-Hellman, not any NP-hardness claim about them, since neither is even known to be NP-hard) and, among newer constructions, lattice problems like Learning With Errors, which come with unusually strong worst-case-to-average-case reduction theorems specifically designed to close this exact gap.

Worked example (a real cryptosystem broken by exactly this gap)

The Merkle-Hellman knapsack cryptosystem (1978), one of the earliest public-key proposals, is the concrete cautionary tale a candidate can point to by name. It was built on subset-sum: given a set of positive integers and a target, decide whether some subset adds up to it, a canonical NP-complete (hence NP-hard) problem. The reasoning behind the design was exactly the flawed argument this question asks about: subset-sum is worst-case hard, so a scheme built around it should be secure.

The trapdoor worked by hiding an easy "superincreasing" sequence (one where each term exceeds the sum of every earlier term, making subset-sum trivial to solve by a simple greedy scan) inside a public sequence disguised by modular multiplication. But the public key this construction actually generates is not a worst-case-hard subset-sum instance, it carries hidden algebraic structure. In 1982, Shamir published a polynomial-time attack showing that the modular multiplication step does not hide the superincreasing structure well enough: exploiting an unusually good simultaneous Diophantine approximation built from the public key, an attacker recovers the private key directly, without ever needing to solve a hard subset-sum instance. (The now more commonly cited lattice-basis-reduction attacks on knapsack cryptosystems, using the LLL algorithm, came from subsequent work, including Adleman's 1983 attack and Lagarias and Odlyzko's low-density subset-sum results.) The general subset-sum problem remains NP-hard to this day, but this specific scheme was broken in practice, a direct historical demonstration that "the underlying problem is NP-hard" said nothing about whether the specific, structured instances a real key-generation algorithm produces are actually hard.

Trade-offs and pitfalls

A frequent misconception worth correcting directly for a junior engineer: RSA and Diffie-Hellman are not, in fact, known to rest on an NP-hard problem at all, factoring is not known to be NP-hard (and is not believed to be, since it lies in NP intersect co-NP, a class most experts do not expect NP-hard problems to fall into). Their security instead rests on decades of failed attempts to find an efficient average-case algorithm for the specific problem, empirical confidence rather than a worst-case complexity-class proof. That distinction, between "provably hard in the worst case" and "believed hard on average based on cryptanalytic experience," is the single most important idea to convey when explaining why NP-hardness alone is neither necessary nor sufficient for a cryptographic hardness assumption.

Direct answer

For a 2048-bit Diffie-Hellman (DH) group used in Transport Layer Security (TLS, the protocol that secures HTTPS connections), pick a safe prime $p = 2q+1$ where $q$ is also prime, choose a generator $g$ of the large prime-order subgroup of size $q$, and validate every peer's public value against that subgroup before using it. Skipping the validation step is what opens the door to small-subgroup and Pohlig-Hellman attacks, even if $p$ and $g$ themselves were chosen correctly.

Structured elaboration

The goal is to make the discrete logarithm problem (DLP) as hard as possible within the group, which means avoiding two structural weaknesses:

• Pohlig-Hellman attack: if $p - 1$ factors into many small primes, an attacker can solve the discrete log modulo each small factor separately (each one cheap) and reassemble the full exponent with the Chinese Remainder Theorem. The fix is ensuring $p-1$ has a large prime factor and working inside the subgroup of that order.
• Small-subgroup attack: if a party is tricked into accepting a public value from a small-order subgroup instead of the intended large one, exponentiating with their secret key leaks that secret modulo the small subgroup's order. The fix is checking every incoming public value actually lies in the intended subgroup.

Worked example (toy-sized parameters, real deployments use 2048+ bits)

Construct a safe prime: pick prime $q = 11$, set $p = 2q + 1 = 23$. Check: $(p-1)/2 = 11 = q$, confirmed.

Find a generator of the order-$q$ subgroup: pick $h = 2$ and square it, $g = h^2 \bmod p = 4 \bmod 23 = 4$. Verify its order is exactly $q$:

$g^q \bmod p = 4^{11} \bmod 23 = 1$

Since $g \neq 1$ and $g^{11} \equiv 1 \pmod{23}$, $g$ generates the order-11 subgroup as intended (squaring a random nonzero element mod a safe prime always lands in the order-$q$ subgroup, since $p-1 = 2q$ has only the factors 2 and $q$).

Real production checks scale this exact pattern up: for a 2048-bit safe prime, $q$ would be roughly 2047 bits (large enough that Pohlig-Hellman on the subgroup is infeasible), and every received public value $A$ would be checked with $2 \le A \le p-2$ and $A^q \equiv 1 \pmod p$ before being used, rejecting anything that fails.

Trade-offs and pitfalls

Safe primes are more expensive to generate than arbitrary strong primes (finding one where both $p$ and $(p-1)/2$ are prime takes longer), but they make the small-subgroup structure trivial to reason about, which is why standards like NIST (the U.S. National Institute of Standards and Technology) SP 800-56A Rev. 3, which approves the safe-prime finite-field DH groups used in protocols like TLS, favor them for DH group generation. A common mistake is validating the group parameters once at setup time but skipping per-message validation of each peer's public value, small-subgroup attacks specifically exploit a live protocol run, not a static parameter file. Finally, parameter provenance matters: using a well-known, published prime (from an RFC, the standards documents published by the IETF, the Internet Engineering Task Force, for instance) rather than a self-generated one avoids the risk of a hidden trapdoor baked into the choice of $p$.

Direct answer

Fermat's Little Theorem says that for a prime p and any integer a not divisible by p, a^(p-1) ≡ 1 (mod p) ("≡" means "leaves the same remainder as"; "mod p" means "after dividing by p"). The Fermat primality test turns this around: to probe whether n might be prime, compute a^(n-1) mod n for a chosen base a. If the result is not 1, n is definitely composite; if it is 1, n merely "passes" for that base. It is only probabilistic evidence, because a family of composites called Carmichael numbers, such as 561, pass for every base coprime to n, so no amount of retrying with more bases will ever catch them. That structural blind spot is exactly why Miller-Rabin is used instead in practice.

Structured elaboration

• Fermat's Little Theorem (FLT): if p is prime and gcd(a, p) = 1 (gcd is the greatest common divisor), then a^(p-1) ≡ 1 (mod p).
• Fermat test on candidate n: pick a base a, compute a^(n-1) mod n.
  • Result is not 1: n is definitely composite (a is a "Fermat witness").
  • Result is 1: n is a "probable prime to base a", or, if n is actually composite, a is a "Fermat liar."
• Why the test is only probabilistic: FLT is a necessary condition for primality, not a sufficient one. A composite n can still satisfy the congruence for some bases, or, in the worst case, for every base coprime to it.

Worked example: the Carmichael number 561

561 = 3 × 11 × 17, which is composite. A composite n is a Carmichael number exactly when it is squarefree and, for every prime factor p of n, (p-1) divides (n-1); this is Korselt's criterion. Checking it for 561, where n-1 = 560:

$3-1=2,\ 560/2=280 \qquad 11-1=10,\ 560/10=56 \qquad 17-1=16,\ 560/16=35$

All three divide evenly, so 561 is a Carmichael number: a^560 ≡ 1 (mod 561) for every a with gcd(a, 561) = 1, no matter which base is tried. For example, with a = 2:

$2^{560} \bmod 561 = 1$

Now run Miller-Rabin on the same n = 561, base a = 2. Decompose 560 = 2^4 × 35 (so s = 4, d = 35). Computing x = 2^35 mod 561 and squaring up to s-1 = 3 more times gives the sequence 263, 166, 67, 1. The sequence does reach 1, but the value immediately before it is 67, not 560 (= n-1). Since 67^2 ≡ 1 (mod 561) yet 67 is neither 1 nor 560, 67 is a nontrivial square root of 1: a value other than ±1 that still squares to 1. Modulo a prime, no such value can exist. Here is why: if y^2 ≡ 1 (mod p) for a prime p, then y^2 - 1 ≡ 0 (mod p), which factors as (y-1)(y+1) ≡ 0 (mod p). Since p is prime, its residues form a field, a number system where a product can only be ≡ 0 (mod p) if one of the factors already is, so one of (y-1) or (y+1) must itself be ≡ 0 (mod p), forcing y ≡ 1 or y ≡ -1 and nothing else. 561 is composite, not prime, so this guarantee breaks down: its residues do not form a field, and a pair like 3 and 7 (both nonzero mod 561, since 561 = 3 × 11 × 17) can multiply to something ≡ 0 (mod 561) without either being 0, exactly the kind of loophole that lets a nontrivial square root of 1 like 67 slip through. That alone certifies 561 as composite, and as a bonus, gcd(67-1, 561) = 33 and gcd(67+1, 561) = 17 both hand back genuine factors of 561 for free.

Trade-offs and pitfalls

Fermat's test is cheap and easy to reason about, but it has no fallback once a composite happens to satisfy the congruence for all bases (a true Carmichael number) or for the specific bases that were sampled (a Fermat pseudoprime to those bases). Increasing the number of random bases does not help against a genuine Carmichael number, since the failure Fermat checks for never occurs for them by construction. Miller-Rabin closes that gap because it inspects the structure of the square-root chain, not just its endpoint, giving a provable error bound of at most 1/4 per random base even against Carmichael numbers. That structural guarantee, not just "more testing," is why every cryptographic library uses Miller-Rabin, or something stronger, rather than plain Fermat testing for prime generation.