[p2p-hackers] What's the risk of sharing private RSA keys?

David Barrett dbarrett at quinthar.com
Sat Jul 7 23:48:55 EDT 2007


Got it.  Thanks for walking me through this.

> -----Original Message-----
> From: p2p-hackers-bounces at lists.zooko.com [mailto:p2p-hackers-
> bounces at lists.zooko.com] On Behalf Of Joseph Ashwood
> Sent: Saturday, July 07, 2007 8:13 PM
> To: theory and practice of decentralized computer networks
> Subject: Re: [p2p-hackers] What's the risk of sharing private RSA keys?
> 
> ----- Original Message -----
> From: "David Barrett" <dbarrett at quinthar.com>
> To: "'theory and practice of decentralized computer networks'"
> <p2p-hackers at lists.zooko.com>
> Sent: Saturday, July 07, 2007 7:27 PM
> Subject: RE: [p2p-hackers] What's the risk of sharing private RSA keys?
> 
> 
> >> -----Original Message-----
> >> From: Joseph Ashwood
> >>
> >> Actually there are. In fact there are a wide number of them. The one
> that
> >> is
> >> most likely to be damaging to the idea you gave is that RSA with a
> >> private
> >> key of less N^0.271 (it is believed that the attack can be extended to
> >> N^0.5) is insecure as the private key can be found quite easily. With a
> >> very
> >> small private key as would happen with our design this search process
> >> becomes very efficient. However, if you meant to ask can you choose the
> >> private key, and then generate the public key, yes that works, just
> make
> >> sure you choose a large private key. For some more exotic things there
> >> was
> >> some research out of Stanford a few years ago about generating key
> pairs
> >> in
> >> some very exotic ways for security.
> >>
> >> And yes, I am a cryptanalyst.
> >>                 Joe
> >
> > Thanks for the insight.  I don't know if I quite followed that, however.
> >
> > Are you saying that, yes, it's easier to guess the public key given the
> > private, than guess the private key given the public?  How much easier?
> >
> 
> Orders of magnitiude easier.
> 
> > Like, if it takes a million years to guess the private key given the
> > public,
> > will it only take a thousand years to guess the public key given the
> > private?  Or one year?  Or 1 second?
> 
> Closer to a second, maybe a few hours. Worse the public key used in most
> generation methods is 65537, and in some cases 3, so if you use OpenSSL to
> generate a key pair any attacker already knows the public key. This
> decision
> was made to speed up encryption, and since it is known anyway, having it
> pre-known doesn't really matter.
> 
> >
> > I'm guessing that for a 1024-bit RSA key, it should be at least 20x
> faster
> > to guess the public key given the private, than the reverse.  Is it more
> > than 20x faster?
> 
> There are many different possible attack times, there is
> guessing which in this case could be fixed time, but worst case this
> becomes
> brute force
> brute force (how long it takes to count to the unknown), in this case the
> multiplier for the sime difference is private key/public key so the
> difference will be somewhere over 2^1000 times
> factoring there will be no difference on this one
> direct attack on the private key, these are things like the 3 attack from
> Coppoersmith, or the N^0.271 attack, both of which are faster than
> factoring
> if they can be applied, the difference will be substantial but difficult
> to
> compute
> 
> RSA is harder to use than it first appears, you have to use
> cryptographically strong formatting internally (like OAEP), because the
> public side is not authenticated you also have to verify the sender
> somehow,
> which is where things get really interesting.
>                 Joe
> 
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at lists.zooko.com
> http://lists.zooko.com/mailman/listinfo/p2p-hackers



More information about the p2p-hackers mailing list