41729

1. Алгоритм шифрования S_AES

2. История проведения конкурса AES

• В 1997 году правительство США объявило на
базе института стандартизации NIST (the
National Institute of Standards and Technology)
открытый конкурс на новый стандарт
блочного шифра США. Победитель конкурса
получал статус нового стандарта
шифрования AES (Advanced Encryption
Standard) и рекомендовался к повсеместному
использованию на территории США.

3. Требования, которые предъявлялись к новому стандарту:

• криптоалгоритм должен быть открыто опубликован;
• криптоалгоритм должен быть симметричным
блочным шифром, поддерживающим 128-, 192- и
256-битные ключи.
• криптоалгоритм должен быть предназначен как для
аппаратной, так и для программной реализации;
• криптоалгоритм должен быть доступен для открытого
использования в любых продуктах, а значит, не
может быть запатентован, в противном случае
патентные права должны быть аннулированы;
• криптоалгоритм подвергается изучению по
следующим параметрам: стойкости, стоимости,
гибкости, реализуемости в smart-картах.

4.

5.

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

Nr
Nb=4
Nb=6
Nb=8
Nk=4
10
12
14
Nk=6
12
12
14
Nk=8
14
14
14

7. Раундовое преобразование

Раунд состоит из четырех различных преобразований:
• замена байтов SubBytes() – побайтовой подстановки
в S-блоках с фиксированной таблицей замен
размерностью 8x256;
• сдвига строк ShiftRows() – побайтового сдвига строк
массива State на различное количество байт;
• перемешивание столбцов MixColumns() – умножение
столбцов состояния, рассматриваемых как
многочлены над GF(28), на многочлен третьей
степени g(x) по модулю x4+1;
• сложение с раундовым ключом AddRoundKey() –
поразрядного XOR с текущим фрагментом
развернутого ключа.

8. Применение преобразования SubBytes()

S00 S01 S02 S03
S10 S11
Sij
S13
SubBytes
S'00 S'01 S'02 S'03
S'10 S'11
S'ij S'13
S20 S21 S22 S23
S'20 S'21 S'22 S'23
S30 S31 S32 S33
S'30 S'31 S'32 S'33

9. Преобразование SubBytes()

Представляет собой нелинейную замену байтов, выполняемую
независимо с каждым байтом состояния. Таблицы замены S-блока
являются инвертируемыми и построены из композиции следующих
двух преобразования входного байта:
• получение обратного элемента относительно умножения в поле GF(28),
нулевой элемент {00} переходит сам в себя;
• применение преобразования над GF(2), определенного следующим
образом:
b0 ' 1
b '
1 1
b2 ' 1
b3 ' 1
b ' 1
4
b5 ' 0
b ' 0
6
b7 ' 0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1 b0 1
1 b1 1
1 b2 0
1 b3 0
0 b4 0
0 b5 1
0 b6 1
1 b7 0
Суть преобразования может быть описана уравнением
bi’=bi b(i+4)mod8 b(i+5)mod8 b(i+6)mod8 b(i+7)mod8 ci,
где c0=c1=c5=c6=1, c2=c3=c4=c7=0, bi и bi’-соответственно исходное и
преобразованное значение i-го бита, i меняется от 0 до 7.

10. Преобразование SubBytes()

11.

Таблица замен S-блока
• Логика работы S-блока при преобразовании байта {xy} отражена в
таблице. Например, результат {26} преобразования байта {23}
находится на пересечении 3-й строки и 4-го столбца.

12. Таблица замен S-блока

• Логика работы S-блока при преобразовании байта {xy} отражена в
таблице. Например, результат {26} преобразования байта {23}
находится на пересечении 3-й строки и 4-го столбца.

13. Преобразование сдвига строк (ShiftRows)

S00
S01 S02
S03 Без сдвига
S10
S11
S13 Циклический сдвиг на С
S20
S30
S00
S01
S02 S03
S11
S12
S13 S10
S21 S
22
S23 Циклический сдвиг на С2 S22
S23
S20 S21
S31 S32
S33 Циклический сдвиг на С3 S33
S30
S31 S32
S12
1

14. Величина сдвига для разной длины блоков

Nb
C1
C2
C3
4
1
2
3
6
1
2
3
8
1
3
4
В стандарте AES, где определен единственный размер блока,
равный 128 битам, С1 = 1, С2 = 2, С3 = 3.

15. Преобразование перемешивания столбцов (MixColumns)

