Основы построения хэш-функций. Итеративная последовательная схема.
Типовая хэш-функция вычисляется путем последовательного шифрования двоичных блоков Мi сообщения М в соответствии со следующим итеративным выражением: Нi = Е (Нi-1, Мi), где Е – базовая функция шифрования (см. рис. 2.).
Типовая схема вычисления блочной хэш-функции:
Н0 – специфицированное начальное значение хэш-функции;
Нn – значение хэш-функции, принимается за эталонную характеристику.
Основы построения хэш функций- принцип итеративной последовательной схемы.
Ядро: преобразование k бит в n бит, где n (разрядность результата хэш), k (разрядность исходного документа):
Ø если k>mn, где m- остаток:
a. добиваем нулями;
b. многократно повторяем сообщение до кратности;
c. добивается случайным набором 1 и 0.
Ø если k<n:
a. многократное повторение;
b. добивание констант.
Итеративные х.ф.:
Х.ф. хэширующая документ целиком- однопроходная. Остальные случаи- многопроходные.
Хэш-функции на основе блочных шифров.
Алгоритм TandemDM.
Алгоритм MD5.
Аппаратное шифрование DES: структура, перестановки, сеть Файштеля, расширение ключа.
Традиционно первой знаменательной вехой в истории блочного шифрования считается опубликование в 1977 году и принятие в 1980 году в США национального стандарта шифрования данных DES (Data Encryption Standart). Параметры алгоритма таковы: разрядность блока- 64 бита, размер ключа- 56 бит. Алгоритм представляет собой классическую сеть Файштеля из 16 раундов с добавлением входной и выходной перестановок бит.
Входные данные (64 бита); входная перестановка бит (цель: распределить равномерно по блоку рядом стоящие биты); сеть Файштеля из 16 раундов; выходная перестановка бит; порядок перестановки обратен ко входной; выходные данные (64 бита).
Добавление материала ключа производится только в сети Файштеля, поэтому, по сути, только она выполняет собственно шифрование данных.
Разрядность ключей раундов, применяемых в DES равна 48 битам. Для симметричности алгоритма шифрования дешифрования в DES, как и в классической сети Файштеля, производится дополнительно размен последнего обмена ветвей. Это позволяет производить шифрование и дешифрование одним и тем же программным кодом, передавая ему в первом случае ключи раундов в прямом порядке (k0, k1,…, k15), а во втором случае- в обратном (k15, k14,…, k0). Общий вид сети Файштеля алгоритма DES:
Образующая функция сети в алгоритме DES состоит из 4 операций:
1. перестановка бит/расширение блока с помощью повторов по определенной схеме;
2. наложение ключа раунда операций ХОR;
3. табличные подстановки;
4. перестановка бит.
Расширение входных данных производится на уровне бит записью некоторых из них в выходной поток дважды. В результате из 32 бит получается 48 битный блок информации, совпадающий по размеру с ключом раунда.
Наложение ключа раунда производится операцией ХОR, разрядность операции- 48 бит.
DES: расширение ключа.
Расширение ключа (создание ключей раунда) производится в DES по следующей схеме. На основе 56 значащих бит из ключа на начальном этапе создаются два 28-битных вектора С0 и D0 путем выбора бит из ключа в определенной последовательности.
Для выбора 48 бит ключа i–го раунда, получившиеся после циклических сдвигов вектора СiDi объединяются, и из 56 бит получившегося массива отбираются 48 по закону.
По-настоящему заставили DES уйти с рынка конкурентно-способных блочных шифров две причины: ориентация на аппаратную реализацию и слишком малый размер ключа.