Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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... –  D.W. Mar 16 at 7:15
1  
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}$ –  Ricky Demer Mar 16 at 7:29
1  
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. –  K.G. Mar 16 at 8:12
    
Take a look at this for an implementation and the work they cite as the basis of their implementation. –  mikeazo Mar 16 at 16:21
1  
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. –  mikeazo Mar 17 at 17:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.