# Can an RSA public key be generated without ever knowing the factors? [duplicate]

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

-

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

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.

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

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