RSA generation: option to generate strong primes.

A 'strong' prime, as defined by the Handbook of Applied Cryptography,
is a prime p such that each of p-1 and p+1 has a large prime factor,
and that the large factor q of p-1 is such that q-1 in turn _also_ has
a large prime factor.

HoAC says that making your RSA key using primes of this form defeats
some factoring algorithms - but there are other faster algorithms to
which it makes no difference. So this is probably not a useful
precaution in practice. However, it has been recommended in the past
by some official standards, and it's easy to implement given the new
general facility in PrimeCandidateSource that lets you ask for your
prime to satisfy an arbitrary modular congruence. (And HoAC also says
there's no particular reason _not_ to use strong primes.) So I provide
it as an option, just in case anyone wants to select it.

The change to the key generation algorithm is entirely in sshrsag.c,
and is neatly independent of the prime-generation system in use. If
you're using Maurer provable prime generation, then the known factor q
of p-1 can be used to help certify p, and the one for q-1 to help with
q in turn; if you switch to probabilistic prime generation then you
still get an RSA key with the right structure, except that every time
the definition says 'prime factor' you just append '(probably)'.

(The probabilistic version of this procedure is described as 'Gordon's
algorithm' in HoAC section 4.4.2.)

1 files changed, 2 insertions, 2 deletions

diff --git a/sshkeygen.h b/sshkeygen.h
index 0f0df587..971a3633 100644
--- a/sshkeygen.h
+++ b/sshkeygen.h
@@ -284,8 +284,8 @@ extern const PrimeGenerationPolicy primegen_provable_maurer_complex;
  * The overall top-level API for generating entire key pairs.
  */
 
-int rsa_generate(RSAKey *key, int bits, PrimeGenerationContext *pgc,
-                 ProgressReceiver *prog);
+int rsa_generate(RSAKey *key, int bits, bool strong,
+                 PrimeGenerationContext *pgc, ProgressReceiver *prog);
 int dsa_generate(struct dss_key *key, int bits, PrimeGenerationContext *pgc,
                  ProgressReceiver *prog);
 int ecdsa_generate(struct ecdsa_key *key, int bits);