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()