Симметричный блочный криптоалгоритм Rijndael

Размещено на http://www.allbest.ru/

ВСТУПЛЕНИЕ

ХХI век - век информатики и информатизации, основной ценностью является информация. Технология дает возможность передавать и хранить все большие объемы информации. Это благо имеет и оборотную сторону. Информация становится все более уязвимой по разным причинам:

– возрастающие объемы хранимых и передаваемых данных;

– расширение круга пользователей, имеющих доступ к информационным системам;

– усложнение информационных систем.

Большую важность защиты имеет проблема защиты информации от несанкционированного доступа (НСД) при передаче и/или хранении. Испытанный метод защиты информации от НСД - шифрование. Шифрованием (encryption) называют процесс преобразования исходных данных (plaintext, например, текстового документа на естественном языке) в шифрованные (ciphertext), нечитаемые без знания специальных параметров преобразования - ключа. Дешифрованием называют обратное преобразование шифрованных данных в открытые. В англоязычной литературе процессы шифрования/дешифрования обозначаются как enciphering/deciphering.

Все известные алгоритмы шифрования делятся на два типа:

– симметричные с единственным секретным ключом для шифрования и дешифрования (они же single-key). Симметричные алгоритмы также подразделяются на два семейства:

- потоковые - шифрование данных посимвольно;

- блочные - шифрование данных кусками (блоками) из нескольких символов конечной и фиксированной длинны;

– асимметричные - с двумя ключами: открытым (public-key) и закрытым ключом (private-key). Первый ключ служит только для шифрования, второй - для дешифрования.

Каждый из указанных типов криптоалгоритмов имеет свои достоинства и недостатки. Так основным недостатком симметричных методов является необходимость организации закрытого канала для передачи ключа. А основным достоинством быстрота выполнения криптопреобразования. И наоборот, асимметричные алгоритмы более медленные в выполнении криптопреобразования, но не требуют закрытых каналов обмена ключами, т.к. открытый ключ не позволяет произвести дешифровку, а передавать закрытый ключ не нужно. криптозащита шифрование rijndael преобразование

В данном курсовом проекте будет рассмотрен симметричный блочный криптоалгоритм Rijndael, принятый как стандарт шифрования США FIPS 197 и получивший название AES (Advanced Encryption Standard).



1. ИСТОРИЯ КОНКУРСА НА НОВЫЙ СТАНДАРТ КРИПТОЗАЩИТЫ

В 1997 году NIST (National Institute of Standards and Technology) объявил конкурс на создание алгоритма симметричного шифрования, алгоритм получил название AES (Advanced Encryption Standard). Алгоритм планировалось принять как стандарт Соединенных Штатов Америки взамен устаревшего к этому времени стандарту DES (Digital Encryption Standard), являвшегося американским стандартом с 1977 года. Необходимость в принятии нового стандарта была вызвана небольшой длиной ключа DES (56 бит), что позволяло успешно применять метод прямого перебора ключей для взлома DES. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия.

2 января 1997 года NIST объявляет о намерении выбрать преемника для DES. Конкурс был объявлен 12 сентября 1997 г. Свой алгоритм могла предложить любая организация или группа исследователей. NIST опубликовал все данные о тестировании кандидатов на роль AES и потребовал от авторов алгоритмов сообщить о базовых принципах построения алгоритмов, используемых в них константах, таблицах для замен (S-box) и т.п. В отличие от ситуации с DES, NIST при выборе AES не стал опираться на секретные и, как следствие, запрещенные к публикации данные об исследовании алгоритмов-кандидатов.

Требования к кандидатам на новый стандарт были следующими:

блочный шифр;

длина блока, равная 128 битам;

ключи длиной 128, 192 и 256 бит.

Дополнительно кандидатам рекомендовалось:

использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах);

ориентироваться на 32-разрядные процессоры

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

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

Алгоритм AES прежде всего должен предлагать высокую степень защиты, обладать простой структурой и высокой производительностью. Уже на уровне внутренней архитектуры он должен обладать надежностью, достаточной для того, чтобы противостоять будущим попыткам его взлома.

Был проведен конкурс среди алгоритмов шифрования на роль AES, 2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как стандарт FIPS 197.

AES не тождественен Rijndael, т.к. оригинальный алгоритм Rijndael поддерживает более широкий диапазон длин ключей и блоков. В AES размер блока фиксирован и равен 128 бит, а в Rijndael поддерживаются различные длины ключей и блоков - от 128 до 256 бит, с шагом 32 бита. AES оперирует с блоком данных 16 байт, а Rijndael позволяет выбирать размер блока.

Rijndael - быстрый и компактный алгоритм с простой математической структурой. Он продемонстрировал хорошую устойчивость к атакам на реализацию, при которых пытаются декодировать зашифрованное сообщение, анализируя внешние проявления алгоритма, в том числе уровень энергопотребления и время выполнения. Алгоритму присущ внутренний параллелизм, что позволяет без труда обеспечить эффективное использование процессорных ресурсов. Далее под AES можно понимать Rijndael с ключом в 128 бит и блоком данных 16 байт.

Преимущества алгоритма Rijndael состоят в:

· высокая эффективность на любых платформах;

· высокий уровень защищенности;

· хорошо подходит для реализации в smart-картах из-за низких требований к памяти;

· быстрая процедура формирования ключа;

· хорошая поддержка параллелизма на уровне инструкций;

· поддержка различных длин ключа с шагом 32 бита.

Недостатки:

· уязвим к анализу мощности.

2. МАТЕМАТИЧЕСКИЕ ОСНОВЫ

В криптоалгоритме некоторые операции выполняются над байтами, которые рассматриваются как элементы поля GF(2⁸), здесь число в скобках 2⁸ указывает на число элементов конечного поля.

Элементами GF(2⁸) являются двоичные многочлены степени N < 8, которые могут быть заданы строкой своих коэффициентов. Так, например, байту 01010111 (`57' в шестнадцатеричной форме) соответствует многочлен:

.

Сложение в поле GF(2⁸) - это обычная операция сложения многочленов с использованием операции XOR при приведении подобных членов; или операция поразрядного XOR, если элементы поля представлены в виде строки коэффициентов соответствующих многочленов. Например:

`57'+`83' = `D4',

так как

,

Или 01010111 + 10000011 = 11010100.

В конечном поле для любого ненулевого элемента существует обратный аддитивный элемент , при этом . В GF(2⁸) справедливо , где нулевой элемент - это 00, то есть каждый ненулевой элемент является собственной аддитивной версией.

В конечном поле для любого ненулевого элемента существует обратный мультипликативный элемент , при этом .

Умножение в поле GF(2⁸) - это обычная операция умножения многочленов со взятием результата по модулю некоторого неприводимого двоичного многочлена восьмой степени и с использованием операции XOR при приведении подобных членов. В Rijndael выбран следующий неприводимый многочлен:

.

Например, вычислим произведение:

`57' `83'.

Результат произведения многочленов:

(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁷ +

+x⁷ + x⁵ + x³ + x² + x + x⁶ + x⁴ + x² + x + 1.

Суммирование коэффициентов при одинаковых степенях производится по правилам сложения в поле, т.е. по модулю 2, например:

1x⁷ + 1x⁷ = (1 1)x⁷ = 0 x⁷.

Получим:

(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ +x⁶ + x⁵ + x⁴ + x³ + 1.

Вычислим остаток от деления полученного выражения на неприводимый многочлен :

(x¹³ + x¹¹ + x⁹ + x⁸ +x⁶ + x⁵ + x⁴ + x³ + 1) mod (x⁸ + x⁴ + x³ + x + 1) =

= x⁷ + x⁶ + 1,

что является представлением числа 193 в десятичном виде.

Таким образом, `57' `83'= `C1'.

Взятие остатка от деления на гарантирует, что результат будет двоичным полиномом степени меньше 8, и таким образом может быть представлен байтом. В отличии от операции сложения, нет другой простой операции на уровне битов, чтобы выполнить умножение.

3. СТРУКТУРА ШИФРА

Rijndael - это итерационный блочный шифр, имеющий переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192, 256 битам.

Промежуточные результаты преобразований, выполняемых в рамках криптоалгоритма, называются состояниями (state). Состояние (рис. 1) можно представить в виде прямоугольного или квадратного массива байтов. Этот массив имеет 4 строки, а число столбцов равно длине блока, деленной на 32.



Рисунок 1 - Пример представления блока данных (состояния) и ключа шифрования при и

В некоторых случаях ключ шифрования рассматривается как линейный массив 4-байтовых слов. Слова состоят из 4 байт, которые находятся в одном столбце (при представлении в виде прямоугольного массива).

Входные данные для шифра обозначаются как байты состояния в порядке S₀₀, S₁₀, S₂₀, S₃₀, S₀₁, S₁₁, S₂₁, S₃₁ … После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке.

Число раундов зависит от значений и как показано в таблице 1:

Таблица 1

	10	12	14
	12	12	14
	14	14	14

При ,: .

4. ШИФРОВАНИЕ

Операция шифрования каждого блока данных проводится независимо от содержимого других блоков. По окончанию шифрования блока матрица заполняется следующей порцией данных и процесс повторяется. В силу независимости шифрования одного блока от другого процесс шифрования хорошо поддается распараллеливанию.

С соответствующими параметрами схема криптопреобразования может быть записана так:

1. Расширение ключа KeyExpansion.

2. Начальная операция AddRoundKey - суммирование с основным ключом.

3. 9 раундов из четырех шагов каждый:

3.1 SubBytes - замена байтов state по таблице замен.

3.2 ShiftRows - циклический сдвиг строк state.

3.3 MixColumns - перестановка столбцов state.

3.4 AddRoundKey - суммирование с раундовым ключом.

4. Заключительный 10-й раунд:

4.1 SubBytes - замена байтов state по таблице замен.

4.2 ShiftRows - циклический сдвиг строк state.

4.3 AddRoundKey - суммирование с раундовым ключом.

Далее подробно описано каждое из преобразований.

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

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

1) Получение обратного элемента с помощью расширенного алгоритма Эвклида (неприводимый многочлен

относительно умножения в поле GF(2⁸), нулевой элемент `00' переходит сам в себя.

Расширенный алгоритм Эвклида:

1. Находим остатки от деления многочленов:

;

;

;

;

…

;

.

Если , то и не взаимно простые, и уравнение не имеет решений.

2. Формируем таблицу:

Таблица 2

		0	1	2	3	…
						…
	1					…

,

,

,

,

…

,

.

3. Решением уравнения есть многочлен:

.

2) Применение преобразования над GF(2⁸), определенного следующим образом:

Другими словами, суть преобразования может быть описана уравнениями:

;

;

;

;

;

;

;

.

Например, осуществим два вышеуказанных преобразования над шестнадцатеричным числом `5A'.

1) Так, например, `5А' в шестнадцатеричной форме соответствует байт:

01011010, а соответственно и многочлен:

.

Находим остатки от деления многочленов:

;

;

;

.

Таблица 2

		0	1	2	3
	1

Решением уравнения есть многочлен:

.

В двоичном виде данный многочлен выглядит следующим образом: 00100010, шестнадцатеричном - `22'.

2) ;

;

;

;

;

;

;

.

Имеем, что у=10111110, что в шестнадцатеричном виде представляется, как `BE'.

Выполнив данную процедуру для всех возможных вариантов представления одного байта, получим таблицу замен для преобразования SubBytes.

Таблица 3

X Y	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
00	63	7c	77	7b	f2	6b	6f	c5	30	01	67	2b	fe	d7	ab	76
10	ca	82	c9	7d	fa	59	47	f0	ad	d4	a2	af	9c	a4	72	c0
20	b7	Fd	93	26	36	3f	f7	cc	34	a5	e5	f1	71	d8	31	15
30	04	c7	23	c3	18	96	05	9a	07	12	80	e2	eb	27	b2	75
40	09	83	2c	1a	1b	6e	5a	a0	52	3b	d6	b3	29	e3	2f	84
50	53	d1	00	ed	20	fc	b1	5b	6a	cb	be	39	4a	4c	58	cf
60	d0	ef	aa	fb	43	4d	33	85	45	f9	02	7f	50	3c	9f	a8
70	51	a3	40	8f	92	9d	38	f5	bc	b6	da	21	10	ff	f3	d2
80	cd	0c	13	ec	5f	97	44	17	c4	a7	7e	3d	64	5d	19	73
90	60	81	4f	dc	22	2a	90	88	46	ee	b8	14	de	5e	0b	db
a0	e0	32	3a	0a	49	06	24	5c	c2	d3	ac	62	91	95	e4	79
b0	e7	c8	37	6d	8d	d5	4e	a9	6c	56	f4	ea	65	7a	ae	08
c0	ba	78	25	2e	1c	a6	b4	c6	e8	dd	74	1f	4b	bd	8b	8a
d0	70	3e	b5	66	48	03	f6	0e	61	35	57	b9	86	c1	1d	9e
e0	e1	f8	98	11	69	d9	8e	94	9b	1e	87	e9	ce	55	28	df
f0	8c	a1	89	0d	bf	e6	42	68	41	99	2d	0f	b0	54	bb	16

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

Байт Z преобразуется в шестнадцатеричную систему счисления, например XYh=`5А', X старший разряд, Y младший разряд. Если старшего разряда нет он заменяется нулем.

В таблице 3 выбирается строка X и столбец Y.

Значение Z' на пересечении строки X и столбца Y таблицы 3 используется как замена Z: Z'= X'Y'h=`В 8'.

Рисунок 2 - Пример замены байта в преобразовании SubBytes

Преобразование сдвига строк ShiftRows. Последние 3 строки (С 1, С 2, С 3, так как первая С 0) состояния циклически сдвигаются на различное число байтов. Строка 1 сдвигается на С 1 байт, строка 2 - на С 2 байт, строка 3 - на С 3 байт. Значения сдвигов С 1, С 2 и С 3 зависят от длины блока . Их величины приведены в таблице 4.

Таблица 4

	С 1	С 2	С 3
4	1	2	3
6	1	2	3
8	1	3	4

Следующий рисунок показывает влияние преобразования ShiftRows на блок данных при .

Рисунок 3 - Преобразование ShiftRows

Преобразование MixColumns. В преобразовании MixColumns - перемешивание столбца - столбцы блока рассматриваются как многочлены над полем GF(2⁸) и умножаются по модулю

на постоянный многочлен:

.

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

,

где С - номер столбца массива данных и .

В результате такого умножения, байты столбца с {} заменяются, соответственно на байты:

;

;

;

.

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

Рисунок 4 - Графическое представление процедуры MixColumns

Преобразование AddRoundKey. В преобразовании AddRoundKey, раундовый ключ RK добавляется к state посредством поразрядного XOR. Каждый раундовый ключ состоит из 16 байт расширенного ключа. Байты раундового ключа записываются в матрицу 44, подобную state. Каждый байт раундового ключа суммируется с соответствующим байтом из state, как показано на рисунке 5.

Рисунок 5 - Суммирование блока данных с раундовым ключом

5. ДЕШИФРОВАНИЕ

Все преобразования шифрования однозначны и, следовательно, имеют обратное преобразование, т.е. могут быть инвертированы и выполнены в обратном порядке, чтобы выполнить дешифрование для алгоритма AES.

Схема обратного криптопреобразования может быть записана так:

1. Расширение ключа KeyExpansion.

2. 9 раундов из четырех шагов каждый:

2.1 AddRoundKey - суммирование с раундовым ключом.

2.2 InvMixColumns - обратная перестановка столбцов state.

2.3 InvShiftRows - обратный циклический сдвиг строк state.

2.4 InvSubBytes - обратная замена байтов state по таблице замен.

3. Заключительный 10-й раунд:

3.1 AddRoundKey - суммирование с раундовым ключом.

3.2 InvShiftRows - обратный циклический сдвиг строк state.

3.3 InvSubBytes - обратная замена байтов state по таблице замен.

Преобразование InvMixColumns. Преобразование InvMixColumns является обратным для преобразования MixColumns. В преобразовании InvMixColumns, столбцы состояния (state) рассматриваются как полиномы над полем F(28) и умножаются по модулю x4 + 1 с постоянным полиномом d(x) = a-1(x), в поле F(28):

d(x) = 0Bhx3 + 0Dhx2 + 09hx + 0Eh.

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

=

где с- номер столбца массива state и 0В результате такого умножения, байты столбца с заменяются, соответственно на байты:

;

;

;

;

Данное преобразование рассмотрим на примере:

=

Преобразование InvShiftRows. Преобразование InvShiftRows обратно преобразованию ShiftRows. Байты последних трех рядов массива state циклически сдвигаются вправо. Строка 1 (нумерация с нуля) смещается на 1 байт, строка 2 - на 2 байта, строка 3 - на 3 байта.

Рисунок 6 - Преобразование обратного сдвига InvShiftRows

Преобразование InvSubBytes. Преобразование InvSubBytes выполняет обратную замену байт с помощью обратной таблицы замен. Обратная таблица замен приведена ниже:

Таблица 5

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
00	52	09	6a	d5	30	36	a5	38	bf	40	a3	9e	81	f3	d7	fb
10	7c	e3	39	82	9b	2f	ff	87	34	8e	43	44	c4	de	e9	cb
20	54	7b	94	32	a6	c2	23	3d	ee	4c	95	0b	42	fa	c3	4e
30	08	2e	a1	66	28	d9	24	b2	76	5b	a2	49	6d	8b	d1	25
40	72	f8	f6	64	86	68	98	16	d4	a4	5c	cc	5d	65	b6	92
50	6c	70	48	50	fd	ed	b9	da	5e	15	46	57	a7	8d	9d	84
60	90	d8	ab	00	8c	bc	d3	0a	f7	e4	58	05	b8	b3	45	06
70	d0	2c	1e	8f	ca	3f	0f	02	c1	af	bd	03	01	13	8a	6b
80	3a	91	11	41	4f	67	dc	ea	97	f2	cf	ce	f0	b4	e6	73
90	96	ac	74	22	e7	ad	35	85	e2	f9	37	e8	1c	75	df	6e
a0	47	f1	1a	71	1d	29	c5	89	6f	b7	62	0e	aa	18	be	1b
b0	fc	56	3e	4b	c6	d2	79	20	9a	db	c0	fe	78	cd	5a	f4
c0	1f	dd	a8	33	88	07	c7	31	b1	12	10	59	27	80	ec	5f
d0	60	51	7f	a9	19	b5	4a	0d	2d	e5	7a	9f	93	c9	9c	ef
e0	a0	e0	3b	4d	ae	2a	f5	b0	c8	eb	bb	3c	83	53	99	61
f0	17	2b	04	7e	ba	77	d6	26	e1	69	14	63	55	21	0c	7d

Преобразование обратное AddRoundKey. Преобразование AddRoundKey, описанное в пункте ранее в пункте 4.4, является обратным для самого себя, так как использует операцию XOR.

Размещено на Allbest.ru

...