In Number Theory, Logic, and Cryptography

Diffie-Hellman Problem


The Diffie-Hellman problem is central to modern cryptography, and is crucial to Internet security.






Suppose Alice has a private key a, and Bob has a private key b.  Both make their public keys, pa mod g and pb mod g, freely known to all.  They therefore immediately have a shared key pab mod g (which Alice can compute by raising Bob’s public key to the ath power, and Bob can compute by raising Alice’s public key to the bth power).  All four of a, b, p, and g are extremely large numbers, typically greater than 100 digits.


The Diffie-Hellman problem is, can an adversary who knows both of the public keys, pa mod g and pb mod g, and also the values of p and g, compute this shared key? 


For further information, please see:

[1] http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_problem

[2] http://crypto.stanford.edu/~dabo/abstracts/DDH.html

[3] http://cseweb.ucsd.edu/~cdcash/dh.pdf


You can check for contributions to this problem on the solutions page.



This web site developed and maintained by

Tim S Roberts

Email: timro21@gmail.com