Hi there,
I have looked at the RSA protocol a bit and have concluded that
1) common factors in (p-1) and (q-1) are also in the factorisation of (p*q-1).
2) by factoring (p*q-1) you can come up with candidates for squares in
the totient.
3) you can also come up with d mod commonfactor^2 if there is a common factor.
the math is shown in my wikipedia users page math blog at:
https://en.wikipedia.org/wiki/User:Endo999#The_Bad_Stuff_That_Happens_When_There_Are_Common_Factors_Between_.28P-1.29_and_.28Q-1.29
I have looked at your latest source to see if you have a possible
common factor for (p-1) and (q-1) in your RSA key generation code.
I have concluded, after a quick look, that you may when you are not
using SAFE mode to generate the keys.
When keys are generated using SAFE mode then (p-1)/2 must be a prime.
As the factorisation of p-1==2*prime and there are checks to make sure
that p and q are not the same, then you cannot have a common factor in
p-1 and q-1 besides 2.
The code in rsa_builtin_keygen() does not use safe mode when
generating keys using
BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb). There are
tests for these primes, but there does not seem to be an explicit
check that there are no common factors in (p-1) and (q-1) besides 2 or
3.
The authors of the code may well correct me here since I have just
quickly looked at it.
A quick check for this condition with BN_GCD(p-1,q-1)>3 in
rsa_builtin_keygen() would detect any problems and avoid the possible
leaking of part of the totient.
I admit that it is unlikely that a large enough part of the totient
would be revealed (when a truely random generator is used) to endanger
the RSA pair, but I think it is a bit of housekeeping that knowledge
of even small factors (besides 2 and 3) are kept out of the attackers
hands.
Thank You
Paul Cheffers
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
