Алгоритм Rijndael Предварительные математические понятия
Скачать 151.8 Kb.
|
Алгоритм RijndaelПредварительные математические понятияПрактически все операции Rijndael определяются на уровне байта. Байты можно рассматривать как элементы конечного поля GF (28). Некоторые операции определены в терминах четырехбайтных слов. Введем основные математические понятия, необходимые для обсуждения алгоритма. Поле GF(28)Элементы конечного поля могут быть представлены несколькими различными способами. Для любой степени простого числа существует единственное конечное поле, поэтому все представления GF (28) являются изоморфными. Несмотря на подобную эквивалентность, представление влияет на сложность реализации. Выберем классическое полиномиальное представление. Байт b, состоящий из битов b7, b6, b5, b4, b3, b2, b1, b0, представляется в виде полинома с коэффициентами из {0, 1}: b7х7 + b6х6 + b5х5 + b4х4 + b3х3 + b2х2 + b1х1 + b0 Пример: байт с шестнадцатеричным значением '57' (двоичное 01010111) соответствует полиному х6 + х4 + х2 + х + 1 Сложение В полиномиальном представлении сумма двух элементов является полиномом с коэффициентами, которые равны сумме по модулю 2 (т.е. 1 + 1 = 0) коэффициентов слагаемых. Пример: '57' + '83' = 'DA' или в полиномиальной нотации: (х6 + х4 + х2 + х + 1) + (х7 + х + 1) = х7 + х6 + х4 + х2 В бинарной нотации мы имеем: 01010111 + 10000011 = 11011010. Очевидно, что сложение соответствует простому XOR (обозначается как  ) на уровне байта.Выполнены все необходимые условия Абелевой группы: операция сложения (каждой паре элементов сопоставляется третий элемент группы, называемый их суммой), ассоциативность, нулевой элемент ('00'), обратный элемент (относительно операции сложения) и коммутативность. Умножение В полиномиальном представлении умножение в GF (28) соответствует умножению полиномов по модулю неприводимого двоичного полинома степени 8. Полином является неприводимым, если он не имеет делителей, кроме 1 и самого себя. Для Rijndael такой полином называется m(x) и определяется следующим образом: m(x) = x8 + x4 + x3 + x + 1 или '11B' в шестнадцатеричном представлении. Пример: '57' • '83' = 'C1' Или
(x8 + x4 + x3 + х + 1) (x5 + x3) + x7 + x6 + 1 = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 +1 Следовательно, x13 + x11 + x9 + x8 + x6 + x5 + x4 + x8 + 1 mod (x8 + x4 + x3 + х + 1) = x7 + x6 + 1 Ясно, что результат является двоичным полиномом не выше 8 степени. В отличие от сложения, простой операции умножения на уровне байтов не существует. Умножение, определенное выше, является ассоциативным, и существует единичный элемент ('01'). Для любого двоичного полинома b(x) не выше 8-й степени можно использовать расширенный алгоритм Евклида для вычисления полиномов a(x) и c(x) таких, что b(x) a(x) + m(x) c(x) = 1 Следовательно, a(x) • b(x) mod m(x) = 1 или b-1(x) = a(x) mod m(x) Более того, можно показать, что a(x) • (b(x) + c(x)) = a(x) • b(x) + a(x) • c(x) Из всего этого следует, что множество из 256 возможных значений байта образует конечное поле GF (28) c XOR в качестве сложения и умножением, определенным выше. Умножение на х Если умножить b(x) на полином х, мы будем иметь: b7x8 + b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x x • b(x) получается понижением предыдущего результата по модулю m(x). Если b7 = 0, то данное понижение является тождественной операцией. Если b7 = 1, m(x) следует вычесть (т.е. XORed). Из этого следует, что умножение на х может быть реализовано на уровне байта как левый сдвиг и последующий побитовый XOR c '1B'. Данная операция обозначается как b = xtime (a). ^ Полиномы могут быть определены с коэффициентами из GF(28). В этом случае четырехбайтный вектор соответствует полиному степени 4. Полиномы могут быть сложены простым сложением соответствующих коэффициентов. Как сложение в GF(28) является побитовым XOR, так и сложение двух векторов является простым побитовым XOR. Умножение представляет собой более сложное действие. Предположим, что мы имеем два полинома в GF(28). a(x) = a3x3 + a2x2 + a1x + a0 b(x) = b3x3 + b2x2 + b1x + b0 c(x) = a(x) b(x) определяется следующим образом: с(x) = с6x6 + с5x5 + с4x4 + с3x3 + с2x2 + с1x + с0 с0 = a0 • b0 с1 = a1 • b0 a0 • b1с2 = a2 • b0 a1 • b1 a0 • b2с3 = a3 • b0 a2 • b1 a1 • b2 a0 • b3с4 = a3 • b1 a2 • b2 a1 • b3с5 = a3 • b2 a2 • b3с6 = a3 • b3 Ясно, что в таком виде с(х) не может быть представлен четырехбайтным вектором. Понижая с(х) по модулю полинома 4-й степени, результат может быть полиномом степени ниже 4. В Rijndael это сделано с помощью полинома M(x) = x4 + 1 так как xj mod (x4 + 1) = xj mod 4 Модуль, получаемый из а(х) и b(x), обозначаемый d(x) = a(x)  b(x), получается следующим образом:d0 = a0 • b0 a3 • b1 a2 • b2 a1 • b3d1 = a1 • b0 a0 • b1 a3 • b2 a2 • b3d2 = a2 • b0 a1 • b1 a0 • b2 a3 • b3d3 = a3 • b0 a2 • b1 a1 • b2 a0 • b3Операция, состоящая из умножения фиксированного полинома а(х), может быть записана как умножение матрицы, где матрица является циклической. Мы имеем  Замечание: х4 + 1 не является несократимым полиномом в GF (28), следовательно, умножение на фиксированный полином необязательно обратимо. В алгоритме Rijndael выбран фиксированный полином, который имеет обратный. Умножение на х При умножении b(x) на полином х будем иметь: b3x4 + b2x3 + b1x2 + b0x x b(x) получается понижением предыдущего результата по модулю 1 + х4.Это дает b2x3 + b1x2 + b0x + b3 Умножение на х эквивалентно умножению на матрицу, как описано выше со всеми ai = '00' за исключением а1 = '01'. Имеем:  Следовательно, умножение на х соответствует циклическому сдвигу байтов внутри вектора. ^ При разработке алгоритма учитывались следующие три критерия:
В большинстве алгоритмов шифрования преобразование каждого раунда имеет структуру сети Фейштеля . В этом случае обычно часть битов в каждом промежуточном состоянии просто перемещается без изменения в другую половину. Преобразование раунда алгоритма Rijndael не имеет структуру сети Фейштеля. Вместо этого преобразование каждого раунда состоит из четырех различных преобразований, называемых слоями. Каждый слой разрабатывался с учетом противодействия линейному и дифференциальному криптоанализу. В основу каждого слоя положена своя собственная функция:
Перед первым раундом применяется дополнительное забеливание с использованием ключа. Причина этого состоит в следующем. Любой слой после последнего или до первого добавления ключа может быть просто снят без знания ключа и тем самым не добавляет безопасности в алгоритм (например, начальная и конечная перестановки в DES). Начальное или конечное добавление ключа применяется также в некоторых других алгоритмах, например IDEA, SAFER и Blowfish. Для того чтобы сделать структуру алгоритма более простой, слой линейного перемешивания последнего раунда отличается от слоя перемешивания других раундов. Можно показать, что это в любом случае не повышает и не понижает безопасность. Это аналогично отсутствию операции swap в последнем раунде DES. ^ Rijndael является блочным алгоритмом шифрования с переменной длиной блока и переменной длиной ключа. Длина блока и длина ключа могут быть независимо установлены в 128, 192 или 256 бит. ^ Различные преобразования выполняются над промежуточным результатом, называемым состоянием. Состояние можно рассматривать как двумерный массив байтов. Этот массив имеет четыре строки и различное число столбцов, обозначаемое как Nb, равное длине блока, деленной на 32. Ключ также можно рассматривать как двумерный массив с четырьмя строками. Число столбцов ключа шифрования, обозначаемое как Nk, равно длине ключа, деленной на 32. В некоторых случаях эти блоки также рассматриваются как одномерные массивы четырехбайтных векторов, где каждый вектор состоит из соответствующего столбца. Такие массивы имеют длину 4, 6 или 8 соответственно, и индексы в диапазонах 0 … 3, 0 … 5 или 0 … 7. Четырехбайтные вектора иногда мы будем называть словами. Если необходимо указать четыре отдельных байта в четырехбайтном векторе, будет использоваться нотация (a, b, c, d), где a, b, c и d являются байтами в позициях 0, 1, 2 и 3, соответственно, в рассматриваемом столбце, векторе или слове.  Рис. 6.1. Пример состояния (с Nb = 6) и ключа шифрования (с Nk = 4) Входы и выходы Rijndael считаются одномерными массивами из 8 байтов, пронумерованными от 0 до 4* Nb - 1. Следовательно, эти блоки имеют длину 16, 24 или 32 байта, и массив индексируется в диапазонах 0 … 15, 0 … 23 или 0 … 31. Ключ считается одномерным массивом 8-битных байтов, пронумерованных от 0 до 4* Nk - 1. Следовательно, эти блоки имеют длину 16, 24 или 32 байта, и массив индексируется в диапазонах 0 … 15, 0 … 23 или 0 … 31. Входные байты алгоритма отображаются в байты состояния в следующем порядке: А0,0, А1,0, А2,0, А3,0, А0,1, А1,1, А2,1, А3,1, … Байты ключа шифрования отображаются в массив в следующем порядке: K0,0, K1,0, K2,0, K3,0, K0,1, K1,1, K2,1, K3,1, … После выполнения операции шифрования выход алгоритма получается из байтов состояния аналогичным образом. Следовательно, если одноразмерный индекс байта в блоке есть n, и двухмерный индекс есть (i,j), то мы имеем: I = n mod 4 J =  n / 4  N = i + 4*j Более того, индекс i является также номером байта в четырехбайтном векторе или слове, j является индексом вектора или слова во вложенном блоке. Число раундов обозначается Nr и зависит от значений Nb и Nk, что показано в следующей таблице.
Преобразование раунда состоит из четырех различных преобразований. В нотации на псевдо С это можно записать следующим образом: Round (State, RoundKey) { ByteSub (State); ShiftRow (State); MixColumn (State); AddRoundKey (State, RoundKey); } Заключительный раунд алгоритма немного отличается и выглядит следующим образом: FinalRound (State, RoundKey) { ByteSub (State); ShiftRow (State); AddRoundKey (State, RoundKey); } Как мы видим, заключительный раунд эквивалентен остальным, за исключением того, что отсутствует слой MixColumn. ^ Преобразование ByteSub является нелинейной байтовой подстановкой, выполняющейся для каждого байта состояния независимо. Таблица подстановки является обратимой и сконструирована в виде композиции двух преобразований:
 Применение описанного S-box ко всем байтам состояния обозначается как ByteSub (State) На рисунке 6.2 показан результат применения преобразования ByteSub к State.  Рис. 6.2. Применение ByteSub для каждого байта в State Инверсия ByteSub есть применение байтовой подстановки в соответствии с инверсной таблицей. Это получается инверсией афинного отображения и мультипликативной инверсией в GF (28). ^ В ShiftRow строки состояния циклически сдвигаются на различные значения. Нулевая строка не сдвигается. Строка 1 сдвигается на С1 байтов, строка 2 на С2 байтов, строка 3 на С3 байтов. Величины С1, С2 и С3 зависят от Nb. Значения приведены в следующей таблице.
