Q7 /20 Choose the public-key cryptosystem that utilizes the fact that the complexity does...
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
/20
Choose the public-key cryptosystem that utilizes the fact that the complexity does not fit within polynomial time
Show answer & explanation
RSA is a public-key cryptosystem whose security relies on the computational hardness of integer factorization—a problem believed to require super-polynomial time (NP-hard) to solve efficiently. IDEA and AES are symmetric-key ciphers, not public-key systems. DSA is a public-key algorithm, but its security basis (discrete logarithm problem) is different from the factorization hardness that RSA explicitly leverages.
Step-by-step Derivation:
Public-key cryptosystems require problems that are easy to solve in one direction (encryption with public key) but computationally infeasible to reverse (decryption without private key). RSA's security is founded on the difficulty of factoring large composite numbers into their prime factors—a task conjectured to be non-polynomial. RSA: public-key ✓, relies on factorization hardness ✓. IDEA: symmetric-key ✗. AES: symmetric-key ✗. DSA: public-key ✓, but based on discrete log, not factorization complexity.