Алгоритмы AES, RSA и DES

АЛГОРИТМЫ AES, RSA И DES.

Методическое пособие для студентов

Костиков Ю. А., Мокряков А. В., Павлов В. Ю., Романенков А. М.

МОСКВА

Пособие для студентов.

Под редакцией авторов

Издательский центр ВИНИТИ.

Типография ИЦ ВИНИТИ

СОДЕРЖАНИЕ

Введение
4

Предварительные сведения из алгебры
5

Структура и особенности алгоритма Rijndael
8

Контрольные вопросы
19

Шифрование в .NET framework 4.5 с использованием алгоритма Rijndael
20

Алгоритм RSA
26

Проверка числа на простоту
30

Алгоритм DES
31

Шифрование в .NET framework 4.5 с использованием алгоритма TripleDES
40

Литература
45

Введение

В 1977 году был инициирован конкурс американским
Национальным 

институтом 
стандартов 
и 
технологий 
(National 
Institute 
of 
Standards

and Technology – NIST) с целью найти достойного приемника DES (Data Encryption 

Standard), который стал доминирующим стандартом не только в государственных 

структурах США, но и в электронной коммерции во всем мире. DES имел уже 

почтенный возраст – несколько десятков лет. (Об алгоритме DES см. [4, 5]) По мере 

роста производительности компьютеров, его небольшая, по нынешним меркам, 

длина ключа – 56 бит – перестала быть надежной защитой. Последнее время DES с 

целью демонстрации взламывали и посредством хитрых алгоритмов дешифровки 

на больших машинах специальных лабораторий, и методом простого перебора 

ключей в распределенных системах из домашних компьютеров пользователей 

Интернета. Современным запросам уже мало стало удовлетворять быстродействие 

и другие параметры старого алгоритма.

Новый 
стандарт 
получил 
название 
AES 
(Advanced 
Encryption 
Stan
dart – улучшенный стандарт шифрования). И вот уже официально объявлено, что 

он будет построен на основе алгоритма Rijndael. Процесс выбора алгоритма для 

AES характеризовался открытостью и прозрач-ностью. До этого правительство 

США склонно было засекречивать все, что касалось криптографии. Одним из 

условий нового алгоритма являлась его открытость. Rijndael не защищен патентами 

и доступен для свободного использования в любых продуктах.

Название алгоритма представляет собой сокращение из имен создателей – двух 

бельгийских ученых, Винсента Рижмена (Vincent Rijmen) и Жоан Демен (Joan 

Daemen). Доктор Демен работает в группе архитектуры и криптографии научно
исследовательского отдела компании Proton World, а ее соавтор, доктор Рижмен, 

руководит исследованиями на факультете электроники Левенского католического 

университета. Их разработка Rijndael была включена американским Национальным 

институтом стандартов и технологий (National Institute of Standards and Technology 

– NIST) в число пяти финалистов конкурса на лучший криптографический 

алгоритм.

Предварительные сведения из алгебры

Практически все операции Rijndael определяются на уровне байта. Байты 

можно рассматривать как элементы конечного поля GF(28). Некоторые операции 

определены в терминах четырехбайтных слов. Введем основные математические 

понятия, необходимые для обсуждения алгоритма [3].

Поле GF(28)

Элементы конечного поля 
могут быть представлены несколькими 

различными способами. Для любого натурального n и простого числа p существует 

единственное поле из pn элементов, поэтому все представления GF(28) являются 

изоморфными. Несмотря на подобную эквивалентность, представление поля влияет 

на сложность реализации
алгоритма.
Для удобства выберем классическое 

полиномиальное представление.

Байт b, состоящий из битов b7, b6, b5, b4, b3, b2, b1, b0, представляется в виде

полинома с коэффициентами из GF(2) = {{0, 1},+,*}:

b7х7 + b6х6 + b5х5 + b4х4 + b3х3 + b2х2 + b1х1 + b0 .

Пример. Байт со значением 
16
2
57
01010111

соответствует полиному  х6 + х4 + 

х2 + х + 1.

Сложение в GF(28)

В полиномиальном представлении сумма двух элементов является 