Операция сдвига строк на указанные значения обозначается как ShiftRow (State) Инверсией для ShiftRow является циклический сдвиг трех нижних строк соответственно на Nb - С1, Nb - С2 и Nb - С3 байт, чтобы байт в позиции j в строке i перемещался в позицию (j + Nb - Ci) mod Nb. ^ В MixColumn столбцы состояния рассматриваются как полиномы в GF (28) и умножаются по модулю х4 + 1 на фиксированный полином: c(x) = '03' x3 + '01' x2 + '01' x + '02' Данный полином является взаимнопростым с х4 + 1 и, следовательно, инвертируем. Как было описано выше, это может быть записано в виде умножения матрицы. Пусть b(x) = c(x) a(x) Применение данной операции ко всем столбцам состояния обозначается как MixColumn (State) Инверсия MixColumn является аналогичным MixColumn. Каждый столбец преобразуется умножением его на полином d(x), определяемый следующим образом: ('03' x3 + '01' x2 + '01' x + '02') d(x) = '01'В результате получаем d(x) = '0B' x3 + '0D' x2 + '09' x + '0E' ^ Выполняется операция побитового XOR ключа раунда с текущим состоянием. Длина ключа раунда равна длине блока Nb. Данное преобразование обозначается как AddRoundKey (State, RoundKey) AddRoundKey является инверсией самого себя. ^ Ключи раунда получаются из ключа шифрования с помощью преобразования, состоящего из двух компонентов: расширение ключа и выбор ключа раунда. Основной принцип состоит в следующем:
^ Expanded Key является линейным массивом четырехбайтных слов и обозначается как W [Nb * (Nr + 1)]. Первые Nk слов состоят из ключа шифрования. Остальные слова определяются рекурсивно. Функция расширения ключа зависит от значения Nk: существует версия функции для Nk, равным или меньшим 6, и версия для Nk больше 6. Для Nk  6 мы имеем:KeyExpansion (byte Key [4*Nk] word W[Nb * (Nr + 1)]) { for (i = 0; i < Nk; i++) W[i] =(Key [4*i], Key [4*i+1], Key [4*i+2], Key [4*i+3]); for (i = Nk; i < Nb * (Nr + 1); i++) { temp = W [i - 1]; if (i % Nk == 0) temp = SubByte (RotByte (temp)) ^ Rcon [i / Nk]; W [i] = W [i- Nk] ^ temp; } } В данном случае SubByte (W) является функцией, которая возвращает четырехбайтное слово, в котором каждый байт является результатом применения S-box Rijndael к байту в соответствующей позиции во входном слове. Функция RotByte (W) возвращает слово, в котором байты циклически переставлены таким образом, что для входного слова (a, b, c, d) создается выходное слово (b, c, d, a). Можно заметить, что первые Nk слов заполняются ключом шифрования. Каждое следующее слово W[i] равно XOR предыдущего слова W[i-1] и позиций слова Nk до W[i - Nk]. Для слов в позициях, которые кратны Nk, сначала применяется преобразование XOR к W[i-1] и константой раунда. Данное преобразование состоит из циклического сдвига байтов в слове RotByte, за которым следут применение табличной подстановки для всех четырех байтов в слове (SubByte). Для Nk > 6 мы имеем: KeyExpansion (byte Key [4*Nk] word W [Nb* (Nr+1)]) { for (i=0; i < Nk; i++) W[i]= (key [4*i], key [4*i+1], key [4*i+2], key [4*i+3]); for (i = Nk; i < Nb * (Nr + 1); i++) { temp = W [i-1]; if (i % Nk == 0) temp = SubByte (RotByte (temp)) ^ Rcon [i / Nk]; else if (i % Nk == 4) temp = SubByte (temp); W[i] = W[i - Nk] ^ temp; } } Отличие в схеме для Nk 6 состоит в том, что для i-4 кратных Nk, SubByte применяется для W[i-1] перед XOR.Константы раунда не зависят от Nk и определяются следующим образом: Rcon [i] = (RC [i], '00', '00', '00') RC [i] являются элементами в GF (28) со значением x(i-1) таким, что: RC [1] = 1 (т.е. '01') RC [i] = x (т.е. '02') • (RC [i-1]) = x(i-1) Выбор ключа раунда Ключ раунда i получается из слов буфера ключа раунда W [Nb * i] до W [Nb * (i+1)]. ^ Алгоритм шифрования Rijndael состоит из
В С-подобном представлении это выглядит так: Rijndael (State, CipherKey) { KeyExpansion (CipherKey, ExpandedKey); AddRoundKey (State, ExpandedKey); for (i=1; i < Nr; i++) Round (State, ExpandedKey + Nb*i); FinalRound (State, ExpandedKey + Nb*Nr) } Расширение ключа может быть выполнено заранее, и Rijndael может быть специфицирован в терминах расширенного ключа. Rijndael (State, ExpandedKey) { AddRoundKey (State, ExpandedKey); for (i=1; i < Nr; i++) Round (State, ExpandedKey + Nb*i); FinalRound (State, ExpandedKey + Nb*Nr) } Замечание: расширенный ключ всегда получается из ключа шифрования и никогда не специфицируется непосредственно. Тем не менее, на выбор самого ключа шифрования ограничений не существует. ^ Преимущества, относящиеся к аспектам реализации:
Простота разработки:
Переменная длина блока:
Расширения:
Расширения^Обработка ключа поддерживает длину ключа, которая была бы кратна 4 байтам. Единственным параметром, который необходим для определения другой длины ключа, отличной от 128, 192 или 256 бит, является число раундов алгоритма. Структура алгоритма допускает произвольную длину блока, кратную 4 байтам, с минимумом в 16 байтов. Добавление ключа и ByteSub и MixColumn преобразования не зависят от длины блока. Единственным преобразованием, которое зависит от длины блока, является ShiftRow. Для каждой длины блока должен быть определен специальный массив С1, С2, С3. Можно определить расширение Rijndael, которое также поддерживает длины блока и ключа между 128 и 256 битами с приращением в 32 бита. Число раундов определяется так: Nr = max (Nk, Nb) + 6 Это расширяет правило для количества раундов для альтернативных длин блока и ключа. Дополнительные значения С1, С2 и С3 определены в следующей таблице.
Обсудим функции, отличные от шифрования, которые могут выполняться алгоритмом Rijndael. МАСRijndael может применяться в качестве алгоритма МАС. Для этого следует использовать блочный алгоритм в режиме СВС-МАС. Хэш-функцияRijndael может использоваться в качестве итерационной хэш-функции. При этом Rijndael применяется в качестве функции раунда. Существует одна возможная реализация. Рекомендуется использовать длину блока и ключа, равной 256 битам. Блок сообщения подается на вход в качестве ключа шифрования. Другим входом является переменная, выход алгоритма XORed с данной переменной, и полученное значение является новым значением этой переменной. ^ Существует много способов, с помощью которых Rijndael можно использовать в качестве генератора псевдослучайных чисел. Рассмотрим один из них, в котором применяются длина блока и длина ключа 256 бит. Существует три операции: Reset:
Seeding (и reseeding):
Генератор псевдослучайного числа:
RC6 является полностью параметризуемым семейством алгоритмов шифрования. RC6 правильнее указывать как RC6-w/r/b, где w - длина слова в битах, r - число раундов, b - длина ключа. Обычно используются значения w = 32 и r = 20.  Рис. 6.3. Алгоритм RC6 Алгоритм является сетью Фейштеля с 4 ветвями смешанного типа: два четных подблока используются для одновременного изменения содержимого двух нечетных подблоков. Затем производится обычный для сети Фейштеля сдвиг на одно слово, что меняет четные и нечетные подблоки местами.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
Похожие:
 | ... | | Общая запись оптимизационной эмм (задача оптимального программирования). Основные элементы и понятия |
| Математические методы и модели в экономике. Основные понятия и общая классификация. Иллюстрация на конкретных примерах | | У 84 Месть за победу — новая война. — М.: Изд-во Алгоритм, Изд-во Эксмо, 2005. — 544 с |
| Векленко В. И. Экономико-математические методы и модели: Курс лекций. Курск: Изд-во Курской гос с. Х акад., 2006. с | | Генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым или сложнорешаемым... |
| «Математические начала натуральной философии», в котором он изложил закон всемирного тяготения и три закона механики, ставшие основой... | | Математические методы принятия решений: Учеб пособие. Тамбов: Изд-во Тамб гос тех ун-та, 2004. 124с. Isbn 5-8265-0259-2 |
| ... | | ... |