S00
S01 S0с
S03
S10
S11 S1с
S13
S'10 S'11
S20
S21
S23
S'20 S'21
S30
S31
S33
S'30 S'31
S2с
S3с
MixColumns
S'00 S'01
S'0с
S'03
S'1с S'13
S'2с
S'23
S'33
S'3с

16. Преобразование перемешивания столбцов (MixColumns)

• Преобразование перемешивания столбцов (MixColumns) это
такое преобразование, при котором столбцы состояния
рассматриваются как многочлены над GF(28) и умножаются по
модулю х4+1 на многочлен g(x), выглядящий следующим
образом: g(x)={03}x3+{01}x2+{01}x+{02}.
• Это может быть представлено в матричном виде следующим
образом:
s'0c 02
s'
1c 01
s'2c 01
s
'
3c 03
03
02
01
01
01
03
02
01
где с – номер столбца массива State.
01 s0c
01 s1c
,0 c 3
s
03 2c
02 s3c

17. Преобразование перемешивания столбцов (MixColumns)

• В результате такого умножения байты
столбца s0c, s1c, s2c, s3c заменяются
соответственно на байты:
• s’0c=({02}*s0c) ({03}*s1c) s2c s3c,
• s’1c=s0c ({02}*s1c) ({03}*s2c) s3c,
• s’2c=s0c s1c ({02}*s2c) ({03}*s3c),
• s’3c=({03}*s0c) s1c s2c ({02}*s3c).

18. Добавление раундового ключа (AddRoundKey)

S00
S01 S0с
S03
S10
S11 S1с
S13
S20
S21
S23
S30
S31
S2с
S33
S3с
k00
k01
k0с
k03
k10
k11
k1с
k13
k20
k21
k30
k31
k2с
k23
k33
k3с
S'00
S'01
S'10
S'11
S'20
S'21
S'0с
S'03
S'1с S'13
S'2с
S'30 S'31
S'23
S'33
S'3с

19. Алгоритм выработки ключей

Раундовые ключи получаются из ключа шифрования посредством
алгоритма выработки ключей. Он содержит два компонента:
расширение ключа (Key Expansion) и выбор раундового ключа (Round
Key Selection). Основополагающие принципы алгоритма выглядят
следующим образом:
общее число битов раундовых ключей равно длине блока, умноженной
на число раундов, плюс 1 (например для длины блока 128 бит и 10
раундов требуется 1408 бит раундовых ключей);
ключ шифрования преобразуется в расширенный ключ (Expanded Key);
раундовые ключи берутся из расширенного ключа следующим
образом: первый раундовый ключ содержит первые Nb слов, второй –
следующие Nb слов и т. д.
Расширенный ключ (Key Expansion) в Rijndael представляет собой
линейный массив w[i] из Nb(Nr+1) 4-байтовых слов.
Первые Nk слов содержат ключ шифрования. Все остальные слова
определяются рекурсивно из слов с меньшими индексами. Алгоритм
выработки подключей зависит от величины Nk.
Первые Nk слов заполняются ключом шифрования. Каждое
последующее слово w[i] получается посредством сложения по модулю
два предыдущего слова w[i-1] и слова на Nk позиций ранее, то есть w[iNk]:
w[i] = w[i-1] w[i-Nk].

20. Алгоритм выработки ключей

Для слов, позиция которых кратна Nk перед операцией сложения по модулю
два применяется преобразование к w[i-1], а затем еще прибавляется раундовая
константа Rconst. Преобразование реализуется с помощью двух
дополнительных функций: RotWord(), осуществляющей побайтовый сдвиг 32разрядного слова по формуле {a0, a1, a2, a3} {a1, a2, a3, a0}, и SubWord(),
осуществляющей побайтовую замену с использованием S-блока функции
SubBytes(). Значение Rconst[j] равно2j-1. Значение w[i] в этом случае равно:
w[i] = SubWord(RotWord(w[i-1])) Rconst[i/Nk] w[i-Nk].
Раундовый ключ i получается из слов массива раундового ключа от W[Nbi] и до
W[Nb(i+1)].

21. Функция зашифрования

Входной блок
Функция Ek
зашифрования
Rijndael
Добавление раундового ключа
AddRoundKey
Замена байтов
SubBytes
Сдвиг строк
ShiftRows
1-й раунд
Перемешивание столбцов
MixColumns
Добавление раундового ключа
AddRoundKey
Замена байтов
SubBytes
Сдвиг строк
ShiftRows
9-й раунд
Перемешивание столбцов
MixColumns
Добавление раундового ключа
AddRoundKey
Замена байтов
SubBytes
Сдвиг строк
ShiftRows
Добавление раундового ключа
AddRoundKey
Выходной блок
10-й раунд
Шифр Rijndael состоит:
из начального добавления
раундового ключа;
Nr – 1 раундов;
заключительного раунда, в
котором отсутствует
операция MixColumns().

