1
$\begingroup$

Let $p$ be a prime number, and $g$ a generator of $\mathbb Z/p\mathbb Z$. For a message $m$, define the hash function $$h(m) = g^m \pmod p.$$ Is $h$ collision-resistant?

$\endgroup$
1
  • $\begingroup$ Instructions for beginners: please @mariyana, click "accept" in the accepted answer. $\endgroup$ Apr 21, 2018 at 12:50

1 Answer 1

2
$\begingroup$

Let $m$ be arbitrary. Then $m'=m+p-1$ yields a collision with $h(m)=h(m')$ as $m\equiv m'\pmod{p-1}$ and thus by $p-1$ being the relevant group's order $g^m\equiv g^{m'}\pmod p$.

Or formulated differently (using $g^{p-1}\bmod p=1$): $$h(m')=g^{m+p-1}=g^m\underbrace{g^{p-1}}_{1}\equiv g^m=h(m)\pmod p$$

$\endgroup$
2
  • 1
    $\begingroup$ Strictly speaking, the domain wasn't specified. If the domain was $\{0, 1, 2, \dots, p - 2\}$, then $h$ is injective and so has no collisions at all! $\endgroup$ Apr 22, 2018 at 4:10
  • $\begingroup$ @SqueamishOssifrage But then $h$ also wouldn't be a "hash function" because it would be non-compressing. $\endgroup$
    – SEJPM
    Apr 22, 2018 at 8:07

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.