РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ
20/43/2
Одобрено кафедрой
«Вычислительная техника»
МЕТОДЫ И СРЕДСТВА
ЗАЩИТЫ КОМПЬЮТЕРНОЙ
ИНФОРМАЦИИ
Задание на контрольную работу
с методическими указаниями для студентов V курса специальности 220100 Вычислительные машины, комплексы, системы и сети (ЭВМ) Москва – 2005 1
1. ЗАДАНИЕ НА КОНТРОЛЬНУЮ РАБОТУ
1.1. Общие требования к выполнению контрольной работы Контрольная работа выполняется на листах формата А4. На титульном листе должны быть указаны данные студента и его учебный шифр. В контрольной работе должны быть выполне ны все пункты задания, которое приводится в начале работы.Контрольные работы, не соответствующие указанным требо С о с т а в и т е л ь — канд. техн. наук, доц. А.Е. Ермаков ваниям, возвращаются студенту без рецензии.
1.2. Исходные данные Р е ц е н з е н т — д р техн. наук, проф. В.Ю. Горелик С помощью симметричного криптографического алгорит ма DES зашифровать свою фамилию, представленную в дво ичном коде. Тип кодировки (приложение) определяется в со ответствии с табл. 1. В качестве исходного ключа шифрования берется представленное в двоичном коде имя студента.
Таблица Последняя цифра 0 1 2 3 4 5 6 7 8 шифра Тип коди- win- ISO88 ISO88 winUnicod КОИ8 CP866 CP866 КОИ8 Unicod ровки 1251 59-5 59-5 П р и м е ч а н и е. При представлении символов кириллицы в двоичном коде рекомендуется использовать два последних шестнадцатеричных символа, приведенных в таблице приложения. Если разрядность полученного двоичного числа будет меньше 64 бит, то его следует дополнить в старшей части нулями.
2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ
КОНТРОЛЬНОЙ РАБОТЫ
2.1. Описание алгоритма DES Алгоритм DES предназначен для шифрования 64 битовых блоков данных с помощью 64 битового ключа, в котором зна Российский государственный открытый технический чащими являются 56 бит (остальные 8 бит — проверочные биты университет путей сообщения, 2005 для контроля на четность). Дешифрование в DES является операцией, обратной шифрованию, и выполняется путем по Таблица вторения операций шифрования в обратной последовательно Матрица начальной перестановки P сти. Обобщенная схема процесса шифрования в алгоритме DES Номер бита показана на рис.1. Процесс шифрования заключается в началь 1 2 3 4 5 6 7 1 58 50 42 34 26 18 10 ной перестановке битов 64 битового блока, шестнадцати цик 2 60 52 44 36 28 20 12 лах шифрования и, наконец, в конечной перестановке битов.Номер байта 3 62 54 46 38 30 22 14 При описании алгоритма DES применены следующие обо 4 64 56 48 40 32 24 16 значения:
5 57 49 41 33 25 17 9 • L и R — последовательности битов (левая (left) и правая 6 59 51 43 35 27 19 11 (right)); 7 61 53 45 37 29 21 13 • LR — конкатенация последовательностей L и R, т.е. такая 8 63 55 47 39 31 23 15 последовательность битов, длина которой равна сумме длин Биты входного блока Т (64 бита) переставляются в соответ L и R; в последовательности LR биты последовательности R ствии с матрицей P: бит 58 входного блока Т становится битом 1, следуют за битами последовательности L; бит 50 — битом 2 и т.д. Эту перестановку можно описать выра • — операция побитового сложения по модулю 2. жением Т0 = P(T). Полученная последовательность битов Т разделяется на две последовательности: L0 — левые или стар шие биты, R0 — правые или младшие биты, каждая из которых Исходный текст содержит 32 бита.
Затем выполняется итеративный процесс шифрования, состо ящий из 16 шагов (циклов). Пусть Тi — результат i й итерации:
Начальная перестановка Тi = Li Ri, Ключ Ши фрование где Li= t1t2...t32 (первые 32 бита);
раз Ri= t33t34...t64 (последние 32 бита).
Рис.1. Обобщенная схема шифрования в алгоритме DES Блок схема алгоритма DES приведена на рис. 2. Пусть из файла исходного текста считан очередной 64 битовый (8 бай товый) блок Т. Этот блок Т преобразуется с помощью матрицы (Подробнее функция шифрования F и алгоритм получения Номер секстета Далее каждый из этих блоков используется как номер эле мента в функциях матрицах S1, S2, … S8, содержащих 4 бито вые значения (табл. 5).
Следует отметить, что выбор элемента в матрице Sj осуще ствляется достаточно оригинальным образом. Пусть на вход матрицы Sj поступает 6 битовый блок Bj = b1b2b3b4b5b6. Тогда двухбитовое число b1b6 указывает номер строки матрицы, а че тырехбитовое число b2b3b4b5 — номер столбца. Например, если на вход матрицы S1 поступает 6 битовый блок B 1 =100110, то 2 битовое число b1b6 = 102 = 210 указывает строку с номером 2 ся биты последовательности С0 (первым битом С0 будет бит матрицы S1, а 4 битовое число b2b3b4b5 =00112=310 указывает ключа шифра, затем бит 49 и т.д., а последними битами — биты столбец с номером 3 матрицы S1. Это означает, что в матрице S1 44 и 36 ключа).
номером 2 и столбца с номером 3, т.е. элемент 810 = 10002. Сово Функция Q первоначальной подготовки ключа битов купность 6 битовых блоков B1, B2, … B8 обеспечивает выбор че (переставленная выборка 1) тырехбитового элемента в каждой из матриц S1, S2, … S8.
В результате получаем S1(B1) S2(B2) … S8(B8), т.е. 32 битовый блок (поскольку матрицы Sj содержат 4 битовые элементы).
Этот 32 битовый блок преобразуется с помощью функции пе рестановки битов Р (табл. 6).
Таким образом, функция шифрования Как нетрудно заметить, на каждой итерации используется но вычисляется из начального ключа К (рис.4). Ключ К представля ет собой 64 битовый блок с 8 битами контроля по четности, рас ния контрольных битов и подготовки ключа к работе использует G(K) разбивается на две половины С0 и D0 по 28 бит каждая.
Первые четыре строки матрицы G определяют, как выбирают Рис. 4. Схема алгоритма вычисления ключей К бираются биты последовательности D0 (т.е. последовательность Функция Н завершающей обработки ключа D0 будет состоять из битов 63, 55, 47,...,12, 4 ключа шифра). (переставленная выборка 2) Как видно из табл. 7, для генерации последовательностей C и D0 не используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для других целей (например, для контроля по четности). Таким образом, в действительности ключ шифра является 56 битовым.
После определения C0 и D0 рекурсивно определяются Сi и Di, i = 1, 2,.... 16. Для этого применяются операции цикличес шага итерации, как показано в табл. 8.
Операции сдвига выполняются для последовательностей Сi Как следует из табл. 9, первым битом ключа Кi, будет 14 й и Di, независимо. Например, последовательность C3 получает бит последовательности Сi, Di, вторым — 17 й бит, 47 м битом ся посредством циклического сдвига влево на две позиции ключа Ki будет 29 й бит Сi, Di, а 48 м битом — 32 й бит Сi, Di.
последовательности С 2, а последовательность D3 — посред ством сдвига влево на две позиции последовательности D2. Пос ледовательности C16 и D16 получаются из C15 и D15 посредством сдвига влево на одну позицию.
Таблица сдвигов Si для вычисления ключа Номер Количество сдвигов Номер Количество сдвигов Ключ Ki, определяемый на каждом шаге итерации, есть ре ленным входным блоком R16L16 на первой итерации использу зультат выбора конкретных битов из 56 битовой последователь ется ключ K16, на второй итерации — K15 и т.д. На 16 й итерации ности С i, D i и их перестановки. Другими словами, ключ, используется ключ K1. На последнем шаге итерации будут по Ki=H(СiDi ), где функция Н определяется матрицей, заверша лучены последовательности L0 и R0, которые конкатенируют матрицей P. Результат такого преобразования — исходная пос Таблица кодировки символов кириллицы Поскольку процессы шифрования и расшифрования ин формации связаны с выполнением громоздких вычислений, выполняемых над двоичными числами, то рекомендуется их автоматизировать. С этой целью целесообразно составить про грамму (программы) на одном из языков высокого уровня. При этом текст программы должен быть приведен в приложении к контрольной работе.