----- Original Message -----
From: "David Barrett" <[EMAIL PROTECTED]>
To: "'theory and practice of decentralized computer networks'"
<[email protected]>
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
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
