Cryptography Hash function properties. In lecture, we gave two different example

Question

Cryptography

Hash function properties. In lecture, we gave two different examples of functions h which produce "message digests". The first example was a function which takes a message of arbitrary size, written as an integer in usual decimal expansion, and produces an integer vector with N coordinates (for a fixed N). The second example was a function h_2: Z/^Z -? Z/pZ where t = and both i and p are prime. Why is hi not preimage-resistant? Justify your answer. Why is hi also not collision-free? Justify your answer. We showed in class that h_2 is collision-free, assuming that discrete logs are hard to compute. Why is h_2 also preimage-resistant?

Explanation / Answer

a....

Preimage resistance:

A hash function is preimage resistant if, given a hash value h, it is hard to find any message m such that h = hash(k, m), where k is the hash key.

This is the most usual property developers think of when they think of a cryptographic hash function. Unlike an encryption, there should be no "dehash" function. A good preimage resistant function should be "hard" to invert. An example of a hash function that is not preimage resistant is h = hash(k, m) = m mod 2k, since it is very easy to invert the function, after guaranteeing that for any value of h, a message of size m can be found (basically, every message of the form h + x 2k, where x is an integer.

So, the function is not preimage resistant in hash function properties.

b...

A function H that maps an arbitrary length message M to a fixed length message digest MD is a collision-free hash function if

1. It is a one-way hash function.

2. It is hard to find two distinct messages (M',M) that hash to the same result H(M')=H(M).  More precisely, any efficient algorithm (solving a P-problem) succeeds in finding such a collision with negligible probability

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.