0
$\begingroup$

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?

$\endgroup$
1
  • $\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, 2016 at 11:38

1 Answer 1

0
$\begingroup$

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

$\endgroup$
5
  • $\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$ Mar 29, 2016 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, 2016 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$ Mar 29, 2016 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, 2016 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$ Mar 29, 2016 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.