1
$\begingroup$

A slight modification of El Gamal signature scheme would be to compute:

$r = g^k$ for some random k (as usual) but $s$ as:

$s = (hash(m) - x)k^{-1} \mod (p-1) $ (instead of $(hash(m)-xr)k^{-1} \mod p - 1$).

The verification procedure would be to check:

$g^{hash(m)} = g^x r^s \mod p$

I don't see what we are losing by doing so.

$\endgroup$

1 Answer 1

1
$\begingroup$

Forging an arbitrary ElGamal signature means finding $(r,s)$ such that $g^h = y^r r^s \mod p$ for given values of $p$, $g$, $h$ and $y$. We don't know how to do that other than selecting $r$ and then having to solve a discrete logarithm for $s$.

In your proposed variant, forging a signature means finding $(r,s)$ such that $g^h = y r^s$. This is just a matter of taking $s = 1$ and $r = g^h / y$. This can't be fixed by adding another constraint on $s$ since the problem would then be to find an $n$th root, which is solvable.

The gist of ElGamal variants is to involve a linear combination of $r$ and $g^r$ during verification. This is what makes a forgery likely to be as hard as solving a discrete logarithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.