![](https://privatefinance.biz/wp-content/uploads/2018/01/f88c64273953610693409380b7e628f1.jpg)
История хеширования
Общая хеш-функция — это специальный тип функции программирования, который используется для сопоставления данных произвольного размера с данными фиксированного размера. Хеш-функции возникли из-за необходимости сжимать данные и уменьшать объем памяти, необходимый для хранения больших файлов.
Наиболее популярным вариантом использования хеш-функции является структура данных, называемая hash table. Она широко используется для быстрого поиска информации. Хеш-функции помогают ускорить поиск таблицы или базы данных, обнаруживая любые два точных хеша.
Они также помогают минимизировать теги для огромных файлов, таких как mp3, PDF или изображения, чтобы упростить работу с этими объёмными данными. Для быстрой идентификации ключевым требованием хеш-функций является то, что они выводят строку с фиксированной длиной буквенно-цифровых символов.
Хотя главной причиной возникновения хеш-функции была необходимость в сжатии контента, вскоре вторая особенность стала основным параметром хеширования — это уникальные идентификаторы.
В идеале, когда происходит хеширование нескольких сообщений, никакие два разных месседжа не должны возвращать один и тот же хеш. Два разных хешированных сообщения, приводящих к одному и тому же выходному хешу, называются столкновением.
С точки зрения управления базой данных это означало бы, что два разных объекта в конечном итоге хранятся в одной и той же ячейке — это неудобно, если вы хотите определить уникальные идентификаторы.
Если мы рассмотрим хеш-функцию с бесконечными входами (это означает, что мы можем хешировать любую строку), мы можем точно определить, почему столкновения на самом деле неизбежны.
Принцип Pigeonhole
В рамках криптографической математики существует понятие, называемое принципом Pigeonhole. Оно означает, что если мы поместим (n) элементы в (m) пространства, где n > m , то существует хотя бы одно пространство (m), занятое более чем двумя элементами (n).
Если вы хотите больше узнать о криптографии, читайте статью Криптография. Пособие для начинающих
Например, четверо человек ищут свои пальто в одной из трёх доступных секций для пальто. По принципу Pigeonhole, поскольку количество пальто (n) больше, чем секций (м), существует 100% вероятность, что по меньшей мере одна секция содержит больше одного пальто.
Обычно разработчики программного обеспечения заинтересованы в хеш-функциях с бесконечным доменом (то есть они принимают входные строки всех возможных длин) и конечным диапазоном.
Снова следуя принципу Pigeonhole: поскольку наш диапазон (n) меньше нашей области (m), должно существовать хотя бы одно столкновение.
Таким образом, эффективная хеш-функция лишь пытается минимизировать количество столкновений — почему это имеет значение, станет более ясным чуть позже, а пока давайте вернемся к истории хеширования.
Хеш-функции были созданы исключительно из потребности в обслуживании и в управлении базами данных. Хеши, в первую очередь, способствовали ускорению работы, а их полезность быстро эволюционировала.
В поле зрения вскоре появилась отдельная ветвь хеш-функций, которая обеспечивала конфиденциальность, безопасность и прозрачность. Данная ветвь находится в центре внимания нашей статьи — это криптографическая хеш-функция.
Криптографическое хеширование
Криптографические функции хеширования, как следует из названия, нужны для обеспечения абсолютной неразрывности сообщений в криптографическом коде. Хотя минимизация столкновений для других хеш-функций — это хорошее дополнение, для специфических криптографических функций она требуется обязательно.
Вместо того, чтобы максимизировать скорость поиска базы данных или таблицы, криптографические хеш-функции построены с учетом состязательного сценария: в нём криптоаналитик пытается вызвать столкновение. Теперь мы определим стандартные обозначения хеш-функций и установим их принципы в криптографической перспективе.
Обозначения хеш-функций
Общая криптографическая хеш-функция имеет два входа: сообщение, которое она сжимает или хеш (x), и открытый ключ (s), который представляет собой выходной сигнал фиксированной длины нашего хеша в алфавитно-цифровых символах. Хешированный результат называется месседж-дайджестом или просто дайджестом (x *). Это выглядит так:
H (s,x) = x *.
Давайте изучим эту формулу на реальном примере хеш-строки, использующей предыдущий стандарт хеш-функции — MD5. Скажем, мы хотим применить MD5 для хеширования строки “Hello World!”. Мы также знаем, что по умолчанию MD5 всегда выводит строку из 128 бит (0 и 1). Обозначение будет выглядеть следующим образом:
H (128, x) = ed076287532e86365e841e92bfc50d8c.
На самом деле, если вы продолжите и попробуете составить хеш-функцию MD5 “Hello World!” самостоятельно, вы получите точно такой же результат. Потрясающе!
Теперь давайте перейдем к настройке обозначений для столкновения. В дополнение к предыдущим переменным H, s, x, и x * вводим второе сообщение (x ‘). Столкновение возникает, когда хеширование двух разных сообщений (x & x ‘) приводит к одинаковому месседж-дайджесту (x *):
Если H (128, x) = H (128, x ‘), наша хеш-функция (H) будет столкновением при x и x’.
Мы установили определение для текущего стандарта криптографической хеш-функции. Если происходит столкновение, хеш-функция больше не считается безопасной.
Заключительные мысли
Хеш-функции возникли из-за необходимости сжатия и вывода унифицированных стандартов данных для удобства хранения, для этого они генерируют псевдослучайные строки фиксированной длины. Тем не менее, чтобы создать полностью устойчивую к столкновению хеш-функцию, каждое сообщение (x) должно иметь хешированный вывод той же длины, что и вход. Без хешей фиксированной длины мы не можем использовать их как удобную структуру данных, но, назначая фиксированную длину, мы не можем застраховать её от столкновений.
PS. Мы уверены, что некоторые из вас заметили: в нашем примере с MD5 мы использовали хеш-функцию, которая возвращает строку длиной в 128 символов, но наш хеш “Hello World!” возвращает 32-символьную буквенно-числовую строку. Об этом парадоксе мы поговорим в следующей статье!
![Privatfinance](https://privatefinance.biz/wp-content/uploads/2020/05/screenshot_1.png)
Над статьями работает команда авторов, переводчиков и редактор. На сайте команда Privatefinance.biz публикует информационные статьи, обзоры, рейтинги, гайды о торговле на финансовых рынках и инвестировании, рекомендации по выбору брокера и инструментов инвестирования, актуальные новости из мира финансов.
Почта для связи с нами: [email protected]