Порядок приложения функций SubBytes() и ShiftRows() не играет роли. То же са мое верно и для операций InvSubBytes() и InvShiftRows(). Это происходит потому, что функции SubBytes() и InvSubBytes() работают с байтами , а операции ShiftRows() и InvShiftRows() сдвигают целые байты, не затрагивая их значений.

Операция MixColumns() является линейной относительно входных данных, что означает InvMixColumns(State XOR RoundKey) = = InvMixColumns(State) XOR InvMixColumns(RoundKey)

Эти свойства функций алгоритма шифрования позволяют изменить порядок применения функций InvSubBytes() и InvShiftRows(). Функции AddRounKey() и InvMixCol-umns() также могут быть применены в обратном порядке, но при условии, что столбцы (32-битные слова) развёрнутого ключа расшифрования предварительно пропущены через функцию InvMixColumns().

Таким образом, можно реализовать более эффективный способ расшифрования с тем же порядком приложения функций как и в алгоритме зашифрования.

Алгоритм выработки ключей (Key Schedule)

Введем следующие обозначения: Rconf] - массив 32-битных раундовых констант;

RotWord() -- операция циклической перестановки входного 4-байтного слова в выходное по следующему правилу [а0, ai, а2, а3 ] --> [ах, а2, а3, а0 ];

SubWord() - операция замены в 4-байтном слове с помощью S-Box каждого байта;

- операция исключающего или XOR.

Рисунок 1.5 «Операция планирования (расширения) ключа реализованная на псевдокоде»

Раундовые ключи получаются из ключа шифрования посредством алгоритма выработки ключей. Он содержит два компонента: расширение ключа (Key Expansion) и выбор раундового ключа (Round Key Selection). Основополагающие принципы алгоритма выглядят следующим образом:

общее число битов раундовых ключей равно длине блока, умноженной на число раундов, плюс 1;

ключ шифрования расширяется в расширенный ключ (Expanded Key);

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

Расширение (планирование) ключа

Расширенный ключ (Рисунок 3.6) представляет собой линейный массив w[i] состоящий из A(Nr +1) 4-байтовых слов, i = О,4(Nr +1).

Рисунок 1.6 «Процедуры расширения и выборки раундового ключа для Nk = 4».

Светло-серым цветом выделены слова расширенного ключа, которые формируются без использования функций SubWord() и RotWord().

Темно-серым цветом ,выделены слова расширенного ключа, при вычислении которых используются преобразования SubWord() и RotWord())»

Первые Nk слов содержат ключ шифрования. Каждое последующее слово w[i] получается посредством XOR предыдущего слова w[i-1] и слова на Nk позиций ранее:

w[i- Nk]: w[i]= w[i-1] w[i- Nk].

Для слов, позиция которых кратна Nk, перед XOR применяется преобразование к w[i-1], а затем еще прибавляется раундовая константа Rcon[i] . Преобразование реализуется с помощью двух дополнительных функций: RotWord() и SubWord().