многочленом с коэффициентами, которые равны сумме по модулю 2 

коэффициентов слагаемых одинаковой степени.

Пример. 5716 + 8316 = D416 или в полиномиальной нотации: 

(х6 + х4 + х2 + х + 1) + (х7 + х + 1) = х7 + х6 + х4 + х2.

В бинарной нотации — 01010111 + 10000011 = 11010100. 

Очевидно, сложение соответствует поразрядной операции исключающего 

или на уровне байта (обозначается как XOR или ).

Таким образом, выполняются все аксиомы абелевой группы: имеется 

коммутативная операция сложения, относительно которой множество полиномов 

над GF(2) замкнуто; она ассоциативна; относительно нее существует нейтральный 

элемент 
16
00 ; для каждого полинома существует обратный относительно сложения.

Умножение в GF(28)

В рассматриваемом случае умножение в GF(28) соответствует умножению 

полиномов по модулю неприводимого двоичного полинома восьмой степени. 

Полином называется неприводимым, если он не имеет делителей, кроме 1 и самого 

себя. В Rijndael такой полином обозначается m(x) и определяется следующим 

образом: m(x) = x8 + x4 + x3 + x + 1 или 11B в шестнадцатеричном представлении.

Пример. 5783 = C1 или

(х6 + х4 + х2 + х + 1) (х7 + х + 1) = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1.

Так как x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1=

=(x8 + x4 + x3 + х + 1) (x5 + x3) + (x7 + x6 + 1),

то x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 mod (x8 + x4 + x3 + x + 1) = x7 + x6 + 1.

Ясно, 
что 
результат 
является 
полиномом 
над 
GF(2) 
степени 

не 
выше 
7. 
В 
отличие 
от 
сложения, 
простой 
операции 
умножения 

на уровне байтов не существует.

Умножение, определенное выше, является ассоциативным, относительно 

него существует единичный элемент 
16
01 . Для любого полинома 𝑏(𝑥) из 𝐺𝐹(28)

можно использовать расширенный алгоритм Евклида[6]
для вычисления 

полиномов a(x) и c(x) таких, что 𝑏(𝑥) 𝑎(𝑥) +  𝑚(𝑥) 𝑐(𝑥) =  1.

Следовательно, a(x) b(x) mod m(x) = 1 или b-1(x) = a(x) mod m(x). Более того, можно 

показать, что 𝑎(𝑥) (𝑏(𝑥) +  𝑐(𝑥)) =  𝑎(𝑥)𝑏(𝑥) +  𝑎(𝑥)𝑐(𝑥).

Следовательно, множество 256 возможных значений байта образует конечное 

поле GF(28) c операцией XOR в качестве сложения и умножением, определенным 

выше.

Умножение на х

Если умножить b(x) на полином х обычным образом, то получим

b7х8 + b6х7 + b5х6 + b4х5 + b3х4 + b2х3 + b1х2 + b0x

Результат произведения x
на b(x) в изучаемом поле получается взятием 

предыдущего выражения по модулю m(x). Если b7 = 0, то данная операция не меняет 

результата произведения. Если b7 = 1, то m(x) следует вычесть. Таким образом,

умножение на х может быть реализовано на уровне байта как левый сдвиг и 

последующий поразрядный XOR c 
16
1B .

Полиномы над конечными полями

Рассмотрим полиномы с коэффициентами из GF(28). В этом случае 

четырехбайтный вектор соответствует полиному третьей степени. Полиномы могут 

быть сложены простым сложением соответствующих коэффициентов. Как и в 

GF(28), сложение двух векторов является простым побитовым XOR.

Умножение представляет собой более сложную операцию. Предположим, что

мы имеем два полинома над GF(28):

a(x) = a3x3 + a2x2 + a1x + a0 и b(x) = b3x3 + b2x2 + b1x + b0.

Тогда их произведение c(x) определяется следующим образом:

с(x) = с6x6 + с5x5 + с4x4 + с3x3 + с2x2 + c1x + с0,

где

с0 = a0 b0 ,

с1 = a1 b0  a0 b1 ,

с2 = a2 b0  a1 b1  a0 b2 ,

