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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:


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

share|improve this question

marked as duplicate by e-sushi, AFS, DrLecter, figlesquidge, Gilles Jan 3 '14 at 21:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

I think the closest one can come to that uses multi-prime RSA. $\;$ – Ricky Demer Dec 28 '13 at 20:41

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.

share|improve this answer
You could replace "threshold" with "multi-party" and "if n of" with "if all of". $\;$ – Ricky Demer Dec 29 '13 at 22:10

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

share|improve this answer
For what I'm thinking of, see the context I linked (IIRC down near the bottom). – BCS Dec 29 '13 at 5:23

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