Значение Rcon[j] равно 2j-1 . Значение w[i] в этом случае определяется выражением: w[i] = SubWord(RotWord(w[i-1]) Rcon[i/Nk] M[i-Nk].

Выбор раундового ключа i-тый раундовый ключ выбирается из слов массива расширенного ключа в промежутке от W[Nb * i] до W[Nb * (i+1)].

Для функции зашифрования расширенный ключ генерируется алгоритмом Рисунок 1.5. Для функции обратного расшифрования используется этот же ключ, но в обратной последовательности начиная с последнего раундового подключа зашифрования.

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

Рисунок 1.7 «Дополнительное преобразование расширенного ключа для функции прямого расшифрования»

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

Раундовое преобразование состоит из последовательного применения к массиву State ряда трансформаций.. Сейчас обсудим детали его реализации.

Нелинейная замена байтов массива состояния посредством трансформации SubBytesQ имеет вид:

Многократное вычисление в процессе зашифрования данного выражения оказывало бы неоправданную вычислительную нагрузку на исполняющую систему, поэтому для практической реализации наиболее приемлемым решением является использование предварительно вычисленной таблицы замены S-Box. Логика работы S-Box при преобразовании байта {ху} отражена в шестнадцатеричном виде на Рисунке 1.8:

Рисунок 1.8 «Таблица S-Box замены байт»

Ее использование сводит операцию SubBytesQ к простейшей выборке байта из массива л(f) = Sbox[f].

В функциях расшифрования применяется операция обратная InvSub-Bytes().

Она реализуется так же просто, как и предыдущая посредством инверсной таблицы S-Box - л-1(f) = InvSbox[f]., ее логика работы при преобразовании байта {ху} отражена в шестнадцатеричном виде на Рисунке 1.9

Рисунок 1.9 «Таблица S-Box инверсной замены байт»

Рисунок 1.10 иллюстрирует применение преобразования замены байт к состоянию в функциях зашифрования и расшифрования:

Рисунок 1.10 «Преобразование состояния посредством таблицы замены S-Box»

В преобразовании сдвига строк (ShiftRows) последние 3 строки состояния циклически сдвигаются ВЛЕВО на различное число байтов. Строка 1 сдвигается на С1 байт, строка 2 - на С2 байт, и строка 3 - на Сз байт. Значения сдвигов С1, С2 и С3 в Rijndael зависят от длины блока Nb .

Рисунок 1.11 «Преобразование сдвига строк в функции зашифрования»

В преобразовании обратного сдвига строк InvShiftRows последние 3 строки состояния циклически сдвигаются ВПРАВО на различное число байтов. Строка 1 сдвигается на С1байт, строка 2 - на С2 байт, и строка 3 - на С3 байт.

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

В преобразовании перемешивания столбцов (MixColumns) столбцы состояния рассматриваются как многочлены над GF(2S) и подвергаются преобразованию /j,(g) = с * gmod(Y4 +1), где с = (Х,1,1,Х +1), т.е умножаются по модулю х4 + 1 на многочлен с(х), выглядящий, как: с(х) = {03}х3 + {01}х2 + {01}х + {02}.

Это преобразование может быть представлено в матричном виде следующим образом:

Применение этой операции ко всем четырем столбцам состояния обозначается, как MixColumns(State). Рисунок 1.13 демонстрирует применение преобразования MixColumnsQ к столбцу состояния.

Рисунок 1.13. «Операция перемешивания действует на столбцы состояния»

В обратном преобразовании InvMixColumnsQ столбцы состояния рассматриваются как многочлены над GF(2S), но, естественно, подвергаются обратному преобразованию v(g) = ^-1(g) = d-gmod(Y4+l), где d = (Х3+Х2 + Х,Х3+l,X3+X2+l,X3+X + 1), т.е умножаются по модулю х4 + 1 на многочлен d(x), выглядящий следующим образом: d(x) = {Ob}x3 + {0d}x2 + {09}х + {0e}.

Это может быть представлено в матричном виде следующим образом:

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

В данной операции раундовый ключ добавляется к состоянию посредством поразрядного XOR. Длина ключа (в 32-разрядных словах) равна длине блока Nb .

Рисунок 1.14 иллюстрирует действие данной операции на состояние. Это преобразование обозначается как AddRoundKey(State, RoundKey).

Основные особенности AES

В заключении сформулируем основные особенности AES:

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

байт-ориентированная структура, удобная для реализация на 8-разрядных микро контроллерах;

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

2. Алгоритм шифрования MARS

Коропорация IBM, создавшая DES, представила алгоритм MARS, обладающий как хорошей криптостойкостью так и высокой скоростью шифрования.

Процесс шифрования состоит из трех стадий: прямого и обратного перемешивания, которые оборачивают шифрование и состоят из 8 раундов, и 16 раундового шифрования. Обратное перемешивание производят для более быстрого достижение лавинного эффекта и нарушения симметричности при перемешивании. Стадии прямого и обратного перемешивания инвертированы относительно друг друга.

Перед прямым перемешиванием происходит входное забеливание (добавление к входному блоку ключей). Далее в течение 8 раундов производится перемешивание без использования ключа. На стадии перемешивания используются операции битового сдвига, исключающего "ИЛИ", сложения и Sbox'ы.

Рис. 2.1 Схема алгоритма MARS

Непосредственное шифрование представляет собой сеть Фейстеля с 4 ветвями. От первой ветви вычисляется функция F. На вход функции F подается 32 битное слово, функция выдает на выход три 32 битных слова. Полученные слова складываются с тремя оставшимися ветвями, далее выполняется перестановка ветвей. Структура функции представлена на рис. 2.2

Рис 2.2 Структура функции зашифрования и расшифрования алгоритма MARS

B первых восьми раундах производится прямое шифрование, в следующих восьми раундах обратное. Прямое и обратное шифрование отличаются порядком функций, выполняемых над выходами функции F.

MARS поддерживает переменную длину ключа от 128 до 448 битов, используя процедуру расширения входного ключа до 40 32-битовых слов, которые используются при шифровании и дешифровании.

Одним из недостатков алгоритма является сложность его криптоанализа из-за использования двойного перемешивания. Алгоритм показал хорошую скорость шифрования. Скорость шифрования на Intel-Pentium 200 МГц достигала 65 Мбит/с, скорость выполнения блока прямого и обратного шифрования достигала 100 Мбит/с.

3. Алгоритм шифрования RC4

Алгоритм RC4 состоит из трех частей:

Создание ключа (иногда называют - расширение ключа).

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

Алгоритм расшифровки.

Создание ключа

Ключ в RC4 представляет собой последовательность байтов произвольной длинны, по которой строится начальное состояние шифра S - перестановка всех 256 байтов. Алгоритм получения начального состояния изображен на рис.3.1.

Рис 3.1 Алгоритм получения начального состояния шифра RC4

Первоначально S заполняется последовательными значениями от 0...255. Затем каждый очередной элемент S обменивается местами с элементом , номер которого определяется элементом ключа K, самим элементом и суммой номеров элементов, с которыми происходил об мен на предыдущих итерациях.

Значения счетчиков i и с изначально равны 0. Сплошные стрелки означают передачу значений между элементами схемы ( присваивание ), двусторонние стрелки - обмен значениями, пунктирные стрелки - индексацию в массиве.

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

Алгоритм схематически изображен на рис. 3.2.

Рис 3.2 Алгоритм шифрования RC4

Очередной элемент псевдослучайной перестановки S всех байтов обменивается с другим, номер которого равен сумме элементов, выбрнных на предыдущих шагах. В качестве очередного байта выдается значение третьего элемента S, номер которого равен сумме первых двух. Значение счетчика x первоначально равно 0, но оно увеличивается на 1 уже перед первой выборкой S(x). Значение y первоначально равно 0. Но затем высчитывается как элемент ключа по номеру x + предыдущее значение y и вся сумма по mod 256.

Некоторые полезные свойства алгоритма RC4.

Преобразование очередного состояния генератора (S,x,y) обратимо, так что все возможные состояния повторяются с одинаковой частотой с некоторым периодом.

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

4. Алгоритм шифрования RC5

RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов. Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325].

