2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Welcome to Cryptography, One cannot see the implementations from here, Could you post as least a link? Also, are you talking about actually, the randomly choose a secret key for El-Gamal Signature Scheme $\endgroup$ – kelalaka Dec 31 '18 at 6:52
  • $\begingroup$ Thanks @kelalaka. Added links and explicitly mentioned that I refer to variable r. $\endgroup$ – Ali.G Dec 31 '18 at 7:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The salt size is set to the hash size for PSS by default. Most implementations of PSS therefore will be probabalistic, even though it is possible to set the salt size to zero bytes, making the algorithm deterministic instead. $\endgroup$ – Maarten Bodewes Dec 31 '18 at 12:38
  • $\begingroup$ @MaartenBodewes “By default” is meaningless for an algorithm. You could say that a specific implementation is “randomized by default” if the salt length is an optional parameter that defaults to the salt length, which I think is common. “Usually randomized in practice” would be true for the algorithm. $\endgroup$ – Gilles Dec 31 '18 at 13:45
-1
$\begingroup$

Modern Cryptography works with the Kerckhoffs's principles, so everything about the encryption system is known by the attacker except the key.

Now, for example, in el-Gamal signature_scheme, the signature generation start with

  • Choose a random $k$ such that $1 < k < p − 1$ and $\gcd(k, p − 1) = 1.$
  • Compute $r \equiv g^k \pmod p $
  • Compute $s \equiv (H(m)-xr)k^{-1}{\pmod {p-1}}$
  • If $s=0$ start over again.

,and the $k$ is chosen randomly per message.

Now assume that the $k$ is deterministic, that is the attacker know the values you generated.

The attacker knows, $p,p-1, k, k^{-1}$,and $s$. If the attacker knows the encrypted message $m$ then he also knows the $H(m)$. Knowing the $m$ is a realistic scenario, not every signed message is encrypted. So, the attacker can solve the below equation to access your private key $x$.

$$s \equiv (H(m)-xr)k^{-1}{\pmod {p-1}}$$

If the $k$ is chosen randomly for each message, then the attacker cannot solve this equation uniquely. The security of the signature scheme relies on the randomly generated $k$. See cryptographically secure pseudo-random number generator. There are also good articles under this on this site.

You can similarly argue for other signature schemes that you listed.

$\endgroup$
  • $\begingroup$ Hmm. Isn't finding the private key a discrete logarithm problem even with the fixed k? Or it's still discrete logarithm problem and random k adds another level of security? $\endgroup$ – Ali.G Dec 31 '18 at 9:35
  • $\begingroup$ Secret key $x$ is used as $x$ in the signature, public key is $g^y$ $\endgroup$ – kelalaka Dec 31 '18 at 9:39
  • $\begingroup$ In ElGamal, Schnorr, DSA and ECDSA, $k$ needs to be secret but it doesn't need to be random. It can be calculated deterministically from the key and the message. $\endgroup$ – Gilles Dec 31 '18 at 10:44
  • 1
    $\begingroup$ My point is that this is wrong: it's ok for $k$ to be predictable, as in, signing the same message twice produces the same signature. What $k$ needs to be is secret, and it must remain secret forever (otherwise the key is compromised, not just the signature for which $k$ was revealed). $\endgroup$ – Gilles Dec 31 '18 at 10:50
  • 1
    $\begingroup$ @kelalaka Yes, but the scheme is also broken if you can find out $k$ after the fact, and conversely $k$ can be chosen deterministically as long as it's properly secret and unique. See my answer for more details. $\endgroup$ – Gilles Dec 31 '18 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.