Особенности аппаратной реализации алгоритма шифрования Стандарт AES, принятый NIST в 2001 году Rijndael 3. Аппаратная реализация структурных блоков 1. - презентация

1 Особенности аппаратной реализации алгоритма шифрования Стандарт AES, принятый NIST в 2001 году Rijndael 3. Аппаратная реализация структурных блоков 1. Описание алгоритма 2. Типовые схемные решения аппаратной реализации 4. Проблемы, возникающие при аппаратной реализации

2 1. Описание алгоритма Rijndael Шифрование с секретным ключом 2

3 3 1. Описание алгоритма Rijndael Состояние и ключ СостояниеКлюч всегда = 4 * В AES Nb всегда = 4 байта Rijndael допускает длину 128, 192 и 256 бит Nk = 4 Может быть длиной 128, 192 и 256 бит Nb = 6 байт *

4 4 Общая структура алгоритма 1. Описание алгоритма Rijndael NrNb = 4Nb = 6Nb = 8 Nk = Nk = Nk = 814 Зависимость количества раундов Nr от длины массивов состояния Nb и ключа Nk

5 5 Обычный и заключительный раунды 1. Описание алгоритма Rijndael

6 6 Преобразование SybBytes 1. Описание алгоритма Rijndael Общая схема применения преобразования SubBytes к состоянию 1. Нахождение обратного значения по отношению к операции умножения в поле Галуа GF(2 8 ) для текущего байта состояния 2. Вычисление афинного преобразования В обратной операции, InvSubBytes, сначала над состоянием выполняется обратное афинное преобразование, а затем находится обратное по умножению значение в GF(2 8 )

7 7 Преобразование ShiftRows 1. Описание алгоритма Rijndael Структура преобразования ShiftRows Зависимость величины сдвигов от длины состояния Nb

8 8 Преобразование MixColumns 1. Описание алгоритма Rijndael Структура преобразования MixColumns Математическое описание преобразования MixColumns c(x ) = 03x x x + 02 Каждый столбец состояния представляется в виде полинома с коэффициентами в поле Галуа GF(2 8 ): a(x ) = a 3 x 3 + a 2 x 2 + a 1 x + a 0 который умножается по модулю M(x) = x на полином:

9 9 Преобразование AddRoundKey 1. Описание алгоритма Rijndael Структура преобразования AddRoundKey текущее состояниеключ текущего раундасостояние-результат Обратное преобразование, InvAddRoundKey, полностью идентично прямому.

10 10 1. Описание алгоритма Rijndael Механизм расширения ключа В каждом раунде используется свой уникальный ключ, сгенерированный на основе главного. Такие ключи называются раундовыми (цикловыми).

11 11 2. Типовые схемные решения аппаратной реализации Основные типы схем

12 12 2. Типовые схемные решения аппаратной реализации Схема, предложенная Стефаном Мангардом, Манфредом Айнером и Сандрой Доминикус (Гразский Технологический Университет, Австрия) Представленная схема является в высшей степени регулярной и масштабируемой. Структурные элементы: 1. Модуль данных. 2. Модуль расширения ключей. 3. Модуль связывания закодированных и незакодированных блоков. (CBC) 4. Интерфейсный модуль.

13 13 2. Типовые схемные решения аппаратной реализации Вариант 2 Схема предложена Намингом Ю и Говардом Хейсом из Electrical and Computer Engineering Memorial University of Newfoundland Реализация одного универсального раунда

14 14 2. Типовые схемные решения аппаратной реализации Вариант 3 Особенность реализации в том, что каждый раунд реализован отдельно, в результате чего получается конвейерная структура. (Pipeline architecture) Структура одного раунда Этот вариант реализации представлен Алирезой Ходжат и Ингрид Вербауведе, факультет электрического проектирования Калифорнийского Университета, Лос-Анджелес

15 15 3. Аппаратная реализация структурных блоков Блок S-Box Вариант, предложенный в стандарте AES В стандарте AES представлены следующие таблицы, которые содержат рассчитанные заранее значения функций S-Box. Их предлагается реализовать в виде выборки по таблице из блока памяти ПЗУ (ROM Table Lookup) Этот способ является наиболее простым, но ресурсозатратным и не подходящим для быстрых реализаций.

