Криптографические хэш-функции используются достаточно широко: они применяются для хранения паролей при аутентификации, для защиты данных в системах проверки файлов, для обнаружения вредоносного программного обеспечения, для кодирования информации в блокчейне. Мы поговорим об алгоритмах хеширования: что это такое, на какие типы подразделяются, и какими обладают свойствами.
Алгоритмы вычисления хеш функций
Криптографические алгоритмы отличаются по сложности, разрядности, криптографической надежности, особенностям работы. Алгоритмы хеширования появилась более полувека назад, и в результате своего развития хеширование данных приобрело много новых свойств.
Что такое хеш (хэш, hash)?
Хеш или хэш — это криптографическая функция хеширования (function), которую обычно называют просто хэшем. Хеш-функция представляет собой математический алгоритм, который может преобразовать произвольный массив данных в строку фиксированной длины, состоящую из цифр и букв.
Вычисление хеш функции
Основная идея используемых в данном случае функций — применение детерминированного алгоритма, то есть алгоритмического процесса, который выдает уникальный и предопределенный результат при получении входных данных. При приеме одних и тех же входных данных создается та же самая строка фиксированной длины (использование одинакового ввода каждый раз приводит к одинаковому результату). Детерминизм — важное свойство этого алгоритма. И если во входных данных изменить хотя бы один символ, то будет создан совершенно другой хэш.
Убедиться в этом можно на любом онлайн-генераторе. И не важно, применяете вы хэш-алгоритм для слова из 4 букв или из 1000 букв, или будет обработано полное собрание сочинений Льва Толстого, на выходе получится код из 40 символов (на алгоритме sha1).
Различные виды hash function производят вывод разной величины, но возможный размер данных на выходе для каждого из алгоритмов хеширования всегда является постоянным. Например, алгоритм SHA-256 может производить вывод исключительно в формате 256-бит, в то время как SHA-1 всегда генерирует 160-битный дайджест.
В криптографии используются хэш-функции 2 классов:
- хэш-функция без ключа;
- хэш-функция с ключом.
Почему это имеет значение?
Криптографические хэш-функции используются в приложениях связанных с информационной безопасностью для аутентификации сообщений и цифровой дактилоскопии. Также, криптографические hash function являются неотъемлемой частью в процессе майнинга, и занимают основную роль в генерации новых ключей и адресов в блокчейн-сетях.
Хеширование демонстрирует весь свой потенциал при работе с огромным количеством информации. Можно пропустить большой файл или набор данных через хэш-функцию, а затем использовать вывод для быстрой проверки точности и целостности данных. Это возможно именно благодаря детерминированной природе хэш-функций: вход всегда будет приводить к упрощенному сжатому выходу (хэшу). Это устраняет необходимость хранить и запоминать большие объемы данных.
Хеширование является в особенности полезным в отношении технологии блокчейн. По факту, практически все криптовалютные протоколы полагаются на хеширование для связывания и сжатия групп транзакций в блоки, а также для создания криптографической взаимосвязи и эффективного построения цепочки из блоков.
Коллизии
Когда hash function генерирует один индекс для нескольких ключей, возникает конфликт (неизвестно, какое значение нужно сохранить в этом индексе). Это называется коллизией хэш-таблицы.
Есть несколько методов борьбы с коллизиями:
- Метод цепочек.
- Метод открытой адресации: линейное и квадратичное зондирование.
Какими свойствами должна обладать hash function
Систематизируем сказанное и добавим новое:
- Идеальная функция приводит любой объем данных к числу заданной длины.
- Вычисление хеша не должно быть слишком простым, высокая сложность нахождения прообраза.
- Малейшее изменение (хоть на один бит) входных данных должно приводить к полному изменению хеша.
- Она стойкая в обратной операции, т.е. вероятность восстановления исходных данных по хешу должна быть весьма низкой (хотя последнее сильно зависит от задействованных мощностей).
- Имеет как можно более низкую вероятность возникновения коллизий.
- Алгоритм работы функции должен быть открытым, чтобы любой желающий мог бы оценить ее криптостойкость, т.е. вероятность восстановления начальных данных по выдаваемому хешу.
