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

Question

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.

Answer 1

$$ p(p+2) = p^2 + 2p = (p+1)^2 - 1 $$

Fermat's method is to test the squares just above the target number, then see if the difference is a square... For twin primes, the very first square tried gives the answer

Answer 2

$$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)$.

Answer 3

If $n$ is known to be the product of a pair of twin primes ($p$ and $p+2$), than $$n=p(p+2)= p^2+2p = (p+1)^2 +1$$

Given $n$ we just compute $p=\sqrt{n-1}-1$ (standard real number square root, easily found) and have our factors $p, p+2$.

The system would be broken in a single, easy step. Other answers have already explained the link to Fermat's method.