In my criptography course I was given the following exercise:
ElGamal proposed the following digital signature scheme using discrete logarithms over a field $\mathbb{F}_p$, where $p$ is a large prime.
Step 1) Everybody agrees on a prime $p$ and a generator
$g$ for $\mathbb{F}_p^*$.
Step 2) A (and all other uses) chooses a secret exponent $d_A$, and makes public
$e_A\equiv g^{d_A}\mod p$ (just like in the ElGamal cryptosystem).
Step 3) To sign a message, encoded as an integer $m$ with $0\le m\le
p-1$, A chooses a random integer
$k$ relatively prime to $p-1$ (i. e. $\gcd(k,p-1)=1$). Then calculates $r\equiv g^k \mod p$ and solves the equation
$g^m\equiv e_A^r r^s
\mod p$ in the unknown $s$. In case $s=0$ (quite unlikely), she starts again with a different $k$. Finally, A sends to B the message $m$ together with the pair $(r,s)$, which is her signatura for that message.
Step 4) Beatriz checks that $g^m \equiv
e_A^r r^s \mod p$. If this holds, B accepts that the signature $(r,s)$ really belongs to A.
a) Check that Ana knows all she needs to calculate $s$.
b) Check that C can not pretend to be A without knowing $d_A$, that is, without being able to solve a discrete logarithm problem, and, therefore $B$ can be sure that the message really comes from A.
c) Why must A discard $k$ if it turns out that $s=0$?
This is what I have:
a) Since $r\equiv g^k\mod p$ and $e_A=g^{d_A}\mod p$ then:
$$g^m\equiv e_A^rr^s\equiv (g^{d_A})^{r}(g^k)^s=g^{d_Ar+ks}\mod p$$
And, Fermat's little theorem implies that $m\equiv d_Ar+ks\mod p-1\Rightarrow ks\equiv m-d_Ar\mod p-1$. Hence, since $\gcd(k,p-1)=1$ we have that $k$ is invertible in $\mathbb{F}^*_p$ and so $s\equiv k^{-1}(m-d_Ar)\mod p-1$. Hence, we are done, since Ana knows $p,k,m,d_A$ and $r$.
b) If $C$ want to pretend to be $A$, it needs to send $m$ and $(r,s)$ such that $g^m\equiv e_A^rr^s\mod p$. But $s$ depends on $d_A$ as we have seen in $a)$. Hence, we can not construct $s$ without knowing $d_A$, and so, if $C$ want to pretend to be $B$, it needs to find $d_A$. But that is hard, since the only thing we know about $d_A$ (if we are not $A$) is that $e_A\equiv g^{d_A}\mod p$ and so, pretending to be $A$ is equivalent to solve a discrete logarithm problem.
c) If $s=0$ then $g^m\equiv e_A^r\equiv g^{d_Ar}\mod p$ and so $m\equiv d_Ar\mod p-1$. From here I am stuck, since this is the only information I have, but I don't see how this enable us to construct a signatura without knowing $d_A$. Of course, we can solve $m\equiv d_Ar\mod p-1$, which will have $\gcd(r,p-1)$ solutions and then cheking which one is the correct $d_A$, but $\gcd(r,p-1)$ can be close to $p-1$ if we have bad luck, and that would mean that this proces is exponential time, and it is not better than solving the discrete logarithm.
If you can check wheter a) and b) are right and give me a hint on c) I will be very grateful.
