Context: http://blog.cryptographyengineering.com/2013/12/a-few-more-notes-on-nsa-random-number.html

Assume I wanted to use RSA as the basis for a hash function or DRBG. Also assume that my construct would be insecure if someone were to have the private key. Is there any way generate the a usable public key to be used such that it is provably just as hard for me to generate the private key as it would be for anyone to do so?

I'm willing to take for granted:

  • the existence of a suitable source of nothing-up-my-sleeve numbers
  • the availability of significant computational resources.

The best idea I've come up with would depend on the ability to prove a lower bound the the size of the smallest factor in a number (e.g.: an $N$-bit number where all factors are at least of size $N*0.49$-bits) with significantly less work than it takes to actually factor it. (That and the ability to find such numbers.)


Unless you relax the restriction to allow for multi-party key generation where, if all the generating parties collude, the key can be recovered, no.

You can create something that operates like an RSA modulus. This was first proposed for use in cryptographic accumulators by Sander in "Efficient Accumulators without Trapdoor Extended Abstract". The idea is to create a number that has at least two large prime factors that are unknown to anyone. It's known as an RSA unfactorable object (RSA UFO) and as far as I know, it's security for use in encryption or signing hasn't been thoroughly examined.

Those issues aside, the problem is the solution is by no means practical. For something with the security of a 1024 bit RSA modulus/key, you would need a 40,000 bit RSA UFO.

  • $\begingroup$ You could replace "threshold" with "multi-party" and "if n of" with "if all of". $\;$ $\endgroup$
    – user991
    Dec 29 '13 at 22:10

While a different solution to the problem, key thresholding might be relevant:

  • $\begingroup$ For what I'm thinking of, see the context I linked (IIRC down near the bottom). $\endgroup$
    – BCS
    Dec 29 '13 at 5:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.