Explore BrainMass
Share

# Division method for a hash function

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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. <B>Give an example of an application in which this property would be undesirable in a hash function.</B>

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