Есть ли коллизии в SHA-1 для сообщения меньше размера хеша (20 байтов)?

Гость (03/03/2013 14:57), топикстартер спрашивает не про хэш-функции вообще, а про свои конкретные конструкции.

…т.е. его то как раз интересует частный случай, где {множество входов} ≤ {множество выходов}. И он почему-то решил, что там коллизий не должно быть.

И он почему-то решил, что там коллизий не должно быть.

Он так считает, потому что полагает функцию сжатия типа SHA алгебраической функцией с аналитически доказанным биективным отображением входов в выходы, а на самом то деле функции типа SHA и т.д. просто другие функции – т.н. случайные, со своими свойствами. Ы?

В основе функции может лежать и такой примитив, например, как кто-то здесь упомянул, блочный шифр. Но режим использования внутри самой функции сжатия (смена ключа) или ряд небольших добавок (простейший XOR входа с выходом) специально делают конструкцию гарантировано небиективной.

https://www.pgpru.com/comment61514

Кажется, понял – если хеш-функция f: M -> N биективная, то выходные значения будут выбираться не из N, а из N – (уже встретившиеся значения), т.е. не будут случайными из N.

где-то тут должно быть M? Или в смысле (N – x), т.е. "минус" встретившиеся значения?

Да.