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

Классификация симметричных криптоалгоритмов:

В зависимости от характера воздействий, производимых над данными:

o Перестановочные– изменение порядка следования группы битов (сдвиг, переупорядочивание), делает информацию недоступной стороннему наблюдателю.

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

В зависимости от размера блока информации криптоалгоритмы:

o Потоковые- Единицей шифрования является один бит. Результат не зависит от прошедшего ранее входного потока. Наиболее распространенными предстателями поточных шифров являются скремблеры.

Достоинства: относятся высокая скорость шифрования, относительная простота реализации и отсутствие размножения ошибок.

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

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

o Блочные– единицей шифрования является блок из нескольких байтов. Результат зависит от всех исходных байтов этого блока.

Достоинства: никакие 2 блока открытого текста не могут быть представлены одним и тем же блоком шифртекста, так как каждый бит блока зависит от значений всех битов соответствующего блока открытого текста.

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

Сеть Фейштеля

Для реализации блочного алгоритма чаще всего применяется Сеть Фейштеля, имеющей следующую структуру.

1. Входной блок делится на несколько подблоков, называемых ветвями, так если блок равен 64 битам, то используется 2 ветви по 32 бита каждая. Назовем ветви L –левая и R-правая.

2. Каждая из ветвей обрабатывается независимо от другой:

Данные левой ветви меняется местами с правой;

Данные левой ветви, с использованием подключа и образующей функции F складываются по mod 2 с правой ветвью, и поступают на левую ветвь.

1. Данное преобразование выполняется n циклов, называемых раундами? оптимальное число которых - от 8 до 32.

2. Осуществляется циклический сдвиг всех ветвей влево.

Рис. Раунд сети Фейштеля

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

Алгоритм DES

Принципы разработки

DES (Data Encryption Standard)- один из самых распространенных и известным алгоритмом симметричного шифрования. Алгоритм разработан в 1977 г. и в 1980 г. принят в США в качестве стандарта (FIPS PUB 46).

DES – сетью Фейштеля с двумя ветвями длина блока 64-бит, длина ключа 56-бит.

Этапы выполнения шифрования:

1. В соответствии со стандартной таблицей выполняется начальная перестановка IP 64-битного исходного текста (забеливание) и 56-битного исходного ключа, в соответствии с таблицей Permuted Choice 1 (РС-1).

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

Операции для данных

2.1.1 64 битный блок делится на левую и правую половины, обозначенные L и R. При этом данные правой половины меняется местами с левой:

.

2.1.2 32 битные данные левой половины разбиваются на подблоки по 4 бита и расширяются до 6 бит, путем присоединения крайних бит из двух соседних подблоков:

Подблок до расширения
			0

Подблок после расширения

2.1.3 Выполняется сложение по модулю 2 (xor) 48-битного значения блока после расширения с 48-битным подключом K_i.

2.1.4 Полученное 48-битное значение подается на вход функции подстановка, состоящей из 8 таблиц S-boxes. На вход таблицы подается 6 бит, а на выходе получается 4 бита, следующим образом: первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход.

строка 1 1
				0	1	1	0
столбец 0 1 1 0

Пересечение третьей строки (11) и шестого столбца (110) соответствует числу 5, т.е. выходом является 0101.

2.1.5 32-битное значение обрабатывается с помощью перестановки Р, целью которой переупорядочивание битов.

2.1.6 Полученный после перестановки блок суммируется по модулю 2 (xor) с данными левой половины.

Рис

Операции для ключа

2.2.1. Ключ делится на два 28-битных подключа и .

2.2.2 Происходит циклический сдвиг влево на 1 или 2 бита, в зависимости от номера раунда.

2.2.3 Полученные значения подключей подаются

- на вход таблицы Permuted Choice 2 (РС-2), осуществляющей перестановку и сжатие, а также формирующей 48-битный подключ , с которым выполняется сложение по модулю 2 блока R после расширения;

- на вход следующего раунда.

Рис

3. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами.

4. Выполняется перестановка IP-1 результата, полученного на третьем этапе инверсная начальной перестановке.

Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

Расшифрование

