Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am trying to figure out this question:

Generalize the Merkle-Damgard construction for any compression func­tion that compresses by at least one bit . You should refer to a general input length £' and general output length E (with £' > E).

It is in my understanding that the Merkle-Damgard takes an input of 2*l(n) and compresses it to l(n). How would I go about breaking up the input so that an arbitrary hash length L' can be outputted?

share|improve this question
Let $m = m_1 m_2 \dots m_n$. Suppose $y_0$ is fixed and let $y_i = f(y_{i-1}, m_i)$, $h(m) = y_n$. This is the basic Merkle-Damgård construction, but some extra tricks are needed. You first need to understand why these tricks are needed. Study how you recover a collision for $f(\cdot)$ from a collision in $h(\cdot)$. Then come up with a suitable trick. Hint: expansion. –  K.G. Apr 24 at 12:51
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.