Лекция № 8. 3. MixColumns (перемешивание)

1. SubBytes (замена)

2. ShiftRov (сдвиг)

3. MixColumns (перемешивание)

4. AddRoundKey (сложение с ключом)

Замена.

Возможности отражены в следующей таблице:

Nr	Nb = 4	Nb = 6	Nb = 8
Nk = 4
Nk = 6
Nk = 8

Быстродействие не очень снижается.

N_r – число раундов; N_b – число столбцов; N_k – число столбцов в ключе.

N_k = 4 – 128 бит

N_k = 6 – 196 бит

N_k = 8 – 256 бит

Описание операции

В′ = АВ С

В′ - выходной столбец.

А – фиксированная матрица. Во всех преобразованиях она не меняется.

С – константа.

А =

Матрица А является невырожденной матрицей, следовательно, она имеет обратную матрицу. Их число достаточно большое.

При расшифровании известно В′

А^-1В′ С = В

1

С =

b₀^′

b₁^′

b₂^′

b₃^′

b₄^′

b₅^′

b₆^′

b₇^′

В′ =

b₀^′

b₁^′

b₂^′

b₃^′

b₄^′

b₅^′

b₆^′

b₇^′

							1

1

b₀

b₁

b₂

b₃

b₄

b₅

b₆

b₇

= *

Это нелинейная операция (аффинная).

b_i^′, i = от 0 до 7

b_i^′ = b_i b_(i+4)mod8 b_(i+5)mod8 b_(i+6)mod8 b_(i+7)mod8 C_i

b₀^′ = b₀ b₄ b₅ b₆ b₇

b₁^′ = b₀ b₁ b₅ b₆ b₇

b₂^′ = b₀ b₁ b₂ b₆ b₇

b₃^′ = b₀ b₁ b₂ b₃ b₇

b₄^′ = b₀ b₁ b₂ b₃ b₄

b₅^′ = b₁ b₂ b₃ b₄ b₅

b₆^′ = b₂ b₃ b₄ b₅ b₆

b₇^′ = b₃ b₄ b₅ b₆ b₇

Матрица реализуется аппаратно

x						…		a	…	f
		7c
…
				ed
…
a
…
f

x = 5, y = 3

Программным способом можно реализовать в виде этой таблицы, где в каждой клетке – байт.

х – номер строки

у – номер столбца

ed – новый байт

Расшифрование производится следующим образом:

b′(x) = a(x)·f(x)mod p(x) g(x)

После выполнения этой операции получаем новую матрицу.

S00	S01	S02	S03
S10	S11	S12	S13
S20	S21	S22	S23
S30	S31	S32	S33

ShiftRov.

S00	S01	S02	S03
S10	S11	S12	S13
S20	S21	S22	S23
S30	S31	S32	S33

S00	S01	S02	S03
S11	S12	S13	S10
S22	S23	S20	S21
S33	S30	S31	S32

Первая строка не изменяется, вторая – сдвигается на одну позицию влево, третья – на 2 позиции, четвертая – на три позиции влево.

MixColumns.

Производится смена столбцов. Результат преобразования ставится на прежнее место.

			01

Матрица циркулянта. Проста для реализации.

S_0c^′

S_1c^′

S_2c^′

S_3c^′

	вых. столбец

=

0≤С≤3

			01

S_0c^′

S_1c^′

S_2c^′

S_3c^′

	рассеивание

*

	вх. столбец

Это можно представить в виде формулы

S_oc′ = ({02}· S_oc) ({03}· S_1c) S_2c S_3c

S_1c′ = S_oc ({02}· S_1c) ({03}· S_2c) S_3c

S_2c′ = S_0c S_1c ({02}· S_2c) ({03}· S_3c)

S_3c′ = ({03}· S_oc) S_1c S_2c ({02}· S_3c)

AddRoundKey

	ключ		Исходное состояние для второго раунда

Данная процедура повторяется 10 раундов. Исходное состояние после 10-ого раунда есть выходной шифр. На каждом раунде используется новый ключ (128 бит).

Алгоритм расширения ключа

w0

w1

w2

w3

w4

w5

w6

w7

…………..

128 бит раунд 1 раунд 10

Преобразование идет со столбцами

Столбцы с индексами, кратными 4, над которыми преобразование производится иначе, чем над столбцами с индексами, некратными четырем (текущими).

Текущее слово w(i) = w(i-1) w(i-N_k)

N_k = 4,6,8

w(5) = w(4) w(1)

w(6) = w(5) w(2)

Для столбцов с индексами, кратными четырем, вводятся следующие операции:

1. RotWord

2. Subbytes

3. Операция сложения с константой

RotWord – сдвиг 32-разрядного слова.

Subbytes – побайтное изменение на основе ранее изложенной операции B′= AB C

R – константа

R_const = 2^j-1

w(4) j=1

R_const (i/N_k) = j

W(i) = SubWord (RotWord(w[i-1])) R_const[i/N_k] w[i-N_k]

Требования к алгоритму расширения ключа

1. Обратимость используемых преобразований.

Из любых N_k последовательных слов можно однозначно восстановить весь развернутый ключ. Это достигается за счет простых обратимых операций.

B = A^-1B′ C

Матрица А должна быть квадратной и ее определитель не должен быть равен нулю (невырожденная матрица). В этом случае она имеет обратную матрицу.

2. Хорошая скорость на различных типах процессоров.

128 + 128 · 10 = 1408 бит – длина ключевой последовательности, работающей в 10 раундах.

3. Наличие раундовых констант для уменьшения симметричности.

4. Хорошее рассеивание изменений в начальном ключе шифрование на формируемый раундовый ключ.

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

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

7. Простота шифрования.

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

1. Обратное преобразование по раундам с использованием обратного расширения.

Вход для расшифрования – результат 10^ого шифра

2. В каждом раунде – тобратное применение операций.

Обратная операция по столбцам

S′ = [C_M] · [S]

S = [C_M^-1] · S′

0c	0b	0d	09
	0c	0b	0d
0d		0c	0b
0b	0d		oc

  S^′

S = *

S_0c′ = ({0c}· S_0c) ({0b}· S_1c) ({0d}· S_2c) ({09}· S_3c)

S_1c′ = ({09}· S_0c) ({0c}· S_1c) ({0b}· S_2c) ({0d}· S_3c)

S_2c′ = ({0d}· S_0c) ({09}· S_1c) ({0c}· S_2c) ({0b}· S_3c)

S_3c′ = ({0b}· S_0c) ({0d}· S_1c) ({09}· S_2c) ({0c}· S_3c)

0≤С≤3

Дата добавления: 2014-01-15