Why Random Secret Necessary Almost in all digital Signature Algorithms

Question

I've read some introduction documents about digital signatures, and all they said is

1. Signer calculates a hash of data to be signed.
2. This hash is encrypted with the private key.
3. Verifier reads the document and calculates hash again and compares it the received hash which is decrypted with a public key of the signer.

Then I've read the implementations like El-Gamal, DSA, and Schnorr. They all use an additional random secret variable (referred to as $r$ in three algorithms). What's the purpose of it?

Answer 1

ElGamal signature, Schnorr signature, DSA and ECDSA are all based on the same core principle. They all use a group where calculating discrete logarithm is infeasible with a generator $g$ (i.e. $k \mapsto g^k$ is a trapdoor function). A key is a group element: the secret key is an index $x$ and the public key is the corresponding group element $y = g^x$. To sign a message:

1. Choose an element of the group by its index $k$. $k$ must remain secret forever and must not be reused for another signature.
2. Calculate a value $r$ which is derived from the group element $g^k$. $k$ must remain secret but $r$ will be public.
3. Calculate a value $s$ that depends on both $r$ and $k$, as well as the secret key $x$ and the message to sign. (Actually Schnorr is structured differently and the message goes into $r$ instead of $s$, but it's still the same core principle.)
4. The signature is the pair $(r,s)$.

The verifier uses $r$, $s$ and the public key to calculate two group elements. If $s$ was derived from $r$ using the secret key and the secret index $k$ then the secrets cancel out and the two group elements are identical. Without knowledge of the secrets, it's infeasible to make the two calculations produce the same value.

The nonce $k$ must have two properties: it must not be reused for another signature in the same group, and it must remain secret. If the nonce for a signature is revealed, it's trivial to calculate the secret key from the nonce and the signature. If the same value $k$ is used for two signatures with the same key then their use cancels out and this again reveals the secret key. Even partial information about $k$, or reusing $k$ with different signatures, leaks information that can make it easier to find the secret key(s).

It is not necessary for $k$ to be random, however. It needs to be as hard to find as the secret key, and as unique as the secret key and the message. It's ok for $k$ to depend deterministically on the secret key and the message. For (EC)DSA this is standardized and commonly used. Deterministic (EC)DSA uses the secret key and the message to seed a pseudorandom generator which is used to generate $k$.

The other family of popular signature methods is based on RSA. There are two signature schemes based on RSA: PKCS#1v1.5 and PSS. Both use the RSA trapdoor permutation on an input that contains the message to sign. PKCS#1v1.5 is not randomized at all, and PSS is optionally randomized to generate the padding (the part of the input from the trapdoor function that isn't the message). The random padding in PSS is revealed as part of the signature. Using random padding gives a proof of security that relies on fewer assumptions than what you can get without random padding, but this doesn't translate to any known attack on signatures without random padding. PKCS#1v1.5 signature, which is always deterministic, has no known attacks if implemented correctly.

Encryption requires non-determinism so that, at a minimum, encrypting the same message twice doesn't produce same output. For asymmetric encryption, this is vital since anybody can use the public key to encrypt: if a public-key encryption scheme wasn't randomized then any ciphertext could be broken simply by guessing the plaintext and encrypting it. The non-determinism is equivalent to building in a secret part in every ciphertext (which needs to be done right!). In public-key encryption, the random nonce needs to remain secret as long as the message, but (at least with some schemes such as RSAES-PKCS1v1_5 and RSAES-OAEP) it can be revealed when the message is decrypted.

Signatures don't have the same requirements. They don't intrinsically require non-determinism. A popular type of signature scheme uses a secret nonce, but the important property of this nonce is that it's secret, not that it's non-deterministic.

Deterministic and randomized signature scheme each have their own benefits and weaknesses. Randomized versions make fewer assumptions on the cryptographic primitives, which makes them more robust in case of partial breakage. However they introduce a reliance on the system's random generator, which is often a weak point in practical design. This tends to make the deterministic variant of (EC)DSA preferable in practice. For RSA, the random nature padding of PSS is not critical for security, but its presence protects against bugs in verifiers: the main problem with PKCS#1v1.5 signatures is that some verifiers don't do a thorough job (Bleichenbacher attacks against PKCS#1v1.5 signature — not to be confused with his attacs against PKCS#1v1.5 encryption), and PSS is more robust against such errors.

Using a random value also introduces a potential covert channel (a black box that is supposed to do nothing but sign a message can get some information out to a third party). The deterministic variants of logarithm-based schemes don't solve this since it's impossible to tell how the nonce was generated. Covert channels are rarely a concern however.