From dawagner@phoenix.princeton.edu Fri Feb 24 11:29:10 EST 1995
Article: 32673 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!phoenix.princeton.edu!dawagner
From: dawagner@phoenix.princeton.edu (David A. Wagner)
Subject: Diffie-Hellman: Uniform Security?
Message-ID: <1995Feb24.105453.27885@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: phoenix.princeton.edu
Organization: Princeton University
Date: Fri, 24 Feb 1995 10:54:53 GMT
Lines: 26

The discrete log problem has this nice feature of being
uniformly difficult to solve, no matter which base you use.
[Proof below.]

How about the problem of breaking Diffie-Hellman: does it
too have this nice property?

In other words, suppose I have an algorithm for breaking
Diffie-Hellman with base 3 and modulus p; but you use base 5
and modulus p.  Can I adapt my algorithm to break your key
exchange?



Proof of uniform difficulty of discrete logs:

Suppose I can compute discrete logs in Z/pZ to base g.
Then I can compute the discrete log of y to base h, too:

Find x such that g^x = y mod p and a such that g^a = h mod p.
Let z = x a^{-1} mod p-1.  Then

h^z = g^(a x a^{-1} mod p-1) = g^x = y mod p.

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu