Что такое хеш и для чего он нужен? Хэш-функция: что это такое, зачем нужна и какой бывает

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

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

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

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

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

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

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

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

Хеш-таблицы должны соответствовать следующим свойствам .

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

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

Методы разрешения коллизий

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

• метод цепочек (внешнее или открытое хеширование );
• метод открытой адресации (закрытое хеширование ).

Метод цепочек . Технология сцепления элементов состоит в том, что элементы множества , которым соответствует одно и то же хеш- значение , связываются в цепочку- список . В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш- значение ключа равно i ; если таких элементов в множестве нет, в позиции i записан NULL . На рис. 38.1 демонстрируется реализация метода цепочек при разрешении коллизий . На ключ 002 претендуют два значения, которые организуются в линейный список .

Рис. 38.1.

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

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

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

И т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или 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: Рекомендация. ГСОЕИ. Общие требования к программному обеспечению средств измерений: Данные измерительная информация, представленная в виде, пригодном для передачи, интерпретации или обработки. Определения термина из… … Словарь-справочник терминов нормативно-технической документации

И т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или 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 .

• Хэшан Мохэянь
• Хэш код

Смотреть что такое "Хэш-функция" в других словарях:

Хэш-функция - функция, осуществляющая хэширование массива данных посредством отображения значений из (очень) большого множества значений в (существенно) меньшее множество значений. По английски: Hash function См. также: Криптографические алгоритмы Финансовый… … Финансовый словарь

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

Односторонняя хэш-функция - хэш функция, являющаяся вычислительно необратимой функцией. По английски: One way hash function См. также: Криптографические алгоритмы Финансовый словарь Финам … Финансовый словарь

TIGER - хэш-функция - TIGER хэш функция, разработанная Росом Андерсоном и Эли Бихамом в 1996 году. Хэш функция TIGER является новой быстрой хэш функцией, которая призвана быть очень быстрой на современных компьютерах, в частности, на 64 разрядных компьютерах. TIGER… … Википедия

односторонняя хэш-функция - Для односторонней функции вычислительно невозможно найти два разных аргумента, для которых ее значения совпадают. [] Тематики защита информации EN one way hash function … Справочник технического переводчика

Tiger (хэш-функция) - Tiger хеш функция, разработанная Росом Андерсоном и Эли Бихамом в 1995 году. Tiger был предназначен для особенно быстрого выполнения на 64 разрядных компьютерах. Tiger не имеет патентных ограничений, может использоваться свободно как с… … Википедия

функция хэширования - хэшфункция 1. Функция, которая управляет процессом занесения данных в хэш таблицу, определяя (адреса свободных ячеек. 2. Функция, представляющая собой отображение фрагмента открытого сообщения в шифрованную строку фиксированной длины. В… … Справочник технического переводчика

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

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

Коллизия хэш-функции - Коллизией хеш функции H называется два различных входных блока данных x и y таких, что H(x) = H(y). Коллизии существуют для большинства хеш функций, но для «хороших» хеш функций частота их возникновения близка к теоретическому минимуму. В… … Википедия

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

Коллизией для функции 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. Величины, используемые на шаге цикла раунда

После 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. Дайте определение понятиям: « », « », « ».

Приложений.

Энциклопедичный YouTube

• 1 / 5

  Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

  Данные требования не являются независимыми:

  • Обратимая функция нестойка к коллизиям первого и второго рода.
  • Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

  Принципы построения

  Итеративная последовательная схема

  При проектировании хеш-функций на основе итеративной схемы возникает проблема с размером входного потока данных. Размер входного потока данных должен быть кратен (k − n ) . Как правило, перед началом алгоритма данные расширяются неким, заранее известным, способом.

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

  Сжимающая функция на основе симметричного блочного алгоритма

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

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

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

  Применения

  Электронная подпись

  Пусть некий клиент, с именем name , производит аутентификацию по парольной фразе, pass , на некоем сервере. На сервере хранится значение хеш-функции H (pass , R 2) , где R 2 - псевдослучайное, заранее выбранное число. Клиент посылает запрос (name , R 1 ), где R 1 - псевдослучайное, каждый раз новое число. В ответ сервер посылает значение R 2 . Клиент вычисляет значение хеш-функции H (R 1 , H (pass , R 2)) и посылает его на сервер. Сервер также вычисляет значение H (R 1 , H (pass , R 2)) и сверяет его с полученным. Если значения совпадают - аутентификация верна.