1
$\begingroup$

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?

Menezes et al.

$\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$
    – kelalaka
    Commented Apr 25 at 9:15
  • $\begingroup$ not sure... kindly complete the argument... thanks in advance. $\endgroup$
    – mxant
    Commented Apr 25 at 9:24
  • $\begingroup$ I think you are low on math to understand the basics. Could someone consider writing an answer? $\endgroup$
    – kelalaka
    Commented Apr 25 at 15:06

1 Answer 1

0
$\begingroup$

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$.

$\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.