Rebuilding the private key from signatures

[David Shaw]

On Feb 24, 2011, at 9:39 AM, Atom Smasher wrote:

> On Thu, 24 Feb 2011, Aaron Toponce wrote:
> 
>> However, I was in a discussion with a friend, and the topic came up that it is theoretically possible to rebuild your private key if someone had access to all your signed mail. We debated the size of signatures and mail that would need to be collected for this to be probable.
>> 
>> Is it?
> =================
> 
> if an attacker has two messages signed with DSA, and they happen to use the same value of "k" then it's trivial to recover the private key.
> 
> a random "k" is the achilles heel of DSA and elgamal (and their ECC derivatives). if "k" is truly random (and reasonably large), the chances of getting a duplicate "k" approaches zero... if "k" is not reasonably large or there's a bias that can produce duplicate "k"s with the same value, you're hosed.
> 
> http://www.the-fifth-hope.org/hoop/5hope_speakers.khtml#panel037
> http://en.wikipedia.org/wiki/Digital_Signature_Algorithm
> http://en.wikipedia.org/wiki/ElGamal_signature_scheme

It's worth mentioning that a variant of this is what caused the Elgamal signing key problem back in 2003 (and indirectly, what caused Elgamal signatures to be dropped from the OpenPGP standard altogether).  See http://lists.gnupg.org/pipermail/gnupg-announce/2003q4/000160.html for the details.

In that attack, all you usually needed was the public key alone, since most Elgamal signing keys were primary keys, and primary keys issue signatures over the user ID, giving you the signature needed to mount the attack.

David