# El Gamal signature scheme variant

Suppose we have the following El Gamal digital signature scheme variant: We fix a prime number $p$ and a generator $g$ of the group $Z_p^*$. We choose $x \in Z_{p-1}^*$, which is going to be our secret key and we compute $y = g^x \pmod{p}$, which is going to be our public key. For the signing algorithm, we choose a random varue $k \in Z_p^*$, then compute $$r = g^k \pmod{p}$$ $$s = (m-kr)*x^{-1} \pmod{p-1}$$ and output $(r,s)$.

In order to verify the signature, it's easy to see that the following should hold: $$y^sr^r \equiv g^m \pmod{p}$$ Now, as far as i can tell, the signing algorithm is faster than the one in the original El Gamal scheme, as we compute the inverse of $x$ once and forever, while in the initial scheme we have to compute the inverse of the new random $k$ every time we want to sign a message.

However, what about security? Can we say that the new scheme provides the same security as the initial one or it can be beaten in some way?

First, you should not use $p-1$ as modulus. Instead , use a big prime factor $q$ of $p-1$, as it is done in the DSA algorithm.