 |
Перестановка с расширением
|
|
|
|
Задание
Используя среду Microsoft Visual Studio 2013, язык C++, разработать программу, осуществляющую шифрование исходного текстового файла по алгоритму шифра Цезаря. Значение ключа k соответствует порядковому номеру студента в списке группы.
МОДУЛЬ 2. АНАЛИЗ И СИНТЕЗ СИММЕТРИЧНЫХ КРИПТОСИСТЕМ.
Лабораторная работа № 2
«Разработка криптосистемы на основе симметричного алгоритма DES
(Data Encryption Standard)»
Цель работы: Ознакомление с базовыми принципами алгоритма DES. Разработка программы, реализующей метод шифрования по алгоритму DES.
Введение
Стандарт шифрования данных DES (Data Encryption Standard), который ANSI называет алгоритмом шифрования данных DEA (Data Encryption Algorithm), а ISO - DEA-1, за 20 лет стал мировым стандартом.
ЗАДАНИЕ
Разработать консольную программу, выполняющую шифрование и дешифрование файлов, основываясь на параметрах командной строки. Для выбора варианта задания использовать приведённую ниже таблицу.
Описание DES
DES представляет собой блочный шифр, он шифрует данные 64-битовыми блоками. С одного конца алгоритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста.
DES является симметричным алгоритмом: для шифрования и дешифрирования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа).
Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки чётности и игнорируется. Биты чётности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определяется ключом.
|
|
|
На простейшем уровне алгоритм не представляет ничего большего, чем комбинация двух основных методов шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов (подстановка, а за ней - перестановка), зависящей от ключа. Такой блок называется этапом. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому
тексту 16 раз.
Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-х. Изобилие повторений в алгоритме делает его идеальным для реализации в специализированной микросхеме. Первоначальные программные реализации были довольно неуклюжи, но сегодняшние программы намного лучше.
 |
Рис.2.1 - DES
2.1 Схема алгоритма
DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называемых функцией f, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая половины объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной).
На каждом этапе биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещённого и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f. Затем результат функции f
объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов
DES.
|
|
|
Рис.2.2- Один этап DES
Если Bi - это результат i-ой итерации, Lt и Ri - левая и правая половины Bt, Ki - 48-битовый ключ для этапа i,a f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:
Li = Ri-i
Ri = Li_i 
f (Ri_i, K)
2.2 Начальная перестановка
Начальная перестановка выполняется ещё до этапа 1, при этом входной блок переставляется, как показано в 11-й. Эту и все другие таблицы этой главы надо читать слева направо и сверху вниз. Например, начальная перестановка перемещает бит 58 в битовую позицию 1, бит 50 - в битовую позицию 2, бит 42 - в битовую позицию 3, и так далее.
Табл. 2.1 – Начальная перестановка
| 58, | 50, | 42, | 34, | 26, | 18, | 10, | 2, | 60, | 52, | 44, | 36, | 28, | 20, | 12, | 4, |
| 62, | 54, | 46, | 38, | 30, | 22, | 14, | 6, | 64, | 56, | 48, | 40, | 32, | 24, | 16, | 8, |
| 57, | 49, | 41, | 33, | 25, | 17, | 9, | 1, | 59, | 51, | 43, | 35, | 27, | 19, | 11, | 3, |
| 61, | 53, | 45, | 37, | 29, | 21, | 13, | 5, | 63, | 55, | 47, | 39, | 31, | 23, | 15, |
Начальная перестановка и соответствующая заключительная перестановка не влияют на безопасность DES.(Как можно легко заметить, эта перестановка в первую очередь служит для облегчения побайтной загрузки данных открытого текста и шифротекста в микросхему DES. Не забывайте, что DES появился раньше 16- и 32-битовых микропроцессорных шин.) Так как программная реализация этой многобитовой перестановки нелегка(в отличие от тривиальной аппаратной), во многих программных реализациях DES начальная и заключительные перестановки не используются. Хотя такой новый алгоритм не менее безопасен, чем DES, он не соответствует стандарту DES и, поэтому, не может называться DES.
2.3 Преобразования ключа
Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита, как показано в 10-й. Эти биты используются только для контроля чётности, позволяя проверять правильность ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый подключ. Эти подключи, Ki, определяются следующим образом.
Табл. 2.2 – Перестановка ключа
| 57, | 49, | 41, | 33, | 25, | 17, | 9, | 1, | 58, | 50, | 42, | 34, | 26, | 18, |
| 10, | 2, | 59, | 51, | 43, | 35, | 27, | 19, | 11, | 3, | 60, | 52, | 44, | 36, |
| 63, | 55, | 47, | 39, | 31, | 23, | 15, | 7, | 62, | 54, | 46, | 38, | 30, | 22, |
| 14, | 6, | 61, | 53, | 45, | 37, | 29, | 21, | 13, | 5, | 28, | 20, | 12, |
|
|
|
Во первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвигаются налево на один или два бита в зависимости от этапа. Этот сдвиг показан в 9-й.
Табл. 2.3 – Число битов сдвига ключа в зависимости от этапа
| Этап | ||||||||||||||||
| Число |
После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция называется перестановка со сжатием. Ее результатом является набор из 48 битов. Перестановка со сжатием (также называемая переставленным выбором) определена в 8-й. Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отбрасывается.
Табл. 2.4 – Перестановка со сжатием
| 14, | 17, | 11, | 2,4, | 1, | 5, | 3, | 28, | 15, | 6, | 21, | 10, |
| 23, | 19, | 11, | 4, | 26, | 8, | 16, | 7, | 27, | 20, | 13, | 2, |
| 41, | 52, | 31, | 37, | 47, | 55, | 30, | 40, | 51, | 45, | 33, | 48, |
| 44, | 49, | 39, | 56, | 34, | 53, | 46, | 42, | 50, | 36, | 29, |
Из-за сдвига для каждого подключа используется отличное подмножество битов ключа. Каждый бит используется приблизительно в 14 из 16 подключений, хотя не все биты используются в точности одинаковое число раз.
Перестановка с расширением
Эта операция расширяет правую половину данных, Ri, от 32 до 48 битов. Так как при этом не просто повторяются определённые биты, но и изменяется их порядок, эта операция называется перестановкой с расширением. У неё две задачи: привести размер правой половины в соответствие с ключом для операции XOR и получить более длинный результат, который можно будет сжать в ходе операции подстановки. Однако главный
криптографический смысл совсем в другом. За счёт влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Это называется лавинным эффектом. DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита открытого текста и каждого бита ключа.
|
|
|
Перестановка с расширением показана на 9-й. Иногда она называется E-блоком (от expansion). Для каждого 4-битового входного блока первый и четвёртый бит представляют собой два бита выходного блока, а второй и третий биты - один бит выходного блока. В 7-й показано, какие позиции результата соответствуют каким позициям исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2324
Рис. 2.3 - Перестановка с расширением
Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.
Табл. 2.5 – Перестановка с расширением
| 32, | 1, | 2, | 3, | 4, | 5, | 4, | 5, | 6, | 7, | 8, | 9, |
| 8, | 9, | 10, | 11, | 12., | 13, | 12, | 13, | 14, | 15, | 16, | 17, |
| 16, | 17, | 18, | 19, | 20, | 21, | 20, | 21, | 22, | 23, | 24, | 25, |
| 24, | 25, | 26, | 27, | 28, | 29, | 28, | 29, | 30, | 31, | 32, |
Подстановка с помощью S-блоков
После объединения сжатого блока с расширенным блоком с помощью XOR над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки,или S-блоках (от substitution). У каждого S-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти.) 48 битов делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, второй - S-блоком 2, и так далее.
Рис.2.4 – Подстановка - S-блоки
Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4-битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное значение. Все восемь S-блоки отображены в приложении к методическим рекомендациям к практическим занятиям.
Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: b1, b2, b3, b4,b5 и b6. Биты b1 и b6 объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы.
Средние 4 бита, с b2 по b5, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу таблицы.
Например, пусть на вход шестого S-блока (т.е., биты функции XOR с 31 по 36) попадает 110011. Первый и последний бит, объединяясь, образуют 11, что соответствует строке 3 шестого S-блока. Средние 4 бита образ уют 1001, что соответствует столбцу 9 того же S-блока. Элемент S-блока 6, находящийся на пересечении строки 3 и столбца 9, - это 14. (Не забывайте, что строки и столбцы нумеруются с 0, а не с 1.) Вместо 110011 подставляется 1110.
|
|
|
Конечно же, намного легче реализовать S-блоки программно в виде массивов с 64 элементами. Для этого потребуется переупорядочить элементы, что не является трудной задачей. (Изменить индексы, не изменяя порядок элементов, недостаточно. S-блоки спроектированы очень тщательно.) Однако такой способ описания S-
блоков помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4-битового элемента: b2 по Ь5являются входом, а некоторое 4-битовое число - результатом. Биты b1 и b6 определяются соседними блоками, они определяют одну из четырёх функций подстановки, возможных в данном S-
блоке.
Подстановка с помощью S-блоков является ключевым этапом DES. Другие действия алгоритма линейны и легко поддаются анализу. S-блоки нелинейные, и именно они в большей степени, чем все остальное, обеспечивают безопасность DES.
В результате этого этапа подстановки получаются восемь 4-битовых блоков, которые вновь объединяются в единый 32-битовый блок. Этот блок поступает на вход следующего этапа - перестановки с помощью P-блоков.
Перестановка с помощью P-блоков
32-битовый выход подстановки с помощью S-блоков, перетасовываются в соответствии с P-блоком. Эта перестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один
бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Позиции, в
которые перемещаются биты, показаны в 5-й. Например, бит 21 перемещается в позицию 4, а бит 4 - в позицию
31.
Табл. 2.6 – Перестановка с помощью P-блоков
Наконец, результат перестановки с помощью P-блока объединяется посредством XOR с левой половиной
первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следующий этап.
Заключительная перестановка
Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й.
Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, вместо
этого объединённый блок R16L16 используется как вход заключительной перестановки. В этом нет ничего особенного, перестановка половинок с последующим циклическим сдвигом привела бы к точно такому же результату. Это сделано для того, чтобы алгоритм можно было использовать как для шифрования, так и для дешифрирования.
Наконец, результат перестановки с помощью P-блока объединяется посредством XOR с левой половиной
первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следующий этап.
Заключительная перестановка
Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й.
Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, вместо
этого объединённый блок R16L16 используется как вход заключительной перестановки. В этом нет ничего особенного, перестановка половинок с последующим циклическим сдвигом привела бы к точно такому же результату. Это сделано для того, чтобы алгоритм можно было использовать как для шифрования, так и для дешифрирования.
Табл. 2.7 – Заключительная перестановка
| 40, | 8, | 48, | 16, | 56, | 24, | 64, | 32, | 39, | 7, | 47, | 15, | 55, | 23, | 63, | 31, |
| 38, | 6, | 46, | 14, | 54, | 22, | 62, | 30, | 37, | 5, | 45, | 13, | 53, | 21, | 61, | 29, |
| 36, | 4, | 44, | 12, | 52, | 20, | 60, | 28, | 35, | 3, | 43, | 11, | 51, | 19, | 59, | 27, |
| 34, | 2, | 42, | 10, | 50, | 18, | 58, | 26, | 33, | 1, | 41, | 9, | 49, | 17, | 57, |
Дешифрирование DES
После всех подстановок, перестановок, операций XOR и циклических сдвигов можно подумать, что алгоритм дешифрирования, резко отличаясь от алгоритма шифрования, точно также запутан. Напротив, различные
компоненты DES были подобраны так, чтобы выполнялось очень полезное свойство: для шифрования и дешифрирования используется один и тот же алгоритм.
DES позволяет использовать для шифрования или дешифрирования блока одну и ту же функцию. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке. То есть, если на этапах
шифрования использовались ключи K1, K2, K3,..., K16, то ключами дешифрирования будут K16, K15, K14,..., K1. Алгоритм, который создаёт ключ для каждого этапа, также цикличен. Ключ сдвигается направо, а число позиций сдвига равно 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.
ЗАДАНИЕ
Разработать консольную программу, выполняющую шифрование и дешифрование файлов, основываясь на параметрах командной строки. Для выбора варианта задания использовать приведённую ниже таблицу.
ВАРИАНТЫ
| № по журналу | С начальной и конечной перестановками | С поддержкой работы с файлами произвольного размера | Тип ключа: число или кодовая фраза |
| Нет | Нет | Число | |
| Нет | Нет | Кодовая фраза | |
| Нет | Да | Число | |
| Нет | Да | Кодовая фраза | |
| Да | Нет | Число | |
| Да | Нет | Кодовая фраза | |
| Да | Да | Число | |
| Да | Да | Кодовая фраза | |
| Нет | Нет | Число | |
| Нет | Нет | Кодовая фраза | |
| Нет | Да | Число | |
| Нет | Да | Кодовая фраза | |
| Да | Нет | Число | |
| Да | Нет | Кодовая фраза | |
| Да | Да | Число | |
| Да | Да | Кодовая фраза | |
| Нет | Нет | Число | |
| Нет | Нет | Кодовая фраза | |
| Нет | Да | Число | |
| Нет | Да | Кодовая фраза | |
| Да | Нет | Число | |
| Да | Нет | Кодовая фраза | |
| Да | Да | Число | |
| Да | Да | Кодовая фраза | |
| Нет | Нет | Число | |
| Нет | Нет | Кодовая фраза | |
| Нет | Да | Число | |
| Нет | Да | Кодовая фраза | |
| Да | Нет | Число | |
| Да | Нет | Кодовая фраза | |
| Да | Да | Число | |
| Да | Да | Кодовая фраза |
Пояснения:
1. С начальной и конечной перестановками
Алгоритм DES может применятся как с этими перестановками так и без, т.к. основная их цель перестановка бит удобным для аппаратной обработки образом. Строго говоря без перестановок это уже не DES, но для лабораторной работы это не важно.
2. С поддержкой работы с файлами произвольного размера
Варианты с такой поддержкой должны корректно обрабатывать файлы любого размера. В то время как варианты без неё должны уметь корректно работать только с файлами, размер которых кратен 8 байт.
3. Тип ключа: число или кодовая фраза
В случае числового ключа, в командной строке должно задаваться именно число (система счисления роли не играет). Для кодовой фразы перед использованием её в качестве ключа следует применить над ней некоторую функцию, которая преобразует её в 64-битовое число.
МОДУЛЬ 2. АНАЛИЗ И СИНТЕЗ СИММЕТРИЧНЫХ КРИПТОСИСТЕМ
Лабораторна я работа № 3
«Разработка криптосистемы на основе симметричного алгоритма ГОСТ 28147-89»
Цель работы: Ознакомление с базовыми принципами алгоритма ГОСТа 28147–89. Разработка программы, реализующей метод шифрования по алгоритму ГОСТа 28147–89.
|
|
|
12 |
