English
Menu

Applied Cryptography

In Diffie–Hellman key exchange, a prime p and a generator g are public; A and B choose secret values a and b and send each other g^a mod p and g^b mod p. Which of the following is the reason an eavesdropper is believed unable to find the shared secret g^(ab) mod p even after seeing all these public values?

  1. AThe problem of finding a from g^a mod p (the discrete logarithm problem) is believed to be infeasible to solve efficiently when p is large
  2. Bg^a mod p and g^b mod p are further encrypted with the other party's public key before being sent, so the eavesdropper cannot read them
  3. CThe shared secret is made from a passphrase the two agreed on when they met in advance
Show answer and explanation

Answer: A. The problem of finding a from g^a mod p (the discrete logarithm problem) is believed to be infeasible to solve efficiently when p is large

Computing g^a mod p is fast, but finding a from the result is believed to be impossible in realistic time when p is large enough (the discrete logarithm problem). Even if the eavesdropper sees g^a mod p and g^b mod p, g^(ab) mod p cannot be formed without knowing a or b. Meanwhile, A just raises B's value to the power a and B raises A's value to the power b, and both obtain the same g^(ab) mod p. Doing the same on an elliptic curve is ECDH, which rests on the difficulty of the elliptic-curve discrete logarithm problem.

  • A. Correct. The difficulty of the discrete logarithm problem, finding the secret value from the public value, is the basis of its security.
  • B. The public values are sent without encryption. Being safe even when seen is the strength of this scheme.
  • C. The strength of this key exchange is that a shared secret can be created over a public channel alone, without sharing a secret beforehand.
Practice this topic Back to topic

Books on Applied Cryptography Ad

As an Amazon Associate I earn from qualifying purchases.

More Applied Cryptography questions

  1. Diffie–Hellman key exchange is checked with small numbers. Let p = 23 and g = 5; A chooses the secret value a = 6 and B the secret value b = 15. A sends A = g^a mod p and B sends B = g^b mod p. Which of the following is the shared secret the two obtain?
  2. Which of the following is the correct combination of a weakness of Diffie–Hellman key exchange without authentication and its countermeasure?
  3. In the table of NIST SP 800-57, which of the following is the combination of RSA key length (the number of bits of n) and elliptic-curve key length given as the guideline for security comparable to a 128-bit symmetric-key cipher (AES-128)?
  4. In TLS, which of the following key exchange methods provides the property that previously recorded communications cannot be decrypted even if the private key of the server certificate leaks later (forward secrecy)?
  5. In ECDSA digital signatures, a secret random number k is used for each signature. Which of the following correctly describes how k must be handled?

Comparisons in this topic