qsieve(1) [netbsd man page]

QSIEVE(1)						    BSD General Commands Manual 						 QSIEVE(1)

NAME

     qsieve, qsafe -- generate system moduli file

SYNOPSIS

     qsieve [megabytes bits [initial]]
     qsafe [trials [generator]]

DESCRIPTION

     The qsieve utility will list candidates for Sophie-Germaine primes (where q = (p-1)/2) to standard output.  The list is checked against small
     known primes (less than 2**30).  This step is both processor and memory intensive.

     The megabytes value sets a limit for the internal sieve buffer.  This should be small enough to remain entirely in memory.  Swap thrashing
     can increase the run time from hours to days or weeks!  When the megabytes value is zero (0), qsieve will select a default suitable for the
     bits.

     The bits value sets the length of the generated possible primes (typically 768, 1024, 1536, 2048, 3072, or 4096, although others can be used
     for variety).

     The optional initial value (hex) specifies the beginning of the search.  Otherwise, qsieve generates a randomly selected number.

     The qsafe utility will perform a Miller-Rabin primality test on the list of candidates (checking both q and p) from standard input.  The
     result is a list of so-call "safe" primes to standard output, suitable for use as Diffie-Hellman moduli.  This step is merely processor
     intensive.

     The trials value sets the number of Miller-Rabin interations (typically 16 to 128).

     The optional generator value (hex) limits testing to candidates with a specific generator (usually 2).  Otherwise, qsafe will test each can-
     didate and suggest a generator.

SEE ALSO

     moduli(5)

HISTORY

     These programs were originally developed for the Photuris project, and later the OpenSSH project.

BSD
								   July 28, 1997							       BSD

MODULI(5)						      BSD File Formats Manual							 MODULI(5)

NAME

     moduli -- system moduli file

DESCRIPTION

     The /etc/moduli file contains the system-wide Diffie-Hellman prime moduli for sshd(8).

     Each line in this file contains the following fields: Time, Type, Tests, Tries, Size, Generator, Modulus.	The fields are separated by white
     space (tab or blank).

     Time: yyyymmddhhmmss.  Specifies the system time that the line was appended to the file.  The value 00000000000000 means unknown (historic).

     Type: decimal.  Specifies the internal structure of the prime modulus.

	   0:	   unknown; often learned from peer during protocol operation, and saved for later analysis.
	   1:	   unstructured; a common large number.
	   2:	   safe (p = 2q + 1); meets basic structural requirements.
	   3:	   Schnorr.
	   4:	   Sophie-Germaine (q = (p-1)/2); usually generated in the process of testing safe or strong primes.
	   5:	   strong; useful for RSA public key generation.

     Tests: decimal (bit field).  Specifies the methods used in checking for primality.  Usually, more than one test is used.

	   0:	   not tested; often learned from peer during protocol operation, and saved for later analysis.
	   1:	   composite; failed one or more tests.  In this case, the highest bit specifies the test that failed.
	   2:	   sieve; checked for division by a range of smaller primes.
	   4:	   Miller-Rabin.
	   8:	   Jacobi.
	   16:	   Elliptic Curve.

     Tries: decimal.  Depends on the value of the highest valid Test bit, where the method specified is:

	   0:	   not tested (always zero).
	   1:	   composite (irrelevant).
	   2:	   sieve; number of primes sieved.  Commonly on the order of 32,000,000.
	   4:	   Miller-Rabin; number of M-R iterations.  Commonly on the order of 32 to 64.
	   8:	   Jacobi; unknown (always zero).
	   16:	   Elliptic Curve; unused (always zero).

     Size: decimal.  Specifies the number of the most significant bit (0 to M).

     Generator: hex string.  Specifies the best generator for a Diffie-Hellman exchange.  0 = unknown or variable, 2, 3, 5, etc.

     Modulus: hex string.  The prime modulus.

     The file should be searched for moduli that meet the appropriate Time, Size and Generator criteria.  When more than one meet the criteria,
     the selection should be weighted toward newer moduli, without completely disqualifying older moduli.

     Note that sshd(8) uses only the Size criteria and then selects a modulus at random if more than one meet the Size criteria.

FILES

     /etc/moduli

SEE ALSO

     qsieve(1), sshd(8)

HISTORY

     The moduli file appeared in OpenBSD 2.8 and NetBSD 1.6.

BSD
								 February 7, 2005							       BSD