Hi Mancha,
Since p*q-1==(p-1)*(q-1)+(p-1)+q-1) any prime that divides (p-1) and
(q-1) will divide all 4 of the terms in the definition of p*q-1. Thus
it will be a common factor in the totient.
I have checked through the key generation code of the openssl ssl
code. I hacked it to report the greatest common divisor of p-1 and
q-1. I then ran 100 key generations. It only had greatest common
divisors of 2, 4 , 8, and 16. There were no other primes reported
besides small powers of 2.
So there doesn't seem to be a practical problem with common divisors
in the openssl code.
Still, I think this is a theoretical problem. There should be a
gcd(p-1,q-1)>16 check for the two primes in key generation.
Paul
Quoting mancha <manc...@zoho.com>:
On Fri, Jul 31, 2015 at 02:36:03AM +0000, p...@securecottage.com wrote:
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
[SNIP]
Hi. How are you finding a common factor f such that f|(p-1) and f|(q-1)?
Thanks.
--mancha
-- https://twitter.com/mancha140
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
