How can I create an RSA modulus for which no one knows the factors?

Question

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:

1. First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port.
2. 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.
3. The moduli were extracted from the DER files and converted to decimal for posting on the Web page.
4. 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.

Answer 1

One practical method: use a Java Card Smart Card. Load a trivial Java applet, made with the free Java Card Classic Development Kit, that generates an RSA key, and outputs the public modulus. Then either destroy the Smart Card, or zeroize it.

The applet will be so simple that it can be convincingly audited, either from source or from the tiny, well documented Java Card bytecode (RSA key generation itself is a few bytes in that, invoking the method built into the Java Card runtime supplied by the card/micromodule manufacturer, possibly calling a library supplied by the chip manufacturer). Some Java Card models are security-certified with similar usage and security demonstration in mind (though it might be hard to purchase these certified models in small quantities, and next to impossible to obtain their full documentation).

A difficult problem: convince oneself/the audience that what's loaded in the Java Card is really the audited applet, and more generally of the integrity of the gear handling the Java Card and the result it produces. In key ceremonies for Smart Cards where the integrity of the gear is paramount, it is common to install a bare OS to a virgin PC without network access from original optical media in front of the customer, but the Smart Card readers might not be scrutinized, even though that equally matters.

Also, there still is a risk that the card developers goofed at writing the RSA key generator. There are precedents:

• section 6.1.1 in Petr Švenda, Matúš Nemec, Peter Sekan, Rudolf Kvašňovský, David Formánek, David Komárek, Vashek Matyáš: The Million-Key Question — Investigating the Origins of RSA Public Keys, best paper of Usenix Security Forum 2016. This one is a Java Card (but not an audited one that I could identify from its traceability data, which I obtained from the lead author).
• Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, Nicko van Someren: Factoring RSA keys from certified smart cards: Coppersmith in the wild, in proceedings of AsiaCrypt 2014. Some part of it appears to be FIPS 140-2 certified, but likely the certification was abused so badly as to become meaningless.

Ah, and of course, it is hard to convince others that the number you exhibit was produced in that way. Not such a good answer..

Answer 2

This may be... hard.

Make an algorithm for this:

Take a PseudoRandom Number Generator.

Ask the computer to get $2^n$ such numbers, $a_1,a_2,...,a_{2^n}$ where $n$ is also a random number, with $2\leq n \leq10$ and $\log{a_i}=\log{a_j}$ .

Divide those numbers into two halves, each having $2^{n-1}$ elements.

Add all numbers in each half.

Multiply the two numbers to get $n$.

This is very unwieldy, but secure. I think.