Расшифрование аналогично шифрованию, но подключи используются в обратной последовательности. Если выходом i-ого раунда шифрования было L_i||R_i, входом (16-i)-ого раунда расшифрования будет R_i||L_i.

Недостаток: в связи с тем, что длина ключа равна 56 битам, существует 2⁵⁶ возможных ключей, на основании которых возможны лобовые атаки.

Алгоритм ГОСТ 28147-89

С 1989 года в России установлен единый алгоритм криптографического преобразования данных для систем обработки информации в сетях ЭВМ, который определяется ГОСТ 28147-89. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптографическую защиту информации. Алгоритм предназначен для аппаратной и программной реализации, удовлетворяет криптографическим требованиям и не накладывает ограничений на степень секретности защищаемой информации.

ГОСТ 28147 является блочным алгоритмом шифрования, длина блока равна 64 битам, длина ключа равна 256 битам, количество раундов равно 32. Алгоритм представляет собой классическую сеть Фейштеля:

1. 64 битный блок делится на левую и правую половины, обозначенные L и R. При этом данные правой половины меняется местами с левой:

.

2.Для 32-битного блока правой половины выполняется сложение по модулю 2³² с 32-битным подключом K_i.

3. Блок размером в 32-бита разбивается на 8 подблоков по 4 бита, которые можно представить как числа от 0 до 15, тогда полученное число является порядковым номером входа в таблицу S-box, а цифра в таблице - выходным значением S-box. Выходы таблицы объединяются в 32-битное слово.

4. Производится циклический сдвиг на 11 бит 32-битного подблока. После чего складывается по модулю 2 с блоком левой половины, результат помещается в правую половину.

Генерация подключей:

1. 256-битный ключ разбивается на восемь 32-битных подключей.

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

	Раунд
1, 9, 17, 32	2, 10, 18, 31	3, 11,19,30	4, 12, 20, 29	5, 13, 21, 28	6, 14, 22, 27	7, 15, 23, 26	8, 16, 24, 25
подключ

Рис.

Хеш-функции

Хеш-функцией называется преобразование h, превращающее сообщение M произвольной длины H в последовательность фиксированной длины h(M) (т.е. происходит сжатие подписываемого документа p до нескольких десятков или сотен бит).

h = H(M)

Хеш-код функции h обозначается как m

Большинство хэш-функции строится на основе однонаправленной функции h(M), где входное значение (М) рассматривается как последовательность n-битных блоков, обрабатывается последовательно блок за блоком, и создается m-битное значение хэш-кода. При этом часто выходная последовательность предыдущего блока, является входной для последующего.

Secure Hash Algorithm (SHA)

Алгоритм безопасного хэширования SHA-1 принят в 1993 г в США.

Алгоритм получает на входе сообщение максимальной длины 2⁶⁴ бит и создает в качестве выхода дайджест сообщения длиной 160 бит.

1. Сообщение М дополняется единицей, за которой следует необходимое количество нулей таким образом, чтобы его длина была кратна 448 по модулю 512

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

3. Используется 160-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как пять 32-битных регистров A, B, C, D,E. Эти регистры инициализируются следующими шестнадцатеричными числами:

A = 67452301

B = EFCDAB89

C = 98BADCFE

D = 10325476

E = C3D2E1F0

4. Каждый текущий 512-битный обрабатываемый блок Y_q и 160-битное значение буфера ABCDEпоступают на модуль, состоящий из 80 циклических обработок, обозначенный как H_SHA. В циклические обработки входят следующие операции: сдвиг влево, сложение по модулю 2.

В каждом цикле используется дополнительная константа К_t, которая принимает значения:

0 t 19 K_t = 5A827999

20 t 39 K_t = 6ED9EBA1

40 t 59 K_t = 8F1BBCDC

60 t 79 K^t = CA62C1D6

Номер цикла	ft (B, C, D)
(0 t 19)	(B C) ( B D)
(20 t 39)	B C D
(40 t 59)	(B C) (B D) (C D)
(60 t 79)	B C D

Для получения SHA_q+1 выход 80-го цикла складывается со значением SHA_q. Сложение по модулю 2³² выполняется независимо для каждого из пяти слов в буфере с каждым из соответствующих слов в SHA^q.

5. После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения.

Хэш-функция ГОСТ 3411

Алгоритм ГОСТ 3411 является отечественным стандартом для хэш-функций. Длина хэш-кода, 256 битам. Алгоритм разбивает сообщение на блоки, длина которых также равна 256 битам. Кроме того, параметром алгоритма является стартовый вектор хэширования Н - произвольное фиксированное значение длиной также 256 бит.

Сообщение обрабатывается блоками по 256 бит справа налево, каждый блок обрабатывается по следующему алгоритму.

1. Генерация четырех ключей K_j=1…4, длиной 256 бит путем перестановки и сдвига

· промежуточного значения хэш-кода Н длиной 256 бит;

· текущего обрабатываемого блока сообщения М длиной 256 бит;

· и некоторых констант С₂, С₄=0, С₃=1⁸ 0⁸ 1¹⁶ 0²⁴ 1₁₆ 0⁸ (0⁸ 1⁸)² 1⁸ 0⁸ (0⁸ 1⁸)⁴ (1⁸ 0⁸)⁴, где степень обозначает количество повторений 0 или 1.и =0 длиной 256 бит.

а) Каждое 256-битное значение рассматривается как последовательность 32 8-битных значений, для которых осуществляется перестановкаP формуле y = (x), где x - порядковый номер 8-битного значения в исходной последовательности; y - порядковый номер 8-битного значения в результирующей последовательности.

y= (х) = 8i + k, где i = 0 ÷ 3, k = 1 ÷ 8

б)Сдвиг А определяется по формуле

A (x) = (x₁ x₂) & x₄& x₃& x_2, где x_i - соответствующие 64 бита 256-битного значения х,

с) Для определения ключа K₁ присваиваются следующие начальные значения:

K₁ = Р (H M)

Ключи K₂, K₃, K₄ вычисляются последовательно по следующему алгоритму:

K_i = Р (A(H) С_i) A(A(M)).

2. Шифрование 64-битных значений промежуточного хэш-кода H на ключах K_i(i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147 в режиме простой замены.

а) Хэш-код Н рассматривается как последовательность 64-битных значений H = h₄& h₃& h₂& h₁

б) Выполняется шифрование алгоритмом ГОСТ 28147

S_j = E_Ki [h_i] в) Результирующая последовательность S_j, j = 1, 2, 3, 4 длиной 256 бит запоминается во временной переменной S = s₁&s₂&s₃&s₄

3.Перемешивание результата шифрования.

а) 256-битное значение рассматривается как последовательность шестнадцати 16-битных значений η₁₆& η₁₅& ...& η₁

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

η₁ η₂ η₃ η₄ η₁₃ η₁₆ & η₁₆& ... & η₂

в) Результирующее значение хэш-кода определяется следующим образом:

Χ(M, H) = ⁶¹ (H (M ¹²(S)))

где H - предыдущее значение хэш-кода, М - текущий обрабатываемый блок, Ψⁱ - i-ая степень преобразования Ψ.

Логика выполнения ГОСТ 3411

Входными параметрами алгоритма являются:

· исходное сообщение М произвольной длины;

· стартовый вектор хэширования Н, длиной 256 битам;

· контрольная сумма Zдлиной 256 бит и начальным значением =0.

· переменная L=М.

Сообщение М делится на блоки длиной 256 бит, каждыйiблок обрабатывается справа налево следующим образом:

1. H = Χ(M_i, H) – ??? алгоритм хеширования описанный выше??

2. Z = Z M_i - сложение по модулю 2²⁵⁶.

3. L рассматривается как неотрицательное целое число, к которому прибавляется 256 и вычисляется остаток от деления на 2²⁵⁶. Результат присваивается L.

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

1. Блок добавляется слева нулями так, чтобы его длина стала равна 256 битам.

2. Вычисляется Σ = Σ M_i.

3. К L прибавляется длина исходного сообщения М и вычисляется остаток от деления на 2²⁵⁶.

4. Вычисляется Н = Χ(М', Н).

5. Вычисляется Н = Χ(L, Н).

6. Вычисляется Н = Χ(Z, Н).

Значением функции хэширования является Н.