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.)
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
