Rebuilding the private key from signatures

[Atom Smasher]

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


-- 
         ...atom

  ________________________
  http://atom.smasher.org/
  762A 3B98 A3C3 96C9 C6B7 582A B88D 52E4 D9F5 7808
  -------------------------------------------------

 	"To consider yourself an environmentalist
 	 and still eat meat is like saying you're
 	 a philanthropist who doesn't give to charity"
 		-- Howard Lyman