22. Функция обратного дешифрования

• Если вместо SubBytes(), ShiftRows(), MixColumns() и
AddRoundKey() в обратной последовательности выполнить
инверсные им преобразования, можно построить функцию
обратного дешифрования. При этом порядок использования
раундовых ключей является обратным по отношению к тому,
который используется при зашифровании.
• Функция AddRoundKey() обратна сама себе, учитывая свойства
используемой в ней операции XOR.
• Для преобразования байта {xy} используется инверсный S-блок
InvSubBytes
• В преобразовании InvShiftRows последние 3 строки состояния
сдвигаются вправо на различное число байтов. Строка 1
сдвигается на С1 байт, строка 2 – на С2 байт, и строка 3 – на С3
байт. Значение сдвигов С1, С2 и С3 зависят от длины блока Nb.

23. Функция обратного дешифрования

• В преобразовании InvMixColumns столбцы состояния
рассматриваются как многочлен над GF(28) и умножаются по
модулю x4+1 на многочлен g-1(x), выглядящий следующим образом:
g-1(x)={0b}x3+{0d}x2+{09}x+{0e}.
• Это может быть представлено в матричном виде следующим
образом:
s'0c 0e 0b 9d 09 s0c
s' 09 0e 0b 0d s
1c
1c
s'2c 0d 09 0e 0b s2c
s'3c 0b 0d 09 0e s3c
• В результате на выходе получаются следующие байты:
s’0c=({0e}*s0c) ({0b}*s1c) ({0d}*s2c) ({09}*s3c),
s’1c=({09}*s0c) ({0e}*s1c) ({0b}*s2c) ({0d}*s3c),
s’2c=({0d}*s0c) ({09}*s1c) ({0e}*s2c) ({0b}*s3c),
s’3c=({0b}*s0c) ({0d}*s1c) ({09}*s2c) ({0e}*s3c).

24. Последовательность преобразований в двухраундовом варианте Rijndael

Функция зашифрования
Функция обратного
двухраундового варианта дешифрования
Rijndael
двухраундового варианта
Rijndael
Эквивалентная функция
прямого дешифрования
двухраундового варианта
Rijndael
AddRoundKey
AddRoundKey
AddRoundKey
SubBytes
InvShiftRows
InvSubBytes
ShiftRows
InvSubBytes
InvShiftRows
MixColumns
AddRoundKey
InvMixColumns
AddRoundKey
InvMixColumns
AddRoundKey
SubBytes
InvShiftRows
InvSubBytes
ShiftRows
InvSubBytes
InvShiftRows
AddRoundKey
AddRoundKey
AddRoundKey

25. Основные особенности Rijndael

Основные особенности Rijndael:
• новая архитектура «Квадрат»,
обеспечивающая быстрое рассеивание и
перемешивание информации, при этом за
один раунд преобразованию подвергается
весь входной блок;
• байт ориентированная структура, удобная
для реализации на 8-разрядных МК;
• все раундовые преобразования
представляют собой операции в конечных
полях, допускающие эффективную
аппаратную и программную реализацию на
различных платформах.

26. Алгоритм шифрования S_AES

27.

Формат представления данных
S00
S01
S10
S11

28.

Формат секретного ключа
шифрования
К00
К01
К10
К11

29. Раундовое преобразование

Раунд состоит из четырех различных преобразований:
• замена полубайтов SubHalfBytes() –подстановки в Sблоках с фиксированной таблицей замен;
• сдвига строк ShiftRows() –сдвига строк массива State
на различное количество полубайт;
• перемешивание столбцов MixColumns() – умножение
столбцов состояния, рассматриваемых как
многочлены над GF(24), на многочлен третьей
степени g(x) по модулю x2+1;
• сложение с раундовым ключом AddRoundKey() –
поразрядного XOR с текущим фрагментом
развернутого ключа.

30. Применение преобразования SubBytes в AES()

S00 S01 S02 S03
S10 S11
Sij
S13
SubBytes
S'00 S'01 S'02 S'03
S'10 S'11
S'ij S'13
S20 S21 S22 S23
S'20 S'21 S'22 S'23
S30 S31 S32 S33
S'30 S'31 S'32 S'33

31. Применение преобразования SubBytes в S_AES()

32. Преобразование SubBytes()

Представляет собой нелинейную замену полубайтов, выполняемую
независимо с каждым полубайтом состояния. Таблицы замены S-блока
являются инвертируемыми и построены из композиции следующих
двух преобразования входного байта:
• получение обратного элемента относительно умножения в поле GF(24),
нулевой элемент {00} переходит сам в себя;
• применение преобразования над GF(24), определенного следующим
образом:
b0 ' 1
b ' 1
1
b2 ' 1
b3 ' 0
0
1
1
1
1
0
1
1
1 b0 1
1 b1 0
0 b2 0
1 b3 1
Суть преобразования может быть описана уравнением
bi’=bi b(i+2)mod4 b(i+3)mod4 ci,
где c0=c3=1, c1=c2=0, bi и bi’-соответственно исходное и преобразованное
значение i-го бита, i меняется от 0 до 3.

33.

Таблица замен S-блока
x
00
01
10
11
Y
00
9
8
6
c
01
e
b
7
4
10
5
d
f
0
11
1
a
3
2

34. Инверсная таблица замен S-блока

Инверсная таблица замен Sблока
x
Y
00
01
10
11
00
e
3
f
B
01
d
2
8
9
10
4
0
7
5
11
c
6
1
a

35. Преобразование сдвига строк в AES (ShiftRows)

S00
S01 S02
S03 Без сдвига
S10
S11
S13 Циклический сдвиг на С
S20
S30
S00
S01
S02 S03
S11
S12
S13 S10
S21 S
22
S23 Циклический сдвиг на С2 S22
S23
S20 S21
S31 S32
S33 Циклический сдвиг на С3 S33
S30
S31 S32
S12
1

36. Преобразование сдвига строк в S_AES (ShiftRows)

37. Величина сдвига для разной длины блоков

Nb
C1
C2
C3
4
1
2
3
6
1
2
3
8
1
3
4
В стандарте AES, где определен единственный размер блока,
равный 128 битам, С1 = 1, С2 = 2, С3 = 3.

38. Преобразование перемешивания столбцов в AES(MixColumns)

S00
S01 S0с
S03
S10
S11 S1с
S13
S'10 S'11
S20
S21
S23
S'20 S'21
S30
S31
S33
S'30 S'31
S2с
S3с
MixColumns
S'00 S'01
S'0с
S'03
S'1с S'13
S'2с
S'23
S'33
S'3с

39. Преобразование перемешивания столбцов в S_AES(MixColumns)

40. Преобразование перемешивания столбцов (MixColumns)

• Преобразование перемешивания столбцов (MixColumns) это
такое преобразование, при котором столбцы состояния
рассматриваются как многочлены над GF(24) и умножаются по
модулю х2+1 на многочлен g(x), выглядящий следующим
образом: g(x)={2}x+{3}.
• Это может быть представлено в матричном виде следующим
образом:
S 0c ' 3 2 S 0c
S ' 2 3 S ,0 c 1,
1c
1c
где с – номер столбца массива State.

41. Преобразование перемешивания столбцов (MixColumns)

• В результате такого умножения
полубайты столбца S0c и S1c заменяются
соответственно на полубайты:
• S0c’ = ({3} S0c) ({2} S1c),
• S1c’ = ({2} S0c) ({3} S1c).

42. Добавление раундового ключа в AES(AddRoundKey)

S00
S01 S0с
S03
S10
S11 S1с
S13
S20
S21
S23
S30
S31
S2с
S33
S3с
k00
k01
k0с
k03
k10
k11
k1с
k13
k20
k21
k30
k31
k2с
k23
k33
k3с
S'00
S'01
S'10
S'11
S'20
S'21
S'0с
S'03
S'1с S'13
S'2с
S'30 S'31
S'23
S'33
S'3с

43. Добавление раундового ключа в S_AES(AddRoundKey)

44. Алгоритм выработки ключей

Раундовые ключи вырабатываются из исходного 16битового секретного ключа по следующей схеме.
Исходный 16-битовый ключ, как уже говорилось
ранее, можно представить в виде четырех
полубайтов К00, К10, К01, К11. Эти четыре полубайта
формируют первый раундовый подключ: К001, К101,
К011, К111. Второй и третий раундовые подключи
можно получить по следующим формулам:
К00r = Sub Half-Bytes*(K11r-1) K00r-1;
К10r = Sub Half-Bytes*(K01r-1) K10r-1 2r-2;
К01r = К00r К01r-1;
К11r = К10r К11r-1,
где верхний индекс r – номер вырабатываемого
подключа