16 16 3. Аппаратная реализация структурных блоков Блок S-Box Вариант, предложенный Намингом Ю и Говардом Хейсом из Electrical and Computer Engineering Memorial University of Newfoundland Представленная реализация отличается от представленных ранее. Дж. Фуллер и В. Миллан, исследуя локальную структуру расстояний Хэмминга между булевыми функциями, использовали новый метод для нахождения эквивалентности между 8 булевыми функциями, используемыми блоками S-Box. Выходная булева функция блока S-Box может быть представлена в виде: b j (x) = b i (D ij x) c j где: D двоичная матрица, с двоичная константа, а b i известная булева функция

17 17 3. Аппаратная реализация структурных блоков Блок S-Box Вариант, предложенный Эдвином Муи из Texco Enterprise Ptd. Схема универсального блока S-Box Схема реализует алгоритм преобразований, описанный авторами Rijndael. Реализация основана на работах Винсента Рэймена Efficient Implementation of the Rijndael S-Box и Акаши Сато ( с соавт.) A Compact Rijndael Hardware Architecture with S-Box Optimization Основная сложность данного метода в реализации нахождения обратного значения текущего байта состояния относительно операции умножения в поле Галуа GF(2 8 ). Поскольку эта операция очень сложна, прибегли к разложению полинома в GF(2 8 ) к полиному в GF(2 4 ). Для таких полиномов существует более простая формула:

18 18 3. Аппаратная реализация структурных блоков Блок S-Box Вариант, предложенный Эдвином Муи из Texco Enterprise Ptd. Схема нахождения мультипликативного инверсного изоморфное преобразование в комплексном поле возведение в квадрат в поле GF(2 4 ) умножение на константу в поле GF(2 4 ) сложение в поле GF(2 4 ) обратное изоморфное преобразование в комплексном поле мультипликативная инверсия в поле GF(2 4 ) умножение в поле GF(2 4 )

19 19 3. Аппаратная реализация структурных блоков Блок S-Box Реализация 3-го варианта

20 20 3. Аппаратная реализация структурных блоков Схема модуля расширения ключей Схема позволяет хранить только текущий цикловой ключ, обеспечивая вычисление нового циклового ключа как в прямом (RoundKey i+1 ), так и в обратном порядке (RoundKey i-1 ).

21 21 3. Аппаратная реализация структурных блоков Схема модуля расширения ключей Вариант, предложенный Намингом Ю и Говардом Хейсом из Electrical and Computer Engineering Memorial University of Newfoundland

22 22 3. Аппаратная реализация структурных блоков Схема модуля расширения ключей Физическая структура блока с указанием уровней конвееризации Схема реализации модуля расширения ключа Этот вариант реализации представлен Алирезой Ходжат и Ингрид Вербауведе, факультет электрического проектирования Калифорнийского Университета, Лос-Анджелес

23 23 3. Аппаратная реализация структурных блоков Преобразование MixColumns Один из возможных способов реализации преобразования MixColumns

24 24 4. Проблемы, возникающие при аппаратной реализации Общие проблемы и сложности 1)минимизация места, занимаемого на кристалле 2)увеличение быстродействия 3)защита от аппаратно-направленных атак (атака по задержкам, атака по анализу энергопотребления) 4)повышение функциональности 5)выбор более долговечной аппаратной базы для реализации

25 25 4. Проблемы, возникающие при аппаратной реализации Отношение количества эквивалентных ячеек и времени задержки для вариантов реализации представленных Алирезой Ходжат и Ингрид Вербауведе, факультет электрического проектирования Калифорнийского Университета, Лос-Анджелес Блок S-Box

26 26 4. Проблемы, возникающие при аппаратной реализации Схема расширения ключа

27 27 4. Проблемы, возникающие при аппаратной реализации Проблема масштабируемости NrNb = 4Nb = 6Nb = 8 Nk = Nk = Nk = 814 Зависимость количества раундов Nr от длины массивов состояния Nb и ключа Nk Зависимость величины сдвигов от длины состояния Nb Nr = f(Nb, Nk) ? C1, C2, C3 = f(Nb) ?