Question:
Division method for a hash function
Please review the problem and explain each step of the solution listed below, and give me an example of an application which this property would be undesirable in a hash function.
problem
----------
Consider a version of the division method in which h(k) = k mod m, where m = (2^p) -1 and k is a character string interpreted in radix 2^p. Show that if a string x can be derived 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.
solution
---------
All permutations can be generated by a sequence of two character interchanges. If two arbitrary characters, i and j, are switched, then the values hash to the same place.
We consider two numbers x and y which have characters i and j interchanged, and i > j.
Note: in this solution xi = x sub i and xj = x sub j (same goes for y).
x - y = (xi - yi)(m + 1)^(i-1) + (xj - yj)(m+1)^(j-1)
= (xi - xj)(m + 1)^(i-1) - (xi - xj)(m+1)^(j-1)
= (xi - xj)[(m + 1)^(i-1) - (m + 1)^(j-1) ]
= (xi - xj)(m + 1)^(j-1) * [(m + 1)^(i-j) -1]
= (xi - xj)(m + 1)^(j-1) * [(m + 1) - 1] * Summation of (m + 1)^k [from k = 0 to i - j - 1]
= 0 mod m