Свойства, назначение и основы построения хеш-функций

ХЕШ-ФУНКЦИИ

• Свойства, назначение и основы построения хеш-функций.

• Построение хеш-функций на основе блочных шифров.

• Самостоятельные хеш – алгоритмы.

СОДЕРЖАНИЕ:

Свойства, назначение и основы построения хеш-функций. 2

Алгоритм применения хэш-функции. 2

Обобщенная схема хэш – функции. 3

ПРИМЕР ХЭШИРОВАНИЯ.. 4

Гипотеза о существовании односторонних функций. 8

Свойства односторонних хэш-функций. 9

Длины однонаправленных хэш-функций. 9

Коллизии и реверс. 9

Методы построения криптографических хэш-функций. 10

Назначение криптографических хэш-функций. 10

Методы криптоанализа хэш-функций. 10

Построение хеш-функций на основе блочных шифров. 12

Схемы, в которых длина хэш-значения равна длине блока. 13

Модификация схемы Davies-Меуеr 14

Тандемная (Таndеm) и одновременная (Abreast) схемы Davies-Meyer. 15

MDC.. 17

Схема алгоритма выработки MDC.. 18

МDС-2 и МDС-4. 18

Хэш-функция АR.. 20

Хэш-функция ГОСТ. 20

Самостоятельные хэш – алгоритмы. 21

Краткое описание наиболее распространенных алгоритмов. 21

Алгоритм MD2. 21

Алгоритм МD3. 22

Алгоритм MD4. 22

Алгоритм MD5. 23

Описание МD5. 23

Отличия MD5 от MD4. 25

ПОЛНЫЙ ПРИМЕР MD5. 25

SECURE HASH ALGORITHM (SHA) 27

RIPE-МD.. 29

HAVAL.. 29

Snefru. 29

Криптоанализ Snefru. 30

Tiger 30

Выбор хэш-функции. 30

Эвристические принципы, сформулированные Ривестом.. 31

Основные требования к алгоритму с точки зрения пользователя. 31

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

Простейшим примером хеш-функции, преобразующей любую последовательность байтов в один байт, является следующая:
y=(a AND NOT e AND NOT u) OR (NOT a AND NOT e AND u) OR (NOT a AND e AND NOT u),
где:
a, e, u- аргументы,
OR - дизъюнкции,
AND - конъюнкции.
Эта функция равна единице только тогда, когда один из ее аргументов равен единице. Пусть задана битовая последовательность. которая состоит из трех байтов. Она для удобства использования записана в три строки:
10 100 100
01 100 011
01 010 110
Определяя поразрядно функцию "y", получаем байт:
10 010 001.
Хеш-функция позволяет преобразовывать код ключа базы данных в ее адрес. Это дает возможность так размещать элементы данных в памяти, что их затем несложно будет найти. Хеш-функции также широко используются при шифровании.

Алгоритм применения хэш-функции:

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

• полученный дайджест шифруется закрытым ключом отправителя (подписывается ЭЦП) и пересылается получателю вместе с сообщением;

• получатель расшифровывает дайджест сообщения открытым ключом отправителя;

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

Обобщенная схема хэш – функции

Первым шагом при выработке хэш-свертки является разбиение входных данных на последовательность битовых блоков определенной длины.

Дополнения до блока требуемой длины возможно: нулями, пробелами, иными символами, вычисленными по определенным правилам значениями.

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

System.Security.Cryptography. PaddingMode (режимы дополнения).

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

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

На каждом шаге алгоритма получаются некоторые промежуточные выходные данные: также в виде битовых блоков. Это так называемая хэш-свертка блока. Она получается в общем случае применением алгоритма хэширования к входным данным, к которым каким-либо образом присоеденена, сконкатенирована свертка с предыдущего шага алгоритма.

Таким образом, происходит последовательная обработка входных блоков данных.

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

Пример получения хэш-свертки для текста произвольной длины:

Дата добавления: 2014-01-20