4 ms·
Just out of curiosity: is a similar problem (generate a valid public key that surely nobody including myself can know the private key of) solvable for RSA?
by patrakov 4y ago
Just out of curiosity: is a similar problem (generate a valid public key that surely nobody including myself can know the private key of) solvable for RSA?
- thaumasiotes 4y agoThat problem can't be solvable in any context. There's no way to rule out the possibility that someone else in the world knows your mathematical secret.
- deleted 4y ago[deleted]
- 3np 4y agoThis reasoning doesn't hold if we're still operating within the base assumptions of RSA (and if we're not, no private key is secure)
- jagged-chisel 4y agoLet’s try it this way: what if two people, unlikely as it may be, generate the same key pair? Two people know the private key, and factoring is still hard.
- hgsgm 4y ago"someone might guess a key by luck" has always been an accepted risk of RSA or any key-based encryption system. It's an "act of God".
- doomrobo 4y agoThis is a great question. To rephrase: is it possible to come up with an RSA modulus that even you don't know the factorization of? The answer, I believe, is we have no way of doing that so far. The closest thing that exists is "multiparty" or "distributed" generation of an RSA modulus. Roughly, in the two party case of Alice and Bob, this means Alice picks some pair of numbers (P1, Q1) and Bob similarly picks some (P2, Q2). Then, Alice and Bob engage in some secure multiparty computation protocol whereby they obliviously a) check P1+P2 and Q1+Q2 are prime, and b) if so, output N=(P1+P2)(Q1+Q2) to both Alice and Bob. At the end of the protocol (after repeating enough times that it succeeds), both parties have derived an N whose factorization they don't know. I don't know much about this area of study, but searching multiparty RSA modulus generation should bring up relevant papers.