Proven Primes

[Tero Kivinen]

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.]
-- 
kivinen at ssh.fi
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 majordomo at wasabisystems.com