Что такое хэш-функция

Обновлено: 21.11.2024

Хеш-функции

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

Сопоставьте ключ с целым числом.
Сопоставьте целое число с сегментом.

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

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

Метод деления (Кормен) Выберите простое число, не близкое к степени двойки. h(k) = k mod m. Плохо работает для многих типов шаблонов во входных данных.

Вариант Кнута на делении h(k) = k(k+3) mod m. Предположительно работает намного лучше, чем метод прямого деления.

Метод умножения (Кормен). Выберите m как степень числа 2. Пусть A будет некоторым случайным действительным числом. Кнут предлагает M = 0,5 * (sqrt (5) - 1). Затем сделайте следующее:

Похоже, этот метод нравится теоретикам.

Чтобы сделать это быстро с помощью целочисленной арифметики, пусть w будет количеством битов в слове (например, 32), а m равно 2^p. Затем вычислите:

Хеш-функции в этом разделе принимают последовательность целых чисел k=k1. kn и получить небольшое целочисленное значение сегмента h(k). m — размер хеш-таблицы (количество сегментов), который должен быть простым числом. Последовательность целых чисел может быть списком целых чисел или массивом символов (строкой).

При использовании следующих алгоритмов входные данные ki должны быть целыми числами без знака. Передача им целых чисел со знаком может привести к странному поведению.

Для каждого из этих алгоритмов пусть h будет выходным значением. Установите h равным 0. Пройдитесь по последовательности целых чисел, добавляя целые числа одно за другим к h. Алгоритмы различаются тем, как именно комбинировать целое число ki с h. Окончательное возвращаемое значение: h mod m.

Вариант CRC: выполнить 5-битный циклический сдвиг h влево. Потом XOR в ки. В частности:

Хэш PJW (Aho, Sethi, and Ullman, стр. 434–438): сдвиг h влево на 4 бита. Добавьте ки. Переместите верхние 4 бита h вниз. В частности:

Он использует все 32 бита. PJW использует только 24 бита. Это, вероятно, не является серьезной проблемой, так как конечное значение m будет намного меньше, чем любое из них.
5-битный сдвиг, вероятно, лучше, чем 4-битный. Предполагается, что сдвиги на 3, 4 и 5 бит работают нормально.
Объединение значений с помощью XOR, вероятно, немного лучше, чем их добавление. Однако, опять же, разница незначительна.

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

Томас Х. Кормен, Чарльз Э. Лейзерсон и Рональд Л. Ривест (1990) Введение в алгоритмы, MIT Press, Кембридж, Массачусетс, и Макгроу-Хилл, Нью-Йорк.

Альфред В. Ахо, Рави Сети и Джеффри Д. Ульман, Компиляторы: принципы, методы и инструменты, Addison-Wesley, 1986.

Дональд Кнут, Искусство компьютерного программирования, том 3: Сортировка и поиск, Addison-Wesley, 1973.

Эта страница была написана Маргарет Флек для CS 70 весной 2000 г. на основе цитируемых ссылок и примечаний Джеффа Куэннинга. Его поддерживает Джефф Куэннинг.

Хэш-функции и хэши

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

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

Вычисление хеш-таблицы:

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

Числа для хеширования: 22, 3, 18, 29

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

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

22 mod 10 = 2, значит, он помещается в слот 2.

3 mod 10 = 3, поэтому он помещается в слот 3.

18 mod 10 = 8, поэтому он помещается в слот 8.

29 mod 10 = 9, поэтому он помещается в слот 9.

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

Пример хэш-таблицы с конфликтами:

Числа для хеширования: 22, 9, 14, 17, 42

Как и раньше, хеш-таблица отображается справа.

Как и прежде, мы хешируем каждое значение в том виде, в котором оно появляется в строке значений, которые нужно хэшировать, начиная с первого значения. Первые четыре значения могут быть введены в хеш-таблицу без проблем. Однако именно последнее значение, 42, вызывает проблему. 42 mod 10 = 2, но уже есть значение в слоте 2 хеш-таблицы, а именно 22. Это коллизия.

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

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

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

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

Влияние грубой силы и парадокса дня рождения

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

\bar p(n) &= 1 \times \left(1-\frac\right) \times \left(1-\frac\right) \times \cdots \times \left(1-\frac\ справа) \\ &= < 365 \times 364 \times \cdots \times (365-n+1) \over 365^n >\\ &= < 365! \over 365^n (365-n)!>= \frac> = \frac<^P_n>\end " width="" height="" />

