Exercise 11.3.3

Consider a version of the division method in which $h(k) = k \bmod m$, where $m = 2^p - 1$ and $k$ is a character string interpreted in radix $2^p$. Show that if we can derive string $x$ from string $y$ by permuting its characters, then $x$ and $y$ hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.

We need to observe that the hash of the string is the sum of the hashes of each character, and it does not depend on the order they are in. If $x = \langle x_n, \ldots, x_1, x_0 \rangle$.

$$\begin{aligned} h(x) &= \left( \sum_{i=0}^{n}{x_i}{2^{ip}} \right) \bmod m \\ &= \sum_{i=0}^{n}{ (x_i \bmod m) \left( 2^{ip} \bmod {(2^p - 1)} \right) } \\ &= \sum_{i=0}^{n}{ (x_i \bmod m) \left( \prod_{1}^{i}{\left( 2^p \bmod {(2^p - 1)} \right)} \right) } \\ &= \sum_{i=0}^{n}{ (x_i \bmod m) \left( \prod_{1}^{i}{1} \right) } \\ &= \sum_{i=0}^{n}{ (x_i \bmod m) } \end{aligned}$$

We can put the elements of $x$ in any other order, and the result will still be the same.