45. Функция зашифрования

46.

Функция
дешифрования

47. ПРИМЕР

Зашифровать входной блок
данных: {7, e, 3, b} с
использованием секретного
ключа К: {3, e, f, a}

48. Запишем эти данные в виде двумерных массивов:

Массив исходных
данных:
Ключ:
7
3
3
f
е
b
e
a

49. Для начала необходимо получить раундовые подключи. Первым раундовым подключом будет являться сам секретный ключ, то есть:

К001 = 3;
К101 = e;
К011 = f;
К111 = a.

50. Воспользовавшись формулами

К00r = Sub Half-Bytes*(K11r-1) K00r-1;
К10r = Sub Half-Bytes*(K01r-1) K10r-1 2r-2;
К01r = К00r К01r-1;
К11r = К10r К11r-1,
где верхний индекс r –
номер вырабатываемого подключа
К001 = 3;
К101 = e;
К011 = f;
К111 = a.
найдем:
К002 = Sub Half-Bytes*(К111) К001 =
= Sub Half-Bytes*(a) 3 = f 3 = c;
К102 = Sub Half-Bytes*(К011) К101 20=
=Sub Half-Bytes*(f) e 1 =2 e 1 = d;
К012 = К002 К011 = c f = 3;
К112 = К102 К111 = d a = 7;
К003 = Sub Half-Bytes*(К112) К002 =
= Sub Half-Bytes*(7) c = a c = 6;
К103 = Sub Half-Bytes*(К012) К102 21
= Sub Half-Bytes*(3) d 2 =1 d 2 = e;
К013 = К003 К012 = 6 3 = 5;
К112 = К103 К112 = e 7 = 9;
x
Y
00
01
10
11
00
9
e
5
1
01
8
b
d
a
10
6
7
f
3
11
c
4
0
2

51. Таким образом, получили три раундовых подключа:

Первый подключ К1
Второй подключ К2
3
f
с
3
e
a
d
7
Третий подключ К3
6
5
e
9

52. Сложение исходных данных с первым раундовым подключом

7 3=4
3 f=с
е е=0
b a=1

53. Произведем замену полубайтов с помощью таблицы замены, получим:

4
с
8
с
0
1
9
е
x
Y
00
01
10
11
00
9
e
5
1
01
8
b
d
a
10
6
7
f
3
11
c
4
0
2

54. Произведем сдвиг

8
с
8
с
9
e
e
9

55. Произведем перемешивание столбцов с помощью операции Mix Columns*()

Для начала представим табличные
данные в виде многочленов.
S00 = {8} = x3,
S10 = {e} = x3 x2 x,
S01 = {c} = x3 x2,
S11 = {9} = x3 1

56.

Теперь можно приступить к нахождению
новых элементов массива:
S00’ = ({3} S00) ({2} S10) = ((x 1) x3)
(x (x3 x2 x)) = (x4 x3) (x4 x3 x2) = x2 = {4};
S10’ = ({2} S00) ({3} S10)=(x x3) ((x 1) (x3 x2 x))=
=(x4) (x4 x3 x2 x3 x2 x) = (x4) (x4 x) =
=x = {2};
S01’ = ({3} S01) ({2} S11)=((x 1) (x3 x2)) (x (x3 1))=
=(x4 x3 x3 x2) (x4 x) = x2 x = {6};
S11’ = ({2} S01) ({3} S11)=(x (x3 x2)) ((x 1) (x3 1))=
=(x4 x3) (x4 x x3 1) = x 1 = {3}.
{2}=x {3}=x 1
Значение модуля х4 x 1

57. Получили массив преобразованных данных

4
6
2
3

58. Сложение исходных данных со вторым раундовым подключом

4 с=8 6 3=5
2 d=f
3 7=4

59. Произведем замену полубайтов с помощью таблицы замены, получим:

8
5
6
b
f
4
2
8
x
Y
00
01
10
11
00
9
e
5
1
01
8
b
d
a
10
6
7
f
3
11
c
4
0
2

60. Произведем сдвиг

6
b
6
b
2
8
8
2

61. Сложение исходных данных со вторым раундовым подключом

6 6=0
b 5=е
8 е=6
2 9=b

62. Итак, в результате шифрования данных с помощью алгоритма шифрования S_AES, мы получили в результате значение {0, 6, e, b}.