If someone is signing a document using the ElGamal signature scheme, and if the random involved in the signature $k \mod (p-1)$ is equal to $a$ (the private key), can an attacker notice? If so can he then determine the value of $a$?

Would it be because the $\beta = \alpha^a \mod p$ from the published key ($p$, $\alpha$, $\beta$) and $r = \alpha^k \mod p$ from the signed message triple ($m$,$r$,$s$) are the same?

  • $\begingroup$ yes, an attacker would notice it (as your argument shows). No, this shouldn't help him in finding $a$ (because he doesn't know $k$ anyway). $\endgroup$ – SEJPM Mar 29 '16 at 11:38

No, it doesn't provide extra information on the private key.

Note that there is no restriction on the private key value, you just have to ensure that $gcd(k, p-1) = 1$ and that $k$ is only used ONCE. Otherwise the private key can be easily found: see this link which explains how it fails for DSA (this is the same reasoning for the ElGamal scheme).

  • $\begingroup$ I understand why it only needs to be used once, and how to determine a if k is used twice. However, I'm asking about the extraordinary case where k is randomly generated as the same value as a. If you didn't guard against that... could an attacker notice? I thought it might be possible by comparing beta and **r. ** $\endgroup$ – Brittany Lemon Mar 29 '16 at 13:32
  • $\begingroup$ @BrittanyLemon I noticed that but as I told you, it doesn't provide extra information on the private key. Yes $\beta$ and $r$ will be equal but the attacker will know $\alpha^k \mod p$ and not $k$ so it doesn't help to find the private key as it is based on the discrete logarithm problem as for $\beta = \alpha^a \mod p$. $\endgroup$ – Raoul722 Mar 29 '16 at 13:39
  • $\begingroup$ Couldn't the values for r and s be used to determine k, though? Maybe I'm still misunderstanding, but I thought if you set up the congruence for beta^r * r^s = alpha^m (mod p) which simplifies to a = m(r+s)^-1 (mod p-1) then you would know a? Is this not possible because you can't guarente r+s will be invertible? $\endgroup$ – Brittany Lemon Mar 29 '16 at 13:48
  • $\begingroup$ I think you are misunderstand something, could you please describe how do you simplify your equation? Be careful, this is modular arithmetic, $a^b \mod c = a^d \mod c$ does not imply that $b = d$. $\endgroup$ – Raoul722 Mar 29 '16 at 14:01
  • 1
    $\begingroup$ Ah, I was working under the assumption that that equation would imply the exponents (b=d) are equivalent. Without that I don't see any way to gain further information. $\endgroup$ – Brittany Lemon Mar 29 '16 at 14:24

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.