UNSOLVED PROBLEMS

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, p^a mod g and p^b mod g, freely known to all.  They therefore immediately have a shared key p^ab mod g (which Alice can compute by raising Bob’s public key to the a^th power, and Bob can compute by raising Alice’s public key to the b^th 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, p^a mod g and p^b 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