5
$\begingroup$

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.

5000 128-bit RSA moduli generated by OpenSSL

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()
Improve this question
$\endgroup$
3
  • $\begingroup$ that's a nice pyramid :) How can I actually read the x-axis? $\endgroup$ – SEJPM♦ Sep 12 '15 at 21:43
  • $\begingroup$ The x-axis shows the modulus. Take the following page for example: fastlizard4.org/wiki/The_Great_Factoring_Challenge#128-bit_RSA The modulus generated there is: 308162938443467880757692372610071660661 This modulus starts with 30... In the graph, you can see that this means that p must be within 6 percent of sqrt(N). $\endgroup$ – Beurtschipper Sep 12 '15 at 22:08
  • 2
    $\begingroup$ The reason for that pyramid is most likely, that you choose primes with a fixed number of bits. A more common assumption is that $p<q<2p$, and in that case the most extreme possible case is $q\approx 2p$, which results in $n\approx 2p^2 \Rightarrow \sqrt{n}\approx \sqrt{2} p$, so that $\sqrt{n} / p \approx \sqrt{2}$. Thus you have an upper bound of roughly "41.4%", or if you consider the smaller prime, that's "29.3%" below. Btw, due to the well-known Fermat factorization, many RSA generators check that the numbers have a minimum distance. $\endgroup$ – tylo Sep 14 '15 at 12:38
8
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.