Используется три действия: XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги являются нелинейной функцией. Эти циклические сдвиги, зависящие и от ключа, и от данных, представляют собой интересную оп е-рацию.

RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных. Шифрование использует 2r+2 зависящих от ключа 32-битовых слов - So, Si, S2, ... S2r+i - где r - число этапов. Эти слова мы сгенерируем позднее. Для шифрования сначала блок открытого текста делится на два 32-битовых слова: А и В. (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра А, и т.д.) Затем:

A=A + S0

B = B + S1

For i = 1 to r:

A = ((A B) <« B) + S2i

В = ((В A) <« A) + S2i+1

Результат находится в регистрах А и В.

Дешифрирование также просто. Блок открытого текста разбивается на два слова, А и В, а затем:

For i = r down to 1:

B = ((B-S2i+1)>>>A) A

A = ((A-S2i)>>>B) B

B = B - S1

A=A - S0

Символ ">>>" обозначает циклический сдвиг направо. Конечно же, все сложения и вычитания выполняются по модулю 232.

Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в ма с-сив L из с 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 232:

S = P

For I =1 to 2(r+1)-1

Si = (Si-1 + Q) mod 232

P = 0xb7el5163 и Q = 0х9е377989, эти константы основываются на двоичном представлении е и phi. Наконец, подставляем L в S:

