Refactor generation of candidate integers in primegen.

I've replaced the random number generation and small delta-finding
loop in primegen() with a much more elaborate system in its own source
file, with unit tests and everything.

Immediate benefits:

 - fixes a theoretical possibility of overflowing the target number of
   bits, if the random number was so close to the top of the range
   that the addition of delta * factor pushed it over. However, this
   only happened with negligible probability.

 - fixes a directional bias in delta-finding. The previous code
   incremented the number repeatedly until it found a value coprime to
   all the right things, which meant that a prime preceded by a
   particularly long sequence of numbers with tiny factors was more
   likely to be chosen. Now we select candidate delta values at
   random, that bias should be eliminated.

 - changes the semantics of the outermost primegen() function to make
   them easier to use, because now the caller specifies the 'bits' and
   'firstbits' values for the actual returned prime, rather than
   having to account for the factor you're multiplying it by in DSA.
   DSA client code is correspondingly adjusted.

Future benefits:

 - having the candidate generation in a separate function makes it
   easy to reuse in alternative prime generation strategies

 - the available constraints support applications such as Maurer's
   algorithm for generating provable primes, or strong primes for RSA
   in which both p-1 and p+1 have a large factor. So those become
   things we could experiment with in future.

1 files changed, 52 insertions, 1 deletions

diff --git a/sshkeygen.h b/sshkeygen.h
index 89b1a243..f5af2a10 100644
--- a/sshkeygen.h
+++ b/sshkeygen.h
@@ -2,7 +2,7 @@
  * sshkeygen.h: routines used internally to key generation.
  */
 
-/*
+/* ----------------------------------------------------------------------
  * A table of all the primes that fit in a 16-bit integer. Call
  * init_primes_array to make sure it's been initialised.
  */
@@ -10,3 +10,54 @@
 #define NSMALLPRIMES 6542 /* number of primes < 65536 */
 extern const unsigned short *const smallprimes;
 void init_smallprimes(void);
+
+/* ----------------------------------------------------------------------
+ * A system for making up random candidate integers during prime
+ * generation. This unconditionally ensures that the numbers have the
+ * right number of bits and are not divisible by any prime in the
+ * smallprimes[] array above. It can also impose further constraints,
+ * as documented below.
+ */
+typedef struct PrimeCandidateSource PrimeCandidateSource;
+
+/*
+ * pcs_new: you say how many bits you want the prime to have (with the
+ * usual semantics that an n-bit number is in the range [2^{n-1},2^n))
+ * and also specify what you want its topmost 'nfirst' bits to be.
+ *
+ * (The 'first' system is used for RSA keys, where you need to arrange
+ * that the product of your two primes is in a more tightly
+ * constrained range than the factor of 4 you'd get by just generating
+ * two (n/2)-bit primes and multiplying them. Any application that
+ * doesn't need that can simply specify first = nfirst = 1.)
+ */
+PrimeCandidateSource *pcs_new(unsigned bits, unsigned first, unsigned nfirst);
+
+/* Insist that generated numbers must be congruent to 'res' mod 'mod' */
+void pcs_require_residue(PrimeCandidateSource *s, mp_int *mod, mp_int *res);
+
+/* Convenience wrapper for the common case where res = 1 */
+void pcs_require_residue_1(PrimeCandidateSource *s, mp_int *mod);
+
+/* Insist that generated numbers must _not_ be congruent to 'res' mod
+ * 'mod'. This is used to avoid being 1 mod the RSA public exponent,
+ * which is small, so it only needs ordinary integer parameters. */
+void pcs_avoid_residue_small(PrimeCandidateSource *s,
+                             unsigned mod, unsigned res);
+
+/* Prepare a PrimeCandidateSource to actually generate numbers. This
+ * function does last-minute computation that has to be delayed until
+ * all constraints have been input. */
+void pcs_ready(PrimeCandidateSource *s);
+
+/* Actually generate a candidate integer. You must free the result, of
+ * course. */
+mp_int *pcs_generate(PrimeCandidateSource *s);
+
+/* Free a PrimeCandidateSource. */
+void pcs_free(PrimeCandidateSource *s);
+
+/* Return some internal fields of the PCS. Used by testcrypt for
+ * unit-testing this system. */
+void pcs_inspect(PrimeCandidateSource *pcs, mp_int **limit_out,
+                 mp_int **factor_out, mp_int **addend_out);