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