I'd like to thank several people for looking into my assertion that it
is possible for common factors in p-1 and q-1 to leak from the
factorisation of n-1.
Particularly, Viktor Dukhovni, for trying tens of thousands of key
generation iterations to see if common factors are possible. From
Viktor's work and other people's comments I drew the following
conclusions:
Viktor Dukhovni reports, after looking at the rsa key generation code
of openssl, that p-1 and q-1 are both checked for the first 2048
factors (up to 17863). As such such low primes are not possible as
factors of either p-1 or q-1. However, common factors higher than
17863 are possible as factors of both p-1 and q-1. But it takes
20,000 key generations (not in safe mode) before such an event
happens. He managed to get a common factor of gcd(p-1,q-1) = 2 * 28559
from the following 1024 bit rsa generated key (factorisation of p*q-1
is shown):
n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *
5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628 67234233761906471233193768567784328338581360170038166729050302672416075037390699071355182394190448204086007354388034161296410061846686501
4941425056336718955019
Any rsa key generation in SAFE mode will always have a gcd(p-1,q-1)=2,
so SAFE mode always avoids common factors.
My conclusion is that openssl code can have common factors (must be
above 17863) in its rsa keys every 20,000 key generations or so when
not generated in SAFE mode, and that at this time approximately 30
bits of the totient will be revealed out of the 1024 bits of the full
totient. There is, of course, no way of knowing which of the 20,000
key generations will have the common factors.
Most people felt that the check (for gcd(p-1,q-1)> 16) was possible
but they were not sure it was worth doing.
I'd like to point out from a cyber-attack possibility the check is
worth doing. In RSA_generate_key_ex() in rsa_gen.c the following code
is seen:
int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
{
#ifdef OPENSSL_FIPS
if (FIPS_mode() && !(rsa->meth->flags & RSA_FLAG_FIPS_METHOD)
&& !(rsa->flags & RSA_FLAG_NON_FIPS_ALLOW)) {
RSAerr(RSA_F_RSA_GENERATE_KEY_EX, RSA_R_NON_FIPS_RSA_METHOD);
return 0;
}
#endif
if (rsa->meth->rsa_keygen)
return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);
#ifdef OPENSSL_FIPS
if (FIPS_mode())
return FIPS_rsa_generate_key_ex(rsa, bits, e_value, cb);
#endif
return rsa_builtin_keygen(rsa, bits, e_value, cb);
}
Third party modules, or methods, can be added to openssl code and
these can do the rsa key generation as in:
if (rsa->meth->rsa_keygen)
return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);
As such it is appropriate that some checks be made at
RSA_generate_key_ex() to make sure that the other software hasn't
returned a bad key. Openssl software is a significant part of the
Internet security infastructure and so it would obviously be the
target of hacking and cyber infiltration. Some redundant checks are
appropriate because of this.
A gcd(p-1,q-1)>16 check will disallow less than 1 percent of the
currently acceptable keys, won't take much time to run, and would
defeat cyber attempts to create a key with a significant common factor
within it.
Thanks
Paul Cheffers
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
