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

*To*: [email protected]*Subject*: Re: D-H key exchange - how does it work?*From*: Hal <[email protected]>*Date*: Thu, 19 May 1994 21:01:06 -0700*Sender*: [email protected]

The problem with "strong" primes, primes for which (p-1)/2 is prime, is that they are hard to find. 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. They may need a dedicated prime-searching machine to do that. (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.) It's much easier to find a "strongish" prime, one for which (p-1)/k is prime, where k is on the order of 100 or so. Take your prime q in the above and try kq+1 for k=2,4,6,.... This only takes a few minutes after you find q. The question is, how good are strongish primes? What fraction of elements of the group will have short periods, given that p-1 has a pretty small number of prime factors? Also, given a strong or strongish prime, are the chances that g^x has a small period good enough that it makes sense to check for that case? Any event whose chances are smaller than your computer making a mistake is generally not worth checking for. Hal

**Follow-Ups**:**D-H key exchange - how does it work?***From:*[email protected] (Eric Hughes)

- Prev by Date:
**WNSTORM UPDATE (STEGO RND CRYPT)** - Next by Date:
**Crypto-history** - Prev by thread:
**Re: D-H key exchange - how does it work?** - Next by thread:
**D-H key exchange - how does it work?** - Index(es):