From 844e766b03550c5e150af058b296791d5f6587be Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Mon, 2 Mar 2020 06:52:09 +0000 Subject: 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.) --- sshkeygen.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'sshkeygen.h') 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); -- cgit v1.2.3