Distribution based integer factorization

Question

The past week I've been looking into - and playing with - algorithms for factoring RSA moduli.

From what I understand, it's important that the primes p and q are of the same magnitude as the square root of N, but they shouldn’t be too close. To find out how close p and q are to sqrt(N) in the real world, I've used OpenSSL to generate a bunch of numbers.

The following image shows a graph. The x-axis shows N, the modulus. The y-axis shows how far p is from the square root of N, in percentage. This graph shows values for 5000 128-bit RSA moduli.

What I find interesting about this graph is that if a 128-bit modulus starts with "20...", I know that p can not be further than 2 percent from the square root of N.

Do algorithms exist that make use of such distributions? What would be the best attack if I know in what range p is located?

Update

If anyone wants to replicate the graph or check for errors in my code, here is the code used for generating OpenSSL N,p,q pairs:

from os import system
import re

def tardReplace(reg,data):
    n = reg.findall(data)[0]
    n = n.replace("\n","").replace("\r","").replace(":","").replace(" ","").replace("\t","")
    return int(n,16)


modDict = {}
genBits = 128
genAmount = 5000

fileName = "generated/" + str(genBits) + "bitRSA" + str(genAmount)
outf = open(fileName + ".txt", "w")


for i in range(genAmount):
    system("openssl genrsa -out foo.key " + str(genBits) + "; openssl rsa -text -in foo.key > values.txt")
    with open('values.txt','r') as f:
        data = f.read()

    if genBits <= 64:
        modReg = re.compile("modulus: ([0-9]+) ")
        mod = modReg.findall(data)[0]
    else:
        modReg = re.compile("modulus:([ \n\r\t0-9a-f:]+)publicExponent")
        mod = tardReplace(modReg, data)

    if genBits <= 128:
        prime1Reg = re.compile("prime1: ([0-9]+) ")
        prime1 = prime1Reg.findall(data)[0]
        prime2Reg = re.compile("prime2: ([0-9]+) ")
        prime2 = prime2Reg.findall(data)[0]
    else:
        prime1Reg = re.compile("prime1:([ \n\r\t0-9a-f:]+)prime2")
        prime1 = tardReplace(prime1Reg, data)

        prime2Reg = re.compile("prime2:([ \n\r\t0-9a-f:]+)exponent1")
        prime2 = tardReplace(prime2Reg, data)

    outf.write(str(mod) + "," + str(prime1) + "," + str(prime2) + "\n")

outf.close()

system("sort " + fileName + ".txt > " + fileName + ".sorted.txt")

And here is the code for making the graph:

import matplotlib.pyplot as plt


with open('../../rsaGen/generated/128bitRSA5000.sorted.txt','r') as f:
    data = f.read().split('\n')

x = []; y = []


for line in data:
    if line == '':  continue
    n,p,q = line.split(',')
    n = int(n);     p = int(p);     q = int(q)
    p = min(p,q)

    sqrtn = n ** 0.5
    diff = sqrtn - p
    percent = (diff/sqrtn)*100

    x.append(n)
    y.append(percent)

plt.scatter(x, y)
plt.show()

Answer 1

The archetypal algorithms that could take advantage of $p$ being close to the square root of $N=pq$ is Fermat's factorization method; and some improvements thereof.

The basic Fermat factoring method makes about $(p+q)/2-\sqrt N$ steps. Applied to $N\approx 2^{127}$ and $p/\sqrt N\approx 0.98$ (as in the question) this is over $2^{51}$ steps. We have heuristic algorithms to factor any 128-bit RSA moduli much faster than that, and nearly as simple (e.g. Pollard's Rho), thus the method is worthless in practice even at the 128-bit level; that only gets worse when we increase the modulus to practical sizes, and compare to more powerful factorization algorithms.

There are improvements of the Fermat factoring method that still benefit from $p$ being close to the square root of $N$. They reduce the number of steps, by skipping most candidates, and performing table lookups rather than squareness tests. The gain is large, but severely bounded by available memory, and is not enough to become competitive at least for $N>2^{1023}$ and $|p-q|>2^{\lceil\log_2N\rceil/2-100}$ (the criteria in FIPS 186-4, with origin in ANSI X9.31:1988, that has plenty of headroom), which has overwhelming odds to be verified for random $p$ and $q$.