tom st denis writes: > 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a439dffffffffffffffff > What is the benefit of having leading/trailing bits fixed?
Those primes are generated using the rules defined in the RFC 2412. > As far as I know it doesn't make any form of index calculus attack > any harder to apply. High order bits makes classical remainder algorithms faster, and low order bits helps the Mongomery-style algoritms. >From the RFC 2412: ---------------------------------------------------------------------- Classical Diffie-Hellman Modular Exponentiation Groups The primes for groups 1 and 2 were selected to have certain properties. The high order 64 bits are forced to 1. This helps the classical remainder algorithm, because the trial quotient digit can always be taken as the high order word of the dividend, possibly +1. The low order 64 bits are forced to 1. This helps the Montgomery- style remainder algorithms, because the multiplier digit can always be taken to be the low order word of the dividend. The middle bits are taken from the binary expansion of pi. This guarantees that they are effectively random, while avoiding any suspicion that the primes have secretly been selected to be weak. Because both primes are based on pi, there is a large section of overlap in the hexadecimal representations of the two primes. The primes are chosen to be Sophie Germain primes (i.e., (P-1)/2 is also prime), to have the maximum strength against the square-root attack on the discrete logarithm problem. The starting trial numbers were repeatedly incremented by 2^64 until suitable primes were located. Because these two primes are congruent to 7 (mod 8), 2 is a quadratic residue of each prime. All powers of 2 will also be quadratic residues. This prevents an opponent from learning the low order bit of the Diffie-Hellman exponent (AKA the subgroup confinement problem). Using 2 as a generator is efficient for some modular exponentiation algorithms. [Note that 2 is technically not a generator in the number theory sense, because it omits half of the possible residues mod P. From a cryptographic viewpoint, this is a virtue.] -- [EMAIL PROTECTED] SSH Communications Security http://www.ssh.fi/ SSH IPSEC Toolkit http://www.ssh.fi/ipsec/ --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
