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$.
If you can check wheter a) and b) are right and give me a hint on c) I will be very grateful.
a) Looks correct to me.
b) Not sure, sorry.
c) If A proceeds instead, note that A sends $m$ and $r$ to Beatriz, and Beatriz knows $p$. Note that there may be many possible values of $d_A$ such that $m\equiv d_A r \mod p-1$, but the right $d_A$ can be found using its relationship with $e_A$.