Вернемся к баранам, я тут подумал и пришел к следущему (более слабому, чем в посте #3 и #5) утверждению (доказать пока не могу и, опять же, поправьте, если оно не верно, по возможности с контрпримером): пусть дано сообщение длиной m бит, хэш функция от этого сообщения длиной n бит, тогда получить заданное значение хэша (из множества его возможных значений) можно изменив и/или добавив в сообщени(и|е) не более max(m,n) бит. К примеру: хэш функция `and' (n = 1), сообщение 10101b (m = 5), получить нужное значение хэша (пусть это будет 1) можно изменив 2 бита (2-й и 4-й), 2 < max(5,1). Причем, чтобы выполнялось более сильное утверждение (#5) необходимо и достаточно, чтобы для любого сообщения длиной m < n хэш был уникальным. Т.е., к примеру, для crc32 не существует более одного сообщения длиной <= 4 байт с одинаковым значением хэша crc32, => получить нужный crc32 можно изменив и/или добавив не более 4 байт сообщения. Это так? Если да, то на вопрос о md5 (#8) можно ответить да, и этот предел равен n = 128. Да ?
Ra!N врятли здесь имеет смысл заниматься подобными глобальными теоремами - каждый алгос требует своего подхода, а общим является только Брут, к тому же, попытку найти хэш с помощью файлов большего размера легко присечь.
Ra!N пусть дано сообщение длиной m бит, хэш функция от этого сообщения длиной n бит, тогда получить заданное значение хэша (из множества его возможных значений) можно изменив и/или добавив в сообщени(и|е) не более max(m,n) бит Поскольку функция предполагается surjective (не знаю термина ), то это утверждение тривиально. Причем, чтобы выполнялось более сильное утверждение (#5) необходимо и достаточно, чтобы для любого сообщения длиной m < n хэш был уникальным. Нет, это неверно. Не пытайся перенести какие-либо наблюдения с одного хеша (здесь CRC) на общий случай. Видимо ты непроизвольно ограничиваешь понятие хэш стандартными алгоритмами на основе базовых манипуляций с битами. Но не забывай, что вручную можно без особого труда построить вообще какую угодно функцию. Если собираешься обобщать, то тебе придется скорее всего предъявлять дополнительные требования к функции. И перестать гадать
