Explain why we should not choose primes p and q that are too close together to form the modulus n in RSA cryptosystem.

For this question, I am trying to show that using a pair of primes p and q = p + 2 would be bad for RSA cryptosystem using Fermat's factorization method. I am new to this subject so any help would be appreciated. Thank you for your time.

Solution 1:

$$n = pq \tag{1}$$ $n$ is known $p$ and $q$ are not.

Let $p = \lfloor \sqrt{n} \rfloor - d \:and \: q = \lfloor \sqrt{n} \rfloor + e\tag{2}$ $d$ and $e$ are unknown, $ \lfloor \sqrt{n} \rfloor$ is easily calculated.

$$n = ({\lfloor \sqrt{n} \rfloor -d})({\lfloor \sqrt{n} \rfloor +e}) = {\lfloor \sqrt{n} \rfloor}^2 + {\lfloor \sqrt{n} \rfloor}(e - d) -ed \tag{3}$$

If $p,q$ are very close then $ed < \lfloor \sqrt{n} \rfloor $ then $(e-d) = \frac{n - {\lfloor \sqrt{n} \rfloor}^2}{{\lfloor \sqrt{n} \rfloor}}$, integer division.

With $(e-d)$ calculated $ed$ then $e$ and $d$ can be calculated.

If $ed > {\lfloor \sqrt{n} \rfloor}$ by a small factor then a small number of trials $k$ (i.e. millions or billions) could be tried with $e-d = \frac{n - {\lfloor \sqrt{n} \rfloor}^2}{{\lfloor \sqrt{n} \rfloor}} - k \tag{4}$

Again solving for $e$ and $d$ and thus $p$ and $q$ ,see $(2)$.