(10 pts) Assume a hash function H(m) which is collision resistant. This particular function maps a message of arbitrary bit length into an n-bit hash value. Can we assume that for all messages m, m' with m m', we have H(m) + H(m')? You must explain your answer to receive credit. (Hint: see textbook section about Secure Hash Functions.)
Solution :
Hash function
A hash function is a mathematical function that converts a number-based input value into another (pressed or forced into a smaller space) number-based value.
The input to the hash function is of random length but output is always of fixed length.
Values returned by a hash function are called message digest or simply hash values.
Crash resistance property
Crash free hash function:This property means it should be hard to find two different inputs of any length that result in the same hash.
For a hash function h, it is hard to find any two different inputs x and y such that h(x) = h(y).
Since, hash function is (pressing or forcing into a smaller space) function with fixed hash length, it is impossible for a hash function not to have crashes. This property of crash free only confirms that these crashes should be hard to find.
This property makes it very hard for an attacker to find two input values with the same hash.
Also, if a hash function is crash-resistant then it is second pre-image resistant.
Pre-Image Resistance
This property means that it should be (math-based/computer-based) hard to reverse a hash function.
if a hash function h produced a hash value z, then it should be a very hard process to find any input value x that hashes to z.
Second Pre-Image Resistance
This property means given an input and its hash, it should be hard to find a different input with the same hash.
if a hash function h for an input x produces a hash value h(x), then it should be very hard to find any other input value y such that h(y) = h(x).
Properties of a "good" (related to secret computer codes) HASH function H():
1. Takes on input of any size
2. Produces fixed-length output
3. Easy to figure out/calculate ((producing a lot with very little waste))
4. Given any h, (math-based/computer-based) incapable of being done to find any x such that H(x) = h
5. For a given x, (math-based/computer-based) incapable of being done to find y such that H(y) = H(x) and ya x
6. (math-based/computer-based) incapable of being done to find any (x, y) such that H(x) = H(y) and x a y
For described/explained understanding :-
Birthday (two separate things are both true, but this seems impossible) problem -
Trending now
This is a popular solution!
Step by step
Solved in 4 steps