Пояснение о хэш-функции

Пусть есть файл, нам нужно как-то проверить, что он не изменился, не сравнивая при этом файл с его полной копией. Для этого нам нужна какая-то функция, которая будет возвращать одно и то же число, если файл не изменился, и (желательно) какое-то другое число, если файл как-то изменился. При этом исходный файл может быть любого размера (сколько поместится на внешнем носителе), а полученное число будет в каком-то ограниченном диапазоне значений (допустим от 0 до 2128-1, если нужен 128-битный хэш). Это и означает, что множество любых возможных файлов сокращается до множества чисел от 0 до 2128-1 (в данном случае).

Простейший пример хэш функции - просуммировать все байты объекта (например, файла), полученную сумму поделить с остатком на максимальное значение хеша + 1. Но для такой функции при желании достаточно легко подобрать исходные данные, которым будет соответствовать одинаковое значение хэша (например, можно просто переставить местами два байта - хэш останется тем же). Есть более надежные алгоритмы хэширования (лучше пользоваться существующими реализациями, а не изобретать свой велосипед), но в любом случае для любых входных данных найдутся другие входные данные с таким же хэшем, поэтому одинаковый хэш не гарантирует одинаковые исходные данные.

Представим себе такую фунцию: Hash(A)=B То-есть хеш от A равно B.

A может быть каким угодно числом, а значит множество вариантов A бесконечно. При этом размер "B" известен, например 512 байт. То-есть существует ограниченное число B.

Значит, для каждого "A" существует только одно "B". А вот для каждого "B" можно подобрать бесконечное число "A".