1

Question: p and q are safe primes and with 1000 digits. Argue for or against if its easy on a Laptop to solve RSA-problem using Fermat's factorization method.

Answer:

First note that when p and q are approximately of the same size, the have the most secure scenario. Using Fermat's method: Find $(⌊\sqrt{N}⌋+i)^2-N=j^2$ for $i=1,2,3,...$. Then we check if gcd$(i-j,N)$ nontrivial. If $p=2a+1$ and $q=2b+1$, if a and b are primes, we get for some i that gives us a square j: gcd$(i-\sqrt{(⌊\sqrt{(2a+1)(2b+1)}⌋+i)^2-(2a+1)(2b+1)},(2a+1)(2b+1))$

What can I get from this?

Linelina
  • 205
  • 3
    It should be obvious that it is supposed to be hard. Otherwise RSA would be broken. You need to show there are so many choices you can't try a reasonable fraction of them. – Ross Millikan Mar 15 '20 at 13:39
  • 3
    You asked a very similar question, where it was mentioned that Fermat only works in practice if the primes are extremely close to each other. This is almost impossible , if we choose them randomly. Of course, eventually Fermat would also work in the other cases, but it would take far too long. – Peter Mar 15 '20 at 14:03
  • 2
    To make RSA secure, we do not need that $p$ and $q$ have the same number of digits , although this is usually the case. As you mentioned in the link question, we could choose $q$ to have one more digit than $p$. In this case, Fermats method would be utterly useless in practice. But even if the primes have the same number of digits, they need not to be "close" to each other. – Peter Mar 15 '20 at 14:10
  • Thankss @Peter! – Linelina Mar 15 '20 at 15:46
  • How can I do that? @RossMillikan I would like to be able to argue for too – Linelina Mar 15 '20 at 15:46
  • You base it on how many $1000$ digit numbers there are. Roughly how far apart would you expect $p$ and $q$ to be? Certainly not within $10^{100}$ of each other. That is just too many to try. – Ross Millikan Mar 15 '20 at 18:15

0 Answers0