Открыть сервисСервис
Главная → Блог → Хеш-функция и хеширование данных

Хеш-функция и хеширование данных

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

Общее понятие

Хеш-функция отображает множество входных сообщений произвольного размера в множество значений фиксированной длины. Например, алгоритм SHA-256 всегда выдаёт 256 бит (32 байта) независимо от того, подан ли на вход один символ или файл размером в несколько гигабайт. Результат обычно записывается в шестнадцатеричном виде.

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

Свойства хеш-функций

Различают общие и криптографические требования.

Общие свойства:

  • Фиксированная длина выхода — независимо от объёма входа.
  • Быстрота вычисления — хеш должен считаться за приемлемое время.
  • Детерминированность — повторяемость результата.

Криптографические свойства:

Коллизия — ситуация, когда двум разным входам соответствует один хеш. Для неограниченного множества входов коллизии неизбежны (принцип Дирихле), поэтому говорят лишь о вычислительной сложности их поиска.

История и алгоритмы

Ранние хеш-функции появились в 1950–1960-е годы для организации быстрого доступа к данным в таблицах. В 1970-х годах в криптографии начали применяться односторонние функции.

Основные алгоритмы:

  • MD5 (1991) — 128-битный хеш; ныне считается криптографически взломанным, коллизии находятся быстро.
  • SHA-1 (1995) — 160 бит; также признан нестойким к коллизиям.
  • Семейство SHA-2 (SHA-256, SHA-512) — разработано АНБ США, широко используется и считается надёжным.
  • SHA-3 (2015) — основан на конструкции «губка» (sponge), принят как новый стандарт.
  • ГОСТ Р 34.11-2012 («Стрибог») — российский стандарт криптографического хеширования с длиной выхода 256 или 512 бит.

Применение

Проверка целостности

Контрольные суммы (хеши) позволяют убедиться, что файл не повреждён при передаче или хранении. При скачивании дистрибутивов часто публикуют их SHA-256, чтобы пользователь мог сверить результат.

Хранение паролей

Пароли не хранят в открытом виде — сохраняют их хеш. Для защиты от перебора применяют «соль» (случайную добавку к паролю) и медленные функции: bcrypt, scrypt, Argon2, PBKDF2. Это затрудняет применение заранее подготовленных таблиц (радужных таблиц).

Структуры данных

Хеш-таблица — структура, где по хешу ключа вычисляется индекс ячейки. Это обеспечивает в среднем доступ к элементу за константное время O(1). Хеш-таблицы лежат в основе словарей и множеств во многих языках программирования.

Криптография и блокчейн

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

Дедупликация и поиск

Системы резервного копирования сравнивают хеши блоков, чтобы не хранить одинаковые данные дважды. Поисковые системы и антивирусы применяют хеши для быстрой идентификации известных файлов.

Хеширование и шифрование

Хеширование часто путают с шифрованием, но это разные операции. Шифрование обратимо: зашифрованные данные можно расшифровать ключом. Хеширование необратимо — исходные данные из хеша не восстанавливаются. Шифрование обеспечивает конфиденциальность, хеширование — целостность и идентификацию.

Атаки и уязвимости

  • Атака перебором — подбор входа по известному хешу; против неё помогают длинные пароли и медленные функции.
  • Атака на основе радужных таблиц — заранее вычисленные цепочки хешей; нейтрализуется солью.
  • Коллизионные атаки — например, атака «дней рождения» снижает сложность поиска коллизий примерно до квадратного корня из размера пространства значений.
  • Атаки удлинением сообщения — эксплуатируют конструкцию Меркла — Дамгора в MD5, SHA-1 и SHA-2; для защиты применяют HMAC или SHA-3.

Интересные факты

  • Термин «хеш» происходит от английского to hash — «рубить, крошить», что отражает перемешивание данных.
  • Число возможных значений SHA-256 превышает количество атомов в наблюдаемой Вселенной.
  • В 2017 году исследователи продемонстрировали практическую коллизию SHA-1 (атака SHAttered).
  • Хеш-таблицы — одна из наиболее используемых структур данных в реальных программах.

Источники: стандарты NIST FIPS 180-4 и FIPS 202, ГОСТ Р 34.11-2012, учебные материалы по алгоритмам и криптографии, документация по структурам данных.

Похожие материалы