с3 = a3 b0  a2 b1  a1 b2  a0 b3 ,

с4 = a3 b1  a2 b2  a1 b3 ,

с5 = a3 b2  a2 b3 ,

с6 = a3 b3.

Ясно, что в таком виде с(х) не может быть представлен четырехбайтным 

вектором. Если же взять с(х) по модулю полинома четвертой степени, результат 

будет удовлетворительным. В Rijndael
это сделано с помощью полинома

M(x) = x4 + 1, так как xj mod (x4 + 1) = xj mod 4.

Результат произведения а(х) и b(x), взятый по модулю M(x), обозначим как 

d(x) = a(x)b(x). Таким образом:

d0 = a0 b0  a3 b1  a2 b2  a1b3,

d1 = a1 b0  a0 b1 a3 b2  a2 b3,

d2 = a2 b0  a1 b1  a0 b2  a3 b3,

d3 = a3 b0  a2 b1  a1 b2  a0 b3.

Операция умножения на фиксированный полином а(х), может быть записана, 

как умножение слева на циклическую матрицу:

























































3

2

1

0

0
1
2
3

3
0
1
2

2
3
0
1

1
2
3
0

3

2

1

0

b
b
b
b

a
a
a
a

a
a
a
a

a
a
a
a

a
a
a
a

d

d

d

d

Замечание. Полином х4 + 1 не является неприводимым над GF (28), 

следовательно, умножение на фиксированный полином необязательно обратимо. 

Умножение на х

При умножении b(x) на полином х будем иметь: b3x4 + b2x3 + b1x2 + b0x.

Полином
xb(x) 
получается 
взятием 
предыдущего 
результата 

по модулю  х4 + 1, что дает b2x3 + b1x2 + b0x + b3.

Умножение на х эквивалентно умножению слева на вышеприведенную 

матрицу со всеми 
i
16
a  = 00 за исключением 
1
16
a  = 01 , т.е:

0
0

1
1

2
2

3
3

00
00
00
01

01
00
00
00
.
00
01
00
00

00
00
01
00

c
b

c
b

c
b

c
b










































Следовательно, умножение на х соответствует циклическому сдвигу байтов 

внутри вектора.

Структура и особенности алгоритма Rijndael.

При разработке алгоритма учитывались следующие три критерия:


противодействие всем известным атакам; 


скорость и компактность кода для широкого круга платформ; 


простота разработки.

В большинстве алгоритмов шифрования преобразование каждого раунда имеет 

структуру сети Фейштеля. Обычно в этом случае часть битов в каждом 

промежуточном состоянии просто перемещается без изменения в другую половину. 

В Rijndael вместо этого преобразование каждого раунда состоит из четырех 

различных преобразований, называемых слоями. Каждый слой разрабатывался с 

учетом противодействия линейному и дифференциальному криптоанализу. В 

основу каждого слоя положена своя собственная функция:

1. Нелинейный слой состоит из параллельного применения S-блоков для 

оптимизации нелинейных свойств в наихудшем случае. 

2. Слой линейного перемешивания строк гарантирует высокую степень 

диффузии для нескольких раундов. 

3. Слой линейного перемешивания столбцов также гарантирует высокую 

степень диффузии для нескольких раундов. 

4. Дополнительный слой ключа состоит из простого XOR промежуточного 

состояния с ключом раунда.

Перед 
первым 
раундом
применяется 
дополнительное 
забеливание
с 

использованием ключа. Причина этого состоит в следующем. Любой слой после 

последнего или до первого добавления ключа может быть просто снят без знания 

ключа и тем самым не добавляет безопасности в алгоритм (например, начальная и 

конечная перестановки в DES). Начальное или конечное добавление ключа 

применяется также в некоторых других алгоритмах, например, IDEA, SAFER и 

Blowfish. Для того чтобы сделать структуру алгоритма более простой, слой 

линейного перемешивания последнего раунда отличается от слоя перемешивания 

других раундов. Можно показать, что это в любом случае не повышает и не 

понижает безопасность. Это аналогично отсутствию операции swap в последнем 

раунде DES.

Спецификация алгоритма

Rijndael является блочным алгоритмом шифрования с переменной длиной блока 

