wizzard

As you probably know, a digital signature is a virtual "seal" that proves that some message has originated from a particular person in possession of a private key.

Let's try to look at this "seal" from the information-theoretic perspective.

We want to reach 128-bit security, i.e. a random guess should have a 1 in 2^128 chance getting a signature right.

Then, the public key is an encoding of a trapdoor function which can map X 256-bit messages into some thumbprint, where there are 2^256 ways (or more) to construct this trapdoor.

( so? )

Meanwhile, everybody knows SSL certificates arent 22 MB but only about 5-20 KB in length. Something just doesnt seem right.

So... anybody else still surprised why DSA, ECDSA, Winternitz, *MSS and other signature schemes allow Rob to compute the private key so easily if Sam does not rigorously follow restrictions of nonce, padding and so on?

This is also the reason I consider most signature schemes being insecure (as in, fundamentally susceptible to cryptanalysis, especially under the chosen-message attack)

( references )