2

Assignment: Assume $p$ and $q$ are approximately of the same size (p 1000 digits and q 1001 digits), argue for or against if its easy to solve RSA-problem using Pollard's $p-1$ factorization method

Against: First we note that if $p$ and $q$ is of approximately the same size, we have chosen them in the most secure way, since its not easier to find either of them. And note that the larger the number the higher the probability is that the number is not a factor of small primes, so since $p$ and $q$ are as large as they are, we may not be able to use Pollar's $p-1$ fac. method.

For: Pollard's $p-1$ method works fast and good if $p-1$ or $q-1$ is a product of small primes. So IF $p-1$ OR $q-1$ are a product of small primes then its easy to solve the RSA-problem using this method. This is because: Assume $p-1$ is a product of small primes. Then $p-1|n!$ for not a too large n. Then its high probability that $p|a^{n!}-1$, since $a^{n!}=a^{(p-1)k}=1$ mod $p$. This also means that $q\not | a^{n!}-1$. So for most choices of a we get a factor of N: $p=$gcd$(a^{n!}-1,N)$.

Is this a true argument? Or have I missed something?

Linelina
  • 205
  • 1
    Your arguments are valid. Note that $p$ and $q$ usually have the same number of digits. Of course we have to be careful that the primes are safe with respect to several kinds of properties or attacking strategies. Of course, we can also choose $q$ to have one digit more than $p$, it does not really make a difference. – Peter Mar 15 '20 at 12:54
  • 1
    If we choose $p$ and $q$ randomly, the danger that the p-1-method can break the code, is very small. – Peter Mar 15 '20 at 12:57
  • 2
    If $p$ and $q$ are really close to each other, then it is rather Fermat factorization that may succeed, I guess – Hagen von Eitzen Mar 15 '20 at 12:57
  • 1
    @HagenvonEitzen Yes, if they are extremely close. Or if one is almost a multiple of the other, some slight variations could find them. – Peter Mar 15 '20 at 12:58
  • 1
    By the way, if the given number is large enough, we can even choose it to have $3$ or even more factors. The ECM-method has an extremely small chance to find a 100+ digit prime factor. And RSA is neither faster if there are more than $2$ prime factors. The usual choice is however $2$ factors and the number of digits is usually the same. – Peter Mar 15 '20 at 13:06
  • https://math.stackexchange.com/questions/3581800/p-and-q-are-safe-primes-and-with-1000-digits-argue-for-or-against-if-its-easy-o – Peter Mar 15 '20 at 14:04
  • Thanks to both of you! – Linelina Mar 15 '20 at 15:42

0 Answers0