I am reading the "Handbook of Applied Cryptography" by Menezes et al. (hashed) ElGamal Signature verification in this book talks about verification of $1\leq r\leq p-1$. Subsequently, this book also provides a justification for this verification step. I attach a picture of the verification description and corresponding justification of the check $1\leq r\leq p-1$ which is marked by $(iv)$. I fail to see how this check is stopping an adversary from just following through the steps mentioned under $(iv)$. Can somebody clarify please?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ well since $r' \equiv r \bmod p$ this is either $ r' = r $ or $r' > (p-1)$. Can you fill the rest? $\endgroup$– kelalakaCommented Apr 25 at 9:15
-
$\begingroup$ not sure... kindly complete the argument... thanks in advance. $\endgroup$– mxantCommented Apr 25 at 9:24
-
$\begingroup$ I think you are low on math to understand the basics. Could someone consider writing an answer? $\endgroup$– kelalakaCommented Apr 25 at 15:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This attack requires that $r' = ru \bmod p-1$ and $r' = r \bmod p$. If $r'$ were less than $p-1$, it would have to be that $r'=r=ru$ over the integers (no modulus), which is unlikely as $u$ is computed from two hashed values (and thus, $u$ is likely not $1$). Thus, for this attack to work, $r'$ must be larger than $p-1$.