Computer Science Homework Solutions
Problem
#71748

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

Solution
What is this?
By OTA - Overall OTA Rating
Xiao Liu, MS - 4.7/5
Purchase Cost Now
$2.19 CAD (was ~$27.93)
Included in Download
  • Plain text response
  • Attached file(s):
    • hash.doc
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
Browse