When $p$ and $q$ are Close

Suppose that $p$ and $q$ are ``close'' to each other. Then it is easy to factor $n$ using a factorization method of Fermat called the Fermat factorization method.

Suppose $n=pq$ with $p>q$ , say. Then

$$n = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2.$$

Since $p$ and $q$ are ``close'',

$$s = \frac{p-q}{2}$$

is small,

$$t = \frac{p+q}{2}$$

is only slightly larger than $\sqrt{n}$ , and $t^2-n=s^2$ is a perfect square. So we just try

$$t = \lceil\sqrt{n}\rceil, \quad t=\lceil\sqrt{n}\rceil+1, \quad t=\lceil\sqrt{n}\rceil+2, \ldots$$

until $t^2-n$ is a perfect square $s^2$ . (Here $\lceil x\rceil$ denotes the least integer $n\geq x$ .) Then

$$p = t+s,\qquad q=t-s.$$

Example 3.3   Suppose $n=23360947609$ . Then

$$\sqrt{n} = 152842.88\ldots.$$

If $t=152843$ , then $\sqrt{t^2-n} = 187.18\ldots$ .

If $t=152844$ , then $\sqrt{t^2-n} = 583.71\ldots$ .

If $t=152845$ , then $\sqrt{t^2-n} = 804\in\mathbb{Z}$ .

Thus $s=804$ . We find that $p=t+s=153649$ and $q=t-s=152041$ .

SAGE Example 3.3   We implement the above algorithm for factoring an RSA modulus $n=pq$ , when one of $p$ and $q$ is close to $\sqrt{n}$ .

sage: def crack_when_pq_close(n):
...    t = Integer(ceil(sqrt(n)))
...    while True:
...       k = t^2 - n
...       if k > 0:
...          s = Integer(int(round(sqrt(t^2 - n))))
...          if s^2 + n == t^2:
...             return t+s, t-s
... 
...       t += 1
...    
sage: crack_when_pq_close(23360947609)
(153649, 152041)

For example, you might think that choosing a random prime, and the next prime after would be a good idea, but instead it creates an easy-to-crack crpytosystem.

sage: p = next_prime(2^128); p
340282366920938463463374607431768211507
sage: q = next_prime(p)
sage: crack_when_pq_close(p*q)
(340282366920938463463374607431768211537, 
      340282366920938463463374607431768211507)