Лабораторная работа 3 Стандарты симметричного шифрования des и гост 2814789 Цель работы Изучить алгоритмы симметричного шифрования информации des и гост 2814789.
 Скачать 1 Mb.
|
|
1 Лабораторная работа № 3 Стандарты симметричного шифрования DES и ГОСТ 28147-89 Цель работы Изучить алгоритмы симметричного шифрования информации DES и ГОСТ 28147-89. Познакомиться с критериями оценки свойств лавинного эффекта. Алгоритм шифрования DES Алгоритм шифрования данных DES (Data Encryption Standard) относится к группе методов симметричного блочного шифрования. Он действовал в США в качестве стандарта в течение 25 лет (с 1977 по 2002 гг.) [1, 2, 4, 6]. Общая схема процесса шифрования DES показана на рисунке 1. Как ив случае любой схемы шифрования, здесь на вход функции шифрования подаётся два типа данных – открытый текст, который требуется зашифровать, и ключ. В данном случае длина открытого текста предполагается равной 64 битам, а длина ключа – 56 битам. 64-битный блок открытого текста 56-битный ключ Первоначальная перестановка (Раунд Раунд Первоначальная подготовка ключа (Завершающая обработка ключа (Циклический сдвиг влево (Завершающая обработка ключа (Циклический сдвиг влево (Перестановка правой и левой частей Обратная перестановка (IP -1 ) 64-битный блок шифрованного текста Рисунок 1 – Общая схема алгоритма шифрования DES Из левой части рисунка 1 видно, что процесс преобразования открытого текста состоит из трёх этапов. Сначала 64-битный блок открытого текста поступает для обработки на вход начальной перестановки ( ), в результате чего получаются переставленные входные данные. Затем следует этап, состоящий из 16 раундов применения одной и той же функции, в которой используются операции перестановки и подстановки. На выходе последнего (го) раунда получается 64-битная последовательность, являющаяся некоторой функцией открытого текста и ключа. Левая и правая половины полученной последовательности данных меняются местами, образуя предрезультат. Наконец, этот предрезультат проходит через перестановку , обратную начальной, в результате чего получается 64-битный блок шифрованного текста. Согласно рекомендациям Шеннона, в каждом раунде выполняется один шаг перемешивания (с использованием соответствующего раун- дового ключа и блоков, после которого следует шаг рассеивания, независящий от ключа. В правой части рисунка 1 показано, каким образом используется 56-битный ключ. Сначала к ключу тоже применяется функция перестановки. Затем с помощью циклического сдвига влево и некоторой перестановки из полученного результата для каждого из 16 раундов генерируется под 2 ключ ( ). Функция перестановки одна и та же для всех раундов, но генерируемые подключи оказываются разными. Необходимо отметить, что все таблицы, приведённые в данной лабораторной работе, стандартные, а, следовательно, должны включаться в реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс дешифрования путём подбора ключа. Структура алгоритма DES показана на рисунке 2. Начальная перестановка IP L(0) R(0) L(1)=R(0) R(1) = L(0) ⊕ f(R(0), K(1)) f K(1) L(2)=R(1) R(2) = L(1) ⊕ f(R(1), K(2)) f K(2) L(15)=R(14) R(15) = L(14) ⊕ f(R(14), K(15)) L(16)=R(15) R(16) = L(15) ⊕ f(R(15), Конечная перестановка Раунд Раунд Раунд Рисунок 2 – Структура алгоритма шифрования DES Пусть из файла считан очередной 8-байтный блок , который преобразуется с помощью матрицы начальной перестановки (см. таблицу 1) следующим образом бит 58 блока становится битом 1, бит 50 – битом 2 и т.д., что даст в результате ( ) ( ). Полученная последовательность бит ( ) разделяется на две последовательности побита каждая ( ) – левые или старшие биты, ( ) – правые или младшие биты. 3 Таблица 1 – Матрица начальной перестановки 58 50 42 34 26 18 10 02 60 52 44 36 28 20 12 04 62 54 46 38 30 22 14 06 64 56 48 40 32 24 16 08 57 49 41 33 25 17 09 01 59 51 43 35 27 19 11 03 61 53 45 37 29 21 13 05 63 55 47 39 31 23 15 07 Затем выполняется шифрование, состоящее из 16 итераций. Результат й итерации описывается следующими формулами ( ) ( ), ( ) ( ) ( ( ) ( )). Функция называется функцией шифрования. Её аргументы – это 32-битная последовательность, полученная на ( й итерации, и 48-битный ключ ( ), который является результатом преобразования 64-битного ключа . Подробно функция шифрования и алгоритм получения ключей ( ) описаны ниже. На й итерации получают последовательности ( ) и ( ), которые дополнительно меняются местами и конкатенируют в результирующую 64-битную последовательность ( ) ( ). Затем позиции бит этой последовательности переставляют в соответствии с матрицей см. таблицу 2). Таблица 2 – Матрица обратной перестановки 40 08 48 16 56 24 64 32 39 07 47 15 55 23 63 31 38 06 46 14 54 22 62 30 37 05 45 13 53 21 61 29 36 04 44 12 52 20 60 28 35 03 43 11 51 19 59 27 34 02 42 10 50 18 58 26 33 01 41 09 49 17 57 25 Матрицы и соотносятся следующим образом значение го элемента матрицы равно 40, а значение го элемента матрицы равно 1, значение го элемента матрицы равно 8, а значение го элемента матрицы равно 2, и т.д. Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей, а затем над последовательностью бит ( ) ( ) выполняются те же действия, что ив процессе шифрования, нов обратном порядке. Итеративный процесс расшифрования может быть описан следующими формулами ( ) ( ), , ( ) ( ) ( ( ) ( )), . На й итерации получают последовательности ( ) и ( ), которые меняют местами и конкатенируют в битовую последовательность ( ) ( ). Затем позиции битов этой последовательности переставляют в соответствии с матрицей . Результат такой перестановки – исходная битовая последовательность. Функция шифрования f для алгоритма DES Теперь рассмотрим функцию шифрования ( ( ) ( )). Схематически она показана на рисунке 3: 4 R(i - 1) (32 бита) Расширитель (E) E ( R(i - 1) ) (48 бит) (48 бит) S4 S5 S2 S3 S1 S7 S8 S6 Перестановка битов (P) f ( R(i - 1), K(i) ) (32 бита) (32 бита) (48 бит) Рисунок 3 – Вычисление функции ( ( ) ( Для вычисления значения функции используются следующие функции-матрицы: – расширение 32-битной последовательности до 48-битной; – преобразование 6-битного блока в 4-битный; – перестановка битв 32-битной последовательности. Функция расширения определяется таблицей 3. В соответствии с этой таблицей первые 3 бита ( ( )) – это биты 32, 1 и 2, а последние – 31, 32 и 1. Таблица 3 – Функция расширения 32 01 02 03 04 05 04 05 06 07 08 09 08 09 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 01 Результат функции ( ( )) есть 48-битная последовательность, которая складывается по модулю 2 (операция ) с 48-битным ключом ( ). Получается 48-битная последовательность, которая разбивается на восемь 6-битных блоков ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ), те. ( ( )) ( ) ( ) ( ) ( ). Функции определяются таблицей 4. Таблица 4 – Функции преобразования Номер столбца 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Номер строки 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 0 1 2 3 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 5 Номер столбца 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 0 1 2 3 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 0 1 2 3 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 0 1 2 3 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 0 1 2 3 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 0 1 2 3 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 К таблице 4 требуются дополнительные пояснения. Пусть на вход функции-матрицы поступает 6-битный блок ( ) , тогда двухбитное число указывает номер строки матрицы, а – номер столбца. Результатом ( ( )) будет 4-битный элемент, расположенный на пересечении указанных строки и столбца. Например, ( ) . Тогда ( ( )) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, ( ) . Применив операцию выбора к каждому из 6-битных блоков ( ) ( ) ( ), получим 32-битную последовательность ( ( )) ( ( )) ( ( )) ( ( )). Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки (см. таблицу 5). Во входной последовательности биты переставляются так, чтобы бит 16 стал битом 1, а бит 7 – битом 2, и т.д. Таблица 5 – Функция перестановки P 16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 10 02 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25 Таким образом, ( ( ) ( )) ( ( ( )) ( ( )) ). Формирование подключей для алгоритма DES Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битных ключей ( ), . На каждой итерации используется новое значение ключа, которое вычисляется изначального ключа . представляет собой 64-битный блок с восемью битами контроля чётности, расположенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и перестановки остальных используется функция первоначальной подготовки ключа (см. таблицу 6). Таблица 6 – Матрица первоначальной подготовки ключа 57 49 41 33 25 17 09 01 58 50 42 34 26 18 10 02 59 51 43 35 27 19 11 03 60 52 44 36 6 63 55 47 39 31 23 15 07 62 54 46 38 30 22 14 06 61 53 45 37 29 21 13 05 28 20 12 04 Результат преобразования ( ) разбивается на два 28-битных блока ( ) и ( ), причём ( ) будет состоять избит преобразованного ключа ( ), а ( ) будет состоять избит преобразованного ключа ( ). После определения ( ) и ( ) рекурсивно определяются ( ) и ( ), . Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в таблице 7. Таблица 7 – Таблица сдвигов для вычисления ключа Номер итерации 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Сдвиг (бит) 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 Полученное значение вновь "перемешивается" в соответствии с матрицей (см. таблицу 8). Таблица 8 – Матрица завершающей обработки ключа 14 17 11 24 01 05 03 28 15 06 21 10 23 19 12 04 26 08 16 07 27 20 13 02 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Ключ ( ) будет состоять избит последовательности ( ) ( ). Таким образом. Восстановление исходного текста осуществляется поэтому же алгоритму, но вначале используется ключ ( ), затем – ( ), и т.д. Алгоритм шифрования ГОСТ 28147-89 ГОСТ 28147-89 – это стандарт симметричного шифрования, принятый в 1989 году в Советском Союзе и установивший алгоритм шифрования данных, составляющих государственную тайну. Вначале х годов алгоритм стал полностью открытым. В Российской Федерации установлен единый стандарт криптографического преобразования текста для информационных систем. Он рекомендован к использованию для защиты любых данных, представленных в виде двоичного кода, хотя не исключаются и другие методы шифрования. Данный стандарт формировался с уч- том мирового опыта, ив частности, были приняты во внимание недостатки и нереализованные возможности алгоритма DES, поэтому использование алгоритма ГОСТ предпочтительнее. ГОСТ предусматривает три режима шифрования (простая замена, гаммирование, гаммиро- вание с обратной связью) и один режим выработки имитовставки. Первый из режимов шифрования предназначен для шифрования ключевой информации и не может использоваться для шифрования других данных, для этого предусмотрены два других режима. Режим выработки ими- товставки (криптографической контрольной комбинации) предназначен для имитозащиты шифруемых данных, те. для их защиты от случайных или преднамеренных несанкционированных изменений. Алгоритм построен потому же принципу, что и DES: это классический блочный шифр с секретным ключом. Однако он отличается от алгоритма DES большей длиной ключа, большим количеством раундов и более простой схемой построения самих раундов. В таблице 9 приведены его основные параметры, для удобства – в сравнении с параметрами алгоритма DES: Таблица 9 – Сравнение параметров алгоритмов DES и ГОСТ Параметры ГОСТ DES Размер блока шифрования 64 бита 64 бита Длина ключа 256 бит 56 бит Число раундов 32 16 Узлы замен (блоки) не фиксированы фиксированы Длина ключа для одного раунда 32 бита 48 бит 7 Параметры ГОСТ DES Схема выработки раундового ключа простая сложная Начальная и конечная перестановки бит нет есть В силу намного большей длины ключа алгоритм ГОСТ гораздо устойчивей алгоритма DES к вскрытию посредством полного перебора по множеству возможных значений ключа. В алгоритме ГОСТ блок текста, подлежащий шифрованию, сначала разбивается на левую половину и правую половину . На этапе используется подключ . На этапе алгоритма ГОСТ выполняется следующее , ( ). Также, как ив алгоритме DES, после 32 раунда выполняется перестановка левой и правой частей полученного шифротекста: Один такт алгоритма ГОСТ показан на рисунке 4. Один такт алгоритма осуществляет одно преобразование Фейстеля [3]. L i-1 (32 бита (32 бита (32 бита (32 бита) S-блоки K i (32 бита) Циклический сдвиг влево на 11 бит Рисунок 4 – Один такт алгоритма ГОСТ 28147-89 Описание функции для алгоритма ГОСТ 28147-89 Сначала правый блок складывается по модулю с подключом . Полученное 32-битное сообщение делится на восемь 4-битных чисел. Каждое из этих 4-битных чисел преобразуется соответствующим блоком в другое 4-битное число. Поэтому любой блок определяется некоторой 16-битной перестановкой на множестве из 16 элементов 0, 1, … , 15. В ГОСТ использовались следующие блоки S1 = ( 4 10 9 2 13 8 0 14 6 11 1 12 7 15 5 3), S2 = ( 14 11 4 12 6 13 15 10 2 3 8 1 0 7 5 9), S3 = ( 5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 11), S4 = ( 7 13 10 1 0 8 9 15 14 4 6 12 11 2 5 3), S5 = ( 6 12 7 1 5 15 13 8 4 10 9 14 0 3 11 2), S6 = ( 4 11 10 0 7 2 1 13 3 6 8 5 9 12 15 14), S7 = ( 13 11 4 1 3 15 5 9 0 10 14 7 6 8 2 12), S8 = ( l 15 13 0 5 7 10 4 9 2 3 14 6 11 8 12). После преобразования блоками полученное 32-битное сообщение сдвигается циклически влево набит. Формирование подключей ГОСТ 28147-89 Исходный 256-битный ключ делится на восемь 32-битных подключей , . Они используются в 32 тактах в следующем порядке При дешифровании порядок использования подключей меняется на противоположный. 8 Критерии оценки свойств лавинного эффекта Пусть ( ) ⊕ , те. бинарный вектор, полученный инвертированием го бита в векторе . Тогда бинарный вектор ( ) ( ( ) ) ( ) называется лавинным вектором по компоненту (здесь – функция шифрования. Пусть для рассматриваемых критериев – это 1 блок открытого текста, размерность вектора равна , аи пусть – это множество, состоящее из всех блоков открытого текста. Введём следующее обозначение мощности множества : , те. – это количество элементов в множестве Матрица зависимостей имеет следующий вид { ( ) }. Эта матрица отражает зависимость го разряда выходного вектора от го разряда входного вектора. Матрица расстояний имеет вид { ( ) ( ( ) ) }, где – функция веса Хэм- минга (число неравных нулю элементов вектора. Существует 4 критерия, по которым предлагается проверять рассеивающие свойства блочных алгоритмов 1. Среднее число бит выхода, изменяющихся при изменении одного бита входного вектора. Это число оценивается по формуле ∑ ∑ ( ) 2. Степень полноты преобразования {( ) } 3. Степень лавинного эффекта 1 1 3 1 2 1 n m ij i j jb m N d nm , где 4. Степень соответствия строгому лавинному критерию 1 1 4 2 1 1 n m ij i j a N d nm , где При исследовании диффузии, те. влияния бит исходного (открытого) текста на преобразованный (зашифрованный) текст, элементы матриц зависимостей и расстояний имеют вид { ( ( ( ) )) ( ( )) }, { ( ( ( ) ) ( )) }. При исследовании конфузии, те. влияния бит ключа на преобразованный (зашифрованный) текст, элементы матриц зависимостей и расстояний имеют вид { ( ( ( ) )) ( ( )) }, { ( ( ( ) ) ( )) }. Задание I. Реализовать приложение для шифрования, позволяющее выполнять следующие действия 1. Шифровать данные по заданному в варианте алгоритму 1) шифруемый текст должен храниться водном файле, а ключ шифрования – в другом 2) зашифрованный текст должен сохраняться в файл 9 3) в процессе шифрования предусмотреть возможность просмотра и изменения ключа, шифруемого и зашифрованного текстов в шестнадцатеричном и символьном виде 4) программа должна показывать время шифрования. 2. Исследовать лавинный эффект (исследования проводить на одном блоке текста 1) для бита, который будет изменяться, приложение должно позволять задавать его позицию (номер) в открытом тексте или в ключе 2) приложение должно уметь после каждого раунда шифрования подсчитывать число бит, изменившихся в зашифрованном тексте при изменении одного бита в открытом тексте либо в ключе 3) приложение может строить графики зависимости числа бит, изменившихся в зашифрованном тексте, от раунда шифрования, либо графики можно строить в стороннем ПО, но тогда приложение для шифрования должно сохранять в файл необходимую для построения графиков информацию. II. Реализовать приложение для дешифрования, позволяющее выполнять следующие действия 1. Дешифровать данные по заданному в варианте алгоритму 1) зашифрованный текст должен храниться водном файле, ключ – в другом 2) расшифрованный текст должен сохраняться в файл 3) в процессе дешифрования предусмотреть возможность просмотра и изменения ключа, зашифрованного и расшифрованного текстов в шестнадцатеричном и символьном виде. III. Реализовать приложение, вычисляющее значения 1–4 критериев для алгоритмов DES и ГОСТ. Можно взять стороннюю реализацию того алгоритма, который не указан в варианте. IV. С помощью реализованных приложений выполнить следующие задания 1. Протестировать правильность работы разработанных приложений. 2. Исследовать лавинный эффект при изменении одного бита в открытом тексте ив ключе построить графики зависимостей числа бит, изменившихся в зашифрованном сообщении, от раунда шифрования (всего должно быть построено 2 графика. 3. Сравнить значения критериев 1–4 для алгоритмов DES и ГОСТ при изменении одного бита в блоке открытого текста и одного бита в ключе при использовании одного итого же сообщения. Сообщение должно состоять хотя бы из пяти блоков (чем больше, тем точнее будут оценки критериев 1–4). 4. Сделать выводы о проделанной работе. Дополнительные критерии оценивания качества работы 1. Наглядность приложений 1 – приложения позволяют просматривать и изменять ключи, шифруемый и зашифрованный тексты во всех предусмотренных заданием представлениях 0 – приложения позволяют просматривать ключи, шифруемый и зашифрованный тексты только в каком-то одном представлении л.р. не принимается – иначе. 2. Построение графиков 1 – программа сама строит графики лавинного эффекта 0 – программа только выгружает необходимые для построения графиков данные л.р. не принимается – программа не строит графики и не выгружает данные. 3. Программное оценивание свойств лавинного эффекта (по критериям 1–4): 1 – программа вычисляет значения критериев 1–4; 0 – программа не вычисляет значения критериев 1–4. Варианты Бригады с нечётным номером реализуют алгоритма бригады сч тным – ГОСТ. 10 Вопросы для защиты 1. Общая схема алгоритма шифрования DES. 2. Почему длина ключа для алгоритма DES равна 56 бит 3. Как соотносятся между собой матрицы ив алгоритме DES? 4. Как происходит шифрование функции ( ( ) ( )) в алгоритме DES? 5. Алгоритм получения раундовых ключей ( ) в алгоритме DES. 6. В чём заключается процесс расшифрования данных в DES? 7. Что представляет собой функция () в алгоритме ГОСТ 8. Как используется заданный ключ при шифровании в алгоритме ГОСТ 9. Общие черты и отличия алгоритмов ГОСТ и DES. 10. Критерии оценки свойств лавинного эффекта. Список литературы 1. Мао, В. Современная криптография теория и практика : Перс англ. / В. Мао. – М. : Издательский дом "Вильямс", 2005. – 768 с. 2. Столлингс, В. Криптография и защита сетей принципы и практика : Перс англ. / В. Столлингс. – е изд. – М. : Издательский дом "Вильямс", 2001. – 672 с. 3. Харин, ЮС. Математические и компьютерные основы криптологии : учебное пособие / ЮС. Харин, В.И. Берник, Г.В. Матвеев, СВ. Агиевич. – Мн. : Новое знание, 2003. – 382 с. 4. Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнайер. – М. : Триумф, 2002. – 816 с. 5. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ 28147-89. – М. : Издательство стандартов, 1989. – 26 с. 6. Data Encryption Standard (DES) : FIPS Publication 46–3. – Gaithersburg : National Institute of Standards and Technology, 1999. – 22 p. |