Следовательно, вероятность того, что любые два из n людей с одинаковым днем рождения действительно имеют один и тот же день рождения, равна 1 — ответ из приведенного выше уравнения. Как показано на диаграмме ниже (Википедия), требуется всего 23 человека, чтобы превысить 50% вероятность того, что два человека в одной комнате имеют одинаковый день рождения.

Гарантия подлинности: криптографические алгоритмы хеширования

Хеш-функции можно использовать для гарантии подлинности данных, если они предназначены для защиты от атак из вредоносных источников. Две такие хеш-функции — RIPEMD-160 и SHA-1.

Следует отметить, что из-за популярности SHA-1 RIPEMD-160, вероятно, не подвергался такому тщательному изучению, как SHA-1 или другие криптографические хеш-функции.

SHA-1 (FIPS PUB 180-1)

SHA-1 работает с сообщениями, длина которых кратна 512 байтам. Чтобы учесть это, он дополняет конец сообщения, чтобы получить сообщение, длина которого кратна 512. Он делает это, сначала добавляя 1 в конец сообщения, затем количество нулей, а затем 64. -битная длина исходного (незаполненного) сообщения. Результатом этого процесса будет сообщение, длина которого кратна 512 байтам.

Мы также должны определить ключи, которые будут использоваться в течение 80 раундов алгоритма SHA-1, которые должны быть следующими:

� 5A827999 для раундов с 0 по 19 (0

� 6ED9EBA1 для раундов с 20 по 39 (20

� 8F1BBCDC для раундов с 40 по 59 (40

� CA62C1D6 для раундов с 60 по 79 (60

Они помечены как K��_t в приведенных ниже функциях, где t обозначает номер текущего раунда.

Нам также необходимо определить f(B,C,D) для 80 итераций SHA-1, которые будут определены следующим образом. В более поздних частях алгоритма это обозначается как f_t( B,C,D), где t — число раундов.

Для раундов с 0 по 19 f( B,C,D) = (B & C) | (!Б и Г)

Для раундов с 20 по 39 f( B,C,D) = B XOR C XOR D

Для раундов с 40 по 59 f(B,C,D) = (B & C) | (Б и Г) | (С и Г)

Для раундов с 60 по 79 f( B,C,D) = B XOR C XOR D

Затем мы обрабатываем каждый 512-байтовый фрагмент этого сообщения по отдельности, используя следующий алгоритм:

Нам нужны два буфера по пять 32-битных слов и временное значение. Первый буфер будет состоять из H₀, H₁, H�₂, H₃, H₄, а второй буфер будет состоять из A, B, C, D и E. Временное значение будет называться T ниже.

Для начала мы инициализируем H₀ значением 67452301, H₁ значением EFCDAB89, H₂ значением 98BADCFE, H_{3< /sub> на 10325476 и H₄ на C3D2E1F0.}

Затем мы берем каждый 512-байтовый блок сообщения и разделяем его на 16 32-байтовых слов, от W₀ до W₁₅. Чтобы вычислить от W₁₇ до W₇₉, используйте следующее уравнение:

Затем, чтобы вычислить дайджест сообщения, или хэш SHA-1, мы делаем следующее, вводя цикл for, который проходит через 80 итераций (начиная с t=0 и заканчивая t=79):

T = A f( B,C,D) + E + W_t + K_t (где все сложения являются сложениями по модулю 2 32 )

В самом конце дайджест сообщения представляет собой просто объединение H₀, H₁, H₂, H₃ и Н₄.

Визуализация раунда алгоритма SHA-1

Ниже на изображении показано, что происходит с A, B, C, D и E во время одной из 80 итераций хеш-функции SHA-1 (Википедия):

В 2007 году Национальный институт стандартов и технологий NIST предложил миру новую криптографическую хэш-функцию, которая заменит SHA-1 и SHA-2. В октябре 2012 г. NIST объявил Кекчака победителем конкурса SHA-3.

Джейк Франкенфилд — опытный писатель, освещающий широкий спектр тем деловых новостей. Его работы публиковались, в частности, в Investopedia и The New York Times. Он проделал обширную работу и исследования в области Facebook и сбора данных, Apple и пользовательского опыта, блокчейна и финансовых технологий, а также криптовалюты и будущего денег.

Амилкар Чаварриа — предприниматель в области финансовых технологий и блокчейна, обладающий более чем десятилетним опытом запуска компаний. Он преподает криптографию, блокчейн и финтех в Корнелле с 2019 года и в Массачусетском технологическом институте и Уортоне с 2021 года. Он консультирует правительства, финансовые учреждения, регулирующие органы и стартапы. Он также занимал руководящие должности в Goldman Sachs и BlackRock.

Кирстен Рорс Шмитт – опытный профессиональный редактор, писатель, корректор и специалист по проверке фактов. У нее есть опыт в области финансов, инвестиций, недвижимости и всемирной истории. На протяжении всей своей карьеры она писала и редактировала контент для многочисленных потребительских журналов и веб-сайтов, составляла резюме и контент для социальных сетей для владельцев бизнеса, а также создавала материалы для академических кругов и некоммерческих организаций. Кирстен также является основателем и директором Your Best Edit; найдите ее в LinkedIn и Facebook.

Что такое криптографические хеш-функции?

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

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

Ключевые выводы

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

Как работают криптографические хеш-функции

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

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

В частности, криптографические хеш-функции обладают следующими тремя свойствами:

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

Описанные выше три свойства желательны, но не всегда могут быть реализованы на практике. Например, несоответствие выборочных пространств для входных и выходных хэшей гарантирует возможность коллизий. Например, в 2017 году инициатива MIT Digital Currency Initiative обнаружила уязвимость коллизий в IOTA.

Примеры криптографических хеш-функций

Криптографические хэш-функции широко используются в криптовалютах для анонимной передачи информации о транзакциях. Например, биткойн, оригинальная и крупнейшая криптовалюта, использует в своем алгоритме криптографическую хеш-функцию SHA-256. Точно так же IOTA, платформа для Интернета вещей, имеет собственную криптографическую хэш-функцию Curl.

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

Подтверждение пароля

Создание и проверка подписи

Проверка подписи — это математический процесс, используемый для проверки подлинности цифровых документов или сообщений. Действительная цифровая подпись, если выполняются предварительные условия, дает получателю надежное доказательство того, что сообщение было создано известным отправителем и что сообщение не было изменено при передаче. Схема цифровой подписи обычно состоит из трех алгоритмов: алгоритм генерации ключа; алгоритм подписи, который на основании сообщения и закрытого ключа создает подпись; и алгоритм проверки подписи. Технология Merkle Trees, используемая в криптовалютах, является своего рода цифровой подписью.

Проверка целостности файла и сообщения

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

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

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

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

Возможности хеш-функций

Типичные особенности хеш-функций —

Вывод фиксированной длины (хэш-значение)

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

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

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

Хеш-функция с n-битным выходом называется n-битной хэш-функцией. Популярные хэш-функции генерируют значения от 160 до 512 бит.

Эффективность работы

Как правило, для любой хеш-функции h с входными данными x вычисление h(x) является быстрой операцией.

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

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

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

Сопротивление перед изображением

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

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

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

Второе сопротивление перед изображением

Это свойство означает, что при заданном вводе и его хэше будет сложно найти другой ввод с таким же хэшем.

Другими словами, если хэш-функция h для входных данных x дает хэш-значение h(x), то должно быть трудно найти любое другое входное значение y, такое что h(y) = h(x).

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

Сопротивление столкновениям

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

Другими словами, для хэш-функции h трудно найти любые два разных входа x и y, такие что h(x) = h(y).

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

Из-за этого свойства злоумышленнику очень сложно найти два входных значения с одинаковым хешем.

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

Проектирование алгоритмов хеширования

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

Размер каждого блока данных зависит от алгоритма. Обычно размер блока составляет от 128 до 512 бит. На следующем рисунке показана хэш-функция —

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

Этот процесс повторяется столько раз, сколько требуется для хеширования всего сообщения. Схема алгоритма хеширования изображена на следующем рисунке —

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

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

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

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

Применение хеш-функций

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

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

Хэш-функции обеспечивают защиту хранилища паролей.

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

Файл паролей состоит из таблицы пар в форме (идентификатор пользователя, h(P)).

Процесс входа показан на следующем рисунке —

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

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

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

Процесс показан на следующем рисунке —

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

Читайте также: