Курс лекций «Проблемы безопасности в информационных технологиях»



жүктеу 4.51 Mb.
бет11/44
Дата13.09.2017
өлшемі4.51 Mb.
түріКурс лекций
1   ...   7   8   9   10   11   12   13   14   ...   44

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


ГОСТ 28147-89 — советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название — «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма. С момента опубликования ГОСТа на нём стоял ограничительный гриф «Для служебного пользования», и формально шифр был объявлен «полностью открытым» только в мае 1994 года. История создания шифра и критерии разработчиков по состоянию на 2010 год не опубликованы.

Алгоритм представляет собой классическую сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки).

Li = Ri-1

Ri = Li f (Ri-1, Ki)


Функция f в ГОСТ 28147 проще, чем в DES. Сначала правая половина и i-ый подключ складываются по модулю 232. Затем результат разбивается на восемь 4-битовых значений, каждое из которых подается на вход S-box. ГОСТ 28147 использует восемь различных S-boxes, каждый из которых имеет 4-битовый вход и 4-битовый выход. Выходы всех S-boxes объединяются в 32-битное слово, которое затем циклически сдвигается на 11 битов влево. Наконец, с помощью XOR результат объединяется с левой половиной, в результате чего получается новая правая половина.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей Ki.




Рис.13 Схема раунда в ГОСТ 28147
Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K1…K8 (т.е. каждый подключ используется в четырёх раундах). Ключи K9…K24 являются циклическим повторением ключей K1…K8 (нумеруются от младших битов к старшим), Ключи K25…K32 являются ключами K1…K8, идущими в обратном порядке:


Раунд

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

Подключ

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

8

7

6

5

4

3

2

1

Все восемь S-блоков могут быть различными. Долгое время структура S-boxes в открытой печати не публиковалась. В настоящее время известны S-boxes, которые используются в приложениях Центрального Банка РФ и считаются достаточно сильными:




Номер S-блока

Значение

1

4

10

9

2

13

8

0

14

6

11

1

12

7

15

5

3

2

14

11

4

12

6

13

15

10

2

3

8

1

0

7

5

9

3

5

8

1

13

10

3

4

2

14

15

12

7

6

0

9

11

4

7

13

10

1

0

8

9

15

14

4

6

12

11

2

5

3

5

6

12

7

1

5

15

13

8

4

10

9

14

0

3

11

2

6

4

11

10

0

7

2

1

13

3

6

8

5

9

12

15

14

7

13

11

4

1

3

15

5

9

0

10

14

7

6

8

2

12

8

1

15

13

0

5

7

10

4

9

2

3

14

6

11

8

12

В мае 2011 года известный криптоаналитик Николя Куртуа доказал существование атаки на данный шифр, имеющей сложность в 28 (256) раз меньше сложности прямого перебора ключей при условии наличия 264 пар открытый текст/закрытый текст. Данная атака не может быть осуществлена на практике ввиду слишком высокой вычислительной сложности.

Можно отметить следующие различия между DES и ГОСТ 28147:


  • DES использует гораздо более сложный алгоритм создания подключей, чем ГОСТ 28147. В ГОСТ эта процедура очень проста.

  • В DES применяется 56-битный ключ, а в ГОСТ 28147 – 256-битный. При выборе сильных S-boxes ГОСТ 28147 считается очень стойким.

  • У S-boxes DES 6-битовые входы и 4-битовые выходы, а у S-boxes ГОСТ 28147 4-битовые входы и выходы. В обоих алгоритмах используется по восемь S-boxes, но размер S-box ГОСТ 28147 существенно меньше размера S-box DES.

  • В DES применяются нерегулярные перестановки Р, в ГОСТ 28147 используется 11-битный циклический сдвиг влево. Перестановка DES увеличивает лавинный эффект. В ГОСТ 28147 изменение одного входного бита влияет на один S-box одного раунда, который затем влияет на два S-boxes следующего раунда, три S-boxes следующего и т.д. В ГОСТ 28147 требуется 8 раундов прежде, чем изменение одного входного бита повлияет на каждый бит результата; DES для этого нужно только 5 раундов.

  • В DES 16 раундов, в ГОСТ 28147 – 32 раунда, что делает его более стойким к дифференциальному и линейному криптоанализу.

