Хэш-функции

Хэш-функции Криптография

Криптографические хэш-функции призваны преобразовать входную последовательность произвольного размера в выходное значение фиксированной длины. Термин «хэш-функция» используется также для обозначения функции отображения при доступе к хэш-таблицам — структурам данных, используемых во многих алгоритмах. У таких функций много свойств, делающих их схожими с криптографическими хэш-функциями, но это разные вещи, и ни в коем случае не стоит путать хэш-функции для хэш-таблиц с криптографическими хэш-функциями. В этой книге рассказывается только о криптографических хэш-функциях.

Читайте: Как заработать на инвестициях в искусственный интеллект? Краудфандинг Daisy от компании EndoTech. Обзор и отзывы о смарт-контракте

Криптографические хэш-функции применяются в криптографии повсеместно: в протоколах аутентификации, цифровой подписи, в генераторах псевдослучайных последовательностей и т. д.

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

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

Хэш-функция должна отображать входные данные произвольного размера в выходной набор бит фиксированного размера. Отображение должно быть равновероятным и случайным.

Похожие требования предъявляются к функциям вычисления контрольных сумм (Cyclical Redundancy Check, CRC), таким как CRC32 или Adler32. Но контрольные суммы призваны, в первую очередь, обнаруживать случайные нарушения целостности. Так что задача подбора двух сообщений, контрольные суммы для которых будут совпадать, или нахождения сообщения с заданным значением контрольной суммы может быть решена эффективно. Например, достаточно откорректировать всего 4 идущих подряд байта, расположенных в любом месте изменяемого сообщения, чтобы значение CRC32 для этого сообщения осталось таким же, как до внесения изменений. Поэтому контрольные суммы (обычно очень простые в реализации) не стоит использовать в криптографии.

Если на выходе хэш-функции, реализующей идеальнсюслулайное равновероятное отображение, получается, например, 128-битовое значение и хэш-функция была вычислена от 2128 разных сообщений, это не значит, что каждое из 2128 возможных выходных значений получилось ровно один раз. Действительно, предположим, что мы вычислили хэш ровно от половины (2127) входных сообщений, и получили 2127 разных выходных значений, т. е. не было ни одного повторения. Учитывая тот факт, что отображение случайно и равновероятно значение хэш-функции от следующего сообщения с вероятностью [/2 будет совпадать с одним из уже полученных значений. И с каждым новым значена хэша вероятность возникновения коллизии будет только возрастать.

Результат вычисления хэш-функции

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

Для того чтобы хэш не вырождался при циклическом вычислении, необходимо на каждом раунде подавать на вход хэш-функции некоторые новые данные, например номер раунда.

Оцените статью
Добавить комментарий