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

Jeff Rose rosejn at gmail.com
Sat Jul 7 20:38:49 EDT 2007


On Jul 8, 2007, at 1:35 AM, David Barrett wrote:
...
> Assume a 1024-bit RSA keypair.  Any data encrypted with the public  
> key can only be decrypted with the private key, and vice versa.
>
> The only real difference between the public and private key is it’s  
> far more expensive to encrypt/decrypt with the private key than  
> with the public – on the order 20x.  So far as I know, other than  
> the difference in CPU cost, they are interchangeable.

Really?  Unless I am not understanding it right, encryption and  
decryption in RSA require basically the same operation, namely,  
taking some number to an exponent, mod n.

http://en.wikipedia.org/wiki/RSA

> So if you agree with the above statements (and if you don’t, please  
> let me know where I’m off), here’s my question:  How much easier is  
> it for a hacker with the private key to guess the public than vice  
> versa?
The security of RSA boils down to the difficulty of factoring n, the  
product of two really big primes: n = p*q.  If you can get the two  
prime numbers and you have the public key you can generate the  
private key.  I'm not really sure that vice versa even works.  It  
seems like it still boils down to factoring n, but I wouldn't bet on  
it without looking into it more.  Anyway, even if it does work it  
will be the same non-polynomial factoring problem.
> Clearly, given the cost difference of the keys, it should be at  
> least 20x more difficult to guess the private key given the public  
> than vice versa using a brute force attack.
Anyway, do you think 20x is worth thinking about, even if it were the  
case.  If an algorithm can be broken by n computers or 20n computers  
it's still broken.  I don't know about RSA, but saw on this link  
(below) that AES (Rijndael) takes on the order of 149 trillion years  
to decrypt with a cryptanalysis machine.  Who cares if it's only 7 or  
8 trillion instead?  I think with a 2048 bit RSA key you can be  
pretty secure about things for your forseable lifetime.  (Quantum  
computing could change things though...)

http://www.ibm.com/developerworks/library/pa-bigiron6/
> But I’m wondering if there are additional attacks that can be waged  
> on the private key that go beyond brute force?  Is there some trick  
> that a hacker could use to more easily generate the corresponding  
> public key given the private?
>
Not likely, but it never hurts to try these things out just to really  
wrap your head around the problem.  This is an area that has been  
picked with a fine tooth comb by a lot of very smart people though.

Cheers,
Jeff

P.S. Where is the P2P though?  What kind of communications are you  
trying to support?  (Actually, that could be a nice survey paper.   
Encryption algorithms and techniques paired with different P2P  
interactions... Probably should be a real crypto person.)

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.zooko.com/pipermail/p2p-hackers/attachments/20070708/d08e25bb/attachment.htm


More information about the p2p-hackers mailing list