Основные проблемы ГОСТа связаны с неполнотой стандарта в части генерации ключей и таблиц замен. Считается, что у ГОСТа существуют «слабые» ключи и таблицы замен, но в стандарте не описываются критерии выбора и отсева «слабых». Также стандарт не специфицирует алгоритм генерации таблицы замен (S-boxes). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой, поднимает ряд проблем:




  • нельзя определить криптостойкость алгоритма, не зная заранее таблицы замен;

  • реализации алгоритма от различных производителей могут использовать разные таблицы замен и могут быть несовместимы между собой;

  • возможность преднамеренного предоставления слабых таблиц замен лицензирующими органами РФ;

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



Разработка Advanced Encryption Standard (AES)


Понимая слабость и уязвимость стандарта DES, NIST (Национальный Институт стандартов и технологий (США)) в 1997 году стал инициатором проведения конкурса на разработку нового криптографического стандарта, который должен был стать преемником DES. Требования к новому стандарту были следующими:

  • блочный шифр.

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

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

Конкурс вызвал значительный интерес, в нём участвовало большое количество разработчиков. Дополнительные рекомендации кандидатам включали:

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

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

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

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

20 августа 1998 года на 1-й конференции AES был объявлен список из 15 кандидатов: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish. В последующих обсуждениях эти алгоритмы подвергались всестороннему анализу, причём исследовались не только криптографические свойства, такие как стойкость к известным атакам, отсутствие слабых ключей, хорошие статистические свойства, но и практические аспекты реализации: оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распараллеливания. Проверка кандидатов на предмет формирования случайных двоичных последовательностей осуществлялась с помощью набора статистических тестов NIST.

В течение первого раунда тестирование проводилось со 128-битными ключами. Лишь 9 алгоритмов из 15 смогли пройти статистические тесты, а именно: CAST-256, DFC, E2, LOKI-97, MAGENTA, MARS, Rijndael, SAFER+ и Serpent. Оставшиеся алгоритмы показали некоторые отклонения в тестах на случайный характер формируемых ими двоичных последовательностей

В марте 1999 года прошла 2-я конференция AES, а в августе 1999 года были объявлены 5 финалистов: MARS, RC6, Rijndael, Serpent и Twofish. Все эти алгоритмы были разработаны авторитетными криптографами с мировыми именами. На 3-й конференции AES в апреле 2000 года авторы выступили с докладами о своих алгоритмах.

MARS выполняет последовательность преобразований в следующем порядке: сложение с ключом в качестве pre-whitening (предварительное «забеливание»), 8 раундов прямого перемешивания без использования ключа, 8 раундов прямого преобразования с использованием ключа, 8 раундов обратного преобразования с использованием ключа, 8 раундов обратного перемешивания без использования ключа и вычитание ключа в качестве post-whitening («постзабеливание»). 16 раундов с использованием ключа называются криптографическим ядром. Раунды без ключа используют два 8х16-битных S-boxes, операции сложения и XOR. В дополнение к этим элементам раунды с ключом используют 32-битное умножение ключа, зависимые от данных циклические сдвиги и добавление ключа. Как раунды перемешивания, так и раунды ядра являются раундами модифицированной сети Фейстеля, в которых четверть блока данных используется для изменения остальных трех четвертей блока данных. MARS был предложен корпорацией IBM.

RC6 является параметризуемым семейством алгоритмов шифрования, основанных на сети Фейстеля; для AES было предложено использовать 20 раундов. Функция раунда в RC6 задействует переменные циклические сдвиги, которые определяются квадратичной функцией от данных. Каждый раунд также включает умножение по модулю 32, сложение, XOR и сложение с ключом. Сложение с ключом также используется для pre- и post-whitening. RC6 был предложен лабораторией RSA.

Rijndael представляет собой алгоритм, использующий линейно-подстановочные преобразования и состоящий из 10, 12 или 14 раундов в зависимости от длины ключа. Блок данных, обрабатываемый с использованием Rijndael, делится на массивы байтов, и каждая операция шифрования является байт-ориентированной. Функция раунда Rijndael состоит из четырех слоев. В первом слое для каждого байта применяется S-box размерностью 8х8 бит. Второй и третий слои являются линейными перемешиваниями, в которых строки рассматриваются в качестве сдвигаемых массивов и столбцы перемешиваются. В четвертом слое выполняется операция XOR байтов подключа и каждого байта массива. В последнем раунде перемешивание столбцов опущено. Rijndael предложен Joan Daemen (Proton World International) и Vincent Rijmen (Katholieke Universiteit Leuven).

Serpent является алгоритмом, использующим линейно-подстановочные преобразования и состоящим из 32 раундов. Serpent также определяет некриптографические начальную и заключительную перестановки, которые облегчают альтернативный режим реализации, называемый bitslice. Функция раунда состоит из трех слоев: операция XOR с ключом, 32-х параллельное применение одного из восьми фиксированных S-boxes и линейное преобразование. В последнем раунде слой XOR с ключом заменен на линейное преобразование. Serpent предложен Ross Anderson (University of Cambridge), Eli Biham (Technion) и LarsKnudsen (University of California San Diego).



Twofish является сетью Фейстеля с 16 раундами. Сеть Фейстеля незначительно модифицирована с использованием однобитных ротаций. Функция раунда влияет на 32-битные слова, используя четыре зависящих от ключа S-boxes, за которыми следуют фиксированные максимально удаленные отдельные матрицы в GF(28), преобразование псевдо-Адамара и добавление ключа. Twofish был предложен Bruce Schneier, John Kelsey и Niels Ferguson (Counterpane Internet Security, Inc.), Doug Whiting (Hi/fn, Inc.), David Wagner (University of California Berkley) и Chris Hall (Princeton University).

Во втором раунде оценка пригодности финалистов первого раунда в качестве генераторов случайных чисел проводилось на основе 192-битных и 256-битных ключей. Продолжительность статистических тестов NIST составило несколько месяцев, причем вычисления производились на множестве рабочих станциях “Sun Ultra”. Все данные формировались и обрабатывались в режиме онлайн. В результате второго раунда было показано, что каждый из пяти вышеуказанных алгоритмов формирует абсолютно случайную бинарную последовательность и поэтому может быть использован в качестве генератора псевдослучайных чисел, причем имеется возможность использования ключей размерами 128, 192 и 256 бит.

Голоса на конференции AES2 распределились следующим образом:


  • Rijndael: 86 за, 10 против

  • Serpent: 59 за, 7 против

  • Twofish: 31 за, 21 против

  • RC6: 23 за, 37 против

  • MARS: 13 за, 83 против

Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа. На ней присутствовало 250 участников, многие из которых приехали из-за рубежа. Двухдневная конференция была разделена на восемь сессий, по четыре в день, плюс к тому состоялась неформальная дополнительная сессия, подводившая итоги первого дня. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FPGA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На сессиях второго дня был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael рассказал Винсент Рэймен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

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

Безопасность являлась самым важным фактором при оценке финалистов. В отношении собственно алгоритмов (полных) никаких атак зафиксировано не было. Зафиксированы были только атаки против упрощённых вариантов алгоритмов, когда число раундов было уменьшено или были сделаны упрощения другими способами.

С одной стороны, варианты с уменьшенным числом раундов на самом деле являются другими алгоритмами, и таким образом атаки на них никак не характеризуют безопасность собственно исходных алгоритмов. Алгоритм может быть безопасен при n раундах, даже если он уязвим при n-1 раунде. С другой стороны, обычной практикой в современном криптоанализе являются попытки сконструировать атаки на варианты с уменьшенным числом раундов. С этой точки зрения вполне понятны попытки оценить "резерв безопасности" рассматриваемых кандидатов, основываясь на атаках на варианты с уменьшенным числом раундов.

Одним из возможных критериев резерва безопасности является число, на которое полное число раундов алгоритма превышает наибольшее число раундов, при котором возможна атака. Существует ряд причин, объясняющих, почему не следует полагаться исключительно на подобную метрику для определения силы алгоритма; тем не менее, данная метрика резерва безопасности может быть полезна.


Атаки на варианты с уменьшенным числом раундов

Алгоритм, раунды

Раунды (длина ключа)

Тип атаки

Текст

Байты памяти

Операции

MARS 16 Core (C)

16 Mixing (M)



11C

Amp. Boomerang

265

270

2229

16M, 5C

Meet-in-Middle

8

2236

2232

16M, 5C

Diff. M-i-M

250

2197

2247

6M, 6C

Amp. Boomerang

269

273

2197

RC6 20

14

Stat. Disting.

2118

2112

2122

12

Stat. Disting.

294

242

2119

14 (192,256)

Stat. Disting.

2110

242

2135

14 (192,256)

Stat. Disting.

2108

274

2160

15 (256)

Stat. Disting.

2119

2138

2215

Rijndael

10 (128)


4

Truncated Diff.

29

Small

29

5

Truncated Diff.

211

Small

240

6

Truncated Diff.

232

7*232

272

6

Truncated Diff.

6*232

7*232

244

7 (192)

Truncated Diff.

19*232

7*232

2155

7 (256)

Truncated Diff.

21*232

7*232

2172

7

Truncated Diff.

2128 - 2199

261

2120

8 (256)

Truncated Diff.

2128 - 2199

2101

2204

9 (256)

Related Key

277

NA

2224

Rijndael

12 (192)


7 (192)

Truncated Diff.

232

7*232

2184

7 (256)

Truncated Diff.

232

7*232

2200

Rijndael

14 (256)


7 (192, 256)

Truncated Diff.

232

7*232

2140

Serpent 32

8 (192, 256)

Amp. Boomerang

2113

2119

2179

6 (256)

Meet-in-Middle

512

2246

2247

6

Differential

283

240

290

6

Differential

271

275

2103

6 (192, 256)

Differential

241

245

2163

7 (256)

Differential

2122

2126

2248

8 (192, 256)

Amp. Boomerang

2128

2133

2163

8 (192, 256)

Amp. Boomerang

2110

2115

2175

9 (256)

Amp. Boomerang

2110

2212

2252

Twofish 16

6 (256)

Impossible Diff.

NA

NA

2256

6

Related Key

NA

NA

NA

NA – информация недоступна.
В итоге финалисты продемонстрировали следующие характеристики, относящиеся к безопасности: ни против одного из пяти алгоритмов не существует общих известных атак, поэтому определение уровня безопасности является достаточно приблизительным:


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

  • RC6 показал адекватный резерв безопасности. Однако RC6 критиковали за небольшой резерв безопасности по сравнению с другими финалистами. С другой стороны, все высоко оценили простоту RC6, облегчающую анализ безопасности. RC6 произошел от RC5, который уже достаточно хорошо проанализирован.

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

  • Serpent показал значительный резерв безопасности. Serpent также имеет простую структуру, безопасность которой легко проанализировать.




  • Twofish показал высокий резерв безопасности. Поскольку Twofish использует зависящую от ключа функцию раунда, для него замечания о резерве безопасности могут иметь меньшее значение, чем для других финалистов. Зависимость S-boxes Twofish только от k/2 битов энтропии в случае k-битного ключа позволяет сделать вывод, что Twofish может быть подвегнут divide-and-conquer-атаке, хотя такая атака не найдена. Twofish был подвергнут критике за сложность, которая затрудняет его анализ.

Стандарт AES (Rijndael)


Advanced Encryption Standard (AES) (Rijndael) – симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта шифрования правительством США по результатам конкурса AES. Этот алгоритм хорошо проанализирован и сейчас широко используется, как это было с его предшественником DES, на смену которому он был предназначен. По состоянию на 2009 год AES является одним из самых распространённых алгоритмов симметричного шифрования. Поддержка AES (и только его) введена фирмой Intel в семейство процессоров x86 начиная с Intel Core i7-980X Extreme Edition, а затем в процессорах Sandy Bridge.

Практически все операции Rijndael определяются на уровне байта. Байты можно рассматривать как элементы конечного поля Галуа GF(28). Некоторые операции определены в терминах четырехбайтных слов.


Определения

Block

последовательность бит, из которых состоит input, output, State и Round Key. Также под Block можно понимать последовательность байт

Cipher Key

секретный, криптографический ключ, который используется Key Expansion процедурой, чтобы произвести набор ключей для раундов(Round Keys); может быть представлен как прямоугольный массив байтов, имеющий четыре строки и Nk колонок.

Ciphertext

выходные данные алгоритма шифрования

Key Expansion

процедура используемая для генерации Round Keys из Cipher Key

Round Key

Round Keys получаются из Cipher Key используя процедуру Key Expansion. Они применяются к State при шифровании и расшифровании

State

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

S-box

нелинейная таблица замен, использующаяся в нескольких трансформациях замены байт и в процедуре Key Expansion для взаимнооднозначной замены значения байта. Предварительно рассчитанный S-box можно увидеть ниже.

Nb

число столбцов(32-ух битных слов), составляющих State. Для AES, Nb = 4

Nk

число 32-ух битных слов, составляющих шифроключ. Для AES, Nk = 4,6, или 8

Nr

число раундов, которое является функцией Nk и Nb. Для AES, Nr = 10, 12, 14

Rcon[]

массив, который состоит из битов 32-х разрядного слова и является постоянным для данного раунда. Предварительно рассчитанный Rcon[] можно увидеть ниже.

S-box


Sbox = array{

0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,

0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,

0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,

0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,

0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,

0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,

0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,

0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,

0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73, 0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,

0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,

0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,

0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,

0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,

0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,

0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16

};

Обратный S-box для процедуры InvSubBytes



InvSbox = array{

0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,

0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,

0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,

0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,

0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,

0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,

0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,

0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,

0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,

0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,

0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,

0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,

0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,

0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,

0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,

0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d

};
Rcon[]

Rcon = array(

array(0x00, 0x00, 0x00, 0x00),

array(0x01, 0x00, 0x00, 0x00),

array(0x02, 0x00, 0x00, 0x00),

array(0x04, 0x00, 0x00, 0x00),

array(0x08, 0x00, 0x00, 0x00),

array(0x10, 0x00, 0x00, 0x00),

array(0x20, 0x00, 0x00, 0x00),

array(0x40, 0x00, 0x00, 0x00),

array(0x80, 0x00, 0x00, 0x00),

array(0x1b, 0x00, 0x00, 0x00),

array(0x36, 0x00, 0x00, 0x00)

);
Вспомогательные процедуры


AddRoundKey()

трансформация при шифровании и обратном шифровании, при которой Round Key XOR’ится c State. Длина RoundKey равна размеру State(те, если Nb = 4, то длина RoundKey равна 128 бит или 16 байт)

InvMixColumns()

трансформация при расшифровании которая является обратной по отношению к MixColumns()

InvShiftRows()

трансформация при расшифровании которая является обратной по отношению к ShiftRows()

InvSubBytes()

трансформация при расшифровании которая является обратной по отношению к SubBytes()

MixColumns()

трансформация при шифровании которая берет все столбцы State и смешивает их данные (независимо друг от друга), чтобы получить новые столбцы

RotWord()

функция, использующаяся в процедуре Key Expansion, которая берет 4-х байтное слово и производит над ним циклическую перестановку

ShiftRows()

трансформации при шифровании, которые обрабатывают State, циклически смещая последние три строки State на разные величины

SubBytes()

трансформации при шифровании которые обрабатывают State используя нелинейную таблицу замещения байтов(S-box), применяя её независимо к каждому байту State

SubWord()

функция, используемая в процедуре Key Expansion, которая берет на входе четырёх-байтное слово и применяя S-box к каждому из четырёх байтов выдаёт выходное слово

Шифрование: Для AES длина input (блока входных данных) и State (состояния) постоянна и равна 128 бит, а длина шифроключа K составляет 128, 192, или 256 бит (параметр). При этом исходный алгоритм Rijndael допускает длину ключа и размер блока от 128 до 256 бит с шагом в 32 бита. Для обозначения выбранных длин input, State и Cipher Key в байтах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.


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

Nr

Nb = 4

Nb = 6

Nb = 8

Nk = 4

10

12

14

Nk = 6

12

12

14

Nk = 8

14

14

14

В начале шифрования input копируется в массив State по правилу s[r,c] = in[r+4c] , для 0 r < 4 и 0 c < Nb. После этого к State применяется процедура AddRoundKey() и затем State проходит через процедуру трансформации (раунд) 10, 12, или 14 раз (в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в output по правилу out[r+4c] = s[r,c], для 0 r < 4 и 0 c < Nb.


Отдельные трансформации SubBytes(), ShiftRows(), MixColumns() и AddRoundKey() – обрабатывают State. Массив w[] – содержит key schedule.
Псевдокод для Cipher

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])

begin

byte state[4,Nb]



state = in
AddRoundKey(state, w[0, Nb-1])
for round = 1 step 1 to Nr-1

SubBytes(state)

ShiftRows(state)

MixColumns(state)

AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])

end for
SubBytes(state)

ShiftRows(state)

AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])


out = state

end
Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов используя таблицу замен (S-box). Такая операция обеспечивает нелинейность алгоритма шифрования. Построение S-box состоит из двух шагов. Во-первых, производится взятие обратного числа в поле Галуа GF(28). Во-вторых, к каждому байту b, из которых состоит S-box, применяется следующая операция:


b = bi b(i+4) mod8b(i+5) mod8 b(i+6) mod8 b(i+7) mod8 Ci
где 0i<8, и где bi это i-ый бит b, а Ci — i-ый бит константы c=6316=9910=011000112. Таким образом, обеспечивается защита от атак, основанных на простых алгебраических свойствах.



Рис.14 В процедуре SubBytes, каждый байт в state заменяется соответствующим элементом в фиксированной 8-битной таблице поиска, S; bij = S(aij).
ShiftRows работает со строками State. При этой трансформации строки состояния циклически сдвигаются на r байт по горизонтали, в зависимости от номера строки. Для нулевой строки r = 0, для первой строки r = 1 и т. д. Таким образом каждая колонка выходного состояния после применения процедуры ShiftRows состоит из байтов из каждой колонки начального состояния. Для алгоритма Rijndael паттерн смещения строк для 128- и 192-битных строк одинаков. Однако для блока размером 256 бит отличается от предыдущих тем, что 2, 3, и 4-е строки смещаются на 1, 3, и 4 байта, соответственно.



Рис.15 В процедуре ShiftRows, байты в каждой строке state циклически сдвигаются влево. Размер смещения байтов каждой строки зависит от её номера
Величина сдвига в зависимости от длины блока

Nb

С1

С2

С3

4

1

2

3

6

1

2

3

8

1

3

4

В процедуре MixColumns, четыре байта каждой колонки State смешиваются, используя для этого обратимую линейную трансформацию. MixColumns обрабатывает состояния по колонкам, трактуя каждую из них как полином четвёртой степени. Над этими полиномами производится умножение в GF(28) по модулю x4 + 1 на фиксированный многочлен c(x) = 3x3 + x2 + x + 2. Вместе с ShiftRows, MixColumns вносит диффузию в шифр.





Рис.16 В процедуре MixColumns, каждая колонка состояния перемножается с

фиксированным многочленом c(x).
В процедуре AddRoundKey, RoundKey каждого раунда объединяется со State. Для каждого раунда Roundkey получается из CipherKey, используя процедуру KeyExpansion; каждый RoundKey такого же размера, что и State. Процедура производит побитовый XOR каждого байта State с каждым байтом RoundKey.

Рис.17 В процедуре AddRoundKey, каждый байт состояния объединяется с RoundKey используя операцию XOR ().
Алгоритм обработки ключа состоит из двух процедур:


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

  • Алгоритм выбора раундового ключа (ключа итерации)

