12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, but the algorithms are not practical for reasonable-sized RSA modulus. I'm pretty sure this has been asked before on this site but I can't seem to find where... $\endgroup$ – D.W. Mar 16 '14 at 7:15
  • 1
    $\begingroup$ One of them specified a non-interactive technique, and the answers to the other one's answers did $\hspace{.36 in}$ not go into detail on the multi-party options since that was not explicitly mentioned in the question. $\hspace{.44 in}$ $\endgroup$ – user991 Mar 16 '14 at 7:29
  • 2
    $\begingroup$ A good place to start may be: Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, Tomas Toft: Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting. CT-RSA 2012: 313-331. $\endgroup$ – K.G. Mar 16 '14 at 8:12
  • $\begingroup$ Take a look at this for an implementation and the work they cite as the basis of their implementation. $\endgroup$ – mikeazo Mar 16 '14 at 16:21
  • 1
    $\begingroup$ Since the OP is "fine with a multi-party algorithm and an assumption that players do not collaborate", I don't think this should be closed as a duplicate. The one that is currently marked as duplicate specifically says non-interactive (and actually points out a potential answer). I'll reopen, but if anyone disagrees, feel free to let me know. $\endgroup$ – mikeazo Mar 17 '14 at 17:25
2
$\begingroup$

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:

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

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would the addition of the numbers be prime somehow? Who is doing the final multiplication? $\endgroup$ – Maarten Bodewes Sep 30 '17 at 12:00
  • $\begingroup$ Thid answer isn't obviously related to the question. I would expect at the mininum some motivation of how any of this relates to the question requirements if not formal proof. $\endgroup$ – Meir Maor Sep 30 '17 at 16:56
  • $\begingroup$ @MaartenBodewes The addition may or may not be prime. $\endgroup$ – MalayTheDynamo Oct 1 '17 at 2:38
  • $\begingroup$ @MeirMaor How so? $\endgroup$ – MalayTheDynamo Oct 1 '17 at 2:38
  • $\begingroup$ It does somethig very complicated and then does a multiplication at the end. The question asked for building a hard to factor composite number suitable for rsa. Your algorithm ends with a multiplication done by someone. You didn't mention anything about secure multibparty to explain why no one noes the factors nor did you supply any motivation for why the result is hard to factor regardless. $\endgroup$ – Meir Maor Oct 1 '17 at 3:22

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.