- •Расчетно-пояснительная записка к выпускной работе бакалавра
- •Техническое задание
- •Общие сведения
- •Назначение и цели создания системы
- •Требования к программе или программному изделию
- •Требования к надежности
- •Список использованных источников.
- •Исследовательская часть
- •Постановка задачи
- •Обоснование выбора темы
- •Обоснование выбора языка программирования
- •Обоснование выбора среды разработки
- •Обоснование выбора платформы
- •Основы криптографии
- •Причины выбора алгоритма
- •Алгоритм Rijndael
- •Побайтовая замена
- •Построчное вращение матрицы
- •Дешифрация
- •Конструкторская часть
- •Функциональное назначение
- •3.2. Руководство программиста
- •Структура программы
- •Технологическая часть
- •4.1. Назначение программного продукта
- •4.2. Назначение и условия применения программного продукта
- •4.3. Тестирование программного продукта
- •4.4. Обращение к программе
- •4.5. Руководство пользователя
- •4.6. Сообщения оператору
- •Заключение
Построчное вращение матрицы
В ходе данной операции каждая строка матрицы данных, кроме первой, вращается (циклически сдвигается) влево на определенное число позиций, зависящее от номера строки и от размера блока данных:
,
1£i£4,
1£j£n.
Первая строка всегда остается на месте: С1 = 0, для нее приведенная выше формула существенно упрощается: z1j = y1j. Ниже в таблице приведены величины сдвига для строк матрицы со второй по четвертую в зависимости от числа столбцов n в матрице:
n |
4 |
6 |
8 |
C2 |
1 |
1 |
1 |
C3 |
2 |
2 |
3 |
C4 |
3 |
3 |
4 |
Умножение на постоянную матрицу
Н
а
этом шаге матрица данных слева умножается
на постоянную матрицу-циркулянт M:
X = M´X,
При выполнении матричного умножения операции сложения и умножения элементов обеих матриц выполняются в конечном поле GF(28). Матрица M является циркулянтом: каждая ее строка получается циклическим сдвигом предыдущей строки вправо на один элемент. Элементы матрицы выбраны таким образом, чтобы свести к минимуму трудоемкость операции умножения: в ней присутствуют лишь небольшие по значению числа 01, 02 и 03, половина элементов - единичные, т.е. реального умножения выполнять для них не требуется. Этим самым обеспечивается высокая эффективность возможных реализаций этой операции.
Следует добавить, что операция умножения в конечном поле GF(28) является достаточно трудоемкой в программной реализации и никаким образом не сводится к обычному арифметическому умножению. Если умножение двоичных чисел реализуется сдвигами и обычным арифметическим суммированием, то умножение полиномов над полем GF(2) - теми же сдвигами и побитовым суммированием по модулю 2. Однако в шифре Rijndael одним из множителей всегда является константа и размер операндов невелик - один байт. Это позволяет реализовать умножение на константу в поле GF(28) как замену, что существенно повышает эффективность программной реализации. Для каждого множителя-константы при этом требуется свой отдельный узел замен. Напротив, наиболее эффективной аппаратной реализацией этой операции является реализация в виде серии сдвигов и побитовых сложений по модулю два в соответствие с ее непосредственным определением.
Дешифрация
Дешифрация в Rijndael алгоритмически эквивалентна шифрованию, однако между этими двумя процедурами имеются определенные различия, гораздо более существенные, чем в сетях Файстеля, где все сводится к порядку использования ключевых элементов. Дешифрование отличается от шифрования по следующим четырем пунктам:
1. Ключевые элементы используются в порядке, обратном тому, в котором они используются при шифровании. Кроме того, все ключевые элементы, кроме первого и последнего, должны быть умножены слева на матрицу, обратную матрице M. Таким образом, если при шифровании используется следующая последовательность ключевых элементов
k1, k2, k3, ... , kR, kR+1,
то при дешифрации должна быть использована следующая последовательность элементов:
kR+1,
M
-1
kR,
... , M
-1
k3,
M
-1
k2,
k1.
2. На шаге побайтовой замены используется узел замен S-1 обратный тому, что применяется в процедуре шифрования S. Это означает, что каково бы ни было байтовое значение b, всегда справедливо следующее соотношение:
S -1[S[b]] = b.
Указанный узел замен S-1 представлен в следующей таблице:
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
xA |
xB |
xC |
xD |
xE |
xF |
0x |
52 |
09 |
6a |
d5 |
30 |
36 |
a5 |
38 |
bf |
40 |
a3 |
9e |
81 |
f3 |
d7 |
fb |
1x |
7c |
e3 |
39 |
82 |
9b |
2f |
ff |
87 |
34 |
8e |
43 |
44 |
c4 |
de |
e9 |
cb |
2x |
54 |
7b |
94 |
32 |
a6 |
c2 |
23 |
3d |
ee |
4c |
95 |
0b |
42 |
fa |
c3 |
4e |
3x |
08 |
2e |
a1 |
66 |
28 |
d9 |
24 |
b2 |
76 |
5b |
a2 |
49 |
6d |
8b |
d1 |
25 |
4x |
72 |
f8 |
f6 |
64 |
86 |
68 |
98 |
16 |
d4 |
a4 |
5c |
cc |
5d |
65 |
b6 |
92 |
5x |
6c |
70 |
48 |
50 |
fd |
ed |
b9 |
da |
5e |
15 |
46 |
57 |
a7 |
8d |
9d |
84 |
6x |
90 |
d8 |
ab |
00 |
8c |
bc |
d3 |
0a |
f7 |
e4 |
58 |
05 |
b8 |
b3 |
45 |
06 |
7x |
d0 |
2c |
1e |
8f |
ca |
3f |
0f |
02 |
c1 |
af |
bd |
03 |
01 |
13 |
8a |
6b |
8x |
3a |
91 |
11 |
41 |
4f |
67 |
dc |
ea |
97 |
f2 |
cf |
ce |
f0 |
b4 |
e6 |
73 |
9x |
96 |
ac |
74 |
22 |
e7 |
ad |
35 |
85 |
e2 |
f9 |
37 |
e8 |
1c |
75 |
df |
6e |
Ax |
47 |
f1 |
1a |
71 |
1d |
29 |
c5 |
89 |
6f |
b7 |
62 |
0e |
aa |
18 |
be |
1b |
Bx |
fc |
56 |
3e |
4b |
c6 |
d2 |
79 |
20 |
9a |
db |
c0 |
fe |
78 |
cd |
5a |
f4 |
Cx |
1f |
dd |
a8 |
33 |
88 |
07 |
c7 |
31 |
b1 |
12 |
10 |
59 |
27 |
80 |
ec |
5f |
Dx |
60 |
51 |
7f |
a9 |
19 |
b5 |
4a |
0d |
2d |
e5 |
7a |
9f |
93 |
c9 |
9c |
ef |
Ex |
a0 |
e0 |
3b |
4d |
ae |
2a |
f5 |
b0 |
c8 |
eb |
bb |
3c |
83 |
53 |
99 |
61 |
Fx |
17 |
2b |
04 |
7e |
ba |
77 |
d6 |
26 |
e1 |
69 |
14 |
63 |
55 |
21 |
0c |
7d |
3. На шаге построчного вращения матрицы данных осуществляется циклический сдвиг строк на то же самое количество элементов, что и при шифровании, но в обратную сторону - вправо. Либо, в силу свойств операции циклического сдвига, можно осуществить вращение строк матрицы в ту же сторону, что и при шифровании, т.е. влево, но на другое количество элементов, вычисляемое по следующей формуле:
Сi' = n - Ci, 2£i£4.
Константы циклического сдвига влево строк матрицы в процедуре дешифрования в зависимости от числа столбцов матрицы данных приведены в следующей ниже таблице:
n |
4 |
6 |
8 |
C2’ |
3 |
5 |
7 |
C3’ |
2 |
4 |
5 |
C4’ |
1 |
3 |
4 |
На шаге умножения слева на постоянную матрицу используется матрица M -1, обратная используемой при шифровании матрице M:
Следует отметить, что умножение в конечном поле GF(28) на элементы матрицы M -1 с точки зрения вычислительных затрат является более трудоемкой операцией, чем умножение на элементы матрицы M. Кроме того, в обратной матрице присутствуют четыре различных элемента, тогда как в исходной - только три, что позволяло "сэкономить" одно умножение из четырех. Все сказанное приводит к тому, что при непосредственной реализации умножения в поле GF(28) модули дешифрования получаются заметно менее быстродействующими, чем модули шифрования. Однако, эта особенность не является настолько существенной, как может показаться на первый взгляд. Во-первых, в большинстве практических режимов использования шифра применяется только прямое преобразование (шифрование) - подобная ситуация имеет место при шифровании с использованием потоковых режимов (в том числе и при дешифрации), при выработке имитовставки (кода аутентификации), при выработке хэш-функции и при выработке массивов псевдослучайных данных. Во вторых, если умножение на константу в поле GF(28) реализовать как замену, различия в трудоемкости нивелируются.