AES алгоритм, используя процедуру KeyExpansion() и подавая в неё CipherKey, K, получает ключи для всех раундов. Всего получается Nb*(Nr + 1) слов: изначально для алгоритма требуется набор из Nb слов, и каждому из Nr раундов требуется Nb ключевых набора данных. Полученный массив ключей для раундов обозначается как w[i], 0 i < Nb * (Nr + 1). Алгоритм KeyExpansion() показан в псевдокоде ниже.


Псевдокод для Key Expansion

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)

begin

word temp



i = 0;

while ( i < Nk)

w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])

i = i+1


end while

i = Nk
while ( i < Nb * (Nr+1))

temp = w[i-1]

if (i mod Nk = 0)

temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]

else if (Nk > 6 and i mod Nk = 4)

temp = SubWord(temp)

end if


w[i] = w[i-Nk] xor temp

i = i + 1

end while

end
Функция SubWord() берет четырёхбайтовое входное слово и применяет S-box к каждому из четырёх байтов. То, что получилось, подается на выход. На вход RotWord() подается слово [a0,a1,a2,a3] которое она циклически переставляет и возвращает [a1,a2,a3,a0]. Массив слов, постоянный для данного раунда, Rcon[i], содержит значения [xi-1, 00,00,00], где x = {02}, а xi-1 является степенью x в GF(28) (I начинается с 1).

Первые Nk слов расширенного ключа заполненны Cipher Key. В каждое последующее слово, w[i], кладётся значение полученное при операции XOR w[i-1] и w[i-Nk], те XOR-а предыдущего и на Nk позиций раньше слов. Для слов, позиция которых кратна Nk, перед XOR’ом к w[i-1] применяется трасформация, за которой следует XOR с константой раунда Rcon[i]. Указанная выше трансформация состоит из циклического сдвига байтов в слове(RotWord()), за которой следует процедура SubWord() — то же самое, что и SubBytes(), только входные и выходные данные будут размером в слово.

Важно заметить, что процедура KeyExpansion() для 256 битного Cipher Key немного отличается от тех, которые применяются для 128 и 192 битных шифроключей. Если Nk = 8 и i-4 кратно Nk, то SubWord() применяется к w[i-1] до XOR-а.

Ниже приведён псевдокод расшифрования по алгоритму AES.

Псевдокод для Inverse Cipher

InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])

begin

byte state[4,Nb]



state = in
AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
for round = Nr-1 step -1 downto 1

InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])

InvMixColumns(state)

end for
InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])


out = state

end
На каждой итерации i раундовый ключ для операции AddRoundKey выбирается из массива w[i], начиная с элемента w[Nb*i] до w[Nb*(i+1)].


Достоинства алгоритма Rijndael, относящиеся к реализации:


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

  • Rijndael можно реализовать в виде кода, используя небольшое ОЗУ (RAM) и имея небольшое число циклов. Выполнена оптимизация размера ROM и скорости выполнения.

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

  • Алгоритм шифрования не использует арифметические операции, поэтому тип архитектуры процессора практически не имеет значения.

Преимущества простоты разработки:



  • Алгоритм шифрования полностью "самоподдерживаемый". Он не использует других криптографических компонентов, S-boxes, взятых из других, хорошо известных алгоритмов, битов, полученных из специальных таблиц и тому подобных уловок.

  • Алгоритм не основывает свою безопасность или часть ее на неясностях или плохо понимаемых итерациях арифметических операций.

  • Компактная разработка алгоритма не дает возможности спрятать люки2.

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

Возможности расширения:



  • Разработка позволяет специфицировать варианты длины блока и длины ключа в диапазоне от 128 до 256 бит с шагом в 32 бита.

  • Хотя число раундов Rijndael зафиксировано в данной спецификации, в случае возникновения проблем с безопасностью он может модифицироваться и иметь число раундов в качестве параметра.



Достарыңызбен бөлісу:
1   ...   7   8   9   10   11   12   13   14   ...   44


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет