Хэширование¶
В предыдущих разделах мы смогли усовершенствовать наши алгоритмы поиска, используя преимущества информации о том, где элементы хранятся относительно друг друга. Например, зная, что список упорядочен, мы можем осуществлять поиск за логарифмическое время, используя бинарный алгоритм. В этом разделе мы попытаемся пойти ещё на шаг дальше: построить такую структуру данных, в которой можно будет осуществлять поиск за время \(O(1)\) . Эту концепцию называют хэшированием.
Теперь нам надо знать больше, чем просто расположение элемента, когда мы ищем его в коллекции. Если каждый элемент находится там, где ему следует быть, то поиск может использовать только сравнения для обнаружения присутствия искомого. Однако, дальше мы увидим, что это, как правило, не единственный выход.
Хэш-таблица — это коллекция элементов, которые сохраняются таким образом, чтобы позже их было легко найти. Каждая позиция в хэш-таблице (часто называемая слотом) может содержать собственно элемент и целое число, начинающееся с нуля. Например, у нас есть слот 0, слот 1, слот 2 и так далее. Первоначально хэш-таблица не содержит элементов, так что каждый из них пуст. Мы можем сделать реализацию хэш-таблицы, используя список, в котором каждый элемент инициализирован специальным значением Python None . Рисунок 4 демонстрирует хэш-таблицу размером \(m=11\) . Другими словами, в ней есть \(m\) слотов, пронумерованных от 0 до 10.
Рисунок 4: Хэш-таблица с 11-ю пустыми слотами
Связь между элементом и слотом, в который он кладётся, называется хэш-функцией. Она принимает любой элемент из коллекции и возвращает целое число из диапазона имён слотов (от 0 до \(m-1\) ). Предположим, что у нас есть набор целых чисел 54, 26, 93, 17, 77 и 31. Наша первая хэш-функция, иногда называемая “методом остатков”, просто берёт элемент и делит его на размер таблицы, возвращая остаток в качестве хэш-значения ( \(h(item)=item \% 11\) ). В таблице 4 представлены все хэш-значения чисел из нашего примера. Обратите внимание: метод остатков (модульная арифметика) обычно присутствует в той или иной форме во всех хэш-функциях, поскольку результат должен лежать в диапазоне имён слотов.
| Элемент | Хэш-значение |
|---|---|
| 54 | 10 |
| 26 | 4 |
| 93 | 5 |
| 17 | 6 |
| 77 | 0 |
| 31 | 9 |
Поскольку хэш-значения могут быть посчитаны, мы можем вставить каждый элемент в хэш-таблицу на определённое место, как это показано на рисунке 5. Обратите внимание, что теперь заняты 6 из 11 слотов. Это называется фактором загрузки и обычно обозначается \(\lambda = \frac \) . В этом примере \(\lambda = \frac \) .
Рисунок 5: Хэш-таблица с шестью элементами
Теперь, когда мы хотим найти элемент, мы просто используем хэш-функцию, чтобы вычислить имя слота элемента и затем проверить по таблице его наличие. Эта операция поиска имеет \(O(1)\) , поскольку на вычисление хэш-значения требуется константное время, как и на переход по найденному индексу. Если всё находится там, где ему положено, то мы получаем алгоритм поиска за константное время.
Возможно, вы уже заметили, что такая техника работает только если каждый элемент отображается на уникальную позицию в хэш-таблице. Например, если следующим в нашей коллекции будет элемент 44, то он будет иметь хэш-значение 0 ( \(44 \% 11 == 0\) ). А так как 77 тоже имеет хэш-значение 0, то у нас проблемы. В соответствии с хэш-функцией два или более элементов должны иметь один слот. Это называется коллизией (иногда “столкновением”). Очевидно, что коллизии создают проблемы для техники хэширования. Позднее мы обсудим их в деталях.
Хэш-функции¶
Для заданной коллекции элементов хэш-функция, связывающая каждый из них с уникальным слотом, называется идеальной хэш-функцией. Если мы знаем, что ни один элемент коллекции никогда не изменится, то возможно создать идеальную хэш-функцию (см. упражнения, чтобы узнать об этом больше). К сожалению, для произвольного набора элементов не существует систематического способа сконструировать идеальную хэш-функцию. К счастью, для эффективной работы она нам и не нужна.
Один из способов всегда иметь идеальную хэш-функцию состоит в увеличении размера хэш-таблицы таким образом, чтобы в ней могло быть размещено каждое из возможных значений элементов. Таким образом гарантируется уникальность слотов. Хотя такой подход практичен для малого числа элементов, при возрастании их количества он перестаёт быть осуществимым. Например, для девятизначных индексов социального страхования потребуется порядка миллиарда слотов. Даже если мы захотим всего лишь хранить данные для класса из 25 студентов, то потратим на это чудовищное количество памяти.
Наша цель: создать хэш-функцию, которая минимизировала бы количество коллизий, легко считалась и равномерно распределяла элементы в хэш-таблице. Существует несколько распространённых способов расширить простой метод остатков. Рассмотрим некоторые из них.
Метод свёртки для создания хэш-функций начинает с деления элемента на составляющие одинаковой величины (кроме последнего, который может иметь отличающийся размер). Эти кусочки складываются вместе и дают результирующее хэш-значение. Например, если наш элемент — телефонный номер 436-555-4601, то мы можем взять цифры и рабить их на группы по два (43, 65, 55, 46, 01). После сложения \(43+65+55+46+01\) мы получим 210. Если предположить, что хэш-таблица имеет 11 слотов, то нужно выполнить дополнительный шаг, поделив это число на 11 и взяв остаток. В данном случае \(210\ \%\ 11\) равно 1, так что телефонный номер 436-555-4601 хэшируется в слот 1. Некоторые методы свёртки идут на шаг дальше и перед сложением переворачивают каждый из кусочков разбиения. Для примера выше мы бы получили \(43+56+55+64+01 = 219\) , что даёт \(219\ \%\ 11 = 10\) .
Другая числовая техника для создания хэш-функций называется методом средних квадратов. Сначала значение элемента возводится в квадрат, а затем из получившихся в результате цифр выделяется некоторая порция. Например, если элемент равен 44, то мы прежде вычислим \(44 ^ = 1,936\) . Выделив две средние цифры (93) и выполнив шаг получения остатка, мы получим 5 ( \(93\ \%\ 11\) ). Таблица 5 показывает элементы, к которым применили оба метода: остатков и средних квадратов. Убедитесь, что понимаете, как эти значения были получены.
| Элемент | Остаток | Средний квадрат |
|---|---|---|
| 54 | 10 | 3 |
| 26 | 4 | 7 |
| 93 | 5 | 9 |
| 17 | 6 | 8 |
| 77 | 0 | 4 |
| 31 | 9 | 6 |
Мы также можем создать хэш-функцию для символьных элементов (например, строк). Слово “cat” можно рассматривать, как последовательность кодов его букв.
>>> ord('c') 99 >>> ord('a') 97 >>> ord('t') 116
Затем можно взять эти три кода, сложить их и спользовать метод остатков, чтобы получить хэш-значение (см. рисунок 6). Листинг 1 демонстрирует функцию hash , принимающую строку и размер таблицы и возвращающую хэш-значение из диапазона от 0 до tablesize -1.
Рисунок 6: Хэширование строки с использованием кодов символов
Листинг 1
def hash(astring, tablesize): sum = 0 for pos in range(len(astring)): sum = sum + ord(astring[pos]) return sum%tablesize
Интересное наблюдение: когда мы используем эту хэш-функцию, анаграммы всегда будут иметь одинаковое хэш-значение. Чтобы исправить это, следует использовать позицию символа в качестве веса. Рисунок 7 показывает один из вариантов использования позиционного значения в качестве весового фактора. Модификацию функции hash мы оставляем в качестве упражнения.
Рисунок 7: Хэширование строки с использованием кодов символов и весов
Вы можете придумать другие числовые способы вычисления хэш-значений для элементов коллекции. Важно только помнить, что эффекитвная хэш-функция не должна являться доминирующей частью процессов хранения и поиска. Если она слишком сложна, то требует много работы на вычисление имени слота. В этом случае проще было бы использовать последовательный или бинарный поиск, описанные выше. Таким образом, сама идея хэширования терпит поражение.
Разрешение коллизий¶
Вернёмся к проблеме коллизий. Когда два элемента хэшируются в один слот, нам требуется систематический метод для размещения в хэш-таблице второго элемента. Этот процесс называется разрешением коллизии. Как мы утверждали ранее, если хэш-функция идеальна, то коллизии никогда не произойдёт. Однако, поскольку часто такое положение дел невозможно, разрешение коллизий становится важной частью хэширования.
Одним из методов разрешения коллизий является просмотр хэш-таблицы и поиск другого свободного слота для размещения в нём элемента, создавшего проблему. Простой способ сделать это — начать с оригинальной позиции хэш-значения и перемещаться по слотам определённым образом до тех пор, пока не будет найден пустой. Заметьте: нам может понадобиться вернуться обратно к первому слоту (циклически), чтобы охватить хэш-таблицу целиком. Этот процесс разрешения коллизий называется открытой адресацией, поскольку пытается найти следующий свободный слот (или адрес) в хэш-таблице. Систематически посещая каждый слот по одному разу, мы действуем в соответствии с техникой открытой адресации, называемой линейным пробированием.
Рисунок 8 показывает расширенный набор целых элементов после применения простой хэш-функции метода остатков (54,26,93,17,77,31,44,55,20). В таблице 4 выше собраны хэш-значения оригинальных элементов, а на рисунке 5 представлено первоначальное содержимое хэш-таблицы. Когда мы пытаемся поместить 44 в слот 0, возникает коллизия. При линейном пробировании мы последовательно — слот за слотом — просматриваем таблицу, до тех пор, пока не найдём открытую позицию. В данном случае это оказался слот 1.
В следующий раз 55, которое должно разместиться в слоте 0, будет положено в слот 2 — следующую незанятую позицию. Последнее значение 20 хэшируется в слот 9. Но поскольку он занят, мы делаем линейное пробирование. Мы посещаем слоты 10, 0, 1, 2 и наконец находим пустой слот на позиции 3.
Рисунок 8: Разрешение коллизий путём линейного пробирования
Поскольку мы построили хэш-таблицу с помощью открытой адресации (или линейного пробирования), важно использовать тот же метод при поиске элемента. Предположим, мы хотим найти число 93. Вчисление его хэш-значения даст 5. Обнаружив в пятом слоте 93, мы вернём True . Но что если мы ищем 20? Теперь хэш-значение равно 9, а слот 9 содержит 31. Нельзя просто вернуть False , поскольку здесь могла быть коллизия. Так что мы вынуждены провести последвательный поиск, начиная с десятой позиции, который закончится, когда найдётся число 20 или пустой слот.
Недостатком линейного пробирования является его склонность к кластеризации: элементы в таблице группируются. Это означает, что если возникает много коллизий с одним хэш-значением, то окружающие его слоты при линейном пробировании будут заполнены. Это начнёт оказывать влияние на вставку других элементов, как мы наблюдали выше при попытке вставить в таблицу число 20. В итоге, кластер значений, хэшируемых в 0, должен быть пропущен, чтобы найти вакантное место. Этот кластер показан на рисунке 9.
Рисунок 9: Кластер элементов для слота 0
Одним из способов иметь дело с кластеризацией является расширение линейного пробирования таким образом, чтобы вместо последовательного поиска следующего свободного места мы пропускали слоты, получая таким образом более равномерное распределение элементов, вызвавших коллизии. Потенциально это уменьшит возникающую кластеризацию. Рисунок 10 показывает элементы после разрешения коллизий с использованием пробирования “плюс 3”. Это означает, что при возникновении коллизии, мы рассматриваем каждый третий слот до тех пор, пока не найдём пустой.
Рисунок 10: Разрешение коллизий с использованием методики “плюс 3”
Общее название для такого процесса поиска другого слота после коллизии — повторное хэширование. С помощью простого линейного пробирования повторная хэш-функция выглядит как \(newhashvalue = rehash(oldhashvalue)\) , где \(rehash(pos) = (pos + 1) \% sizeoftable\) . Повторное хэширование “плюс 3” может быть определёно как \(rehash(pos) = (pos+3) \% sizeoftable\) . В общем случае: \(rehash(pos) = (pos + skip) \% sizeoftable\) . Важно отметить, что величина “пропуска” должна быть такой, чтобы в конце концов пройти по всем слотам. В противном случае часть таблицы окажется неиспользованной. Для обеспечения этого условия часто предполагается, что размер таблицы является простым числом. Вот почему в примере мы использовали 11.
Ещё одним вариантом линейного пробирования является квадратичное пробирование. Вместо использования константного значения “пропуска”, мы используем повторную хэш-функцию, которая инкрементирует хэш-значение на 1, 3, 5, 7, 9 и так далее. Это означает, что если первое хэш-значение равно \(h\) , то последующими будут \(h+1\) , \(h+4\) , \(h+9\) , \(h+16\) и так далее. Другими словами, квадратичное пробирование использует пропуск, состоящий из следующих один за другим полных квадратов. Рисунок 11 демонстрирует значения из нашего примера после использования этой методики.
Рисунок 11: Разрешение коллизий с помощью квадратичного пробирования
Альтернативным методом решения проблемы коллизий является разрешение каждому слоту содержать ссылку на коллекцию (или цепочку) значений. Цепочки позволяют множеству элементов занимать одну и ту же позицию в хэш-таблице. Чем больше элементов хэшируются в одно место, тем сложнее найти элемент в коллекции. Рисунок 12 показывает, как элементы добавляются в хэш-таблицу с использованием цепочек для разрешения коллизий.
Рисунок 12: Разрешение коллизий с помощью цепочек
Когда мы хотим найти элемент, мы используем хэш-функцию для генерации номера слота, в котором он должен размещаться. Поскольку каждый слот содержит коллекцию, мы используем различные техники поиска, чтобы определить, представлен ли он в ней. Преимуществом данного подхода является вероятность получить гораздо меньше элементов в каждом слоте, так что поиск будет более эффективным. Более подробный анализ мы проведём в конце этой главы.
Q-50: В хэш-таблице размером 13 какой индекс будет связан со следующими двумя ключами 27, 130?
Q-51: Предположим, у вас есть следующий набор ключей для вставки в хэш-таблицу, содержащую ровно 11 значений: 113 , 117 , 97 , 100 , 114 , 108 , 116 , 105 , 99. Что из следующего лучше всего демонстрирует содержимое таблицы после вставки всех ключей с использованием линейного пробирования?
Реализация абстрактного типа данных Map ¶
Одной из наиболее используемых коллекций Python являются словари. Напомним, что словарь — ассоциативный тип данных, в котором можно хранить пары ключ-значение. Ключи используются для поиска ассоциативных значений данных. Мы часто называем эту идею отображением.
Абстрактный тип данных Map можно определить следующим образом. Его структура — неупорядоченная коллекция ассоциаций между ключами и значениями. Все ключи уникальны, таким образом поддерживаются отношения “один к одному” между ключами и значениями. Операции для такого типа данных представлены ниже:
- Map() Создаёт новый пустой экземпляр типа. Возвращает пустую коллекцию отображений.
- put(key, val) Добавляет новую пару ключ-значение в отображение. Если такой ключ уже имеется, то заменяет старое значение новым.
- get(key) Принимает ключ, возвращает соответствующее ему значение из коллекции или None .
- del Удаляет пару ключ-значение из отображения, используя оператор вида del map[key] .
- len() Возвращает количество пар ключ-значение, хранящихся в коллекции.
- in Возвращает True для оператора вида key in map , если данный ключ присутствует в коллекции, или False в противном случае.
Одним из больших преимуществ словарей является то, что, имея ключ, мы можем найти ассоциированное с ним значение очень быстро. Для обеспечения надлежащей скорости требуется реализация, поддерживающая эффективный поиск. Мы можем использовать список с последовательным или бинарным поиском, но правильнее будет воспользоваться хэш-таблицей, описанной выше, поскольку поиск элемента в ней может приближаться к производительности \(O(1)\) .
В листинге 2 мы используем два списка, чтобы создать класс HashTable , воплощающий абстрактный тип данных Map . Один список, называемый slots , будет содержать ключи элементов, а параллельный ему список data — значения данных. Когда мы находим ключ, на соответствующей позиции в списке с данными будет находиться связанное с ним значение. Мы будем работать со списком ключей, как с хэш-таблицей, используя идеи, представленные ранее. Обратите внимание, что первоначальный размер хэш-таблицы выбран равным 11. Хотя это число произвольно, важно, чтобы оно было простым. Это сделает алгоритм разрешения коллизий максимально эффективным.
Листинг 2
class HashTable: def __init__(self): self.size = 11 self.slots = [None] * self.size self.data = [None] * self.size
hashfunction реализует простой метод остатков. В качестве техники разрешения коллизий используется линейное пробирование с функцией повторного хэширования “плюс 1”. Функция put (см. листинг 3) предполагает, что в конце-концов найдётся пустой слот, или такой ключ уже присутствует в self.slots . Она вычисляет оригинальное хэш-значение и, если слот не пуст, применяет функцию rehash до тех пор, пока не найдёт свободное место. Если непустой слот уже содержит ключ, старое значение данных будет заменено на новое.
Листинг 3
def put(self,key,data): hashvalue = self.hashfunction(key,len(self.slots)) if self.slots[hashvalue] == None: self.slots[hashvalue] = key self.data[hashvalue] = data else: if self.slots[hashvalue] == key: self.data[hashvalue] = data #replace else: nextslot = self.rehash(hashvalue,len(self.slots)) while self.slots[nextslot] != None and \ self.slots[nextslot] != key: nextslot = self.rehash(nextslot,len(self.slots)) if self.slots[nextslot] == None: self.slots[nextslot]=key self.data[nextslot]=data else: self.data[nextslot] = data #replace def hashfunction(self,key,size): return key%size def rehash(self,oldhash,size): return (oldhash+1)%size
Аналогично функция get (см. листинг 4) начинает с вычисления начального хэш-значения. Если искомая величина не содержится в этом слоте, то используется rehash для определения следующей позиции. Обратите внимание: строка 15 гарантирует, что поиск закончится, проверяя, не вернулись ли мы в начальный слот. Если такое происходит, значит все возможные слоты исчерпаны, и элемент в коллекции не представлен.
Кончный метод класса HashTable предоставляет для словарей дополнительный функционал. Мы перегружаем методы __getitem__ и __setitem__ , чтобы получать доступ к элементам с помощью [] . Это подразумевает, что созданному экземпляру HashTable будет доступен знакомый оператор индекса. Оставшиеся методы мы оставляем в качестве упражнения.
Листинг 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def get(self,key): startslot = self.hashfunction(key,len(self.slots)) data = None stop = False found = False position = startslot while self.slots[position] != None and \ not found and not stop: if self.slots[position] == key: found = True data = self.data[position] else: position=self.rehash(position,len(self.slots)) if position == startslot: stop = True return data def __getitem__(self,key): return self.get(key) def __setitem__(self,key,data): self.put(key,data)
Следующая сессия демонстрирует класс HashTable в действии. Сначала мы создаём хэш-таблицу и сохраняем в неё несколько элементов с целочисленными ключами и строковыми значениями данных.
>>> H=HashTable() >>> H[54]="cat" >>> H[26]="dog" >>> H[93]="lion" >>> H[17]="tiger" >>> H[77]="bird" >>> H[31]="cow" >>> H[44]="goat" >>> H[55]="pig" >>> H[20]="chicken" >>> H.slots [77, 44, 55, 20, 26, 93, 17, None, None, 31, 54] >>> H.data ['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
Далее мы получаем доступ и изменяем некоторые из элементов в хэш-таблице. Обратите внимание, что значение с ключом 20 заменяется.
>>> H[20] 'chicken' >>> H[17] 'tiger' >>> H[20]='duck' >>> H[20] 'duck' >>> H.data ['bird', 'goat', 'pig', 'duck', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat'] >> print(H[99]) None
Целиком пример хэш-таблицы можно увидеть в ActiveCode 1.
Выбор криптографической хеш-функции Python
При разработке приложений, где нужна криптографическая защита данных, часто требуется использование хеш-функций. В Python есть несколько встроенных криптографических хеш-функций. Давайте разберем основные моменты выбора криптографической хеш-функции в Python.
Как выбрать криптографическую хеш-функцию в Python
В Python уже встроена поддержка криптографического хеширования. Сторонние фреймворки либо библиотеки для этого не понадобятся. Встроенный модуль hashlib предлагает все, что может понадобиться большинству разработчиков для криптографического хеширования.
В множестве algorithms_guaranteed хранятся все хеш-функции, которые гарантированно поддерживаются на всех платформах. Из этого множества вам и предстоит выбирать. Мало кому требуются функции за пределами данного набора:
import hashlib
sorted ( hashlib . algorithms_guaranteed )
[ ‘blake2b’ , ‘blake2s’ , ‘md5’ , ‘sha1’ , ‘sha224’ , ‘sha256’ , ‘sha384’ ,
‘sha3_224’ , ‘sha3_256’ , ‘sha3_384’ , ‘sha3_512’ , ‘sha512’ , ‘shake_128’ ,
Вряд ли вам хоть когда-то повстречаются хеш-функции не из этого списка.
Само собой, настолько широкий выбор может озадачить. И прежде чем выбирать, нужно разделить эти функции на безопасные и небезопасные.
Безопасные хеш-функции
Безопасные хеш-функции из списка algorithms_guaranteed принадлежат семействам:
Хеш-функция SHA-2
Семейство хеш-функций SHA-2 было представлено NSA в 2001 году. Оно состоит из функций SHA-224, SHA-256, SHA-384 и SHA-512. Основными функциями являются SHA-256 и SHA-512. Можете не запоминать их названия, пока что нас интересует только SHA-256. Она вам еще не раз встретится на протяжении книги.
Для криптографического хеширования по умолчанию стоит использовать SHA-256. Это очевидный выбор, ведь эта функция уже применяется в любом сервисе. Операционные системы и сетевые протоколы, поверх которых работает приложение, уже полагаются на SHA-256. Выбирать не приходится: пришлось бы серьезно постараться никак не задействовать эту функцию. Она является безопасной, широко поддерживается и используется повсеместно.
В названиях всех функций SHA-2 уже указана длина их хешей. О хеш-функции часто судят по длине ее хеша, и его длина нередко фигурирует в названии. SHA-256, например, выдает хеш длиной, как вы уже догадались, 256 бит. Чем длиннее хеш, тем вероятнее, что он уникален, и тем меньше вероятность коллизии. Чем длиннее, тем лучше.
Хеш-функция SHA-3
Семейство хеш-функций SHA-3 состоит из SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128 и SHAKE256. Семейство SHA-3 безопасно, и оно считается наследником SHA-2. Увы, на момент написания книги оно еще не набрало популярности. Стоит подумать об использовании функции этого семейства, например SHA3-256, если требуется повышенная безопасность. Но не забывайте, что поддержка данного семейства не настолько широкая, как у SHA-2.
Хеш-функция BLAKE2
Алгоритм BLAKE2 не настолько популярен, как SHA-2 или SHA-3, но у него есть козырь в рукаве. BLAKE2 умело использует возможности современных ЦП, чтобы считать хеши на сверхвысоких скоростях. Именно поэтому BLAKE2 – ваш выбор, если вам требуется подсчитывать хеши для солидного объема данных. Есть две разновидности BLAKE2: BLAKE2b и BLAKE2s. BLAKE2b предназначен для 64-битных платформ. BLAKE2s разработан для платформ от 8 до 32 бит.
Мы познакомились с безопасными хеш-функциями и узнали, как выбирать между ними. Теперь пора узнать в лицо небезопасные, чтобы избегать их.
Лесли Лэмпорт — американский ученый в области теории вычислительных систем. Один из первых в области хеш-функций. В 1979 году он предложил алгоритм хеширования, который называется «хеш Лэмпорта». Этот алгоритм был спроектирован для обеспечения целостности данных в распределенных системах.
Небезопасные хеш-функции
Хеш-функции множества algorithms_guaranteed пользуются популярностью и отличаются кросс-платформенностью. Но это не значит, что все они безопасны для криптографических целей. Небезопасные хеш-функции оставлены в Python для обеспечения обратной совместимости. Знать о них стоит, потому что они могут повстречаться вам в устаревших системах. Небезопасные функции среди algorithms_guaranteed следующие:
Хеш-функция MD5
MD5 – устаревшая 128-битная хеш-функция родом из начала 90-х. Это самая широко используемая хеш-функция всех времен и народов. Увы, она до сих пор в ходу, несмотря на то что исследователи продемонстрировали коллизии в ней еще в 2004 году. В наше время криптоаналитикам нужно менее часа, чтобы создать коллизию MD5-хешей на домашнем компьютере.
Хеш-функция SHA-1
SHA-1 – устаревшая 160-битная хеш-функция, разработанная NSA в середине 90-х. Как и MD5, эта функция была некогда популярна, но она больше не считается безопасной. Google в сотрудничестве с Центром математики и информатики (Centrum Wiskunde & Informatica), научно-исследовательским институтом, расположенным в Нидерландах, сообщили о первых коллизиях в ней в 2017 году. Говоря языком терминов, они лишили эту функцию сильного сопротивления поиску коллизий. Слабое сопротивление по-прежнему в строю.
Многие разработчики знакомы с SHA-1 по системам контроля версий Git и Mercurial. Там хеши SHA-1 используются для проверки целостности коммитов и их идентификации. Линус Торвальдс, создатель Git, в 2007 году на Google Tech Talk сказал: «Применение SHA-1, во всяком случае в Git, не для безопасности вовсе. Это лишь способ наведения порядка».
ВНИМАНИЕ! MD5 либо SHA-1 ни за что не должны использоваться для целей безопасности при создании новых систем. Любой устаревший сервис, использующий эти функции, должен быть переписан с использованием безопасных альтернатив. Эти функции были некогда популярны, но сейчас популярной и безопасной является SHA-256. Устаревшие функции быстрые, но BLAKE2 еще быстрее и безопаснее.
Выводы
Итак, давайте подведем итог и сделаем выводы. Как выбирать криптографическую хеш-функцию в Python:
- Для большинства задач подходит SHA-256.
- Для обеспечения высокой безопасности подходит SHA3-256, но за это придется заплатить не настолько широкой поддержкой.
- Для объемных сообщений подходит BLAKE2.
- Ни за что не используйте MD5 либо SHA1 для целей безопасности.
Сегодня вы узнали, как выбрать безопасную криптографическую хеш-функцию в Python. В будущем мы применим эти знания на практике.
- Библиотеки для обфускации Python
- Шифрование в Python с помощью алгоритма AES
- Безопасное управление пакетами с помощью Pipenv Python
hashlib — хеширование строк в Python на примерах — MD5, SHA1
В Python хеш-функция принимает вводную последовательность с переменной длиной в байтах и конвертирует ее в последовательность с фиксированной длиной. Данная функция односторонняя.
Это значит, что если f является функцией хеширования, f(x) вычисляется довольно быстро и без лишних сложностей, однако на повторное получение х потребуется очень много времени. Значение, что возвращается хеш-функцией, обычно называют хешем, дайджестом сообщения, значением хеша или контрольной суммой. В подобающем большинстве случаев для предоставленного ввода хеш-функция создает уникальный вывод. Однако, в зависимости от алгоритма, есть вероятность возникновения конфликта, вызванного особенностями математических теорий, что лежат в основе этих функций.
Что такое хеш-функция Python
Хеш-функции используются в криптографических алгоритмах, электронных подписях, кодах аутентификации сообщений, обнаружении манипуляций, сканировании отпечатков пальцев, контрольных суммах (проверка целостности сообщений), хеш-таблицах, хранении паролей и многом другом.
Как Python-разработчику, вам могут понадобиться эти функции для проверки дубликатов данных и файлов, проверки целостности данных при передаче информации по сети, безопасного хранения паролей в базах данных или, возможно, для какой-либо работы, связанной с криптографией.
Есть вопросы по Python?
На нашем форуме вы можете задать любой вопрос и получить ответ от всего нашего сообщества!
Хеш-функция, что это такое?
Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.
Общие сведения
Криптографическая хеш-функция — это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера.
Результат, производимый хеш-функцией, называется «хеш-суммой» или же просто «хешем», а входные данные часто называют «сообщением».
Для идеальной хеш-функции выполняются следующие условия:
а) хеш-функция является детерминированной, то есть одно и то же сообщение приводит к одному и тому же хеш-значению
b) значение хеш-функции быстро вычисляется для любого сообщения
c) невозможно найти сообщение, которое дает заданное хеш-значение
d) невозможно найти два разных сообщения с одинаковым хеш-значением
e) небольшое изменение в сообщении изменяет хеш настолько сильно, что новое и старое значения кажутся некоррелирующими
Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.
Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.
На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.
Любой заинтересованный читатель задаст себе вопрос: «А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?»
Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит — это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:
Надеюсь, теперь нет сомнений в том, что это очень внушительное число!
Поэтому ничего не мешает нам сопоставлять длинному входному массиву данных массив фиксированной длины.
Свойства
Криптографическая хеш-функция должна уметь противостоять всем известным типам криптоаналитических атак.
В теоретической криптографии уровень безопасности хеш-функции определяется с использованием следующих свойств:
Pre-image resistance
Имея заданное значение h, должно быть сложно найти любое сообщение m такое, что
Second pre-image resistance
Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что
Collision resistance
Должно быть сложно найти два различных сообщения и таких, что
Такая пара сообщений и называется коллизией хеш-функции
Давайте чуть более подробно поговорим о каждом из перечисленных свойств.
Collision resistance. Как уже упоминалось ранее, коллизия происходит, когда разные входные данные производят одинаковый хеш. Таким образом, хеш-функция считается устойчивой к коллизиям до того момента, пока не будет обнаружена пара сообщений, дающая одинаковый выход. Стоит отметить, что коллизии всегда будут существовать для любой хеш-функции по той причине, что возможные входы бесконечны, а количество выходов конечно. Хеш-функция считается устойчивой к коллизиям, когда вероятность обнаружения коллизии настолько мала, что для этого потребуются миллионы лет вычислений.
Несмотря на то, что хеш-функций без коллизий не существует, некоторые из них достаточно надежны и считаются устойчивыми к коллизиям.
Pre-image resistance. Это свойство называют сопротивлением прообразу. Хеш-функция считается защищенной от нахождения прообраза, если существует очень низкая вероятность того, что злоумышленник найдет сообщение, которое сгенерировало заданный хеш. Это свойство является важным для защиты данных, поскольку хеш сообщения может доказать его подлинность без необходимости раскрытия информации. Далее будет приведён простой пример и вы поймете смысл предыдущего предложения.
Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что
Отсюда становится ясно, что атака по нахождению второго прообраза включает в себя поиск коллизии. Поэтому любая хеш-функция, устойчивая к коллизиям, также устойчива к атакам по поиску второго прообраза.
Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.
Таким образом, если два сообщения имеют одинаковый хеш, то можно быть уверенным, что они одинаковые.
В частности, хеш-функция должна вести себя как можно более похоже на случайную функцию, оставаясь при этом детерминированной и эффективно вычислимой.
Применение хеш-функций
Рассмотрим несколько достаточно простых примеров применения хеш-функций:
• Проверка целостности сообщений и файлов
Сравнивая хеш-значения сообщений, вычисленные до и после передачи, можно определить, были ли внесены какие-либо изменения в сообщение или файл.
• Верификация пароля
Проверка пароля обычно использует криптографические хеши. Хранение всех паролей пользователей в виде открытого текста может привести к массовому нарушению безопасности, если файл паролей будет скомпрометирован. Одним из способов уменьшения этой опасности является хранение в базе данных не самих паролей, а их хешей. При выполнении хеширования исходные пароли не могут быть восстановлены из сохраненных хеш-значений, поэтому если вы забыли свой пароль вам предложат сбросить его и придумать новый.
• Цифровая подпись
Подписываемые документы имеют различный объем, поэтому зачастую в схемах ЭП подпись ставится не на сам документ, а на его хеш. Вычисление хеша позволяет выявить малейшие изменения в документе при проверке подписи. Хеширование не входит в состав алгоритма ЭП, поэтому в схеме может быть применена любая надежная хеш-функция.
Предлагаю также рассмотреть следующий бытовой пример:
Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать решить задачу сам, но все же хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу (сохраняя решение в секрете). Затем, когда Боб сам придумает решение, Алиса может доказать, что она получила решение раньше Боба. Для этого ей нужно попросить Боба хешировать его решение и проверить, соответствует ли оно хеш-значению, которое она предоставила ему раньше.
Теперь давайте поговорим о SHA-3.
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.
Алгоритм получения хеш-функции можно разделить на несколько этапов:
• С помощью функции дополнения исходное сообщение M дополняется до строки P длины кратной r
• Строка P делится на n блоков длины
• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.
• «Отжимание»: пока длина результата меньше чем , где — количество бит в выходном массиве хеш-функции, первых бит строки состояния добавляется к результату . После каждой такой операции к строке состояния применяется функция перестановок и данные продолжают «отжиматься» дальше, пока не будет достигнуто значение длины выходных данных .
Все сразу станет понятно, когда вы посмотрите на картинку ниже:
Функция дополнения
В SHA-3 используется следующий шаблон дополнения 10. 1: к сообщению добавляется 1, после него от 0 до r — 1 нулевых бит и в конце добавляется 1.
r — 1 нулевых бит может быть добавлено, когда последний блок сообщения имеет длину r — 1 бит. В этом случае последний блок дополняется единицей и к нему добавляется блок, состоящий из r — 1 нулевых бит и единицы в конце.
Если длина исходного сообщения M делится на r, то в этом случае к сообщению добавляется блок, начинающийся и оканчивающийся единицами, между которыми находятся r — 2 нулевых бит. Это делается для того, чтобы для сообщения, оканчивающегося последовательностью бит как в функции дополнения, и для сообщения без этих бит значения хеш-функции были различны.
Первый единичный бит в функции дополнения нужен, чтобы результаты хеш-функции от сообщений, отличающихся несколькими нулевыми битами в конце, были различны.
Функция перестановок
Базовая функция перестановки состоит из раундов по пять шагов:
Тета, Ро, Пи, Хи, Йота
Далее будем использовать следующие обозначения:
Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как
Обозначим результат преобразования состояния функцией перестановки
Также обозначим функцию, которая выполняет следующее соответствие:
— обычная функция трансляции, которая сопоставляет биту бит ,
где — длина слова (64 бит в нашем случае)
Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.
Шаг
Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и
Схематическое представление функции:
Шаг
Отображение направлено на трансляции внутри слов (вдоль оси z).
Проще всего его описать псевдокодом и схематическим рисунком:
Шаг
Шаг представляется псевдокодом и схематическим рисунком:
Шаг
Шаг является единственный нелинейным преобразованием в
Псевдокод и схематическое представление:
Шаг
Отображение состоит из сложения с раундовыми константами и направлено на нарушение симметрии. Без него все раунды были бы эквивалентными, что делало бы его подверженным атакам, использующим симметрию. По мере увеличения раундовые константы добавляют все больше и больше асимметрии.
Ниже приведена таблица раундовых констант для бит
Все шаги можно объединить вместе и тогда мы получим следующее:
Где константы являются циклическими сдвигами и задаются таблицей:
Итоги
В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm
Надеюсь, все было понятно и интересно
Всем спасибо за внимание!