Каким критериям должна удовлетворять хорошая хэш функция
Идеальное хеширование используется в задачах со статическим множеством ключей (т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно.
В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным. Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
Используется тот же принцип, что и в случае хеширования с цепочками: [math]n[/math] ключей хешируются в [math]m[/math] ячеек с использованием хеш-функции [math]h(k) = ((a\cdot k+b) \bmod p) \bmod m[/math] , случайно выбранной из семейства универсальных хеш-функций [math]H_[/math] , где [math]p[/math] — простое число, превышающее [math]m[/math] .
На данном уровне вместо создания списка ключей будем использовать вторичную хеш-таблицу [math]S_j[/math] , хранящую все ключи, хешированные функцией [math]h[/math] в ячейку [math]j[/math] , со своей функцией [math]h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j[/math] , выбранной из множества [math]H_[/math] . Путем точного выбора хеш-функции [math]h_j[/math] мы можем гарантировать отсутствие коллизий на этом уровне. Для этого требуется, чтобы размер [math]m_j[/math] хеш-таблицы [math]S_j[/math] был равен квадрату числа [math]n_j[/math] ключей, хешированных функцией [math]h[/math] в ячейку [math]j[/math] .
Несмотря на квадратичную зависимость, ниже будет показано, что при корректном выборе хеш-функции первого уровня количество требуемой для хеш-таблицы памяти будет [math]O(n)[/math] .
Если [math]n[/math] ключей сохраняются в хеш-таблице размером [math]m=n^2[/math] c использованием хеш-функции [math]h[/math] , случайно выбранной из универсального множества хеш-функций, то математическое ожидание числа коллизий не превышает [math][/math] .
Всего имеется [math]\dbinom[/math] пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из универсального семейства хеш-функций [math]H[/math] , то для каждой пары вероятность возникновения коллизии равна [math][/math] . Пусть [math]X[/math] — случайная величина, которая подсчитывает количество коллизий. Если [math]m = n^2[/math] , то математическое ожидание числа коллизий равно
Это является очень хорошим результатом, если хотя бы вспомнить на примере парадокса дней рождения о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.
Если мы сохраняем [math]n[/math] ключей в хеш-таблице размеров [math]m=n[/math] c использованием хеш-функции [math]h[/math] , выбираемой случайным образом из универсального множества хеш-функций, то [math]E\left[\displaystyle \sum_
[math]E\left[\displaystyle \sum_^ n_j^2 \right] =[/math] [math] E\left[ \displaystyle \sum_^ (n_j + 2 \dbinom)\right] = [/math] [math] E\left[ \displaystyle \sum_^ n_j\right] + 2E\left[\displaystyle \sum_^ \dbinom\right] = [/math] [math] E\left[n\right] + 2E\left[\displaystyle \sum_^ \dbinom\right] = n + 2E\left[\displaystyle \sum_^ \dbinom \right][/math]
Первый переход в равенстве мы совершили благодаря формуле [math]a^2 = a + 2\cdot\dbinom[/math] . Далее мы воспользовались свойствами математического ожидания, в частности - линейности.
Очевидно, что [math]\displaystyle \sum_^ \dbinom[/math] - просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает [math]\binom = = [/math] А так как [math]m = n[/math] , то
Теперь выведем 2 следствия из этой теоремы.
Если мы сохраняем [math]n[/math] ключей в хеш-таблице размером [math]m=n[/math] с использованием хеш-функции [math]h[/math] , выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным [math]m_j=n_j^2[/math] [math](j=0,1. m-1)[/math] , то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает [math]2n[/math] .
Поскольку [math]m_j=n_j^2[/math] для [math]j=0,1. m-1[/math] , согласно предыдущей теореме:
Если мы сохраняем [math]n[/math] ключей в хеш-таблице размером [math]m=n[/math] с использованием хеш-функции [math]h[/math] , выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным [math]m_j=n_j^2[/math] [math](j=0,1. m-1)[/math] , то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее [math]4n[/math] , меньше чем [math][/math] .
Применим неравенство Маркова [math]P(X \geqslant t) \leqslant E[X]/t[/math]
Начинаем неделю с полезного материала приуроченного к запуску курса «Алгоритмы для разработчиков». Приятного прочтения.
Хеширование — отличный практический инструмент, с интересной и тонкой теорией. Помимо использования в качестве словарной структуры данных, хеширование также встречается во многих различных областях, включая криптографию и теорию сложности. В этой лекции мы опишем два важных понятия: универсальное хеширование (также известное как универсальные семейства хеш-функций) и идеальное хеширование.
Материал, освещенный в этой лекции, включает в себя:
- Формальная постановка и общая идея хеширования.
- Универсальное хеширование.
- Идеальное хеширование.
Мы рассмотрим основную проблему со словарем, которую мы обсуждали до этого, и рассмотрим две версии: статическую и динамическую:
- Статическая: дано множество элементов S, мы хотим хранить его таким образом, чтобы можно было быстро выполнять поиск.
- Например, фиксированный словарь.
- Динамическая: здесь у нас есть последовательность запросов на вставку, поиск и, возможно, удаление. Мы хотим сделать все это эффективно.
3. Основы хеширования
Формальная постановка для хеширования заключается в следующем.
- Ключи принадлежат некоторому большому множеству U. (Например, представьте, что U — набор всех строк длиной не более 80 символов ascii.)
- Есть некоторое множество ключей S в U, которое нам на самом деле нужно (ключи могут быть как статическими, так и динамическими). Пусть N = |S|. Представьте, что N гораздо меньше, чем размер U. Например, S — это множество имен учеников в классе, которое намного меньше, чем 128^80.
- Мы будем выполнять вставки и поиск с помощью массива A некоторого размера M и хеш-функции h: U → . Дан элемент x, идея хеширования состоит в том, что мы хотим хранить его в A[h(x)]. Обратите внимание, что если бы U было маленьким (например, 2-символьные строки), то можно было бы просто сохранить x в A[x], как в блочной сортировке. Проблема в том, что U большое, поэтому нам нужна хеш-функция.
- Нам нужен метод для разрешения коллизий. Коллизия — это когда h(x) = h(y) для двух разных ключей x и y. В этой лекции мы будем обрабатывать коллизии, определяя каждый элемент A как связанный список. Есть ряд других методов, но для проблем, на которых мы сосредоточимся здесь, это самый подходящий. Этот метод называется методом цепочек. Чтобы вставить элемент, мы просто помещаем его в начало списка. Если h — хорошая хеш-функция, то мы надеемся, что списки будут небольшими.
Желательные свойства. Основные желательные свойства для хорошей схемы хеширования:
- Ключи хорошо рассредоточены, чтобы у нас не было слишком много коллизий, так как коллизии влияют на время выполнения поиска и удаления.
- M = O(N): в частности, мы бы хотели, чтобы наша схема достигла свойства (1) без необходимости, чтобы размер таблицы M был намного больше, чем число элементов N.
- Функция h должна быстро вычисляться. В нашем сегодняшнем анализе мы будем рассматривать время для вычисления h(x) как константу. Тем не менее, стоит помнить, что она не должна быть слишком сложной, потому что это влияет на общее время выполнения.
Доказательство: по принципу Дирихле. В частности, чтобы рассмотреть контрапозиции, если бы каждое местоположение имело не более N — 1 элементов U, хэширующих его, то U мог бы иметь размер не более M (N — 1).
Вот ключевая идея: давайте использовать рандомизацию в нашей конструкции h, по аналогии с рандомизированной быстрой сортировкой. (Само собой разумеется, h будет детерминированной функцией). Мы покажем, что для любой последовательности операций вставки и поиска (нам не нужно предполагать, что набор вставленных элементов S является случайным), если мы выберем h таким вероятностным способом, производительность h в этой последовательности будет хорошо в ожидании. Таким образом, это та же самая гарантия, что и в рандомизированной быстрой сортировке или ловушках. В частности, это идея универсального хеширования.
Как только мы разработаем эту идею, мы будем использовать ее для особенно приятного приложения под названием «идеальное хеширование».
4. Универсальное хеширование
Определение 1. Рандомизированный алгоритм H для построения хеш-функций h: U →
универсален, если для всех x != y в U имеем
Мы также можем сказать, что множество H хеш-функций является универсальным семейством хеш-функций, если процедура «выбрать h ∈ H наугад» универсальна. (Здесь мы отождествляем множество функций с равномерным распределением по множеству.)
Теорема 2. Если H универсален, то для любого множества S ⊆ U размера N, для любого x ∈ U (например, который мы могли бы искать), если мы строим h случайным образом в соответствии с H, ожидаемое число коллизий между х и другими элементами в S не более N/M.
Доказательство: у каждого y ∈ S (y != x) есть не более 1 / M шанса столкновения с x по определению «универсального». Так,
- Пусть Cxy = 1, если x и y сталкиваются, и 0 в противном случае.
- Пусть Cx обозначает общее количество столкновений для x. Итак, Cx = Py∈S, y != x Cxy.
- Мы знаем, что E [Cxy] = Pr (x и y сталкиваются) ≤ 1 / M.
- Таким образом, по линейности ожидания E [Cx] = Py E [Cxy]
Следствие 3. Если H универсален, то для любой последовательности операций L вставки, поиска и удаления, в которых в системе одновременно может быть не более M элементов, ожидаемая общая стоимость L операций для случайного h ∈ H равна только O (L) (просмотр времени для вычисления h как константы).
Доказательство: для любой данной операции в последовательности ее ожидаемая стоимость постоянна по теореме 2, поэтому ожидаемая общая стоимость L операций равна O (L) по линейности ожидания.
Вопрос: можем ли мы на самом деле построить универсальную H? Если нет, то это все довольно бессмысленно. К счастью, ответ — да.
4.1. Создание универсального хеш-семейства: матричный метод
Допустим, ключи имеют длину u-бит. Скажем, размер таблицы M равен степени 2, поэтому индекс длиной b-битов с M = 2b.
Что мы сделаем, это выберем h в качестве случайной матрицы 0/1 b-by-u и определим h (x) = hx, где мы добавим mod 2. Эти матрицы короткие и толстые. Например:
Утверждение 4. Для x != y Prh [h (x) = h (y)] = 1 / M = 1 / 2b.
Доказательство: во-первых, что означает умножение h на x? Мы можем думать об этом как о добавлении некоторых из столбцов h (делая векторное сложение mod 2), где 1 бит в x указывает, какие из них добавить. (например, мы добавили 1-й и 3-й столбцы h выше)
Теперь возьмем произвольную пару ключей x, y такую, что x != y. Они должны где-то отличаться, так что, скажем, они различаются по i-й координате, а для конкретности скажем xi = 0 и yi = 1. Представьте, что сначала мы выбрали все h, кроме i-го столбца. По оставшимся выборкам i-го столбца h (x) является фиксированным. Однако каждая из 2b различных настроек i-го столбца дает различное значение h (y) (в частности, каждый раз, когда мы переворачиваем бит в этом столбце, мы переворачиваем соответствующий бит в h (y)). Таким образом, есть точно 1 / 2b шанс, что h (x) = h (y).
Существуют и другие методы построения универсальных хеш-семейств, основанных также на умножении простых чисел (см. Раздел 6.1).
Следующий вопрос, который мы рассмотрим: если мы исправим множество S, сможем ли мы найти хеш-функцию h такую, что все поиски будут иметь постоянное время? Ответ — да, и это приводит к теме идеального хеширования.
5. Идеальное хеширование
Мы говорим, что хеш-функция является идеальной для S, если все поиски происходят за O(1). Вот два способа построения идеальных хеш-функций для заданного множества S.
5.1 Метод 1: решение в пространстве O(N2)
Скажем, мы хотим иметь таблицу, размер которой квадратичен по размеру N нашего словаря S. Тогда вот простой метод построения идеальной хеш-функции. Пусть H универсален и M = N2. Тогда просто выберите случайный h из H и попробуйте! Утверждение состоит в том, что есть по крайней мере 50% шанс, что у нее не будет коллизий.
Утверждение 5. Если H универсален и M = N2, то Prh∼H (нет коллизий в S) ≥ 1/2.
• Сколько пар (x, y) есть в S? Ответ:
• Для каждой пары вероятность их столкновения составляет ≤ 1 / M по определению универсальности.
• Итак, Pr (существует коллизия) ≤ / M
Это как другая сторона «парадокса дня рождения». Если количество дней намного больше, чем количество людей в квадрате, то есть разумный шанс, что ни у одной пары не будет одинакового дня рождения.
Итак, мы просто выбираем случайную h из H, и если возникают какие-либо коллизии, мы просто выбираем новую h. В среднем нам нужно будет сделать это только дважды. Теперь, что если мы хотим использовать только пространство O(N)?
5.2 Метод 2: решение в пространстве O(N)
Вопрос о том, можно ли достичь идеального хеширования в пространстве O(N), был в течение некоторого времени открытым: «Должны ли таблицы быть отсортированы?». То есть для фиксированного набора можно получить постоянное время поиска только с линейным пространством? Была серия все более и более сложных попыток, пока, наконец, она не была решена с использованием хорошей идеи универсальных хеш-функций в двухуровневой схеме.
Способ заключается в следующем. Сначала мы будем хэшировать в таблицу размера N, используя универсальное хеширование. Это приведет к некоторым коллизиям (если только нам не повезет). Однако затем мы перехешируем каждую корзину, используя метод 1, возводя в квадрат размер корзины, чтобы получить нулевые коллизии. Таким образом, схема состоит в том, что у нас есть хеш-функция первого уровня h и таблица A первого уровня, а затем N хеш-функций второго уровня h1,…, hN и N таблицы второго уровня A1,…, А.Н… Чтобы найти элемент x, мы сначала вычисляем i = h (x), а затем находим элемент в Ai [hi (x)]. (Если бы вы делали это на практике, вы могли бы установить флаг так, чтобы вы делали второй шаг, только если на самом деле были коллизии с индексом i, а в противном случае просто помещали бы сам x в A [i], но давайте не будем об этом беспокоиться здесь .)
Скажем, хеш-функция h хеширует n элементов S в местоположение i. Мы уже доказывали (анализируя метод 1), что мы можем найти h1,…, hN, так что общее пространство, используемое во вторичных таблицах, равно Pi (ni) 2. Осталось показать, что мы можем найти функцию первого уровня h такую, что Pi (ni) 2 = O (N). На самом деле, мы покажем следующее:
Теорема 6. Если мы выберем начальную точку h из универсального множества H, то
Теперь, хитрый трюк заключается в том, что один из способов подсчитать это количество — подсчитать количество упорядоченных пар, у которых возникает коллизия, включая коллизии с самим собой. Например, если корзина имеет , то у d возникнет коллизия с каждым из , у e возникнет коллизия с каждым из , и у f возникнет коллизия с каждым из , поэтому мы получаем 9. Итак, мы имеем:
6. Дальнейшее обсуждение
6.1 Еще один метод универсального хеширования
Вот еще один метод построения универсальных хеш-функций, который немного более эффективен, чем матричный метод, приведенный ранее.
В матричном методе мы рассматривали ключ как вектор битов. В этом методе вместо этого мы будем рассматривать ключ x как вектор целых чисел [x1, x2,…, xk] с единственным требованием, чтобы каждый xi находился в диапазоне . Например, если мы хешируем строки длиной k, то xi может быть i-м символом (если размер нашей таблицы не менее 256) или i-й парой символов (если размер нашей таблицы не менее 65536). Кроме того, мы будем требовать, чтобы размер нашей таблицы M был простым числом. Чтобы выбрать хеш-функцию h, мы выберем k случайных чисел r1, r2,…, рк из и определить:
Доказательство того, что этот метод универсален, строится точно так же, как доказательство матричного метода. Пусть x и y два разных ключа. Мы хотим показать, что Prh (h (x) = h (y)) ≤ 1 / M. Поскольку x != y, должен быть случай, когда существует некоторый индекс i такой, что xi != yi. Теперь представьте, что сначала вы выбрали все случайные числа rj для j != i. Пусть h ′ (x) = Pj6 = i rjxj. Итак, выбрав ri, мы получим h (x) = h ′ (x) + rixi. Это означает, что у нас возникает коллизия между x и y именно тогда, когда
Поскольку M — простое, деление на ненулевое значение mod M является допустимым (каждое целое число от 1 до M −1 имеет мультипликативный обратный по модулю M), что означает, что существует ровно одно значение ri по модулю M, для которого выполняется приведенное выше уравнение истина, а именно ri = (h ′ (y) — h ′ (x)) / (xi — yi) mod M. Таким образом, вероятность этого происшествия равна точно 1 / M.
6.2 Другое использование хеширования
Предположим, у нас есть длинная последовательность элементов, и мы хотим увидеть, сколько разных элементов находятся в списке. Есть ли хороший способ сделать это?
Одним из способов является создать хеш-таблицу, а затем сделать один проход по последовательности, сделав для каждого элемента поиск и затем вставку, если его еще нет в таблице. Количество отдельных элементов — это просто количество вставок.
А теперь, что если список действительно огромен и у нас нет места для его хранения, но нам подойдёт приблизительный ответ. Например, представьте, что мы являемся маршрутизатором и наблюдаем, как проходит много пакетов, и мы хотим (приблизительно) увидеть, сколько существует различных IP-адресов источника.
Вот хорошая идея: скажем, у нас есть хеш-функция h, которая ведет себя как случайная функция, и давайте представим, что h (x) — действительное число от 0 до 1. Одна вещь, которую мы можем сделать, это просто отслеживать минимальный хеш стоимость произведена до сих пор (поэтому у нас не будет таблицы вообще). Например, если ключи 3,10,3,3,12,10,12 и h (3) = 0,4, h (10) = 0,2, h (12) = 0,7, то мы получим 0,2.
Дело в том, что если мы выберем N случайных чисел в [0, 1], ожидаемое значение минимума будет 1 / (N + 1). Кроме того, есть хороший шанс, что он довольно близок (мы можем улучшить нашу оценку, запустив несколько хеш-функций и взяв медиану минимумов).
Вопрос: зачем использовать хеш-функцию, а не просто выбирать случайное число каждый раз? Это потому, что мы заботимся о количестве различных элементов, а не только об общем количестве элементов (эта проблема намного проще: просто используйте счетчик. ).
Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.
О себе
Студент кафедры информационной безопасности.
О хэшировании
Здесь v — некоторая константа, часто ее называют инициализирующим вектором. Она выбирается
из различных соображений и может представлять собой секретную константу или набор случайных данных (выборку даты и времени, например).
При таком подходе свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции.
О статистических свойствах и требованиях
Как я уже говорил основным требованием к хэш-функциям является равномерность распределения их значений при случайном выборе значений аргумента. Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось. Это называется лавинным эффектом.
К ключевым функциям хэширования предъявляются следующие требования:
— невозможность фабрикации,
— невозможность модификации.
К бесключевым функциям предъявляют требования:
— однонаправленность,
— устойчивость к коллизиям,
— устойчивость к нахождению второго прообраза.
Это была теоретическая часть, которая пригодится нам в дальнейшем…
О популярных хэш-алгоритмах
Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).
Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.
Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.
Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.
Функция перестановок
Базовая функция перестановки состоит из раундов по пять шагов:
Тета, Ро, Пи, Хи, Йота
Далее будем использовать следующие обозначения:
Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как
Обозначим результат преобразования состояния функцией перестановки
Также обозначим функцию, которая выполняет следующее соответствие:
- обычная функция трансляции, которая сопоставляет биту бит ,
где - длина слова (64 бит в нашем случае)
Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.
Шаг
Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и
Схематическое представление функции:
Шаг
Отображение направлено на трансляции внутри слов (вдоль оси z).
Проще всего его описать псевдокодом и схематическим рисунком:
Шаг
Шаг представляется псевдокодом и схематическим рисунком:
Шаг
Шаг является единственный нелинейным преобразованием в
Псевдокод и схематическое представление:
Шаг
Отображение состоит из сложения с раундовыми константами и направлено на нарушение симметрии. Без него все раунды были бы эквивалентными, что делало бы его подверженным атакам, использующим симметрию. По мере увеличения раундовые константы добавляют все больше и больше асимметрии.
Ниже приведена таблица раундовых констант для бит
Все шаги можно объединить вместе и тогда мы получим следующее:
Где константы являются циклическими сдвигами и задаются таблицей:
Общие сведения
Криптографическая хеш-функция - это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера.
Для идеальной хеш-функции выполняются следующие условия:
Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.
Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.
На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.
Любой заинтересованный читатель задаст себе вопрос: "А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?"
Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит - это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:
Надеюсь, теперь нет сомнений в том, что это очень внушительное число!
Поэтому ничего не мешает нам сопоставлять длинному входному массиву данных массив фиксированной длины.
Итоги
В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm
Функция, которая преобразует данный большой номер телефона в небольшое практическое целое значение. Отображенное целочисленное значение используется в качестве индекса в хеш-таблице. Проще говоря, хеш-функция отображает большое число или строку в маленькое целое число, которое можно использовать в качестве индекса в хеш-таблице.
Что подразумевается под хорошей хэш-функцией?
Хорошая хеш-функция должна иметь следующие свойства:
- Эффективно вычислимо.
- Должны равномерно распределять ключи (каждая позиция таблицы одинаково вероятна для каждого ключа)
Например: Для телефонных номеров плохая хеш-функция состоит в том, чтобы брать первые три цифры. Лучшей функцией считается последние три цифры. Обратите внимание, что это может быть не самой лучшей хэш-функцией. Там могут быть лучшие способы.
На практике мы часто можем использовать эвристические методы для создания хэш-функции, которая хорошо работает. Качественная информация о распределении ключей может быть полезна в этом процессе проектирования. В общем, хеш-функция должна зависеть от каждого отдельного бита ключа, так что два ключа, которые отличаются только одним битом или одной группой битов (независимо от того, находится ли группа в начале, конце или середине ключа или присутствует во всем ключе) хэш в разные значения. Таким образом, хеш-функция, которая просто извлекает часть ключа, не подходит. Аналогично, если два ключа являются просто цифрами или символьными перестановками друг друга (например, 139 и 319) , они также должны хешироваться в разные значения.
Два эвристических метода — это хэширование делением и хэширование умножением :
- Метод мода:
- В этом методе для создания хеш-функций мы отображаем ключ в один из слотов таблицы, беря остаток ключа, разделенный на table_size. То есть хеш-функция
- Поскольку для этого требуется только одна операция деления, хеширование по делениям происходит довольно быстро.
- При использовании метода деления мы обычно избегаем определенных значений table_size, таких как table_size, которые не должны быть степенью числа, например r , так как если table_size = r ^ p , то h (ключ) — это только p младших битов ключа. Если мы не знаем, что все p-битовые комбинации младших разрядов одинаково вероятны, нам лучше разработать хеш-функцию, которая будет зависеть от всех битов ключа.
- Было обнаружено, что наилучшие результаты при использовании метода деления достигаются, когда размер таблицы прост. Однако, даже если table_size является простым, требуется дополнительное ограничение. Если r — это число возможных кодов символов на компьютере, и если table_size — это простое число, такое что r% table_size равно 1, то хеш-функция h (key) = key% table_size — это просто сумма двоичного представления символов в ключ мод table_size.
Пример:
- Предположим, что r = 256 и table_size = 17, в котором r% table_size, т.е. 256% 17 = 1.
- Таким образом, для ключа = 37596 , его хэш
- Но для ключа = 573 его хэш-функция также
- Отсюда видно, что с помощью этой хэш-функции многие ключи могут иметь одинаковый хэш. Это называется столкновением .
- Простое число, не слишком близкое к точной степени 2, часто является хорошим выбором для table_size.
где функция floor (x) , доступная в стандартной библиотеке math.h , возвращает целую часть действительного числа x, а frac (x) — дробную часть. [frac (x) = x — этаж (x)]
Применение хеш-функций
Рассмотрим несколько достаточно простых примеров применения хеш-функций:
• Верификация пароля
Проверка пароля обычно использует криптографические хеши. Хранение всех паролей пользователей в виде открытого текста может привести к массовому нарушению безопасности, если файл паролей будет скомпрометирован. Одним из способов уменьшения этой опасности является хранение в базе данных не самих паролей, а их хешей. При выполнении хеширования исходные пароли не могут быть восстановлены из сохраненных хеш-значений, поэтому если вы забыли свой пароль вам предложат сбросить его и придумать новый.
• Цифровая подпись
Подписываемые документы имеют различный объем, поэтому зачастую в схемах ЭП подпись ставится не на сам документ, а на его хеш. Вычисление хеша позволяет выявить малейшие изменения в документе при проверке подписи. Хеширование не входит в состав алгоритма ЭП, поэтому в схеме может быть применена любая надежная хеш-функция.
Предлагаю также рассмотреть следующий бытовой пример:
Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать решить задачу сам, но все же хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу (сохраняя решение в секрете). Затем, когда Боб сам придумает решение, Алиса может доказать, что она получила решение раньше Боба. Для этого ей нужно попросить Боба хешировать его решение и проверить, соответствует ли оно хеш-значению, которое она предоставила ему раньше.
Теперь давайте поговорим о SHA-3.
Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.
Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:
Способность противостоять атакам злоумышленников
• Производительность и стоимость
Вычислительная эффективность алгоритма и требования к оперативной памяти для программных реализаций, а также количество элементов для аппаратных реализаций
• Гибкость и простота дизайна
Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности
В финальный тур попали всего 5 алгоритмов:
Победителем и новым SHA-3 стал алгоритм Keccak.
Давайте рассмотрим Keccak более подробно.
Keccak
Хеш-функции семейства Keccak построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, а затем результат Z «отжимается» из губки.
Любая губчатая функция Keccak использует одну из семи перестановок которая обозначается , где
перестановки представляют собой итерационные конструкции, состоящие из последовательности почти одинаковых раундов. Число раундов зависит от ширины перестановки и задаётся как где
В качестве стандарта SHA-3 была выбрана перестановка Keccak-f[1600], для неё количество раундов
Далее будем рассматривать
Давайте сразу введем понятие строки состояния, которая играет важную роль в алгоритме.
Строка состояния представляет собой строку длины 1600 бит, которая делится на и части, которые называются скоростью и ёмкостью состояния соотвественно.
Соотношение деления зависит от конкретного алгоритма семейства, например, для SHA3-256
В SHA-3 строка состояния S представлена в виде массива слов длины бит, всего бит. В Keccak также могут использоваться слова длины , равные меньшим степеням 2.
Алгоритм получения хеш-функции можно разделить на несколько этапов:
• Строка P делится на n блоков длины
• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.
• «Отжимание»: пока длина результата меньше чем , где - количество бит в выходном массиве хеш-функции, первых бит строки состояния добавляется к результату . После каждой такой операции к строке состояния применяется функция перестановок и данные продолжают «отжиматься» дальше, пока не будет достигнуто значение длины выходных данных .
Все сразу станет понятно, когда вы посмотрите на картинку ниже:
Функция дополнения
Свойства
Криптографическая хеш-функция должна уметь противостоять всем известным типам криптоаналитических атак.
В теоретической криптографии уровень безопасности хеш-функции определяется с использованием следующих свойств:
Pre-image resistance
Second pre-image resistance
Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что
Collision resistance
Давайте чуть более подробно поговорим о каждом из перечисленных свойств.
Несмотря на то, что хеш-функций без коллизий не существует, некоторые из них достаточно надежны и считаются устойчивыми к коллизиям.
Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что
Отсюда становится ясно, что атака по нахождению второго прообраза включает в себя поиск коллизии. Поэтому любая хеш-функция, устойчивая к коллизиям, также устойчива к атакам по поиску второго прообраза.
Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.
В частности, хеш-функция должна вести себя как можно более похоже на случайную функцию, оставаясь при этом детерминированной и эффективно вычислимой.
Читайте также: