Методы сжатия преобразуемых данных на основе однонаправленных ХЭШ-функций
Хэш-функция (hash, hash-function) – это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины. Простейшими примерами являются контрольные суммы (например, crc32). Бывают:
· криптографические хэши;
· программистские хэши.
Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим:
m - исходные данные,
h(m) – хэш-функция от них.
Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0.
Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1 не равно m2, но h(m1) = h(m2).
Криптографические хэш-функции разделяются на два класса:
Хэш-функции без ключа (MDC (Modification (Manipulation) Detect Code) - коды),
Хэш-функции c ключом (MАC (Message Authentication Code) - коды).
Хэш-функции без ключа разделяются на два подкласса: слабые хэш-функции, сильные хэш-функции.
Слабой хэш-функцией называется односторонняя функция H(x), удовлетворяющая следующим условиям:
1. аргумент х может быть строкой бит произвольной длины;
2. значение h(x) должно быть строкой бит фиксированной длины;
3. значение h(x) легко вычислить;
4. для любого фиксированного x вычислительно невозможно найти другой x" ≠ x, такой что h(x")=h(x).
Пара x" ≠ x, когда h(x")=h(x) называется коллизией хэш-функции.
Сильной хэш-функцией называется односторонняя функция h(x), удовлетворяющая условиям 1-4 для слабой хэш-функции и свойству 5:
5. вычислительно невозможно найти любую пару x" ≠ x, такую, что h(x")=h(x).
Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 5 говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.
Существует несколько алгоритмов вычисления хэш-функций
MD2 (Message Digest) – алгоритм криптографической свертки. Порождает блок длиной 128 бит от сообщения произвольной длины. Общая схема работы MD2:
a. дополнение текста сообщений до длины, кратной 128 бит;
b. вычисление 16-битной контрольной суммы, старшие разряды отбрасываются;
c. добавление контрольной суммы к тексту;
d. повторное вычисление контрольной суммы.
Алгоритм MD2 очень медленный, поэтому чаще применяются MD4, MD5, SHA (Secure Hash Algorithm). Результирующий хэш имеет длину 160 бит.
ГОСТ Р34.11-94. Российский алгоритм. Длина свертки - 256 бит (очень удобно для формирования по паролю ключа для ГОСТ 28147-89).
Национальный институт стандартов и технологий (НИСТ) США на своем веб-сайте http://www.nist.gov/sha/ опубликовал спецификации новых алгоритмов хеширования SHA-256, SHA-384 и SHA-512, цель которых - обеспечить уровень криптостойкости хэша, соответствующий длинам ключей нового стандарта шифрования DES.
Напомним, что n-битный хэш - это отображение сообщения произвольной длины в n-битную псевдослучайную последовательность (хэш-значение). Криптографический хэш, как особая разновидность такой функции, это n-битный хэш, обладающий свойствами «однонаправленности» и «стойкости к коллизиям».
До настоящего времени наиболее популярными хеш-функциями были созданные Райвистом MD4 и MD5, генерирующие хэш-коды длиной n=128, и алгоритм SHA-1, разработанный в АНБ США и порождающий хэш-код длиной n=160.
ГОСТ Р34.10-94 «Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма».
Например, мы можем подать на вход 128-битной хеш-функции роман Льва Толстого в шестнадцатеричном виде или число 1. В результате на выходе мы в обоих случаях получим разные наборы псевдослучайных шестнадцатеричных цифр вида: «c4ca4238a0b923820dcc509a6f75849b».
При изменении исходного текста даже на один знак результат хеш-функции полностью меняется.
Это свойство хеш-функций позволяет применять их в следующих случаях:
- при построении ассоциативных массивов ;
- при поиске дубликатов в сериях наборов данных;
- при построении уникальных идентификаторов для наборов данных;
- при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в них ошибок (возникших случайно или внесённых намеренно), возникающих при хранении и/или передаче данных;
- при сохранении паролей в системах защиты в виде хеш-кода (для восстановления пароля по хеш-коду требуется функция, являющаяся обратной по отношению к использованной хеш-функции);
- при выработке электронной подписи (на практике часто подписывается не само сообщение, а его «хеш-образ»);
- и др.
Виды «хеш-функций»
«Хорошая» хеш-функция должна удовлетворять двум свойствам :
- быстрое вычисление;
- минимальное количество «коллизий ».
Введём обозначения:
∀ k ∈ (0 ; K) : h (k) < M {\displaystyle \forall k\in (0;\,K):h(k)В качестве примера «плохой» хеш-функции можно привести функцию с M = 1000 {\displaystyle M=1000} , которая десятизначному натуральному числу K {\displaystyle K} сопоставляет три цифры, выбранные из середины двадцатизначного квадрата числа K {\displaystyle K} . Казалось бы, значения «хеш-кодов» должны равномерно распределяться между «000 » и «999 », но для «реальных » данных это справедливо лишь в том случае, если «ключи » не имеют «большого» количества нулей слева или справа .
Рассмотрим несколько простых и надёжных реализаций «хеш-функций».
«Хеш-функции», основанные на делении
1. «Хеш-код» как остаток от деления на число всех возможных «хешей»
Хеш-функция может вычислять «хеш» как остаток от деления входных данных на M {\displaystyle M} :
h (k) = k mod M {\displaystyle h(k)=k\mod M} ,где M {\displaystyle M} - количество всех возможных «хешей» (выходных данных).
При этом очевидно, что при чётном M {\displaystyle M} значение функции будет чётным при чётном k {\displaystyle k} и нечётным - при нечётном k {\displaystyle k} . Также не следует использовать в качестве M {\displaystyle M} степень основания системы счисления компьютера , так как «хеш-код» будет зависеть только от нескольких цифр числа k {\displaystyle k} , расположенных справа, что приведёт к большому количеству коллизий . На практике обычно выбирают простое M {\displaystyle M} ; в большинстве случаев этот выбор вполне удовлетворителен.
2. «Хеш-код» как набор коэффициентов получаемого полинома
Хеш-функция может выполнять деление входных данных на полином по модулю два. В данном методе M {\displaystyle M} должна являться степенью двойки, а бинарные ключи ( K = k n − 1 k n − 2 . . . k 0 {\displaystyle K=k_{n-1}k_{n-2}...k_{0}} ) представляются в виде полиномов , в качестве «хеш-кода» «берутся» значения коэффициентов полинома , полученного как остаток от деления входных данных K {\displaystyle K} на заранее выбранный полином P {\displaystyle P} степени m {\displaystyle m} :
K (x) mod P (x) = h m − 1 x m − 1 + ⋯ + h 1 x + h 0 {\displaystyle K(x)\mod P(x)=h_{m-1}x^{m-1}+\dots +h_{1}x+h_{0}} h (x) = h m − 1 . . . h 1 h 0 {\displaystyle h(x)=h_{m-1}...h_{1}h_{0}}При правильном выборе P (x) {\displaystyle P(x)} гарантируется отсутствие коллизий между почти одинаковыми ключами .
«Хеш-функции», основанные на умножении
Обозначим символом w {\displaystyle w} количество чисел, представимых машинным словом . Например, для 32-разрядных компьютеров, совместимых с IBM PC , w = 2 32 {\displaystyle w=2^{32}} .
Выберем некую константу A {\displaystyle A} так, чтобы A {\displaystyle A} была взаимно простой с w {\displaystyle w} . Тогда хеш-функция, использующая умножение, может иметь следующий вид:
h (K) = [ M ⌊ A w ∗ K ⌋ ] {\displaystyle h(K)=\left}В этом случае на компьютере с двоичной системой счисления M {\displaystyle M} является степенью двойки, и h (K) {\displaystyle h(K)} будет состоять из старших битов правой половины произведения A ∗ K {\displaystyle A*K} .
Среди преимуществ хеш-функций, основанных на делении и умножении, стоит отметить выгодное использование неслучайности реальных ключей. Например, если ключи представляют собой арифметическую прогрессию (например, последовательность имён «Имя 1», «Имя 2», «Имя 3»), хеш-функция, использующая умножение, отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшит количество коллизий по сравнению со случайной ситуацией .
Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи . Хеширование Фибоначчи основано на свойствах золотого сечения . В качестве константы A {\displaystyle A} здесь выбирается целое число, ближайшее к φ − 1 ∗ w {\displaystyle \varphi ^{-1}*w} и взаимно простое с w {\displaystyle w} , где φ {\displaystyle \varphi } - это золотое сечение .
Хеширование строк переменной длины
Вышеизложенные методы применимы и в том случае, если необходимо рассматривать ключи, состоящие из нескольких слов, или ключи переменной длины.
Например, можно скомбинировать слова в одно при помощи сложения по модулю w {\displaystyle w} или операции «исключающее или ». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона.
Универсальное хеширование
Методы борьбы с коллизиями
Коллизией (иногда конфликтом или столкновением) называется случай, при котором одна хеш-функция для разных входных блоков возвращает одинаковые хеш-коды.
Методы борьбы с коллизиями в хеш-таблицах
Большинство первых работ, описывающих хеширование, посвящено методам борьбы с коллизиями в хеш-таблицах. Тогда хеш-функции применялись при поиске текста в файлах большого размера. Существует два основных метода борьбы с коллизиями в хеш-таблицах:
- метод цепочек (метод прямого связывания);
- метод открытой адресации.
При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе создаётся новая пара «список ключей» - «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется N {\displaystyle N} ключей и M {\displaystyle M} списков, средний размер хеш-таблицы составит N M {\displaystyle {\frac {N}{M}}} . В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в M {\displaystyle M} раз.
При использовании метода открытой адресации в хеш-таблице хранятся пары «ключ» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; пара «ключ» - «хеш-код» сохраняется в таблице. В этом случае при поиске по таблице по сравнению со случаем, в котором используются связные списки, ссылки не используются, выполняется последовательный перебор пар «ключ» - «хеш-код», перебор прекращается после обнаружения нужного ключа. Последовательность, в которой просматриваются ячейки таблицы, называется последовательностью проб .
Криптографическая соль
Применение хеш-функций
Хеш-функции широко используются в криптографии.
Хеш используется как ключ во многих структурах данных - хеш-таблицаx , фильтрах Блума и декартовых деревьях .
Криптографические хеш-функции
Среди множества существующих хеш-функций принято выделять криптографически стойкие , применяемые в криптографии , так как на них накладываются дополнительные требования. Для того, чтобы хеш-функция H {\displaystyle H} считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:
Данные требования не являются независимыми.
Хеширование (иногда хэширование, англ. hashing) - преобразование входного массива данных произвольной длины в выходную строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки , входной массив – прообразом , а результаты преобразования - хешем, хеш-кодом, хеш-образом, цифровым отпечатком или дайджестом сообщения (англ. message digest).Хеш-функция – легко вычислимая функция, преобразующая исходное сообщения произвольной длины (прообраз) в сообщение фиксированное длины (хеш-образ), для которой не существует эффективного алгоритма поиска коллизий.
Коллизией для функции h называется пара значений x, y, x ≠ y , такая, что h(x) = h(y) . Т.о. хеш-функция должна обладать следующими свойствами:
Для данного значения h(x) невозможно найти значение аргумента x . Такие хеш-функции называют стойкими в смысле обращения или стойкими в сильном смысле ;
Для данного аргумента x невозможно найти другой аргумент y такой, что h(x) = h(y) . Такие хеш-функции называют стойкими в смысле вычисления коллизий или стойкими в слабом смысле .
В случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то это значение называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .
На практике хеш-функции используют в следующих целях:
Для ускорения поиска данных в БД;
Ускорения поиска данных. Например, при записи текстовых полей в базе данных может рассчитываться их хеш-код и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста и сразу станет известно, в каком разделе их надо искать, т.е. искать надо будет не по всей базе, а только по одному её разделу (это сильно ускоряет поиск).
Бытовым аналогом хеширования в данном случае может служить размещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только раздел с нужной буквой.
Процедура вычисления (стандартная схема алгоритма) хеш-функции представлена на следующем рисунке.
Рис.10.1. Процедура вычисления значения хеш-функции
1) К исходному сообщению Т добавляется вспомогательная информация (например, длина прообраза, вспомогательные символы и т.д.) так, чтобы длина прообраза Х стала кратной величине L бл , определенной спецификацией (стандартом) хеш-функции.
2) Для инициализации процедуры хеширования используется синхропосылка y 0 .
3) Прообраз X разбивается на n блоков x i (i = 1 .. n) фиксированной длины L бл , над которыми выполняется однотипная процедура хеширования f(y i-1 , x i) , зависящая от результата хеширования предыдущего блока y i-1 .
4) Хеш-образом h(T) исходного сообщения Т будет результат процедуры хеширования y n , полученный после обработки последнего блока x n .
10.2. MD5
MD5 (англ. Message Digest 5) – 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 г. Является улучшенной в плане безопасности версией MD4 .
Ниже приведен алгоритм вычисления хеша.
1. Выравнивание потока.
В конец исходного сообщения, длиной L , дописывают единичный бит, затем необходимое число нулевых бит так, чтобы новый размер L" был сравним с 448 по модулю 512 (L’ mod 512 = 448). Добавление нулевых бит выполняется, даже если новая длина, включая единичный бит, уже сравнима с 448.
2. Добавление длины сообщения.
К модифицированному сообщению дописывают 64-битное представление длины данных (количество бит в сообщении). Т.е. длина сообщения T становится кратной 512 (T mod 512 = 0). Если длина исходного сообщения превосходит 2 64 - 1, то дописывают только младшие 64 бита. Кроме этого, для указанного 64-битного представления длины вначале записываются младшие 32 бита, а затем старшие 32 бита.
3. Инициализация буфера.
Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения (шестнадцатеричное представление):
A
= 67 45 23 01;
B
= EF CD AB 89;
C
= 98 BA DC FE;
D
= 10 32 54 76.
В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.
4. Вычисление хеша в цикле.
Исходное сообщение разбивается на блоки T , длиной 512 бит. Для каждого блока в цикле выполняется процедура, приведенная на рис.10.2. Результат обработки всех блоков исходного сообщения в виде объединения 32-битных значений переменных ABCD и будет являться хешем.
Рис.10.2. Шаг основного цикла вычисления хеша
В каждом раунде над переменными ABCD и блоком исходного текста Т в цикле (16 итераций) выполняются однотипные преобразования по следующей схеме.
Рис.10.3. Одна итерация цикла раунда
Условные обозначения.
1) RF - раундовая функция, определяемая по следующей таблице.
Таблица 10.1. Раундовые функции RF
2) t j - j-ая 32-битовая часть блока исходного сообщения Т с обратным порядком следования байт;
3) k i - целая часть константы, определяемой по формуле
k i = 2 32 * | sin(i + 16 * (r - 1)) |, (10.1)
где i – номер итерации цикла (i = 1..16);
r – номер раунда (r = 1..4).
Аргумент функции sin измеряется в радианах.
4) ⊞ – сложение по модулю 2 32 .
5) <<< s i – циклический сдвиг влево на s i разрядов.
Используемая 32-битовая часть блока исходного сообщения t j и величина циклического сдвига влево s i зависят от номера итерации и приведены в следующей таблице.
Таблица 10.2. Величины, используемые на шаге цикла раунда
№ итерации | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
Раунд 1 | t j | t 1 | t 2 | t 3 | t 4 | t 5 | t 6 | t 7 | t 8 | t 9 | t 10 | t 11 | t 12 | t 13 | t 14 | t 15 | t 16 |
s i | 7 | 12 | 17 | 22 | 7 | 12 | 17 | 22 | 7 | 12 | 17 | 22 | 7 | 12 | 17 | 22 | |
Раунд 2 | t j | t 2 | t 7 | t 12 | t 1 | t 6 | t 11 | t 16 | t 5 | t 10 | t 15 | t 4 | t 9 | t 14 | t 3 | t 8 | t 13 |
s i | 5 | 9 | 14 | 20 | 5 | 9 | 14 | 20 | 5 | 9 | 14 | 20 | 5 | 9 | 14 | 20 | |
Раунд 3 | t j | t 6 | t 9 | t 12 | t 15 | t 2 | t 5 | t 8 | t 11 | t 14 | t 1 | t 4 | t 7 | t 10 | t 13 | t 16 | t 3 |
s i | 4 | 11 | 16 | 23 | 4 | 11 | 16 | 23 | 4 | 11 | 16 | 23 | 4 | 11 | 16 | 23 | |
Раунд 4 | t j | t 1 | t 8 | t 15 | t 6 | t 13 | t 4 | t 11 | t 2 | t 9 | t 16 | t 7 | t 14 | t 5 | t 12 | t 3 | t 10 |
s i | 6 | 10 | 15 | 21 | 6 | 10 | 15 | 21 | 6 | 10 | 15 | 21 | 6 | 10 | 15 | 21 |
После 4 раундов новое (модифицированное) значение каждой из переменных ABCD складывается (⊞ ) с исходным (значением переменной до 1-го раунда).
5. Перестановка байт в переменных ABCD . После обработки всех блоков исходного сообщения для каждой переменной выполняется обратная перестановка байт.
Поиск коллизий.
В 2004 г. китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.
10.3. Применение шифрования для получения хеш-образа
Для выработки устойчивого к коллизиям хеш-образа могут применяться специальные режимы, предусмотренные в блочных шифрах (например, сцепление блоков шифра у ), или в самой хеш-функции, как составная часть, может использоваться один из режимов блочного шифра (например, составной часть хеш-функции по ГОСТ 34.11-94 1 является режим простой замены алгоритма криптографического преобразования по 2).
Напомним что в случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то хеш-образ называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .
В качестве примера приведем режим (сцепление блоков шифра - Cipher Block Chaining).
Рис.10.4. Схема алгоритма DES в режиме сцепления блоков шифра
Последний зашифрованный блок C n и есть хеш-образ сообщения T = {T 1 , T 2 , …, T n } .
1 ГОСТ 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования».
2 ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».
Вопросы для самопроверки
1. Дайте определение понятиям: « », « », « ».
Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.
О себе
Студент кафедры информационной безопасности.О хэшировании
В настоящее время практически ни одно приложение криптографии не обходится без использования хэширования.Хэш-функции – это функции, предназначенные для «сжатия» произвольного сообщения или набора данных, записанных, как правило, в двоичном алфавите, в некоторую битовую комбинацию фиксированной длины, называемую сверткой. Хэш-функции имеют разнообразные применения при проведении статистических экспериментов, при тестировании логических устройств, при построении алгоритмов быстрого поиска и проверки целостности записей в базах данных. Основным требованием к хэш-функциям является равномерность распределения их значений при случайном выборе значений аргумента.
Криптографической хеш-функцией называется всякая хеш-функция, являющаяся криптостойкой, то есть удовлетворяющая ряду требований специфичных для криптографических приложений. В криптографии хэш-функции применяются для решения следующих задач:
- построения систем контроля целостности данных при их передаче или хранении,
- аутентификация источника данных.
Хэш-функцией называется всякая функция h:X -> Y , легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X - множество всех сообщений, Y - множество двоичных векторов фиксированной длины.
Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x 1 , x 2)
двух переменных, где x 1
, x 2
и y
- двоичные векторы длины m
, n
и n
соответственно, причем n
- длина свертки, а m
- длина блока сообщения.
Для получения значения h(M)
сообщение сначала разбивается на блоки длины m
(при этом, если длина сообщения не кратна m
то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M 1 , M 2 ,.., M N
применяют следующую последовательную процедуру вычисления свертки:
H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = H N
Здесь 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 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.
Российский стандарт - ГОСТ 34.11-94 .
В следующей статье
Обзор алгоритмов MD (MD4, MD5, MD6).
Литература
А. П. Алферов, Основы криптографии.
Брюс Шнайер, Прикладная криптография.
Алгоритмы хэширования строк помогают решить очень много задач. Но у них есть большой недостаток: что чаще всего они не 100%-ны, поскольку есть множество строк, хэши которых совпадают. Другое дело, что в большинстве задач на это можно не обращать внимания, поскольку вероятность совпадения хэшей всё-таки очень мала.
Определение хэша и его вычисление
Один из лучших способов определить хэш-функцию от строки S следующий:
H(S) = S + S * P + S * P^2 + S * P^3 + ... + S[N] * P^N
где P - некоторое число.
Разумно выбирать для P простое число, примерно равное количеству символов во входном алфавите. Например, если строки предполаются состоящими только из маленьких латинских букв, то хорошим выбором будет P = 31. Если буквы могут быть и заглавными, и маленькими, то, например, можно P = 53.
Во всех кусках кода в этой статье будет использоваться P = 31.
Само значение хэша желательно хранить в самом большом числовом типе - int64, он же long long. Очевидно, что при длине строки порядка 20 символов уже будет происходить переполнение значение. Ключевой момент - что мы не обращаем внимание на эти переполнения, как бы беря хэш по модулю 2^64.
Пример вычисления хэша, если допустимы только маленькие латинские буквы:
Const int p = 31;
long long hash = 0, p_pow = 1;
for (size_t i=0; i В большинстве задач имеет смысл сначала вычислить все нужные степени P в каком-либо массиве. Уже теперь мы в состоянии эффективно решить такую задачу. Дан список строк S, каждая длиной не более M символов. Допустим, требуется найти все повторяющиеся строки и разделить их на группы, чтобы в каждой группе были только одинаковые строки. Обычной сортировкой строк мы бы получили алгоритм со сложностью O (N M log N), в то время как используя хэши, мы получим O (N M + N log N). Алгоритм. Посчитаем хэш от каждой строки, и отсортируем строки по этому хэшу. Vector Предположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S. По определению имеем: H = S[I] + S * P + S * P^2 + ... + S[J] * P^(J-I)
H * P[I] = S[I] * P[I] + ... + S[J] * P[J],
H * P[I] = H - H
Полученное свойство является очень важным. Действительно, получается, что, зная только хэши от всех префиксов строки S, мы можем за O (1) получить хэш любой подстроки
. Единственная возникающая проблема - это то, что нужно уметь делить на P[I]. На самом деле, это не так просто. Поскольку мы вычисляем хэш по модулю 2^64, то для деления на P[I] мы должны найти к нему обратный элемент в поле (например, с помощью Расширенного алгоритма Евклида), и выполнить умножение на этот обратный элемент. Впрочем, есть и более простой путь. В большинстве случаев, вместо того чтобы делить хэши на степени P, можно, наоборот, умножать их на эти степени
. Допустим, даны два хэша: один умноженный на P[I], а другой - на P[J]. Если I < J, то умножим перый хэш на P, иначе же умножим второй хэш на P. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать. Например, код, который вычисляет хэши всех префиксов, а затем за O (1) сравнивает две подстроки: String s; int i1, i2, len; // входные данные
// считаем все степени p
const int p = 31;
vector Вот некоторые типичные применения хэширования: Пусть дана строка S длиной N, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке. Для решения переберём по очереди длину подстроки: L = 1 .. N. Для каждого L мы построим массив хэшей подстрок длины L, причём приведём хэши к одной степени, и отсортируем этот массив. Количество различных элементов в этом массиве прибавляем к ответу. Реализация: String s; // входная строка
int n = (int) s.length();
// считаем все степени p
const int p = 31;
vectorПример задачи. Поиск одинаковых строк
Хэш подстроки и его быстрое вычисление
Применение хэширования
Определение количества различных подстрок