Given a published key ($ n $, $ e $) and a known encrypted message $ c \equiv m^e \pmod $ and that $ p $ and $ q $ are close $ q < p < 2q $, then by calculating approximations of $ n/e $ using continued fractions, it is possible to find the value of $ p $ and $ q $ and therefore the value of $ d $. By calculating the GCD of 2 keys, if the value found is different from 1, then the GCD is a first factor of $ n $ (therefore $ p $ or $ q $), by dividing $ n $ by the gcd is the second factor ($ p $ or $ q $). Key generation is random but it is not unlikely that a factor $ p $ (or $ q $) could be used to calculate the values of 2 different public keys $ n $. Method 2: Find the common factor to several public keys $ n $ With $ p $ and $ q $ the private key $ d $ can be calculated and the messages can be deciphered. a key $ n $ comprising less than 30 digits (for current algorithms and computers), between 30 and 100 digits, counting several minutes or hours, and beyond, calculation can take several years. In practice, this decomposition is only possible for small values, i.e. To find the private key, a hacker must be able to perform the prime factorization of the number $ n $ to find its 2 factors $ p $ and $ q $. The RSA cipher is based on the assumption that it is not possible to quickly find the values $ p $ and $ q $, which is why the value $ n $ is public. Method 1: Prime numbers factorization of $ n $ to find $ p $ and $ q $.
