Сжимающая функция

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

История

Идея сжатия данных с помощью математических преобразований восходит к ранним работам по теории информации. В 1949 году Клод Шеннон в своей статье «Теория связи в секретных системах» заложил основы для понимания свойств необратимости и рассеивания информации. В 1976 году Уитфилд Диффи и Мартин Хеллман в работе «Новые направления в криптографии» формально описали концепцию однонаправленной функции, необходимой для асимметричного шифрования.

Первые практические реализации сжимающих функций появились в 1980-х годах. В 1989 году Рональд Ривест разработал MD2, а в 1990 — MD4. В 1992 году был опубликован MD5, ставший одним из самых распространённых алгоритмов, но впоследствии признанный уязвимым к коллизиям. В 1993 году Национальный институт стандартов и технологий США (NIST) утвердил стандарт SHA-0, который вскоре был заменён на SHA-1 (1995). В 2001 году NIST представил семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), которое остаётся стандартом де-факто на начало 2020-х годов. В 2012 году NIST выбрал алгоритм Keccak в качестве нового стандарта SHA-3 после открытого конкурса, длившегося четыре года.

Основные свойства

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

• Однонаправленность (необратимость) — для заданного хеша h вычислительно невозможно найти сообщение m, такое что hash(m) = h.
• Стойкость к коллизиям — вычислительно невозможно найти два различных сообщения m1 и m2, таких что hash(m1) = hash(m2).
• Стойкость к прообразу второго рода — для заданного сообщения m1 вычислительно невозможно найти другое сообщение m2, такое что hash(m1) = hash(m2).
• Лавинный эффект — малое изменение входных данных (например, одного бита) должно приводить к существенному изменению хеша (в среднем меняется половина битов выходной строки).
• Фиксированная длина выхода — независимо от размера входных данных, выход всегда имеет заданную длину (например, 256 бит для SHA-256).

Классификация

Сжимающие функции делятся на несколько категорий по различным признакам.

По области применения

• Криптографические хеш-функции — используются для обеспечения безопасности: цифровые подписи, аутентификация сообщений, генерация ключей. Примеры: SHA-2, SHA-3, BLAKE2.
• Некриптографические хеш-функции — применяются для ускорения поиска в хеш-таблицах, проверки целостности данных (контрольные суммы) и дедупликации. Примеры: CRC32, MurmurHash, xxHash. Такие функции не обязаны быть стойкими к коллизиям.

По внутренней структуре

• Функции на основе конструкции Меркла — Дамгора — последовательно обрабатывают блоки данных фиксированной длины, используя сжимающую функцию на каждом шаге. Состояние обновляется после каждого блока. Примеры: MD5, SHA-1, SHA-2.
• Функции на основе губчатой конструкции (Sponge) — используют впитывание (absorb) и отжим (squeeze) данных через фиксированное внутреннее состояние. Пример: SHA-3 (Keccak).
• Функции на основе конструкции Дэвиса — Мейера — частный случай, где сжимающая функция строится на базе блочного шифра.

По длине выхода

• Короткие хеши (до 128 бит) — часто используются для контрольных сумм и в старых алгоритмах (MD5, CRC32).
• Стандартные хеши (256–512 бит) — современный стандарт для криптографических приложений (SHA-256, SHA-512).
• Длинные хеши (более 512 бит) — применяются в специализированных системах, например, в некоторых блокчейн-протоколах.

Устройство и принцип работы

Большинство криптографических сжимающих функций работают по итеративной схеме. Входное сообщение сначала дополняется (падинг) до длины, кратной размеру блока обработки. Затем сообщение разбивается на блоки фиксированного размера (например, 512 или 1024 бита). Каждый блок обрабатывается сжимающей функцией, которая принимает текущее внутреннее состояние (обычно от 160 до 512 бит) и очередной блок данных, и выдаёт новое состояние. После обработки всех блоков итоговое состояние преобразуется в выходной хеш.

В конструкции Меркла — Дамгора сжимающая функция f работает по формуле: H_i = f(H_{i-1}, M_i), где H_0 — инициализационный вектор, M_i — очередной блок сообщения. Финальный хеш — H_n.

В губчатой конструкции (SHA-3) используется внутреннее состояние S фиксированного размера (например, 1600 бит). На этапе впитывания данные XOR-ятся с частью состояния, затем применяется перестановка f. После обработки всех данных на этапе отжима из состояния извлекается хеш нужной длины.

Применение

Сжимающие функции широко используются в информационных технологиях и криптографии.

Цифровые подписи и аутентификация

Хеш сообщения подписывается асимметричным ключом, что позволяет проверять подлинность и целостность данных без раскрытия самого сообщения. Примеры: алгоритмы DSA, ECDSA, EdDSA.

Контроль целостности данных

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

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

Вместо хранения паролей в открытом виде системы хранят их хеши (часто с солью — случайным значением, добавляемым к паролю). При аутентификации введённый пароль хешируется и сравнивается с сохранённым хешем. Примеры: bcrypt, scrypt, Argon2 (специализированные функции для хеширования паролей, устойчивые к перебору).

Блокчейн и криптовалюты

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

Генерация псевдослучайных чисел и ключей

Хеш-функции применяются в генераторах псевдослучайных чисел (PRNG) и в схемах вывода ключей (KDF) для получения ключей из паролей или других источников энтропии.

Примеры алгоритмов

Критика и уязвимости

Основной проблемой сжимающих функций является возможность нахождения коллизий. В 2004 году китайские криптографы Сяоюнь Ван и Хунбо Юй продемонстрировали практические коллизии для MD5. В 2017 году команда Google и CWI Amsterdam объявила о первой практической коллизии для SHA-1 (атака SHAttered). После этих событий MD5 и SHA-1 были признаны устаревшими, и их использование не рекомендуется для криптографических целей.

Другие уязвимости включают атаки на основе удлинения сообщения (length extension attack), возможные для функций на основе конструкции Меркла — Дамгора (SHA-256, SHA-1). Для защиты от таких атак применяются модификации, такие как HMAC или SHA-3, которая не подвержена этому типу атак.

Кроме того, существуют теоретические атаки на некоторые алгоритмы, снижающие их эффективную стойкость. Например, для SHA-256 известно, что стойкость к коллизиям составляет около 2^128 операций (вместо теоретических 2^256), что всё равно считается практически недостижимым на современных вычислительных мощностях.

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

• Алгоритм SHA-256 используется в протоколе Биткойна для майнинга. Сложность майнинга регулируется так, чтобы среднее время нахождения блока составляло около 10 минут. По состоянию на 2025 год суммарная вычислительная мощность сети Биткойна превышает 600 экзахешей в секунду.
• В 2017 году NIST объявил конкурс на новый стандарт лёгкой криптографии (Lightweight Cryptography), ориентированный на устройства с ограниченными ресурсами. Победителем в 2023 году стал алгоритм ASCON, включающий в себя лёгкую хеш-функцию.
• Хеш-функции используются в системах электронного голосования для обеспечения анонимности и целостности бюллетеней. В России с 2019 года применяется система дистанционного электронного голосования (ДЭГ), использующая криптографические хеши для защиты данных.
• Существуют так называемые «хеш-пазлы» (hash puzzles), в которых требуется найти сообщение, хеш которого начинается с заданного количества нулевых битов. Такие пазлы лежат в основе майнинга криптовалют и систем защиты от спама (proof-of-work).

Источники

• Шеннон К. «Теория связи в секретных системах» (1949)
• Диффи У., Хеллман М. «Новые направления в криптографии» (1976)
• Национальный институт стандартов и технологий США (NIST). «FIPS PUB 180-4: Secure Hash Standard (SHS)» (2015)
• Национальный институт стандартов и технологий США (NIST). «FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions» (2015)
• Ван С., Юй Х. «How to Break MD5 and Other Hash Functions» (2005)
• Стивенс М. и др. «The First Collision for Full SHA-1» (2017)
• Бернштейн Д. и др. «BLAKE2: simpler, smaller, fast as MD5» (2012)
• ГОСТ Р 34.11-2012 «Функция хэширования» (российский стандарт, известный как Streebog)