Исследование принципов функционирования и анализа блочных шифров. Изучение упрощенного алгоритма блочного шифрования S-DES

Тема №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] Шаблон лабораторной работы, выполняющий операции шифрования/расшифрования и генерации ключей студентам выдается только на время проведения лабораторной работы.


9136940079143810.html
9137010221040708.html

9136940079143810.html
9137010221040708.html
    PR.RU™