ISE Cryptography — Quiz Solutions
L05: Public Key Cryptography
10 questions · 1 mark each · 10 marks total.
Q01: Trapdoor function correctness
A trapdoor function scheme \(\mathcal{T} = (G, F, I)\) satisfies the correctness property: for all \((pk, sk)\) output by \(G\) and all \(x \in \mathcal{X}\), \(I(sk, F(pk, x)) = x\). What does this guarantee?
Answer:
A holder of \(sk\) can recover \(x\) from \(y = F(pk, x)\): the secret key inverts the forward function.
Q02: What the OW-TDF adversary must produce
In the one-way security game for a trapdoor function scheme, the challenger sends \((pk, y)\) where \(y = F(pk, x)\) for a randomly sampled \(x\). What must the adversary output to win?
Answer:
A value \(\hat{x} \in \mathcal{X}\) such that \(\hat{x} = x\).
Q03: Why textbook RSA is not IND-CPA secure
Textbook RSA encryption is defined as \(c = m^e \bmod n\) where \((n, e)\) is the public key. Why does this fail the IND-CPA security game, regardless of the size of \(n\)?
Answer:
Encryption is deterministic: the adversary holding \(pk\) can re-encrypt each candidate message and compare against the challenge ciphertext.
Why: in the IND-CPA game, the adversary submits \((m_0, m_1)\) and receives \(c^* = m_b^e \bmod n\). Since encryption is deterministic and the public key is known, the adversary computes \(m_0^e \bmod n\) and \(m_1^e \bmod n\) and checks which matches \(c^*\). No assumption about factoring is needed; the attack is direct.
Q04: Breaking RSA by factoring
Which statement most accurately describes the relationship between factoring and breaking the RSA assumption?
Answer:
If an adversary can factor \(n\), they can recover \(d\) and break RSA; the reverse direction is not known to hold.
Why: knowing \(p\) and \(q\) gives \(\phi(n) = (p-1)(q-1)\), and then \(d = e^{-1} \bmod \phi(n)\) is computable. Whether breaking RSA (without factoring) is possible remains an open question.
Q05: CDH, DDH and discrete log
Let DL be the discrete log assumption, CDH the computational Diffie-Hellman assumption, and DDH the decisional Diffie-Hellman assumption, all in the same group \(\mathbb{G}\). Which chain of implications correctly describes their relative strength?
Answer:
\(\text{DDH hard} \Rightarrow \text{CDH hard} \Rightarrow \text{DL hard}\)
Why: CDH says you cannot compute \(g^{ab}\) given \(g^a\) and \(g^b\). DDH says you cannot even distinguish \(g^{ab}\) from a random group element. DDH is CDH plus that extra indistinguishability requirement, so it is the stronger assumption. Similarly, DL says you cannot recover \(a\) from \(g^a\) alone. CDH is DL plus the requirement that you still cannot compute \(g^{ab}\) even when handed a second element \(g^b\), without needing to recover any exponent. So CDH is the stronger assumption.
Reading the chain left to right: each assumption includes everything to its right, and then some.
Q06: Safe primes and prime-order subgroups
Why do we prefer to run DH in a prime-order subgroup of \(\mathbb{Z}_p^*\) rather than in \(\mathbb{Z}_p^*\) itself?
Answer:
\(\mathbb{Z}_p^*\) has composite order \(p - 1\), which makes it vulnerable to Pohlig-Hellman; a prime-order subgroup avoids this entirely.
Why: Pohlig-Hellman solves discrete log in time proportional to the largest prime factor of the group order. For \(\mathbb{Z}_p^*\), the order is \(p - 1\), which factors into many small primes unless \(p\) is a safe prime. Working in a subgroup of prime order \(q\) means Pohlig-Hellman faces an order with no small factors to exploit.
Q07: Elliptic curves and security per bit
256-bit elliptic curve cryptography is comparable to which combination of symmetric and RSA key sizes?
Answer:
128-bit symmetric, 3072-bit RSA.
Q08: PKE from TDF — what the random x provides
The PKE-from-TDF construction encrypts by sampling \(x \xleftarrow{R} \mathcal{X}\), computing \(y \leftarrow F(pk, x)\) and \(k \leftarrow H(x)\), then outputting \((y, E_s(k, m))\). Which property addresses the IND-CPA failure of textbook RSA?
Answer:
Each encryption samples a fresh random \(x\), so the same message under the same \(pk\) produces a different ciphertext every time.
Q09: Which DH value delivers forward secrecy in 3DH
In Triple Diffie-Hellman, the session key derives from \(\text{KDF}(DH_1 \| DH_2 \| DH_3)\) where \(DH_1 = g^{ay}\), \(DH_2 = g^{bx}\), \(DH_3 = g^{xy}\). Which component is responsible for forward secrecy?
Answer:
\(DH_3 = g^{xy}\), because it uses only ephemeral secrets that are destroyed after the session.
Why: \(DH_1\) and \(DH_2\) each involve one long-term key (\(a\) or \(b\)). \(DH_3\) involves only the ephemeral secrets \(x\) and \(y\), which are deleted once the session ends. Compromising long-term identity keys later cannot recover \(DH_3\), and therefore cannot recover the session key.
Q10: Logjam — the operational lesson
The 2015 Logjam attack broke TLS, IPsec and SSH deployments that used 512-bit DH parameters. Precomputation on a single shared 512-bit prime cost roughly a week, after which each new session could be broken in about 70 seconds. What is the operational lesson?
Answer:
Parameter size and parameter diversity both matter: a single shared prime amortises the precomputation cost across every deployment using it.
Why: the expensive step in the number field sieve is the per-prime precomputation, not the per-session sieving. If many deployments share the same prime (as happened with widely-adopted defaults), an attacker amortises that precomputation cost across all of them. The fix is both larger primes (2048-bit minimum) and use of distinct, freshly-generated parameters — or switching to elliptic curve DH, which has no shared-prime problem.