Новичку — Х(е|э)ши. Из чего готовят и с чем их едят.

Не так давно в одном из комментов зашла речь про хеши (или хэши) и было внесено предложение написать о них подробней... Постараюсь выполнить запрос :)

И так... Для начала пара определений с вики:




Теперь то же самое, но на человеческом языке: Хеш - результат работы хеш-функции. Хеш-функция - преобразовывает любую строку в другую строку, которая имеет фиксированную длину, т.е. по сути создаёт идентификатор строки или её личную подпись. Такие подписи для каждой строки будут (должны быть) уникальны, т.е. две различные строки будут иметь две различные подписи (хотя чисто теоретически есть множество строк, которое будет иметь одинаковый хеш с другими строками, но на практике это практически (или вообще?) не встречается, т.е. в принципе на уникальность хешей вполне можно расчитывать).

Некоторые хеши ещё называют "контрольной суммой". Почему - про это будет ниже.

Хеширование похоже на кодирование.Но в отличие от кодирования, хеширование не подразумевает обратной операции, т.е. из строки можно сделать хеш, но сделать строку из хеша - не получится. По поводу того, как же происходит хеширование - тут мне особо сказать нечего, каждая хеш-функция использует свой алгоритм. Простейшим случаем такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование, что применяется, например, в TCP/IP.

В итоге, что нам это даёт? Существует два самых распространённых применения хешированию:
Хранение паролей
Проверка целостности и неизменности файлов

Первый вариант использования подразумевает хранение паролей в открытом виде, без шифрования. Это значительно упрощает работу с базами пользователей, но создаёт приличную дыру в безопасности, ведь стоит кому-то постороннему получить доступ к записям БД или файлу, в котором хранятся пароли, и всё, все пароли как на ладони. Поэтому для хранения паролей и используются хеши: получив доступ к хэшам, злоумышленник ничего не добъётся - восстановить пароль из хеша фактически не реально. При этом проверка введённого пароля усложняется лишь незначительно: чтобы проверить введённый пароль, его необходимо будет сначала подвергнуть обработке той же хеш-функции и сравнивать уже полученный хеш с сохранённым. Если хэши совпали, значит и пароли совпадают. Единственная проблема этого подхода - забытый пароль нельзя восстановить, можно только назначить новый.

Второй вариант используется при передаче данных через сеть или при контроле целостности хранящихся файлов. Здесь используется та особенность хеша, при которой изменение исходной строки даже на 1 бит изменит и хеш этой строки. Т.е. на практике это выглядит примерно так: перед передачей файла через сеть я предварительно создаю хеш этого файла, его контрольную сумму, и отправляют и сам файл и его контрольную сумму. Хэш как правило иммет небольшой размер и его повреждение при передаче, если и будет иметь место, то это будет сразу видно. Получатель, скачав файл, тоже создаёт хеш файла по тому же алгоритму, что и я, и сравнивает полученную контрольную сумму с той, что прислал я. Хеши одинаковы - файл дошёл без изменений и повреждений. Другие варианты проверки целостности файлов менее удобны и практичны: можно проверять файлы по размеру, но это не защитит от подмены нескольких символов, при которой размер останется прежним, но содержимое изменится.

Сейчас существует множество алгоритмов хеширования. Самые распространённые из них это MD5, CRC-32, SHA-1 и несколько других. Разные алгоритмы хеширования отличаются скоростью работы, криптостойкостью и областью применения. По первым двум пунктам всё понятно, а третий как раз и делит хеш-функции на те, что используются для создания контрольных сумм и те, что используются для защиты данных. В обеих областях к хеш-функциям предъявляются разные требования: при создании контрольных сумм важна скорость работы и простота реализации (такие хеш функции работают очень быстро, но при этом страдает криптостойкость - есть лёгкая возможность подогнать сообщение под заранее известную сумму); для функций, предназначенных для защиты данных, на первом месте - криптостойкость, т.е. чем сложнее подогнать файл под заранее известный хеш, тем лучше (скорость при этом, конечно, страдает).

Без хешей сейчас не обходится фактически ни одна система авторизации (обходятся только те, которые шифруют данные, и то не все). Авторизация в линукс тоже использует хэши - все пароли пользователей хранятся в файле /etc/shadow в виде хешей. Подавляющее (я надеюсь) большинство веб-сайтов хранят пароли пользователей в базе в виде хешей. Хеши используются в p2p-сетях для идентификации файлов. Системы контроля версий также используют хеширование.

Интересно, как люди раньше обходились без хешей? %) Просьба строго не судить. Если есть что добавить или исправить - милости просим :)