Тема №3.
Лабораторная работа №1.
Изучение упрощенного алгоритма блочного шифрования S-DES.
Цель работы: Изучение принципов функционирования и структуры коммерческого стандарта шифрования DES на основе упрощенного алгоритма.
Общие сведения.
Упрощенный DES (S-DES) – алгоритм шифрования, по свойствам и структуре подобен DES, но имеет гораздо меньше параметров. Данный алгоритм разработан Эдвардом Шейфером [2].
На рис. 1 показана общая структура алгоритма S-DES.
Рис.1 Схема алгоритма S-DES.
Данный алгоритм получает на входе 8-битовый блок открытого текста (например, 10111101) и 10-битовый ключ, а на выходе генерируется 8-битовый блок шифрованного текста. Алгоритм расшифрования S-DES в качестве входных данных использует 8-битовый блок шифрованного текста и тот-же 10-битовый ключ, который применялся для шифрования, а в результате работы алгоритм расшифрования должен генерировать 8-битовый блок открытого текста.
Алгоритм шифрования включает последовательное выполнение пяти операций: начальной перестановки IP, сложной функции fK, являющейся композицией операций перестановки и замены, зависящей от полученного ключа, перестановки SW, при которой две половинки последовательности просто меняются местами, еще раз функции fK, и, наконец, перестановки, обратной начальной (IP-1). Использование нескольких последовательных перестановок и замен приводит к получению алгоритма, значительно более сложного для криптоанализа.
Функция fK использует в качестве исходных данных не только шифруемый текст, но и 8-битовые подключи, которые генерируются из 10-битового ключа для каждого вызова функции fK, как показано на рис.1. При этом 10-битовый ключ сначала преобразуется путем перестановки (P10). После этого применяется операция сдвига (shift), а полученные в ее результате данные поступают на вход перестановки (P8), которая генерирует первый 8-битовый подключ (K1). Те-же полученные в результате операции сдвига данные поступают на вход другой операции сдвига (shift) и другой функции перестановки (P8), в результате чего генерируется второй подключ (K2).
|
|
Данный алгоритм можно представить в виде композиции функций:
IP-1 fK1 SW fK2 IP,
или, иначе,
шифртекст = IP-1(fK2(SW(fK1(IP(открытый текст))))),
где
K1 = P8(shift(P10(ключ))),
K2 = P8(shift(shift(P10(кдюч)))).
Процесс расшифрования, также представленный на рис.1, по сути, является процессом, обратным процессу шифрования:
открытый текст = IP-1(fK1(SW(fK2(IP(шифртекст))))).
Вычисление ключей S-DES.
В алгоритме S-DES используется 10-битовый ключ, который должен быть как у отправителя, так и у получателя сообщения. Из этого ключа на определенных этапах шифрования и расшифрования генерируется два 8-битовых подключа.
На рис. 2 показана схема процедуры создания этих подключей.
Рис. 2 Вычисление ключей S-DES.
Сначала выполняется перестановка битов ключа следующим образом. Если 10-битовый ключ представить в виде (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10), то перестановку P10 можно задать формулой:
P10(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6)
Можно также представить перестановку P10 в следующей табличной форме.
| P10 | |||||||||
Эту таблицу следует читать слева направо. Каждый ее элемент идентифицирует позицию бита исходных данных в генерируемой выходной последовательности. Иными словами первым битом в в выходной последовательности будет третий бит исходной последовательности, вторым – пятый и т. д. Например, в соответствии с данной таблицей ключ (1010000010) будет преобразован к виду (1000001100). После этого отдельно для первых пяти битов и отдельно для вторых выполняется циклический сдвиг влево (LS-1), который еще называют вращением. В нашем случае в результате будет получена последовательность (00001 11000).
|
|
Затем применяется перестановка P8, в результате которой из 10-битового ключа сначала выбираются, а затем переставляются 8 битов по следующему правилу.
| P8 | |||||||
В результате этой операции получается первый подключ (K1). В нашем примере он будет иметь вид (10100100).
Теперь нужно вернуться к двум 5-битовым строкам, полученным в результате применения функций LS-1, и выполнить с каждой из этих строк циклический сдвиг влево на две позиции (LS-2). В нашем конкретном случае значение (00001 11000) будет преобразовано к виду (00100 00011). Наконец, применив к полученной в результате последовательности перестановку P8, получим подключ K2. Для нашего примера результатом будет (01000011).
Шифрование S-DES.
На рис.3 представлена более подробная схема алгоритма шифрования S-DES. Как уже упоминалось, процесс шифрование представляет собой последовательное выполнение пяти операций, которые мы рассмотрим каждую в отдельности.
Начальная и завершающая перестановки: На вход алгоритма поступает 8-битовый блок открытого текста, к которому применяется начальная перестановка, заданная функцией IP.
|
|
| IP | |||||||
Все 8 битов открытого текста сохраняют свои значения, но меняется порядок их следования. На завершающей стадии алгоритма выполняется обратная перестановка.
| IP-1 | |||||||
Как легко убедиться с помощью простой проверки, вторая из приведенных выше перестановок действительно является обратной по отношению к первой, т.е. IP-1(IP(X)) = X.
Рис. 3 Подробная схема шифрования S-DES.
Функция fK: является самым сложным компонентом S-DES и представляет собой комбинацию перестановки и замены. Пусть L и R означают соответственно первые 4 бита и последние 4 бита 8-битовой последовательности, подаваемой на вход fK, и пусть F – некоторое отображение пространства 4-битовых строк в себя, не обязательно являющееся взаимно однозначным. Тогда положим:
fK(L,R) = (L Å F(R, SK), R),
где SK обозначает подключ, а Å - операцию XOR (побитовое исключающее "ИЛИ", также называемое "суммой по модулю 2" или "суммой Жегалкина"). Например, если в результате применения функции IP (рис 3) получено значение (10111101) и F(1101, SK) = (1110) Для некоторого ключа SK, то fK(10111101) = (01011101), так как (1101) Å (1110) = (0101).
Теперь опишем отображение F. На входе этого отображения имеем 4-битовое значение (n1n2n3n4). Первой операцией является операция расширения/перестановки:
| E/P | |||||||
К этому значению с помощью операции XOR добавляется 8-битовый подключ K1. После этого первые четыре бита поступают на вход модуля S0, на выходе которого получается 2-битовая последовательность, а оставшиеся четыре бита – на вход модуля S1, на выходе которого получается другая 2-битовая последовательность. Модули S0 и S1 можно определить так:
| S0= | , | S1= | ||||||||||
Эти S-модули (матрицы кодирования) работают следующим образом. Первый и четвертый биты входной последовательности рассматриваются как 2-битовые числа, определяющие строку, а второй и третий – как числа, определяющие столбец S-матрицы. Элементы, находящиеся на пересечении соответствующих строки и столбца, задают 2-битовые выходные значения. Например, если (k1 k4) = (00) и (k2 k3) = (10), то выходные два бита задаются значением, которое находится на пересечении строки 0 и столбца 2 матрицы S0 (оно равно 3 или (11) в двоичном представлении). Точно также (k5 k8) и (k6 k7) служат для определения строки и столбца матрицы S1, на пересечении которых лежит значение, задающее вторые 2 бита.
Теперь 4 бита, полученные на выходе модулей S0 и S1, преобразуются с помощью перестановки следующим образом:
| P4 | |||
Результат применения перестановки P4 и является результатом функции F.
Функция-переключатель: Функция fK изменяет только четыре левых бита. Поэтому следующей операцией в алгоритме шифрования является использование функции SW, которая меняет местами первые и последние четыре бита последовательности, чтобы при следующем вызове функции fK последняя работала уже с другой четверкой битов. При втором вызове fK функции E/P, S0, S1, и P4 остаются теми же, что и при первом, но вместо ключа K1 используется ключ K2.
Задание.
1. Используя бланк отчета (см. Приложение 1), произвести вручную пошаговое шифрование и/или расшифрование на основе 8-битового блока открытого/шифрованного текста и 10-битового ключа, заданного преподавателем.
2. Используя файл MS Excel[1], для выполнения данной лабораторной работы (см. Приложение 2 – файл s-des.xls), установить:
а) Значение шифртекста при использовании нулевых открытого текста и ключа.
б) Арифметическую разность открытого и шифрованного текстов и число различающихся битов при изменении по сравнению с нулевыми значениями:
- ключа на 1 бит,
- открытого текста на 1 бит.
3. Используя шаблон MS Excel, провести силовую атаку прямым подбором ключа при известных шифртексте и открытом тексте, с разбиением на интервалы по подгруппам.
4. Оформить отчет с результатами и выводами по работе.
Литература.
1. Столлингс В. Криптография и защита сетей. Принципы и практика. 2-е изд. – М.: Вильямс, 2001. – 672 с.
2. Schaefer E. "A Simplified Data Encryption Standard Algorithm." //Cryptologia, January 1996.
[1] Шаблон лабораторной работы, выполняющий операции шифрования/расшифрования и генерации ключей студентам выдается только на время проведения лабораторной работы.