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.

The DSA variant you describe exists as an elliptic curve version. It is called EC-GDSA ( Elliptic Curve German Digital Signature Algorithm) . It is described here: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TR03111/BSI-TR-03111_pdf.pdf?__blob=publicationFile

| improve this answer | |

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.