Recover RSA primes p, q for |p – q| sufficiently small

Let s = sqrt(pq). Assume p ≤ q.

Starting from s, find the smallest prime k ≥ s.

Since q – p is small, q – s is small also. So pk is close to pq, i.e. pq – pk is small.

Starting from pq, since k is prime, exactly one n{a, a + 1, a + 2, …, a + k – 1 = pq} is not coprime with k. Using the method found here, n = a + (-a mod k) .

Let d = gcd(n, pq). If d > 1 then d = p. Otherwise choose the next k consecutive numbers less than a and repeat.

Runnable code in the Frink language:

p = 96436875510168134260978951531720215975911176926194651907111357743104310827706384687021784900521146900897417521181
q = 96436875510168134260978951531720215975911176926194651907111357743104310827706384687021784900521146900897417697981

if isPrime[p]
  println["p is prime"]
if isPrime[q]
  println["q is prime"]

println["prime difference:"]
println[q - p]

mysqrt[n] :=
{
  b = bitLength[n]
  m = 0
  i = ceil[b/2] - 1
  while i >= 0
  {
     if (m+2^i)^2 <= n
       m = m + 2^i
     i = i - 1
  }
  return m
}

pq = p * q
s = mysqrt[pq]
if s^2 <= pq && (s+1)^2 > pq
  println["sqrt function works"]
else
  println["wtf"]
k = nextPrime[s - 1]
println["prime between q and s:"]
println[k]
println["prime, sqrt difference:"]
println[k - s]
i = pq - k + 1
do
{
  n = i + (-i % k)
  d = gcd[n,pq]
  if d > 1
  {
    println["good"]
    break
  }
  i = i - k
} while i >= s
Advertisements