0
$\begingroup$

I have been studying how ElGamal is a public-key algorithm built on top of the Diffie-Hellman key exchange but I got confused. How exactly could an attacker break the Diffie-Hellman protocol (i.e. compute $g^{ab} \bmod p$ efficiently given $p, \space g, \space g^a \bmod p$, and $g^b \bmod p$) if they can efficiently find the plaintext messages from their ciphertexts (encrypted using ElGamal)?

$\endgroup$
2
  • $\begingroup$ What do you mean by " they can efficiently find the plaintext messages from their ciphertexts"? Without a private key? $\endgroup$
    – Maf
    Commented Apr 22, 2020 at 11:13
  • 2
    $\begingroup$ Hint: Write how the ciphertext is produced in ElGamal encryption (some of this answer details it). Assume an algorithm that can find it. Add some bells and whistles to turn it into an algorithm that breaks Diffie-Hellman (more formally: use the hypothetical algorithm as a subprogram). Also, note the proper name of Martin Hellman. $\endgroup$
    – fgrieu
    Commented Apr 22, 2020 at 11:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.