i=j = 0

А=В = 0

выполнить п раз (где п - максимум 2(r + 1) и с):

А = Si = (Si + А+ В)<<<3

B = Li = (Li +A+B) <<< (А + В) ;

i = (i+1) mod 2(r+l)

j = (j + 1 ) mod с

По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым cл овом и 64-битовым блоком, не существует причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, Р и Q равны 0xb7el51628aed2a6b и 0x9e3779b97f4a7cl5, соответственно. Ривест обозначил различные реализации RC5 как RC5- wlrlb, где w - это размер слова, r - число этапов, а b -длина ключа в байтах.

RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 2 24 выбранных открытых текстов для 5 этапов, 245 для 10 этапов, 253 для 12 этапов и 268 для 15 этапов. Конечно же, существует только 264 возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.

RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утверждает, что плата за лицензирование будет очень мала, но это лучше проверить.

5. Алгоритм шифрования RC6

Авторы: Рональд Райвест (Ronald Rivest), а также:М. Робшоу (M. Robshaw), Р. Сидни (R.Sidney), Y. Yin. Архитектура:Архитектура на базе сбалансированной сети Файстеля с существенными отклонениями от классического варианта:

другая схема разбиения блока на части: блок делится на четыре подблока одинакового размера, изменяемые и неизменные подблоки чередуются, между раундами подблоки циклически меняются местами;

другой способ использования ключевой информации: ключевой элемент не используется при выработке функции шифрования, вместо этого его половины прибавляются к модифицируемым подблокам на выходе каждого раунда, перед первым и после последнего раунда к двум подблокам также прибавляются половинки ключевого элемента;

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

Параметры:

Особенности:

RC6 представляет собой целое семейство шифров с переменным размером блока, переменным размером ключа от 1 до 32 байт и переменным числом раундов. В шифре вовсе не используются узлы замен, вместо этого используется умножение и циклические сдвиги на переменное число разрядов w/4-битовых чисел, где w - размер блока данных в битах. В силу этого алгоритм неэффективно реализуется на процессорах без быстрой команды умножения и без команды циклического сдвига на переменное число битов. Кроме того, операция умножения ресурсоемка при аппаратной реализации. По указанным причинам RC6 не был избран в качестве усовершенствованного стандарта шифрования США, хотя на ряде 32-битовых платформ его реализация оказалась существенно эффективней, чем реализация AES.

Замечания

(1) В версии RC6, номинировавшейся на место нового стандарта размер блока фиксировани и равен 128 бит, число раундов также фиксировано и равно равно 20, размер ключа может принимать одно из трех значениий: 128, 192 или 256 бит.

Схема алгоритма представлена RC6 на рис 5.1

Рис. 5.1 Схема алгоритма RC6

Характерной особенностью алгоритма является отказ от привычных Sbox'ов и введение операция квадратичной трансформации. Простота и высокая скорость шифрования являются его основными достоинствами, к тому же RC6 имеет наибольшую скорость среди финалистов AES (12.6 Мбайт/с)

6. Алгоритм шифрования TwoFish

Алгоритм, разработанный Шнайером, является модификацией алгоритма BlowFish, созданного в 1993г. Алгоритм TwoFish основан на 16 раундовой сети Фейстеля. В алгоритме используются преобразование РНТ (Pseudo-Hadamard Transforms), MDS матрицы, зависимые от ключа Sbox'ы, по сравнению с другими алгоритмами TwoFish имеет довольно сложную структуру, которая представлена на рисунке 6.1

