Add qsieve and qsafe, two programs used for generating the moduli file.

These were written by William Allen Simpson and submitted in PR 21983,
and are added with minor adjustments and nits from christos@ and myself.

Approved by christos@ and groo@.

1 files changed, 117 insertions, 0 deletions

diff --git a/moduli/qsieve/qsieve.6 b/moduli/qsieve/qsieve.6
new file mode 100644
index 00000000..4279236d
--- /dev/null
+++ b/moduli/qsieve/qsieve.6
@@ -0,0 +1,117 @@
+.\"     $NetBSD: qsieve.6,v 1.1 2006/01/19 23:23:58 elad Exp $
+.\"
+.\" Copyright 1997, 2003 William Allen Simpson <wsimpson@greendragon.com>
+.\" All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\" 3. All advertising materials mentioning features or use of this software
+.\"    must display the following acknowledgement:
+.\"      This product includes software designed by William Allen Simpson.
+.\" 4. The name of the author may not be used to endorse or promote products
+.\"    derived from this software without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+.\"
+.\" Manual page, using -mandoc macros
+.\"
+.Dd July 28, 1997
+.Dt QSIEVE 1
+.Os
+.Sh NAME
+.Nm qsieve ,
+.Nm qsafe 
+.Nd generate system moduli file
+.Sh SYNOPSIS
+.Nm
+.Op Ar megabytes Ar bits Op Ar initial
+.br
+.Nm qsafe
+.Op Ar trials Op Ar generator
+.Sh DESCRIPTION
+The
+.Nm
+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.
+.Pp
+The 
+.Ar 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 
+.Ar megabytes
+value is zero (0),
+.Nm
+will select a default suitable for the
+.Ar bits .
+.Pp
+The
+.Ar 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).
+.Pp
+The optional
+.Ar initial
+value (hex)
+specifies the beginning of the search.
+Otherwise,
+.Nm
+generates a randomly selected number.
+.Pp
+The
+.Nm 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.
+.Pp
+The
+.Ar trials
+value
+sets the number of Miller-Rabin interations
+(typically 16 to 128). 
+.Pp
+The optional
+.Ar generator
+value (hex)
+limits testing to candidates with a specific generator
+(usually 2). 
+Otherwise,
+.Nm qsafe
+will test each candidate
+and suggest a generator.
+.Sh SEE ALSO
+.Xr moduli 5
+.Sh HISTORY
+These programs were originally developed for
+the Photuris project,
+and later
+the OpenSSH project.