ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ВОЛЖСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (филиал) ВОЛГОГРАДСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА
КАФЕДРА «ИНФОРМАТИКА И ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ»
Блочное симметричное шифрование
Методические указания к лабораторным работам по
курсу «Методы и средства защиты компьютерной информации»
Волгоград 2008
УДК 004.056
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМ: Блочное симметричное шифрование / Сост. Лясин Д.Н., Макушкин И.А.; Волгоград. гос. техн. ун-т. - Волгоград, 2008,. – 24 с.
Содержатся сведения, необходимые для изучения студентами основных принципов блочного симметричного шифрования данных: структуры шифров, формирования образующих функций, использования материала ключа. Дан обзор современных блочных симметричных шифров и режимов их использования. Приведены варианты заданий к лабораторным работам.
Предназначены для студентов, обучающихся по направлению 5528 "Информатика и вычислительная техника" и специальности 2201 "Вычислительные машины, комплексы, системы и сети" всех форм обучения в рамках курса «Методы и средства защиты компьютерной информации»
Ил. 6. Табл. 6. Библиогр.: 5 назв.
Рецензент: к.т.н., доцент каф. ВАЭ и ВТ ВПИ (филиал) ВолгГТУ
Студеникин А.В.
Печатается по решению редакционно-издательского совета Волгоградского государственного технического университета
© Волгоградский государственный
технический университет, 2008
Лабораторная работа N 2
Блочное симметричное шифрование
Цель работы:
изучение структуры и основных принципов работы современных алгоритмов блочного симметричного шифрования, приобретение навыков программной реализации блочных симметричных шифров.
Основные сведения
Блочное симметричное шифрование предполагает выполнение криптографического преобразования над блоками открытого текста фиксированного размера (32, 64, 128, 256 бит). Таким образом, блочный шифр можно представить как шифр замены над очень большим алфавитом, который, например, для блока размером 64 бита имеет 264
символов. Любой шифр замены можно представить в виде таблицы соответствия между входными и выходными символами. Однако размер такой таблицы для современных блочных шифров будет настолько велик (требуется 270
бит ЗУ для алгоритма с 64-битным блоком только для одного ключа шифрования), что представление соответствия входных и выходных данных эффективно описывается только алгоритмически.
Обобщенно алгоритм блочного шифрования описывается следующим образом: блок открытого текста X
преобразуется в блок шифротекста Y
того же размера с использованием некоторого ключа шифрования Key
:
Y
=Encrypt(X,
Key
)
Процедура дешифрации выполняет обратное преобразование, используя тот же самый ключ:
X
=Decrypt(Y,
Key
)
Преобразования Encrypt и Decrypt трактуют блоки открытого и зашифрованного текста как целые числа и выполняют над ними ряд арифметических либо логических действий, основная задача которых – тщательно «перемешать» биты блока открытого текста между собой, а также связать их с битами используемого ключа шифрования для формирования блока закрытого текста. При этом для блочного шифра несущественен тип преобразуемой информации, он разбивает ее на блоки определенного размера, интерпретирует эти блоки как целые числа в диапазоне [0..2k
-1], где k
- размер блока, и выполняет над этими числами ряд преобразований в соответствии с алгоритмом метода.
Для выполнения криптографических преобразований в блочных шифрах особую роль играют обратимые операции, поскольку только использование данных операций обеспечивает инъективность (обратимость) всего криптопреобразования [1]. Наиболее часто используемые в современных блочных шифрах обратимые операции приведены в таблице 1.
Таблица 1. Основные обратимые операции
| Название операции |
Графическое обозначение |
Формула преобразования |
Обратное преобразование |
| Сложение |
|
X’
|
Вычитание |
| Сложения по модулю 2 |
|
X’
|
Автообратима |
| Умножение по модулю 2N
|
|
X’
|
Сомножитель можно найти по алгоритму Евклида |
| Циклические сдвиги вправо/влево |
|
X’
X’
|
Циклический сдвиг в обратном направлении |
| Перестановка бит |
|
||
| Табличная подстановка |
|
X’
|
Обратная подстановка |
Особенное внимание в таблице 1 необходимо уделить операциям умножения и табличной подстановки, поскольку они, внося нелинейность в общее криптопреобразование, делают алгоритм более стойким к линейному криптоанализу [2].
Одним из основных принципов структурного построения современных криптоалгоритмов является принцип итерирования. Его идея заключается в многократной, состоящей из нескольких циклов (или раундов), обработке одного блока открытого текста с использованием на каждом цикле специального ключа раунда, вычисляемого на основе ключа шифрования. Количество циклов можно варьировать из соображений криптостойкости и эффективности реализации алгоритма: увеличение количества циклов приводит к повышению стойкости шифра, но увеличивает время шифрации и потребляемые вычислительные ресурсы. Подобные циклические структуры принято называть сетями,
и большинство современных блочных шифров построены с использованием сетевой архитектуры.
В качестве примера криптографических сетей можно привести SP-сети, содержащие в каждом раунде два слоя – подстановки (substitution), в котором обычно используются обратимые операции преобразования над шифруемым блоком и материалом ключа, и перестановки (permutation), в котором происходит перестановка бит внутри блока. Однако самой популярной сегодня является сеть Фейштеля, схема которой представлена на рис.1.
При шифровании блок открытого текста разбивается на две равные части - левую и правую. Очевидно, что длина блока при этом должна быть четной. На каждом цикле одна из частей подвергается преобразованию при помощи образующей
функции F
и вспомогательного ключа раунда ki
, полученного из исходного ключа. Результат преобразования складывается по модулю 2 с другой частью, после чего части меняются местами. Преобразования на каждом цикле идентичны и лишь после последнего раунда не выполняется перестановка частей блока.
Достоинством сети Фейштеля является то, что дешифрация выполняется той же последовательностью преобразований, лишь порядок следования вспомогательных ключей меняется на обратный. Это достигается за счет автообратимости операции суммы по модулю 2, смешивающей части блока между собой
. Если размер блока шифрования криптоалгоритма слишком велик, возможны модификации сети Фейштеля с 4 ветвями.
Описание алгоритмов шифрования DES и TEA, построенных на основе сети Фейштеля, можно найти в [2, 5]. Сеть Фейштеля использована как структурная основа таких алгоритмов шифрования, как FEAL, CAST, Blowfish, IDEA, RC5, COST, ГОСТ 28147-89 и многих других. Рассмотрим подробнее некоторые из этих алгоритмов.
Алгоритм IDEA
(Intrnational Data Encryption Algorithm) задумывался как замена стандарта шифрования DES и не стал таковым по причине его запатентованности и необходимости лицензирования для коммерческих приложений. Конечная редакция алгоритма была опубликована в 1992 году.
IDEA оперирует 64-битовыми блоками открытого текста. Исходный блок данных разбивается на 4 части – все операции IDEA выполняются в 16-битной арифметике. Затем в каждом из 8-ми раундов над ветвями и материалом ключа выполняются в специально подобранной очередности три операции:
поразрядное сложение по модулю 2 (операция "исключающее ИЛИ"); операция обозначается как (+);
сложение беззнаковых целых по модулю 216
; операция обозначается как [+];
умножение беззнаковых целых по модулю (216
+1), причем блок из 16 нулей рассматривается как 216
; операция обозначается как (·). Если после взятия модуля результат равен 216
, то он заменяется на 0.
Для обеспечения симметричности операций шифрования/дешифрования после восьми раундов над ветвями производится дополнительное преобразование.
Алгоритм использует 128-битный ключ. Создание подключей раунда Z
1
...Z
6
также относительно несложно. Алгоритм использует всего 52 подключа (по шесть для каждого из восьми циклов и еще четыре для преобразования выхода). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это - первые восемь подключей для алгоритма (шесть подключей - для первого цикла и первые два подключа - для второго). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей (четыре подключа - для второго цикла и четыре подключа - для третьего). Ключ снова циклически сдвигается влево на 25 бит для получения следующих восьми подключей и т.д., пока выполнение алгоритма не завершится.
Дешифрование осуществляется аналогичным образом, за исключением того, что порядок использования подключей становится обратным, причем ряд подключей дешифрования являются или аддитивными, или мультипликативными обратными величинами подключей шифрования (см. таблицу 2).
Таблица 2. Подключи шифрования и дешифрования алгоритма IDEA
| Цикл |
Подключи шифрования |
Подключи дешифрования |
| 1 |
Z1
|
Z1
|
| 2 |
Z1
|
Z1
|
| 3 |
Z1
|
Z1
|
| 4 |
Z1
|
Z1
|
| 5 |
Z1
|
Z1
|
| 6 |
Z1
|
Z1
|
| 7 |
Z1
|
Z1
|
| 8 |
Z1
|
Z1
|
| 9 |
Z1
|
Z1
|
.
Рисунок 2 - Cхема алгоритма IDEA (режим шифрования)
Для реализации алгоритма IDEA было принято соглашение, что мультипликативная обратная величина от 0 равна 0.
Алгоритм IDEA обладает рядом преимуществ перед алгоритмом DES. Он значительно безопаснее алгоритма DES, поскольку 128-битовый ключ алгоритма IDEA вдвое больше ключа DES. Внутренняя структура алгоритма IDEA обеспечивает лучшую устойчивость к криптоанализу. Существующие программные реализации примерно вдвое быстрее реализаций алгоритма DES. Недостатком алгоритма является его ориентированность на 16-разрядную архитектуру, что снижает эффективность использования вычислительных средств.
Для поиска мультипликативного обратного при получении ключей дешифрования можно использовать расширенный алгоритм Евклида
, который позволяет в целых числах найти решение уравнения ax
+
by
=
1 при заданных а
и b
.
Очевидно, что если решение существует (а оно существует, если а
и b
взаимно просты), то x
будет величиной, мультипликативно обратной а
по модулю b
.
Алгоритм Евклида 1. Определить матрицу E
:
2. Вычислить r
–остаток от деления числа a
на b
:
a
=
bq
+
r
,
0 £ r
< b
3. Если r
=
0, то первый столбец матрицы E
является решением уравнения.
4.Если r
¹
0, заменить матрицу Е
:
5.Поменять местами столбцы матрицы Е
.
6. Заменить пару чисел a
,
b
на b
,
r
и перейти к шагу 2.
Отечественным стандартом блочного шифрования является алгоритм ГОСТ 28147-89
, который использует 256-битный ключ шифрования и 32 цикла преобразования 64-битных блоков исходного сообщения. Алгоритм реализует классическую схему сети Фейштеля из рис.1. При этом образующая функция реализована следующим образом (рис.3) .
Сначала правая половина блока и ключ раунда складываются по модулю 232
. Результат сложения разбивается на восемь 4-битовых последовательностей, каждая и которых поступает на вход соответствующего S
-блока. Каждый блок представляет собой таблицу подстановки, которая заменяет поступающее на вход число в диапазоне [0..15] на другое число в том же диапазоне. Выходы всех S
-блоков объединяются в 32-битное слово, которое затем циклически сдвигается влево на 11 битов и объединяется с левой частью блока операцией XOR.
Формирование ключей раунда осуществляется по простой схеме. 256-битный ключ разбивается на восемь 32-битных машинных слов. Они нумеруются с К0
по К7.
32 ключа раунда получаются применением этих машинных слов в следующем порядке:
К0,
К1,
К2,..,.
К7,
К0,
К1,
К2,...,
К7,
К0,
К1,
К2,…,
К7,
К7,
К6,
К5,...,
К0,
то есть в последних 8 раундах ключи подаются в обратном порядке.
Алгоритм ГОСТ является симметричным, и для дешифрации достаточно подать на вход алгоритма блоки зашифрованных сообщений и ключи раундов в порядке, обратном их следованию при шифрации.
Особенностью алгоритма является отсутствие в стандарте каких-либо рекомендаций по выбору содержимого таблиц подстановок (S
-блоков). Первоначально 8*16*4=512 бит таблиц подстановок являлись также частью ключевой информации. Впоследствии требование к секретности содержимого таблиц было упразднено, однако статическое, обеспечивающее высокую криптостойкость алгоритма, содержимое таблиц подстановки так и не было опубликовано. Набор S
-блоков, рекомендуемый стандартом хеширования ГОСТ Р 34.11-94, использующего блочный шифр ГОСТ 28147-89 в качестве основной преобразующей операции, приведен в таблице 3 [4].
Таблица 3. S
-блоки алгоритма ГОСТ 28147-89
| S0 |
4 |
10 |
9 |
2 |
13 |
8 |
0 |
14 |
6 |
11 |
1 |
12 |
7 |
15 |
5 |
3 |
| S1 |
14 |
11 |
4 |
12 |
6 |
13 |
15 |
10 |
2 |
3 |
8 |
1 |
0 |
7 |
5 |
9 |
| S2 |
5 |
8 |
1 |
13 |
10 |
3 |
4 |
2 |
14 |
15 |
12 |
7 |
6 |
0 |
9 |
11 |
| S3 |
7 |
13 |
10 |
1 |
0 |
8 |
9 |
15 |
14 |
4 |
6 |
12 |
11 |
2 |
5 |
3 |
| S4 |
6 |
12 |
7 |
1 |
5 |
15 |
13 |
8 |
4 |
10 |
9 |
14 |
0 |
3 |
11 |
2 |
| S5 |
4 |
11 |
10 |
0 |
7 |
2 |
1 |
13 |
3 |
6 |
8 |
5 |
9 |
12 |
15 |
14 |
| S6 |
13 |
11 |
4 |
1 |
3 |
15 |
5 |
9 |
0 |
10 |
14 |
7 |
6 |
8 |
2 |
12 |
| S7 |
1 |
15 |
13 |
0 |
5 |
7 |
10 |
4 |
9 |
2 |
3 |
14 |
6 |
11 |
8 |
12 |
Достоинствами алгоритма ГОСТ можно назвать простоту реализации, причем как программной, так и аппаратной, поскольку алгоритм не использует битовых перестановок, большой размер ключа делает малоперспективной силовую атаку на шифр, большое количество раундов затрудняют дифференциальный и лин
Алгоритм Rijndael
в 2000 году стал победителем открытого конкурса на криптостандарт блочного шифрования США, проводившегося под эгидой Национального Института Стандартизации и Техники (NIST). После победы в конкурсе этот алгоритм получил второе название AES
(Advanced Encryption Standard). Данный блочный шифр развивает нетрадиционную для последнего времени структуру прямоугольных KALST-сетей. KALST
представляет собой аббревиатуру английских терминов Key Addition (добавление ключа), Substitution (табличная подстановка), Linear Transposition (линейное перемешивание).
Rijndael представляет собой итеративный блочный шифр, имеющий переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть независимо друг от друга 128, 192 или 256 бит.
Разнообразные преобразования работают с промежуточным результатом, называемым состоянием (State).
Состояние можно представить в виде прямоугольного массива байтов. Этот массив имеет 4 строки, а число столбцов обозначено как Nb
и равно длине блока, деленной на 32. Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками. Число столбцов обозначено как Nk
и равно длине ключа, деленной на 32. Это показано на рисунке 1.
Рисунок 4. Пример представления состояния (Nb
=6) и ключа шифрования (Nk
=4)
Входные данные для шифра обозначаются как байты состояния в порядке A0,0
, A
1,0
,
A
3,0
,
A
0,1
,
A
1,1
,
A
3,1
,
A
4,1
... После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке. Число циклов обозначено как Nr
и зависит от значений Nb
и Nk
. Оно приведено в таблице 4.
| Таблица 4. Число раундов Rijdael как функция от длины блока и длины ключа |
|||
| Nr |
Nb = 4 |
Nb = 6 |
Nb = 8 |
| Nk = 4 |
10 |
12 |
14 |
| Nk = 6 |
12 |
12 |
14 |
| Nk = 8 |
14 |
14 |
14 |
Алгоритм шифрования Rijndael состоит из:
1. Начального сложения блока открытого текста с ключом;
2. Nr
- 1 раундов основного преобразования;
3. Заключительного раунда.
Преобразование раунда состоит из четырех различных преобразований: табличной подстановки (ByteSub), циклического сдвига строк (ShiftRow), линейного перемешивания столбцов (MixColumn), добавления материала ключа (AddRoundKey). В заключительном раунде из преобразований исключается линейное преобразование столбцов.
Преобразование ByteSub является нелинейной байтовой подстановкой, выполняющейся для каждого байта состояния независимо. Таблица подстановки является обратимой и сконструирована в виде композиции двух преобразований:
1.Во-первых, c помощью алгоритма Евклида берется мультипликативная инверсия в GF (28
) по модулю полинома m
(x
) вида m(x) = x
8
+ x
4
+ x
3
+ x
+ 1. '00' отображается сам в себя (подробнее о полях Галуа и преобразованиях в них см [3]). 2.Затем применяется аффинное (в GF (2)) преобразование, определяемое следующим образом:
Инверсия ByteSub есть применение байтовой подстановки в соответствии с инверсной таблицей. Это получается инверсией аффинного отображения и мультипликативной инверсией в GF (28
).
В преобразовании ShiftRow строки состояния циклически сдвигаются на различные значения. Нулевая строка не сдвигается. Строка 1 сдвигается на С1
байтов, строка 2 на С2
байтов, строка 3 на С3
байтов. Величины С1
, С2
и С3
зависят от Nb
. Значения приведены в таблице 5.
|
|
|||
| Nb
|
С1
|
С2
|
С3
|
| 4 |
1 |
2 |
3 |
| 6 |
1 |
2 |
3 |
| 8 |
1 |
3 |
4 |
Инверсией для ShiftRow является циклический сдвиг трех нижних строк соответственно на Nb
- С1
,
Nb
- С2
и Nb
- С3
байт, чтобы байт в позиции j
в строке i
перемещался в позицию (j
+
Nb
-
Ci
) mod Nb
.
В преобразовании MixColumn столбцы состояния рассматриваются как полиномы в GF (28
) и умножаются по модулю х
4
+ 1 на фиксированный полином:
c
(x
) = '03' x
3
+ '01' x
2
+ '01' x
+ '02'. Данный полином является взаимно простым с х
4
+ 1 и, следовательно, инвертируем. Это может быть записано в виде умножения матрицы. Пусть b
(x
) = c
(x
) * a
(x
).
Инверсия MixColumn является аналогичным MixColumn. Каждый столбец преобразуется умножением его на полином d
(x
), определяемый следующим образом: ('03' x
3
+ '01' x
2
+ '01' x
+ '02') * d
(x
) = '01'
В результате получаем
d
(x
) = '0B' x
3
+ '0D' x
2
+ '09' x
+ '0E'
Сложение с ключом раунда AddRoundKey выполняется как операция побитового XOR ключа раунда с текущим состоянием. Длина ключа раунда равна длине блока Nb. AddRoundKey является инверсией самого себя.
Ключи раунда получаются из ключа шифрования с помощью преобразования, состоящего из двух компонентов ключа (Key Expansion) и выбор циклового ключа (Round Key Selection). Основополагающие принципы алгоритма выглядят следующим образом:
1. Общее число бит ключей раунда равно длине блока, умноженной на число циклов плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа).
2. Ключ шифрования расширяется в Расширенный Ключ (Expanded Key).
3. Цикловые ключи берутся из Расширенного ключа следующим образом: первый цикловой ключ содержит первые Nb слов, второй - следующие Nb слов и т.д.
Expanded Key является линейным массивом четырехбайтных слов и обозначается как W
[Nb
* (Nr
+ 1)]. Первые Nk
слов состоят из ключа шифрования. Остальные слова определяются рекурсивно. Функция расширения ключа зависит от значения Nk
: существует версия функции для Nk
, равному или меньшему 6, и версия для Nk
больше 6. Для Nk
≤6 мы имеем:
KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+1)]){ for(i=0;i<Nk;i++) W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key [4*i+3]); for(i=Nk;i<Nb*(Nr+1);i++) { temp=W[i-1]; if (i%Nk==0) temp=ByteSub(RotByte(temp))^Rcon[i/Nk]; W[i]=W[i-Nk]^temp; }}
В данном случае ByteSub является функцией, которая возвращает четырехбайтное слово, в котором каждый байт является результатом применения S
-box Rijndael к байту в соответствующей позиции во входном слове. Функция RotByte (W
) возвращает слово, в котором байты циклически переставлены таким образом, что для входного слова (a
,
b
,
c
,
d
) создается выходное слово (b
,
c
,
d
,
a
).
Можно заметить, что первые Nk
слов заполняются ключом шифрования. Каждое следующее слово W
[i
] равно XOR предыдущего слова W
[i
-1] и позиций слова Nk
до W
[i
-
Nk
]. Для слов в позициях, которые кратны Nk
, сначала применяется преобразование XOR к W
[i
-1] и константой раунда. Данное преобразование состоит из циклического сдвига байтов в слове RotByte, за которым следует применение табличной подстановки для всех четырех байтов в слове (ByteSub).
Для Nk
> 6 имеем:
KeyExpansion(byte Key [4*Nk],word W[Nb*(Nr+1)]){ for (i=0;i<Nk;i++) W[i]=(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]); for (i=Nk;i<Nb*(Nr+1); i++) { temp=W[i-1]; if(i % Nk==0) temp=SubByte(RotByte(temp))^Rcon[i/Nk]; else if (i % Nk==4) temp=SubByte(temp); W[i]=W[i-Nk]^temp; }}
Отличие в схеме для Nk
6 состоит в том, что для i
-4 кратных Nk
, SubByte применяется для W
[i
-1] перед XOR.
Константы раунда не зависят от Nk
и определяются следующим образом:
Rcon
[i
] = (RC
[i
], '00', '00', '00').
RC
[i
] являются элементами в GF (28
) со значением x
(
i
-1)
таким, что:
RC
[1] = 1 (т.е. '01')RC
[i
] = x
(т.е. '02') • (RC
[i
-1]) = x
(i
-1)
Ключ раунда i получается из слов буфера ключа раунда W
[Nb
*
i
] до W
[Nb
* (i
+1)].
Достоинствами алгоритма Rijndael является хорошее быстродействие, вариативность при выборе длины блока и ключа, возможность распараллеливания процедур шифрации/дешифрации.
Основным недостатком алгоритма является его несимметричность по процедурам шифрации/дешифрации.
Шифр RC
6
был также представлен на конкурсе AES группой разработчиков во главе с известным криптографом Рональдом Ривестом. Шифр очень прост, что делает его очень привлекательным для использования в различных прикладных задачах. Он представляет собой сеть Фейштеля из 20 раундов с 4 ветвями смешанного типа – результат образующих функций, вычисленных от четных ветвей, накладывается на нечетные ветви, затем ветви меняются местами. Размер блока – 128 бит. Структура алгоритма приведена на рис.5.
Рисунок 5 – Алгоритм шифрования RC6
Преобразование T
представляет собой функцию: T
(X
)=(X
*(2*X
+1)) mod 232
. Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины. В качестве параметра циклического сдвига на переменное число бит поступает результат умножения, циклически смещенный влево на 5 бит. Таким образом, реально величину переменного сдвига определяют 5 старших бит результата 32-битного умножения – а именно эти биты находятся в центре 64 битного общего (до взятия вычета) произведения, и, следовательно, зависят от всех бит входного параметра X
.
Дешифрование алгоритма RC6 производится инвертированием порядка выполняемых в сети Фейштеля действий и заменой операции сложения на вычитание.
Формирование ключей раунда в RC6 происходит следующим образом. Сначала ключ, размер которого может иметь произвольную длину, выравнивается по 32-битной границе нулями. В результате получается массив K
из с
машинных слов K
[0]..K
[c
-1]. Массив ключей раунда назовем k
, всего потребуется 44 элемента. На первом этапе массив k заполняется с использованием специальных констант, полученных из двоичной записи чисел e
(основание натурального логарифма) и φ
(золотое сечение):
k
[i
]=B7E1516316
+i
*9E3779B916
, i
=0..43.
На втором этапе производится рекурсивное перемешивание между собой массивов K
и k
:
A=0;B=0;i=0;j=0;
for( x=0;x<44*3;x++)
{
k[i]=(k[i]+A+B) ROL 3; B=k[i];
i=(i+1) %44;
K[j]=(K[j]+A+B) ROL (A+B);A=k[j];
j=(j+1)%c;
}
Троекратное рекурсивное перемешивание материала ключа с ключом при наличии сдвига на переменное количество бит существенно затрудняет криптоанализ алгоритма.
Основное преимущество алгоритма – высокая скорость работы на 32-разрадных аппаратных платформах. Его криптостойкость определяется стойкостью к атакам его предшественника (RC5), который в свое время очень хорошо изучен криптографами. К недостатком алгоритма относят его слабую распараллеливаемость.
При практическом использовании блочных шифров применяются различные схемы шифрования, известные под названием рабочие режимы шифрования
. Эти режимы позволяют реализовать дополнительные, отсутствующие в исходной конструкции блочного шифра функции. Наиболее популярны следующие 4 режима шифрования (рис. 6):
1) режим электронной кодовой книги (Electronic Code Book, ECB);
2) режим сцепления блоков шифра (Cipher Block Changing, CBC);
3) режим обратной связи по шифротексту (Electronic Feedback, CFB);
4) режим обратной связи по выходу (Output Feedback, OFB).
В режиме ECB шифрование/дешифрование i-го блока открытого текста/шифротекста выполняется независимо от остальных блоков:
ci
=Ek
(mi
), mi
=Dk
(ci
).
Недостатком данного режима шифрования является то, что одинаковые блоки входного текста будут кодироваться в одинаковые блоки шифротекста, что дает возможность злоумышленнику, во-первых, делать предположения о характере информации в открытом тексте, а во-вторых, подменить один или несколько блоков шифротекста. Достоинством режима можно назвать простоту реализации, а также возможность распараллеливания процедуры шифрации.
Режим CBC предполагает следующие алгоритмы шифрации/дешифрации:
ci
=Ek
(mi
Å ci-1
), mi
=Dk
(ci
) Å ci-1
В режиме CBC каждый блок открытого текста складывается с блоком шифротекста, полученным на предыдущем этапе. Таким образом, происходит сцепление блоков друг с другом и независимая манипуляция с каждым из них невозможна, а одинаковые входные блоки будут давать на выходе разные блоки. Однако задача распараллеливания процедуры кодирования в этом режиме затруднена. Дополнительным параметром процедур шифрования/дешифрования является параметр c0
. Существует модификация данного режима, называемая PCBC (Propagating Cipher Block Changing), которая позволяет при дешифрации распространить единичную ошибку, возникшую при передаче шифротекста, на весь шифротекст и таким образом обнаруживать ошибки передачи. Правила шифрования и дешифрации PCBC:
ci
=Ek
(mi
Å mi-1
Å ci-1
), mi
=Dk
(ci
) Å ci-1
Å mi-1
Режим PCBC не утвержден международными стандартами, однако находит применение в протоколе ключевого обмена Kerberos.
В режиме CFB также происходит «маскировка» блока открытого текста уже зашифрованными блоками:
ci
=mi
Å Ek
(ci-1
), mi
=Е
k
(ci-1
) Å ci
Режим CFB также связывает значение текущего блока шифротекста со значениями всех предыдущих блоков входного текста. Если длина сообщения не кратна размеру блока шифра, то в режиме CBC необходимо дополнять последний блок дополнительными битами и сообщать на принимающую сторону истинный размер сообщения, а режим CFB позволяет сформировать шифротекст того же размера, что и исходное сообщение. Еще одна отличительная особенность – отсутствие процедуры дешифрации, что упрощает реализацию криптосистемы, особенно для несимметричных криптоалгоритмов.
В режиме OFB исходное сообщение вообще не подвергается криптопреобразованию, оно складывается с шифруемыми на секретном ключе блоками si
(s0
является задаваемым несекретным параметром режима):
ci
=mi
Å si
, mi
=ci
Å si
, si
=Ek
(si-1
)
В этом режиме, как и в режиме ECB, ошибки, которые могут возникнуть при передаче шифротекста по каналам связи, локализуются в блоке, не распространяясь на соседние, причем в режиме OFB ошибочными будут только биты, подвергшиеся изменению (в ECB изменится весь блок). Это дает возможность злоумышленнику незаметно для принимающей стороны подменить блок шифротекста. Возможности распараллеливания процедур шифрации/дешифрации затруднены. Режим также не требует реализации процедуры дешифрации данных. В режиме усовершенствованного OFB предлагается маскировать блок открытого текста не величиной si
,
а si
+V
(mod 264
), где V
– некоторый вектор инициализации.
Более полный список режимов шифрования можно посмотреть в [5].
Порядок выполнения работы
1. Ознакомьтесь с теоретическими основами блочного симметричного шифрования в настоящих указаниях, а также в [2] и конспектах лекций.
2. Получите вариант задания у преподавателя.
3. Напишите программу согласно варианту задания.
4. Отладьте разработанную программу и покажите результаты работы программы преподавателю.
5. Составьте отчет по лабораторной работе
Содержание отчета
Отчет по лабораторной работе должен содержать следующие сведения:
- название и цель работы;
- вариант задания;
- листинг разработанной программы с комментариями;
- результаты работы программы.
Варианты заданий
Реализовать систему симметричного блочного шифрования, позволяющую шифровать и дешифровать файл на диске с использованием заданного блочного шифра в заданном режиме шифрования. Перечень блочных шифров и режимов шифрования приведен в таблице 6. Номер шифра и режима для реализации получить у преподавателя.
Таблица 6 – Варианты заданий к лабораторной работе
| Алгоритм |
Режим шифрования |
||
| Номер |
Название |
Номер |
Режим |
| 1 |
TEA |
а |
ECB |
| 2 |
IDEA |
б |
CBC |
| 3 |
RC6 |
в |
PCBC |
| 4 |
ГОСТ 28147-89 |
г |
CFB |
| 5 |
Rijndael |
д |
OFB |
| 6 |
DES |
||
Контрольные вопросы
1. Перечислите основные обратимые операции, используемые в образующих функциях блочных шифров.
2. Что такое сеть Фейштеля? В чем ее основные достоинства?
3. Какие параметры блочных шифров влияют на его криптостойкость?
4. Какие блочные шифры, построенные по принципу сети Фейштеля, вам известны?
5. Проведите сравнительный анализ алгоритмов ГОСТ 28147-89 и Rijndael.
6. Проведите сравнительный анализ режимов шифрования CBC и ECB.
7. Проведите сравнительный анализ режимов шифрования CBC и CFB
Л и т е р а т у р а
1. Конеев И.Р., Беляев А.В. Информационная безопасность предприятия. -СПб.: БХВ-Петербург, 2003.- 752с.:ил.
2. Лясин Д.Н., Саньков С.Г. Методы и средства защиты компьютерной информации (учебное пособие). – Волгоград, Издательство ВолгГТУ РПК "Политехник”, 2005г.
3. Официальный сайт национального института стандартизации и техники (NIST) США. http://csrc.nist.gov/CryptoToolkit/aes/
4. Чмора А.Л. Современная прикладная криптография. 2-е изд. -М.: Гелиос АРВ, 2002.-256с.:ил.
5. Шнайер Б. Прикладная криптография.- М. : Триумф, 2002. – 816с.
Составители: Дмитрий Николаевич Лясин
Игорь Александрович Макушкин
Блочное симметричное шифрование. Методические указания к лабораторным работам по курсу «Методы и средства защиты компьютерной информации».
В авторской редакции.
Темплан 2008 г. , поз. N 13В (з)
Лицензия ИД N04790 от 18.05.01
Подписано в печать _________ . На магнитном носителе.
Усл. печ. л. 1,4 . Уч. -изд.л. 1,44.
Волгоградский государственный технический университет.
400131 Волгоград , пр. Ленина , 28.
РПК "Политехник" Волгоградского государственного технического
университета.
400131 Волгоград , ул. Советская , 35.