Re: diffie-hellman subject to an easy brute-force attack?

srt_at_nospam.unt.edu
Date: 07/09/03 

Date: Wed, 9 Jul 2003 00:13:38 +0000 (UTC)

Eric Lee Green <eric@badtux.org> wrote:

>> Therefore, there's no way the random (private) "x" values can be
>> large, if "g" is large. I suppose that the Diffie-hellman key
>> exchange should to happen within fractions of a second -- for this to
>> occur, "x" must be very, very small.

> No, typically g is very small, for exactly that reason.

???? Why in the world would either g or x have to be small? I can
raise a 1024-bit g to a 1024-bit power x, modulo a 1024-bit p, in a
matter of milliseconds....

To the original poster -- x should *not* be small. If your prime
modulus p is 1024 bits long, you should use a number that is randomly
chosen from the full range 1..p-1 -- which will almost certainly have
over 1000 significant bits. And you clearly can't brute-force that... 

-- 
Steve Tate - srt[At]cs.unt.edu | "A computer lets you make more mistakes faster
Dept. of Computer Sciences     | than any invention in human history with the
University of North Texas      | possible exceptions of handguns and tequila."
Denton, TX  76201              |         -- Mitch Ratliffe, April 1992
Quantcast