It's easy to create an RSA modulus where almost no one knows the factors: for example, I can generate two 1024-bit primes $p$ and $q$ and set $n=pq$. If I publish $n$, I will be the only person in the world who knows, or can know, $p$ and $q$.
The (now defunct) RSA Factoring Challenge numbers were generated like this:
- First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port.
- The random bytes were used as the seed values for the B_GenerateKeyPair function, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion was exported, in DER format to a disk file.
- The moduli were extracted from the DER files and converted to decimal for posting on the Web page.
- The laptop's hard drive was destroyed.
But all of this leaves me feeling unsatisfied because--despite claims that the laptop's hard drive was destroyed--I still worry about insiders who know the factors.
Is there a method which can generate an RSA modulus so that no one knows the factors? This might seem a ridiculous question, but we do know composites of unknown factorization. For example, many of the largest Mersenne composites have unknown factorizations (wikipedia).
I would be fine with a multi-party algorithm and an assumption that players do not collaborate.