[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: D-H key exchange - how does it work?*From*: [email protected] (Eric Hughes)*Date*: Fri, 20 May 94 08:02:57 -0700*In-Reply-To*: Hal's message of Thu, 19 May 1994 21:01:06 -0700 <[email protected]>*Sender*: [email protected]

It takes hours and hours of searching to find a 1024 bit strong prime on a workstation. Granted, you don't need to change very often perhaps, but some people would like to change every day. If they really want to change that often, they can buy a dedicated machine. There's no good cryptographic reason to change that often, if the modulus is large enough. In addition, changing the modulus can have unpleasant effects on traffic analysis, if not done properly. (The best way I know to find strong primes is to find a prime q and then check 2q+1 for primality. Finding 1024 bit primes takes a long time, and the chances that 2q+1 is prime is very low.) Well, there are faster ways. One can combine the sieve for q with a sieve for p. The biggest problem is that there are just a lot fewer primes with the above property. The question is, how good are strongish primes? Just fine. The complexity of taking discrete logs is dependent on the largest prime factor of the modulus. What fraction of elements of the group will have short periods, given that p-1 has a pretty small number of prime factors? If q is the largest prime factor, then about p/q will have short periods, namely, those divisible by q. When p=2q+1, there is one element of order 1 (namely 1), one element of order 2 (namely -1, aka 2q), and every other element has order 2q or q. For primes of the form p=kq+1, there are about k with short periods. Eric

**Follow-Ups**:**Re: D-H key exchange - how does it work?***From:*"Perry E. Metzger" <[email protected]>

**References**:

- Prev by Date:
**Re: Patent infringement (fwd)** - Next by Date:
**Re: Sternlight "kill" file** - Prev by thread:
**Re: D-H key exchange - how does it work?** - Next by thread:
**Re: D-H key exchange - how does it work?** - Index(es):