Rebuilding the private key from signatures

Atom Smasher atom at
Thu Feb 24 15:39:10 CET 2011

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.


  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

More information about the Gnupg-users mailing list