# ElGamal scheme signature: if private key a mod p is equal to private sig. key k mod p-1, can an attacker notice and determine the value of a?

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?

• 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). – SEJPM Mar 29 '16 at 11:38

## 1 Answer

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).

• 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. ** – Brittany Lemon Mar 29 '16 at 13:32
• @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$. – Raoul722 Mar 29 '16 at 13:39
• 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? – Brittany Lemon Mar 29 '16 at 13:48
• 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$. – Raoul722 Mar 29 '16 at 14:01
• 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. – Brittany Lemon Mar 29 '16 at 14:24