Хеширование. Что такое хеш и для чего он нужен
Методы сжатия преобразуемых данных на основе однонаправленных ХЭШ-функций
Хэш-функция (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 «Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма».
И т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC .
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет. Поэтому существует множество массивов данных, дающих одинаковые хеш-коды - так называемые коллизии . Вероятность возникновения коллизий играет немаловажную роль в оценке «качества» хеш-функций.
Контрольные суммы
Несложные, крайне быстрые и легко реализуемые аппаратно алгоритмы, используемые для защиты от непреднамеренных искажений, в том числе ошибок аппаратуры.
По скорости вычисления в десятки и сотни раз быстрее, чем криптографические хеш-функции, и значительно проще в аппаратной реализации.
Платой за столь высокую скорость является отсутствие криптостойкости - легкая возможность подогнать сообщение под заранее известную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.
Простейшим случаем такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование, что применяется, например, в TCP/IP .
Как правило, к такому алгоритму предъявляются требования отслеживания типичных аппаратных ошибок, таких, как несколько подряд идущих ошибочных бит до заданной длины. Семейство алгоритмов т. н. «циклический избыточных кодов » удовлетворяет этим требованиям. К ним относится, например, CRC32 , применяемый в аппаратуре ZIP.
Криптографические хеш-функции
Среди множества существующих хеш-функций принято выделять криптографически стойкие , применяемые в криптографии . Криптостойкая хеш-функция прежде всего должна обладать стойкостью к коллизиям двух типов:
Применение хеширования
Хеш-функции также используются в некоторых структурах данных - хеш-таблицаx и декартовых деревьях . Требования к хеш-функции в этом случае другие:
- хорошая перемешиваемость данных
- быстрый алгоритм вычисления
Сверка данных
В общем случае это применение можно описать, как проверка некоторой информации на идентичность оригиналу, без использования оригинала. Для сверки используется хеш-значение проверяемой информации. Различают два основных направления этого применения:
Проверка на наличие ошибок
Например, контрольная сумма может быть передана по каналу связи вместе с основным текстом. На приёмном конце, контрольная сумма может быть рассчитана заново и её можно сравнить с переданным значением. Если будет обнаружено расхождение, то это значит, что при передаче возникли искажения и можно запросить повтор.
Бытовым аналогом хеширования в данном случае может служить приём, когда при переездах в памяти держат количество мест багажа. Тогда для проверки не нужно вспоминать про каждый чемодан, а достаточно их посчитать. Совпадение будет означать, что ни один чемодан не потерян. То есть, количество мест багажа является его хеш-кодом.
Проверка парольной фразы
В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хеш-значения. Хранить парольные фразы нецелесообразно, так как в случае несанкционированного доступа к файлу с фразами злоумышленник узнает все парольные фразы и сразу сможет ими воспользоваться, а при хранении хеш-значений он узнает лишь хеш-значения, которые не обратимы в исходные данные, в данном случае в парольную фразу. В ходе процедуры аутентификации вычисляется хеш-значение введённой парольной фразы, и сравнивается с сохранённым.
Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP . В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.
Ускорение поиска данных
Например, при записи текстовых полей в базе данных может рассчитываться их хеш код и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста и сразу станет известно, в каком разделе их надо искать, то есть, искать надо будет не по всей базе, а только по одному её разделу (это сильно ускоряет поиск).
Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.
Список алгоритмов
- SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
- RIPEMD-160
- RIPEMD-320
- Snefru
- Tiger (Whirlpool
- IP Internet Checksum (RFC 1071)
Ссылки
Wikimedia Foundation . 2010 .
Смотреть что такое "Хэш код" в других словарях:
Хэш-код - результат арифметической комбинации со всеми байтами программного кода или набора данных. Результат алгоритма хэширования включает только некоторые байты, а алгоритм построен таким образом, что любая модификация кода программы или данных с… … Официальная терминология
Хэш-код - результат арифметической комбинации со всеми байтами программного кода или набора данных. Результат алгоритма хеширования включает только некоторые байты, а алгоритм построен таким образом, что любая модификация кода программы или данных с… …
код аутентификации сообщения, использующий хэш-функцию - (МСЭ Т Н.235.3, МСЭ Т Н.235.1). Тематики электросвязь, основные понятия EN hashed message authentication codeHMAC … Справочник технического переводчика
В программировании хеш таблица это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления … Википедия
MAC (имитовставка, англ. message authentication code код аутентичности сообщения) средство обеспечения имитозащиты в протоколах аутентификации сообщений с доверяющими друг другу участниками специальный набор символов, который добавляется к… … Википедия
Хеширование (иногда хэширование, англ. hashing) преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш функциями или функциями свёртки, а их результаты… … Википедия
Эта статья о коде. О методе мозгового штурма см. CRC карта. Циклический избыточный код (англ. Cyclic redundancy check, CRC) алгоритм вычисления контрольной суммы, предназначенный для проверки целостности… … Википедия
- (сокращение от англ. hash based message authentication code, хеш код аутентификации сообщений). Наличие способа проверить целостность информации, передаваемой или хранящийся в ненадежной среде является неотъемлемой и необходимой частью мира… … Википедия
МИ 2891-2004: Рекомендация. ГСОЕИ. Общие требования к программному обеспечению средств измерений - Терминология МИ 2891 2004: Рекомендация. ГСОЕИ. Общие требования к программному обеспечению средств измерений: Данные измерительная информация, представленная в виде, пригодном для передачи, интерпретации или обработки. Определения термина из… … Словарь-справочник терминов нормативно-технической документации
Процесс поиска данных в больших объемах информации сопряжен с временными затратами, которые обусловлены необходимостью просмотра и сравнения с ключом поиска значительного числа элементов. Сокращение поиска возможно осуществить путем локализации области просмотра. Например, отсортировать данные по ключу поиска, разбить на непересекающиеся блоки по некоторому групповому признаку или поставить в соответствие реальным данным некий код, который упростит процедуру поиска.
В настоящее время используется широко распространенный метод обеспечения быстрого доступа к информации, хранящейся во внешней памяти – хеширование .
Хеширование (или хэширование , англ. hashing ) – это преобразование входного массива данных определенного типа и произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свертки , а их результаты называют хешем, хеш-кодом, хеш-таблицей или дайджестом сообщения (англ. message digest ).
Хеш-таблица – это структура данных , реализующая интерфейс ассоциативного массива, то есть она позволяет хранить пары вида " ключ - значение " и выполнять три операции : операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Хеш-таблица является массивом, формируемым в определенном порядке хеш-функцией .
- функция должна быть простой с вычислительной точки зрения;
- функция должна распределять ключи в хеш-таблице наиболее равномерно;
- функция не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;
- функция должна минимизировать число коллизий – то есть ситуаций, когда разным ключам соответствует одно значение хеш-функции (ключи в этом случае называются синонимами ).
При этом первое свойство хорошей хеш-функции зависит от характеристик компьютера, а второе – от значений данных.
Если бы все данные были случайными, то хеш-функции были бы очень простые (например, несколько битов ключа). Однако на практике случайные данные встречаются достаточно редко, и приходится создавать функцию, которая зависела бы от всего ключа. Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай – когда все ключи хешируются в один индекс .
При возникновении коллизий необходимо найти новое место для хранения ключей, претендующих на одну и ту же ячейку хеш-таблицы. Причем, если коллизии допускаются, то их количество необходимо минимизировать. В некоторых специальных случаях удается избежать коллизий вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую инъективную хеш-функцию, которая распределит их по ячейкам хеш-таблицы без коллизий . Хеш-таблицы, использующие подобные хеш-функции , не нуждаются в механизме разрешения коллизий , и называются хеш-таблицами с прямой адресацией .
Хеш-таблицы должны соответствовать следующим свойствам .
- Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение является индексом в исходном массиве.
- Количество хранимых элементов массива, деленное на число возможных значений хеш-функции , называется коэффициентом заполнения хеш-таблицы (load factor ) и является важным параметром, от которого зависит среднее время выполнения операций.
- Операции поиска, вставки и удаления должны выполняться в среднем за время O(1) . Однако при такой оценке не учитываются возможные аппаратные затраты на перестройку индекса хеш-таблицы, связанную с увеличением значения размера массива и добавлением в хеш-таблицу новой пары.
- Механизм разрешения коллизий является важной составляющей любой хеш-таблицы.
Хеширование полезно, когда широкий диапазон возможных значений должен быть сохранен в малом объеме памяти, и нужен способ быстрого, практически произвольного доступа. Хэш-таблицы часто применяются в базах данных, и, особенно, в языковых процессорах типа компиляторов и ассемблеров , где они повышают скорость обработки таблицы идентификаторов. В качестве использования хеширования в повседневной жизни можно привести примеры распределение книг в библиотеке по тематическим каталогам, упорядочивание в словарях по первым буквам слов, шифрование специальностей в вузах и т.д.
Методы разрешения коллизий
Коллизии осложняют использование хеш-таблиц, так как нарушают однозначность соответствия между хеш-кодами и данными. Тем не менее, существуют способы преодоления возникающих сложностей:
- метод цепочек (внешнее или открытое хеширование );
- метод открытой адресации (закрытое хеширование ).
Метод цепочек . Технология сцепления элементов состоит в том, что элементы множества , которым соответствует одно и то же хеш- значение , связываются в цепочку- список . В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш- значение ключа равно i ; если таких элементов в множестве нет, в позиции i записан NULL . На рис. 38.1 демонстрируется реализация метода цепочек при разрешении коллизий . На ключ 002 претендуют два значения, которые организуются в линейный список .
Рис.
38.1.
Каждая ячейка массива является указателем на связный список (цепочку) пар ключ - значение , соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.
Операции поиска или удаления данных требуют просмотра всех элементов соответствующей ему цепочки, чтобы найти в ней элемент с заданным ключом. Для добавления данных нужно добавить элемент в конец или начало соответствующего списка, и, в случае если коэффициент заполнения станет слишком велик, увеличить размер массива и перестроить таблицу.
При предположении, что каждый элемент может попасть в любую позицию таблицы с равной вероятностью и независимо от того, куда попал любой другой элемент,
Или Хеш-функция — это функция, превращает входные данные любого (как правило большого) размера в данные фиксированного размера. Хеширование (иногда г ешування, англ. Hashing) — преобразование входного массива данных произвольной длины в выходной битовый строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хэшем, хэш-кодом, хеш-суммой, или дайджестом сообщения (англ. Message digest).
Хэш-функция используется в частности в структурах данных — хеш-таблицах, широко используется в программном обеспечении для быстрого поиска данных. Хэш-функции используются для оптимизации таблиц и баз данных за счет того, что в одинаковых записей одинаковые значения хэш-функции. Такой подход поиска дубликатов эффективен в файлах большого размера. Примером этого нахождения подобных участков в последовательностях ДНК. Криптографическая хеш-функция позволяет легко проверить, что некоторые входные данные сопоставляются с заданным значением хеш, но, если входные данные неизвестны, намеренно трудно восстановить входное значение (или эквивалентную альтернативу), зная сохранено значение хеш-функции. Это используется для обеспечения целостности передаваемых данных и является строительным блоком для HMACs, которые обеспечивают аутентификацию сообщений.
Хэш-функции связаны (и их часто путают) с суммой, контрольными цифрами, отпечатками пальцев, рандомизации функций, кодами, исправляют ошибки, и с шифрами. Хотя эти понятия в определенной степени совпадают, каждый из них имеет свою собственную область применения и требования и является разработанным и оптимизированным по-разному.
История
Дональд Кнут приписывает первую систематическую идею хеширования сотруднику IBM Ханса Петера Луна, предложил хеш в январе 1953 года.
В 1956 году Арнольд Думы в своей работе «Computers and automation» первым представил концепцию хеширования такой, какой ее знает большинство программистов в наше время. Думы рассматривал хеширования, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток от деления на простое число.
Первой значительной работой, которая была связана с поиском в больших файлах, была статья Уэсли Питерсона в IBM Journal of Research and Development 1957 года в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Через шесть лет была опубликована работа Вернера Бухгольца, в которой в значительной степени исследовались хэш-функции. В течение нескольких следующих лет хеширования широко использовалось, однако не было опубликовано ни одной значительной работы.
В 1967 году хеширования в современном смысле упомянуто в книге Херберта Хеллерман «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис опубликовал в Communications of the ACM большой обзор о хеширования. Эта работа считается публикацией, вводящий понятие о хешировании в научный оборот и окончательно закрепляет среди специалистов термин «хэш».
К началу 1990-х годов эквивалентом термина «хеширования», благодаря работам Андрея Ершова, использовалось слово «расстановка» (рус.), А для коллизий использовался термин «конфликт» (рус.) (Ершов использовал «расстановки» с 1956, а также в русскоязычном издании книги Никлауса Вирта "Алгоритмы и структуры данных» (1989) используется этот термин). Однако ни один из этих вариантов не прижился, и в литературе используется преимущественно термин «хеширования».
Описание
Хеширования применяется для построения ассоциативных массивов, поиска дубликатов в сериях наборов данных, построения уникальных идентификаторов для наборов данных, контрольного суммирования с целью выявления случайных или преднамеренных ошибок при хранении или передачи, для хранения паролей в системах защиты (в этом случае доступ к области памяти " памяти, где находятся пароли, не позволяет восстановить сам пароль), при выработке электронной подписи (на практике часто подписывается не самое сообщение, а его хеш-образ).
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хэш-функций меньше, чем число вариантов значений входного массива. Существует множество массивов с разным содержанием, но дают одинаковые хеш-коды — так называемые коллизии. Вероятность возникновения коллизий играет важную роль в оценке качества хеш-функций.
Существует множество алгоритмов хеширования с различными свойствами (разрядность, вычислительная сложность, криптостойкость и т.д.). Выбор той или иной хэш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.
Виды хеш-функций
Хорошая хеш-функция должна удовлетворять двум свойствам:
- Быстро исчисляться;
- Минимизировать количество коллизий
Допустим, для определенности, — количество ключей, а хэш-функция имеет не больше различных значений:
Как пример «плохой» хеш-функции можно привести функцию с, которая десятизначный натуральному числу сопоставляет три цифры, выбранные с середины двадцатизначные квадрата числа. Казалось бы, значение хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит только в том случае, если ключи не имеют большого количества нулей слева или справа.
Однако, существует несколько других простых и надежных методов, на которых базируется много хэш-функций.
Хэш-функции на основе деления
Первый метод заключается в том, что мы используем в качестве хэша — остаток от деления на, где — это количество всех возможных хэшей:
При этом очевидно, что при парном режим экономии парным, при парном. А нечетным — при нечетном, что может привести к значительному смещению данных в файлах. Также не следует использовать в качестве базу системы счисления компьютера, поскольку хэш будет зависеть только от нескольких цифр числа, расположенных справа, что приведет к большому количеству коллизий. На практике обычно выбирают простое — в большинстве случаев этот выбор вполне удовлетворительное.
Еще следует сказать о методе хэширования, в основе которого заключается деления на поленом по модулю два. В данном методе также должна быть степенью двойки, а бинарные ключи () имеют вид полиномов. В этом случае в качестве хеш-кода берутся значения коэффициентов полинома, полученного как остаток от деления на заранее выбранный полином степени:
При правильном выборе такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами.
Мультипликативная схема хеширования
Второй метод заключается в выборе некоторой целой константы, взаимно простой с, где — количество возможных вариантов значений в виде машинного слова (в компьютерах IBM PC). Тогда можем взять хеш-функцию вида:
В этом случае, на компьютере с двоичной системой счисления, представляет собой степень двойки, а состоять из старших битов правой половины произведения.
Среди преимуществ этих двух методов стоит отметить, что они выгодно используют то, что реальные ключи неслучайны. Например, в том случае, если ключи представляют собой арифметическую прогрессию (допустим последовательность названий «имья1», «имя2», «имья3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенную арифметическую прогрессию различных хеш-значений, уменьшает количество коллизий по сравнению со случайной ситуацией.
Одной из вариаций данного метода является хеширования Фибоначчи, основанное на свойствах золотого сечения. В качестве здесь избирается ближайшее к целое число, взаимно простое с
Хеширования строк переменной длины
Вышеизложенные методы применяются и в том случае, когда нам необходимо рассматривать ключи, состоящие из нескольких слов или ключи с переменной длиной. Например, можно скомбинировать слова в одно с помощью сложения по модулю или операции «сложение по модулю 2». Одним из алгоритмов, работающих по такому принципу, является хэш-функция Пирсона.
Хеширования Пирсона (англ. Pearson hashing) — алгоритм, предложенный Питером Пирсоном (англ. Peter Pearson) для процессоров с 8-битными регистрами, задачей которого является быстрое вычисление хэш-кода для строки произвольной длины. На вход функция получает слово, состоящее из символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. При этом значение хеш-кода зависит от каждого символа входного слова.
Алгоритм можно описать следующим псевдокодом, который получает на вход строку и использует таблицу перестановок
h: = 0 For each c in W loop index:= h xor ch:= T End loop Return h
Среди преимуществ алгоритма следует отметить:
- простоту вычисления;
- не существует таких входных данных, для которых вероятность коллизии самая;
- возможность модификации в идеальную хеш-функцию.
В качестве альтернативного способа хеширования ключей, состоящие из символов (), можно предложить вычисления
Применение хэш-функций
Хэш-функции широко используются в криптографии, а также во многих структурах данных — хеш-таблицах, фильтрах Блума и декартовых деревьях.
Криптографические хеш-функции
Среди множества существующих хеш-функций принято выделять криптографически стойкие, применяемые в криптографии, так как на них накладываются дополнительные требования. Для того, чтобы хеш-функция считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хеш-функций в криптографии:
- Необратимость: для заданного значения хэш-функции m должно быть вычислительно невозможно найти блок данных, для которого.
- Устойчивость коллизиям первого рода: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого.
- Устойчивость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений, имеющих одинаковый хеш.
Данные требования зависят друг от друга:
- Оборотная функция неустойчива к коллизиям первого и второго рода.
- Функция, неустойчивая к коллизиям первого рода, неустойчивая к коллизиям второго рода; обратное неверно.
Следует отметить, что не доказано существование необратимых хеш-функций, для которых вычисления любого прообраза заданного значения хэш-функции теоретически невозможно. Обычно нахождения обратного значения являются только вычислительно сложной задачей.
Атака «дней рождения» позволяет находить коллизии для хэш-функции с длиной значений n бит в среднем за примерно вычислений хэш-функции. Поэтому n — битная хэш-функция считается крипостийкою, если вычислительная сложность нахождения коллизий для нее близка к.
Для криптографических хэш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект). В частности, значение хеша не должно давать утечки информации, даже об отдельных биты аргумента. Это требование является залогом криптостойкости алгоритмов хеширования, хешуючих пароль пользователя для получения ключа.
Хеширования часто используется в алгоритмах электронно-цифровой подписи, где шифруется не самое сообщение, а его хэш, что уменьшает время вычисления, а также повышает криптостойкость. Также в большинстве случаев, вместо паролей хранятся значения их хеш-кодов.
Геометрическое хеширования
Геометрическое хеширования (англ. Geometric hashing) — широко применяемый в компьютерной графике и вычислительной геометрии метод для решения задач на плоскости или в трехмерном пространстве, например, для нахождения ближайших пар в множестве точек или для поиска одинаковых изображений. Хэш-функция в данном методе обычно получает на вход какой метрический пространство и разделяет его, создавая сетку из клеток. Таблица в данном случае является массивом с двумя или более индексами и называется файл сетки (англ. Grid file). Геометрическое хеширования также применяется в телекоммуникациях при работе с многомерными сигналами.
Ускорение поиска данных
Хеш-таблица — это структура данных, позволяет хранить пары вида (ключ, хеш-код) и поддерживает операции поиска, вставки и удаления элементов. Задачей хеш-таблиц является ускорение поиска, например, в случае записей в текстовых полей в базе данных может рассчитываться их хэш код и данные могут помещаться в раздел, соответствующий этому хэш-кода. Тогда при поиске данных надо будет сначала вычислить хэш текста и сразу станет известно, в каком разделе их надо искать, то есть, искать надо будет не по всей базе, а только по одному ее раздела (это сильно ускоряет поиск).
Бытовым аналогом хеширования в данном случае может служить размещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.
Хеширование
Хеширование (иногда «хэширование» , англ. hashing ) - преобразование по детерменированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки , а их результаты называют хешем , хеш-кодом или сводкой сообщения (англ. message digest ). Если у двух строк хеш-коды разные, строки гарантированно различаются, если одинаковые - строки, вероятно, совпадают.
Хеширование применяется для построения ассоциативных массивов , поиска дубликатов в сериях наборов данных, построения достаточно уникальных идентификаторов для наборов данных, контрольное суммирование с целью обнаружения случайных или намеренных ошибок при хранении или передаче, для хранения паролей в системах защиты (в этом случае доступ к области памяти, где находятся пароли, не позволяет восстановить сам пароль), при выработке электронной подписи (на практике часто подписывается не само сообщение, а его хеш-образ).
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше , чем вариантов входного массива; существует множество массивов с разным содержимым, но дающих одинаковые хеш-коды - так называемые коллизии . Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
Существует множество алгоритмов хеширования с различными свойствами (разрядность , вычислительная сложность , криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC .
История
Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона (англ. W. Wesley Peterson ) в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет был опубликована работа Вернера Бухгольца (нем. Werner Buchholz ), в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.
В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем» . В 1968 году Роберт Моррис (англ. Robert Morris ) опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».
До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Ершова использовалось слово «расстановка» , а для коллизий использовался термин "конфликт" (Ершов использовал «расстановку» с 1956 года, в русскоязычном издании книги Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка»). Предлагалось также назвать метод русским словом «окрошка» . Однако ни один из этих вариантов не прижился, и в русскоязычной литературе используется преимущественно термин «хеширование».
Виды хеш-функций
Хорошая хеш-функция должна удовлетворять двум свойствам:
- Быстро вычисляться;
- Минимизировать количество коллизий
Предположим, для определённости, что количество ключей , а хеш-функция имеет не более различных значений:
В качестве примера «плохой» хеш-функции можно привести функцию с , которая десятизначному натуральном числу сопоставляет три цифры выбранные из середины двадцатизначного квадрата числа . Казалось бы значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа.
Однако существует несколько более простых и надежных методов, на которых базируются многие хеш-функции.
Хеш-функции основанные на делении
Первый метод заключается в том, что мы используем в качестве хеша остаток от деления на , где это количество всех возможных хешей:
При этом очевидно, что при чётном значение функции будет чётным, при чётном , и нечётным - при нечётном, что может привести к значительному смещению данных в файлах. Также не следует использовать в качестве степень основания счисления компьютера, так как хеш-код будет зависеть только от нескольких цифр числа , расположенных справа, что приведет к большому количеству коллизий. На практике обычно выбирают простое - в большинстве случаев этот выбор вполне удовлетворителен.
Ещё следует сказать о методе хеширования, основанном на делении на полином по модулю два. В данном методе также должна являться степенью двойки, а бинарные ключи () представляются в виде полиномов. В этом случае в качестве хеш-кода берутся значения коэффциентов полинома, полученного как остаток от деления на заранее выбранный полином степени :
При правильном выборе такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами.
Мультипликативная схема хеширования
Второй метод состоит в выборе некоторой целой константы , взаимно простой с , где - количество представимых машинным словом значений (в компьютерах IBM PC ). Тогда можем взять хеш-функцию вида:
В этом случае, на компьютере с двоичной системой счисления, является степенью двойки и будет состоять из старших битов правой половины произведения .
Среди преимуществ этих двух методов стоит отметь, что они выгодно используют то, что реальные ключи неслучайны, например в том случае если ключи представляют собой арифметическую прогрессию (допустим последовательность имён «ИМЯ1», «ИМЯ2», «ИМЯ3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшает количество коллизий по сравнению со случайной ситуацией.
Одной из вариаций данного метода является хеширование Фибоначчи , основанное на свойствах золотого сечения . В качестве здесь выбирается ближайшее к целое число, взаимно простое с
Хеширование строк переменной длины
Вышеизложенные методы применимы и в том случае, если нам необходимо рассматривать ключи, состоящие из нескольких слов или ключи переменной длины. Например можно скомбинировать слова в одно при помощи сложения по модулю или операции «исключающее или». Одним из алгоритмов, работающих по такому принципу является хеш-функция Пирсона.
Универсальное хеширование
Универсальным хешированием (англ. Universal hashing ) называется хеширование, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму . Использование универсального хеширования обычно обеспечивает низкое число коллизий. Универсальное хеширование имеет множество применений, например, в реализации хеш-таблиц и криптографии.
Описание
Предположим, что мы хотим отобразить ключи из пространства в числа . На входе алгоритм получает некоторый набор данных и размерностью , причем неизвестный заранее. Как правило целью хеширования является получение наименьшего числа коллизий , чего трудно добиться используя какую-то определенную хеш-функцию.
В качестве решения такой проблемы можно выбирать функцию случайным образом из определенного набора, называемого универсальным семейством .
Методы борьбы с коллизиями
Как уже говорилось выше, коллизией (иногда конфликтом или столкновением) хеш-функции называются такие два входных блока данных, которые дают одинаковые хеш-коды.
В хеш-таблицах
Большинство первых работ описывающих хеширование было посвящено методам борьбы с коллизиями в хеш-таблицах, так как хеш-функции применялись для поиска в больших файлах. Существует два основных метода используемых в хеш-таблицах:
- Метод цепочек(метод прямого связывания)
- Метод открытой адресации
Первый метод заключается в поддержке связных списков , по одному на каждое значение хеш-функции. В списке хранятся ключи, дающие одинаковое значение хеш-кодов. В общем случае, если мы имеем ключей и списков, средний размер списка будет и хеширование приведет к уменьшению среднего количества работы по сравнению с последовательным поиском примерно в раз.
Второй метод состоит в том, что в массиве таблицы хранятся пары ключ-значение. Таким образом мы полностью отказываемся от ссылок и просто просматриваем записи таблицы, пока не найдем нужный ключ или пустую позицию. Последовательность, в которой просматриваются ячейки таблицы называется последовательностью проб.
Криптографическая соль
Существует несколько способов для защиты от подделки паролей и подписей , работающих даже в том случае, если криптоаналитику известны способы построения коллизий для используемой хеш-функции. Одним из таких методов является добавление криптографической соли (строки случайных данных) к входным данным (иногда «соль» добавляется и к хеш-коду), что значительно затрудняет анализ итоговых хеш-таблиц. Данный метод, к примеру, используется для хранения паролей в UNIX-подобных операционных системах .
Применение хеш-функций
Криптографические хеш-функции
Среди множества существующих хеш-функций принято выделять криптографически стойкие , применяемые в криптографии , так как на них накладываются дополнительные требования. Для того чтобы хеш-функция считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хеш-функций в криптографии:
Данные требования не являются независимыми:
- Обратимая функция нестойка к коллизиям первого и второго рода.
- Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.
Следует отметить, что не доказано существование необратимых хеш-функций, для которых вычисление какого-либо прообраза заданного значения хеш-функции теоретически невозможно. Обычно нахождение обратного значения является лишь вычислительно сложной задачей.
Хеширование часто используется в алгоритмах электронно-цифровой подписи, где шифруется не само сообщение, а его хеш-код, что уменьшает время вычисления, а также повышает криптостойкость. Также в большинстве случаев, вместо паролей хранятся значения их хеш-кодов.
Контрольные суммы
Несложные, крайне быстрые и легко осуществимые аппаратные алгоритмы, используемые для защиты от непреднамеренных искажений, в том числе ошибок аппаратуры. С точки зрения математики является хеш-функцией, которая вычисляет контрольный код, применяемый для обнаружения ошибок при передаче и хранении информации
По скорости вычисления в десятки и сотни раз быстрее, чем криптографические хеш-функции, и значительно проще в аппаратном исполнении.
Платой за столь высокую скорость является отсутствие криптостойкости - лёгкая возможность подогнать сообщение под заранее известную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.
Простейшим случаем такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование, что применяется, например, в TCP/IP .
Как правило, к такому алгоритму предъявляются требования отслеживания типичных аппаратных ошибок, таких, как несколько подряд идущих ошибочных бит до заданной длины. Семейство алгоритмов т. н. «циклических избыточных кодов » удовлетворяет этим требованиям. К ним относится, например, CRC32 , применяемый в устройствах Ethernet и в формате сжатия данных ZIP .
Контрольная сумма, например, может быть передана по каналу связи вместе с основным текстом. На приёмном конце, контрольная сумма может быть рассчитана заново и её можно сравнить с переданным значением. Если будет обнаружено расхождение, то это значит, что при передаче возникли искажения и можно запросить повтор.
Бытовым аналогом хеширования в данном случае может служить приём, когда при переездах в памяти держат количество мест багажа. Тогда для проверки не нужно вспоминать про каждый чемодан, а достаточно их посчитать. Совпадение будет означать, что ни один чемодан не потерян. То есть, количество мест багажа является его хеш-кодом. Данный метод легко дополнить до защиты от фальсификации передаваемой информации (метод MAC). В этом случае хеширование производится криптостойкой функцией над сообщением, объединенным с секретным ключом, известным только отправителю и получателю сообщения. Таким образом, криптоаналитик не сможет восстановить код по перехваченному сообщению и значению хеш-функции, то есть, не сможет подделать сообщение (См. имитозащита).
Геометрическое хеширование
Геометрическое хеширование (англ. Geometric hashing ) – широко применяемый в компьтерной графике и вычислительной геометрии метод для решения задач на плоскости или в трёхмерном пространстве, например для нахождения ближайших пар в множестве точек или для поиска одинаковых изображений. Хеш-функция в данном методе обычно получает на вход какое-либо метрическое пространство и разделяет его, создавая сетку из клеток. Таблица в данном случае является массивом с двумя или более индексами и называется файл сетки(англ. Grid file ). Геометрическое хеширование также применяется в телекоммуникациях при работе с многомерными сигналами.
Ускорение поиска данных
Хеш-таблицей называется структура данных, позволяющая хранить пары вида (ключ,хеш-код) и поддерживающая операции поиска, вставки и удаления элемента. Задачей хеш-таблиц является ускорение поиска, например, при записи текстовых полей в базе данных может рассчитываться их хеш код и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста и сразу станет известно, в каком разделе их надо искать, то есть, искать надо будет не по всей базе, а только по одному её разделу (это сильно ускоряет поиск).
Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.
Примечания
Литература
- Брюс Шнайер "Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си". - М .: Триумф, 2002. - ISBN 5-89392-055-4
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. - 2-е изд. - М .: «Вильямс», 2007. - С. 824. -