Рисунок 6.1 Структура алгоритма Twofish

Входное отбеливание

Один раунд шифрования

Еще 15 раундов

Отмена последнего обмена местами пар слов

Выходное отбеливание

128-битовый блок P открытого текста (16 байт p0 ,…, p15) разбивается на четыре 32-битовых слова P0, P1, P2 и P3 c сохранением прямого порядка байтов (Little-Endian Convention):

На этапе входного «отбеливания» выполняется операция XOR между этими словами и четырьмя ключами K0, K1, K2 и K3:

После этого следуют 16 раундов шифрования. В каждом раунде два «левых» слова являются входными для функций g (биты одного из входных слов сначала циклически сдвигаются на 8 позиций влево). К полученным выходным словам функций g затем применяется псевдопреобразование Адамара (PHT - Pseudo-Hadamard Transform) и добавляются два раундовых ключа K2r+8 и K2r+9, где r -- номер раунда шифрования. Далее между модифицированными таким образом «левыми» словами и двумя «правыми» словами (биты одного из которых прежде циклически сдвигаются на одну позицию влево) выполняется операция XOR, после чего циклическому сдвигу на 1 бит вправо подвергается другое из теперь уже видоизмененных «правых» слов. «Левая» и «правая» пары слов затем меняются местами для следующего раунда шифрования. Таким образом,

где r = 0 , …, 15, а аббревиатурами ROR и ROL обозначены функции двух аргументов, выполняющие побитовый циклический сдвиг первого аргумента вправо и влево соответственно на число позиций, равное второму аргументу.

После реализации всех 16-ти раундов шифрования последний обмен местами «левой» и «правой» пар слов отменяется, и между полученными 32-битовыми словами и ключами K4, K5, K6 и K7 выполняется операция XOR (этап выходного «отбеливания»):

Сi = R16,(i+2)mod4 K i=0,…,3

Полученные слова C0, C1, C2 и C3 затем объединяются в 128-битовый блок C (16 байт c0 ,… , c 15) зашифрованного текста:

где x - целая часть х.

Несколько слов по поводу криптостойкости Twofish.

Разработчики алгоритма уже изначально были уверены в неприступности своего творения для криптоаналитиков. Во время первого раунда конкурса на новый американский правительственный стандарт шифрования Б. Шнайером был даже объявлен конкурс на лучшую криптоатаку против Twofish с призовым фондом в 10 тысяч долларов. Задача была действительно непростая: сложность алгоритма сыграла свою роль (и стала, кстати, одной из причин, по которой Twofish не стал новым стандартом шифрования США).

Тем не менее, определенные успехи в криптоанализе Twofish все же были достигнуты. Один из известных методов (Impossible Differential Attack), принадлежащий Ларсу Нудсену (Lars Knudsen), для 6-раундового Twofish (без «отбеливаний») имеет сложность 2128 для 128-битового ключа, 2160 для 192-битового ключа и 2192 для 256-битового ключа. Также была предложена атака на 7-раундовый Twofish (опять же без «отбеливаний») со сложностью 2256 для 256-битового ключа.

С «отбеливаниями» наилучшая атака «ломала» 6-раундовый Twofish cо сложностью 2256 и только с длиной ключа, равной 256 бит.

Таким образом, значительный запас криптостойкости Twofish очевиден.

Список использованных источников

1. Брюс Шнайер Прикладная криптография 2-е издание

2.О процессе принятия AES. Б. Киви http://byrd.narod.ru/aes/aes2.htm

3.Конкурс на новый криптостандарт AES. Б. Киви http://kiwibyrd.chat.ru/ru/aes1 .htm

4.Общие сведения о конкурсе AES http://www.citforum.ru/internet/infsecure/its2000 21 .shtml

Страницы: 1, 2