Cryptographic challenge solved by two German scientists! In 1989 I
offered $100US for the solution of a problem in computational number and
cryptography. At the time that I proposed it, I felt that it was unlikely to
be solved in the near term, but I wanted to make it just beyond what was
feasible at the time. This problem was recently solved by Damian Weber and
Thomas Denny, using the number field sieve.
The problem was to solve a Diffie-Hellman problem modulo the prime p, where
p = 2*739*q+1, and q=(7149-1)/6.
I tell you that there exist integer x and y such that
7y = 180162285287453102444782834836799895015967046695346697313025121734059953772058475958176910625380692101651848662362137934026803049
The problem is to compute 7xy (mod p).
The solution provided by Weber and Denny is to supply x, which is:
It is interesting to consider what lessons can be learned from such an
- At the time that I first proposed the Diffie-Hellman challenge,
microprocessor power was increasing rapidly, but it was pretty clear that this
alone offered little threat to the security of systems because it was
following a relatively predictable course of Moore's law as described in 1965.
A new technological breakthrough in something like quantum computing might
have changed things, but we have yet to see such a breakthrough.
- At the time that I first proposed the Diffie-Hellman challenge, the
number field sieve was unknown. Protecting against unknown algorithmic
advances is chancy at best, since it requires us to forecast something
we cannot possibly know. As it turned out, I chose a prime that was
relatively amenable to breaking by the number field sieve. I did this to
allow for an easy construction of a prime using the Cunningham tables of
factorization of numbers of the form an -1. The same
convenience that allowed me to easily derive the primality of the system
parameter was what led to the weakness against the number field sieve!
- Design of real-world cryptographic systems is largely a matter of educated
guesswork in the presence of human ignorance. It reaffirms the need for
further study to discover constructions with mathematically rigorous notions
- There are easier ways to make $100, but if these keys had been deployed
to protect monetary value in excess of $100, then the level of effort might
have been more easily justified. Weber and Denny pursued their prize for
the sake of pure scientific achievement, but it is wise to remember that
real adversaries in this world have other goals in mind.
Return to my home page
ps. The author claims an exemption from the minimum wage in offering this