1
$\begingroup$

Provided some modulus for RSA 2048, is there a way I could look up if

  • the modulus
  • and their factors

exists online?

$\endgroup$
1
$\begingroup$

TL;DR

It's not possible, because there are way too many prime numbers.

It's possible that there might be a database with some of these numbers, but not a database with all the possible numbers. There are just way too many prime numbers to fit them all in one database.


How many 1024-bit prime numbers are there?

To get a 2048-bit modulus you multiply two 1024-bit prime numbers together. Using $$\frac{n}{\ln(n)}$$ we can estimate the amount of prime numbers with the length of 1024-bits. The amount of 1024-bit numbers is $2^{1023} - 1$.

$$2^{1023} - 1 \approx 8.9 \times 10^{307}$$

We then apply the approximation:

$$\frac{8.9 \times 10^{307}}{\ln(8.9 \times 10^{307})} \approx 1.25 \times 10^{305}$$

We now have an approximation of how many 1024-bit prime numbers there are.


How large is the database?

If you want to put them all in a database you just have to calculate the number of these primes multiplied with their size (which is of course 1024-bits). That gives you the size of your database in bits:

$$1024 \times 1.25 \times 10^{305} \approx 1.28 \times 10^{308}$$

So as you can see this database would be way too large and it wouldn't be practical to even try to fit them in any database.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think it is not about the size or possibility of such a database. One can just collect modulus from servers. And some researchers did that. Or, maybe not. We need clarifications. $\endgroup$ – kelalaka Nov 1 '19 at 9:25
  • $\begingroup$ Thank you for this explanation. It makes sense that it would be infeasible to store all such values. For my purposes I wanted to see if there was a way to find the factors for some notable numbers, factordb.com/index.php did the trick. $\endgroup$ – averma Nov 1 '19 at 9:50
  • 2
    $\begingroup$ Kidding: It is debatable that storing a 1024-bit prime requires 1024 bits. For a start its bits 0 and 1023 are set, which saves 2 bits. More generally it is not divisible by small primes, and that can save a few more bits (3 considering primes to 7879). Start to use extreme similarity of high-order bits with neighboring primes for huge savings. The sky is the limit: in the end, we virtually store that whole database with a primality testing program, and fast direct access is possible with a relatively small cache. $\endgroup$ – fgrieu Nov 1 '19 at 12:55
  • 2
    $\begingroup$ Also, you included the primes less than 1024-bit. $\endgroup$ – kelalaka Nov 1 '19 at 13:07
  • $\begingroup$ Actually, the number of 1024-bit integers is precisely $2^{1023}$. $\endgroup$ – fgrieu Nov 1 '19 at 13:26
0
$\begingroup$

There have been several services that scanned the internet for common factors in public RSA moduli—from TLS certificates, from OpenPGP certificates on the key servers, from SSH host keys—to which you could submit your own modulus to check it against them. Of the three such services I can remember, only one seems to be still functioning and findable on the intarwebs:

How does this work? Factoring is hard, isn't it? Well, finding the uniform random 1024-bit primes $p$ and $q$ given $pq$ is hard, but finding $q$ given $pq$ and $qr$ is easy: $q = \gcd(pq, qr)$, which you can compute with the Euclidean algorithm with a few thousand arithmetic operations at most. Even better, you can perform a batch GCD on $k$ different moduli much more cheaply than with $O(k^2)$ pairwise GCD computations.

Normally, the space of (say) 1024-bit primes is so staggeringly huge that nobody will ever choose the same primes,* but broken random number generators—such as on embedded devices with no entropy sources, or on decade-old Debian systems—might accidentally search the same narrow subset of primes on many devices.

In 2012, two research groups at the same time apparently independently realized that you could do this, and did it (finding lots of common factors on the internet!), and came up with a cutesy title for it:


* There are over $2^{1000}$ primes between $2^{1023}$ and $2^{1024}$ by the prime-counting approximation $\pi(x) \approx x/\!\log x$, giving $\pi(2^{1024}) - \pi(2^{1023}) \approx 2^{1014} - 2^{1013} = 2^{1013}$. In fact, it is even safe to compress keys (§10) by narrowing the space of primes dramatically to share about 2/3 of their bits.

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