АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Однонаправленные хэш-функции

Читайте также:
  1. Однонаправленные хеш-функции
  2. Простые хэш-функции
  3. Хэш-функции SHA-2

Хэш-функция предназначена для сжатия подписываемого документа M до нескольких десятков или сотен бит. Хэш-функция h(·) принимает в качестве аргумента сообщение (документ) M произвольной длины и возвращает хэш-значение h(M)=H фиксированной длины. Обычно хэшированная информация является сжатым двоичным представлением основного сообщения произвольной длины. Следует отметить, что значение хэш-функции h(M) сложным образом зависит от документа M и не позволяет восстановить сам документ M. Хэш-функция должна удовлетворять целому ряду условий:

- хэш-функция должна быть чувствительна к всевозможным изменениям в тексте M, таким как вставки, выбросы, перестановки и т.п.;

- хэш-функция должна обладать свойством необратимости, то есть задача подбора документа M', который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;

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

Большинство хэш-функций строится на основе однонаправленной функции f(·), которая образует выходное значение длиной n при задании двух входных значений длиной n. Этими входами являются блок исходного текста Mi и хэш-значение Hi–1 предыдущего блока текста (рисунок 8.1):

Hi = f (Mi, Hi–1).


Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения M.

Рисунок 8.1 – Построение однонаправленной хэш-функции

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

8.2.1Однонаправленные хэш-функции на основе симметричных блочных алгоритмов

Однонаправленную хэш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение m посредством блочного алгоритма в режиме CBC или CFB с помощью фиксированного ключа и некоторого вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения M. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-функцию, но всегда можно получить код аутентификации сообщения MAC (Message Authentication Code).

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

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

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

H0 = IH,

Hi = EA(B) Å C,

где IH – некоторое случайное начальное значение; A, B и C могут принимать значения Mi, Hi–1, (Mi Å Hi–1) или быть константами.

Рисунок 8.2 – Обобщенная схема формирования хэш-функции

Сообщение M разбивается на блоки Mi принятой длины, которые обрабатываются поочередно.

Три различные переменные A, B и C могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо тривиально слабыми, либо небезопасными. Остальные 12 безопасных схем хэширования перечислены в таблице 8.1.

Таблица 8.1- Схемы безопасного хэширования, у которых длина хэш-значения равна длине блока

Номер схемы Функция хэширования
  Hi = (Mi) Å Mi Hi = (MiÅ Hi–1) Å MiÅ Hi–1 Hi = (Mi) Å Hi–1 Å Mi Hi = (MiÅ Hi–1) Å Mi Hi = (Hi–1) Å Hi–1 Hi = (MiÅ Hi–1) MiÅ Hi–1 Hi = (Hi–1) MiÅ Hi–1 Hi = (MiÅ Hi–1) Å Hi–1 Hi = (Mi) Å Mi Hi = (Hi–1) Å Hi–1 Hi = (Mi) Å Hi–1 Hi = (Hi–1) Å Mi

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

Рисунок 8.3 – Четыре схемы безопасного хэширования

8.2.2 Отечественный стандарт хэш-функции

Российский стандарт ГОСТ Р 34.11-94 определяет алгоритм и процедуру вычисления хэш-функции для любых последовательностей двоичных символов, применяемых в криптографических методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя в принципе можно было бы использовать и другой блочный алгоритм шифрования с 64-битовым блоком и 256-битовым ключом.

Данная хэш-функция формирует 256-битовое хэш-значение.

Функция сжатия Hi = f (Mi, Hi–1) (оба операнда Mi и Hi–1 являются 256-битовыми величинами) определяется следующим образом:

1. Генерируются 4 ключа шифрования Kj, j = 1…4, путем линейного смешивания Mi, Hi–1 и некоторых констант Cj.

2. Каждый ключ Kj, используют для шифрования 64-битовых подслов hi слова Hi–1 в режиме простой замены: Sj= (hj). Результирующая последовательность S4, S3, S2, S1 длиной 256 бит запоминается во временной переменной S.

3. Значение Hi является сложной, хотя и линейной функцией смешивания S, Mi и Hi–1.

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

Hn – хэш-значение последнего блока сообщения;

Z – значение контрольной суммы, получаемой при сложении по модулю 2 всех блоков сообщения;

L – длина сообщения.

Эти три переменные и дополненный последний блок M´ сообщения объединяются в окончательное хэш-значение следующим образом:

H = f (Z Å M´, f (L, f (M´, Hn))).

Данная хэш-функция определена стандартом ГОСТ Р 34.11-94 для использования совместно с pоссийским стандартом электронной цифровой подписи.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)