и переменной длиной ключа. Длина блока и длина ключа могут быть независимо 

установлены в 128, 192 или 256 бит.

Состояние, ключ шифрования и число раундов.

Различные преобразования выполняются над промежуточным результатом, 

называемым состоянием (state). Состояние можно рассматривать как двумерный 

массив байтов. Этот массив имеет четыре строки и различное число столбцов, 

обозначаемое как Nb, равное длине блока, деленной на 32. Ключ также можно 

рассматривать как двумерный массив с четырьмя строками. Число столбцов ключа 

шифрования, обозначаемое как Nk, равно длине ключа, деленной на 32. В 

некоторых случаях эти блоки также рассматриваются как одномерные массивы 

четырехбайтных векторов, где каждый вектор состоит из соответствующего 

столбца. Такие массивы имеют длину 4, 6 или 8 соответственно, и индексы в 

диапазонах 0..3, 0..5 или 0..7. Четырехбайтные векторы мы будем называть словами. 

Если необходимо указать четыре отдельных байта в слове, будет использоваться 

нотация (a, b, c, d), где a, b, c и d являются байтами в позициях 0, 1, 2 и 3, 

соответственно, в рассматриваемом столбце, векторе или слове.

Пример состояния (с Nb = 6) и ключа шифрования (с Nk = 4).

Входы 
и 
выходы 
Rijndael
считаются 
одномерными 
массивами

из 8 байтов, пронумерованными от 0 до 4Nb - 1. Следовательно, эти блоки имеют 

длину 
16, 24 или 32 байта, и массив индексируется 
в диапазонах

0..15, 
0..23 
или 
0..31. 
Ключ 
считается 
одномерным 
массивом 

8-битных байтов, пронумерованных от 0 до 4Nk
1. Следовательно, 

эти блоки имеют длину 16, 24 или 32 байта, и массив индексируется 

в диапазонах 0..15, 0..23 или 0..31.

Входные 
байты 
алгоритма 
отображаются 
в 
байты 
состояния 

в следующем порядке: А0,0, А1,0, А2,0, А3,0, А0,1, А1,1, А2,1, А3,1… Байты ключа 

шифрования отображаются в массив в следующем порядке: K0,0, K1,0, K2,0, K3,0, K0,1, 

K1,1, K2,1, K3,1,… После выполнения операции шифрования выход алгоритма 

получается из байтов состояния аналогичным образом.

Число раундов
обозначается Nr
и зависит от значений Nb
и Nk:

𝑁𝑟 = max{𝑁𝑏, 𝑁𝑘} + 6 (см. в таблице).

A0,0 A0,1 A0,2 A0,3 A0,4 A0,5

A1,0 A1,1 A1,2 A1,3 A1,4 A1,5

A2,0 A2,1 A2,2 A2,3 A2,4 A2,5

A3,0 A3,1 A3,2 A3,3 A3,4 A3,5

K0,0 K0,1 K0,2 K0,3

K1,0 K1,1 K1,2 K1,3

K2,0 K2,1 K2,2 K2,3

K3,0 K3,1 K3,2 K3,3

Число раундов как функция от длины блока и длины ключа

Nr
Nb = 4
Nb = 6
Nb = 8

Nk = 4
10
12
14

Nk = 6
12
12
14

Nk = 8
14
14
14

Преобразование раунда

Преобразование раунда состоит из четырех различных преобразований. В 

нотации на псевдо C это можно записать следующим образом:

Round (State, RoundKey)

{ 

ByteSub (State);

ShiftRow (State);

MixColumn (State);

AddRoundKey (State, RoundKey); 

}

Заключительный раунд алгоритма немного отличается и выглядит следующим 

образом:

FinalRound (State, RoundKey)

{

ByteSub (State);

ShiftRow (State); // Всего лишь отсутствует MixColumn.

AddRoundKey (State, RoundKey);

}

Преобразование ByteSub.

Преобразование ByteSub является нелинейной байтовой подстановкой, 

выполняющейся для каждого байта состояния независимо. Таблица подстановки 

является обратимой и сконструирована в виде композиции двух преобразований: