Мы здесь приведем краткое описание алгоритма DES, подробное изложение можно найти в [1], [2], [3], [4].
DES представляет собой блочный шифр, он шифрует данные 64-битовыми блоками. На вход алгоритма подается 64-битовый блок открытого текста, а выходит 64-битовый блок шифртекста. DES является симметричным алгоритмом: для шифрования и расшифрования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа).
Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определяется ключом.
Алгоритм является комбинацией двух основных методов шифрования: смещения и диффузии. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз.
Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-x.
Схема алгоритма представлена на рисунке 7.1.
(рис 7.1) DES
| 58 | 50 | 42 | 34 | 26 | 18 | 10 | 2 | 60 | 52 | 44 | 36 | 28 | 20 | 12 | 4 |
| 62 | 54 | 46 | 38 | 30 | 22 | 14 | 6 | 64 | 56 | 48 | 40 | 32 | 24 | 16 | 8 |
| 57 | 49 | 41 | 33 | 25 | 17 | 9 | 1 | 59 | 51 | 43 | 35 | 27 | 19 | 14 | 3 |
| 61 | 53 | 45 | 37 | 29 | 21 | 13 | 5 | 63 | 55 | 47 | 39 | 31 | 23 | 15 | 7 |
Биты входных данных нумеруются по порядку, начиная с 1, и переставляются подстановкой $$IP$$ согласно таблице 7.1. Таблица трактуется следующим образом: значение 58 бита входной последовательности перемещается в битовую позицию 1, бит 50 -- в битовую позицию 2, бит 42 -- в битовую позицию 3, и так далее.
После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называемых функцией $$f$$, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая половины объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной).
На каждом этапе (см. рис 7.2) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией $$f$$. Затем результат функции $$f$$ объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов DES.
(рис 7.2) Один раунд шифра DES
Если $$B_i$$ --- результат $$i$$-ой итерации, $$L_i$$ и $$R_i$$ --- левая и правая половины $$B_i$$, $$K_i$$ --- 48-битовый ключ для этапа $$i$$, a $$f$$ - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:
$$L_i = R_{i-1}, \qquad R_i = L_{i-1}\oplus f(R_{i-1},K_i).$$В алгоритме ГОСТ ключевая информация состоит из двух структур данных. Помимо собственно ключа, необходимого для всех шифров, она содержит еще и таблицу замен. Ниже приведены основные характеристики ключевых структур ГОСТа.
Ключ является массивом из восьми 32-битовых элементов кода, далее в настоящей работе он обозначается $$K: K=\{K_i\}_{i=0}^7$$.
В ГОСТе элементы ключа используются как 32-разрядные целые числа без знака: $$0\leq K_i<2^{32}$$. Таким образом, размер ключа составляет $$32\cdot 8=256$$ бит, или 32 байта.
Таблица замен может быть представлена в виде $$8\times 16$$-матрицы, содержащей 4-битовые элементы, которые можно представить в виде целых чисел от 0 до 15. Строки таблицы замен называются узлами замен, они должны содержать различные значения, то есть каждый узел замен должен содержать 16 различных чисел от 0 до 15 в произвольном порядке.
Основной шаг криптопреобразования по своей сути является оператором, определяющим преобразование 64-битового блока данных. Дополнительным параметром этого оператора является 32-битовый блок, в качестве которого используется какой-либо элемент ключа. Схема алгоритма основного шага приведена на рисунке 7.3.
Ниже даны пояснения к алгоритму основного шага.
(рис 7.3) Схема одного раунда преобразования по алгоритму ГОСТ 28147-89
Шаг 0. Определяет исходные данные для основного шага криптопреобразования: $$N_i$$ -- преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая ($$A_i$$) и старшая ($$B_i$$) части обрабатываются как отдельные 32-битовые целые числа без знака. Таким образом, можно записать $$N_i=(A_i, B_i)$$. $$K_i$$ -- 32-битовый элемент ключа;
Шаг 1. Сложение с ключом. Младшая половина преобразуемого блока складывается по модулю $$2^{32}$$ с используемым на шаге элементом ключа, результат передается на следующий шаг;
Шаг 2. Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: $$S=(S_i)_{i=0}^7$$. Далее значение каждого из восьми блоков заменяется новым, которое выбирается по таблице замен следующим образом: значение блока $$S_i$$ меняется на $$S_i$$ - ый по порядку элемент (нумерация с нуля) $$i$$-того узла замен (т.е. $$i$$ -той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Теперь становится понятным размер таблицы замен: число строк в ней равно числу 4-битовых элементов в 32-битовом блоке данных, то есть восьми, а число столбцов равно числу различных значений 4-битового блока данных, равному шестнадцати.
Шаг 3. Циклический сдвиг на 11 бит влево. Результат предыдущего шага сдвигается циклически на 11 бит в сторону старших разрядов и передается на следующий шаг.
Шаг 4. Побитовое сложение: значение, полученное на шаге 3, побитно складывается по модулю 2 со старшей половиной преобразуемого блока.
Шаг 5. Сдвиг по цепочке: младшая часть преобразуемого блока сдвигается на место старшей, а на ее место помещается результат выполнения предыдущего шага.
Шаг 6. Полученное значение преобразуемого блока возвращается как результат выполнения алгоритма основного шага криптопреобразования.
Для количественного анализа устойчивости процедур преобразования данных в ходе шифрования используется их представление в виде структур, состоящих из булевых функций. Этот же метод позволяет оценивать зависимость криптостойкости шифрования от выбранной ключевой информации, определяя, таким образом, критерии выбора "сильных" ключей и блоков замен (в случае ГОСТ 28147-89 и других, менее распространенных шифров с секретными блоками замен).Здесь мы кратко изложим метод исследования устойчивости алгоритма блочного шифрования к наиболее распространенным атакам, подробнее см. [2].
Определение 7.1 Булевой функцией называется отображение $${\left\{0,1\right\}}^{n}\rightarrow \left\{0,1\right\}$$, то есть правило, однозначно сопоставляющее вектору из $$n$$ бит значение 0 или 1.
Способы задания булевой функции [2]:
1) Табличный -- в виде таблицы, каждая строка которой задает значение функции при определенном наборе значений входных переменных. Число строк такой таблицы равно $${2}^{n}$$.
Пример 7.1 Таблица 7.2 задаёт булеву функцию $$f\left({x}_{0},{x}_{1},{x}_{2}\right)$$.
| $${x}_{2}$$ | $${x}_{1}$$ | $${x}_{0}$$ | $$f\left({x}_{0},{x}_{1},{x}_{2}\right)$$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
2) Векторный -- в виде вектора, состоящего из значений булевой функции, выписанных в порядке возрастания аргумента, если его представить в виде числа от 0 до $$2^n-1$$. В самом деле, вместо $$n$$ логических переменных $${x}_{0},{x}_{1},{{\dots},x}_{n-1}$$ в качестве аргумента функции можно использовать $$n$$-битное целое число
$$x={x}_{0}+{x}_{1}{\cdot}2+{x}_{2}{\cdot}{2}^{2}+{\dots}+{x}_{n-1}{\cdot}{2}^{n-1}=\sum\limits_{i=0}^{n-1}{{x}_{i}{\cdot}{2}^{i}}.$$Функция из примера 1 в векторном виде будет представлена следующим образом: $$f\left({x}_{0},{x}_{1},{x}_{2}\right)=\left(01101001\right)$$ (последний столбец таблицы выписан сверху вниз).
3) Аналитический -- в виде формулы, выражающей зависимость значения функции от значений ее аргументов.
Функция из примера 7.1 в аналитическом виде можно представить следующим образом: $$f\left({x}_{0},{x}_{1},{x}_{2}\right)={x}_{0}\oplus {x}_{1}\oplus {x}_{2}$$, где $$\oplus$$ - операция сложения бит по модулю 2 (XOR).
Определение 7.2 Весом булевой функции называется количество наборов значений входных переменных, при которых она принимает значение 1.
Проще говоря, это число единиц в векторном представлении булевой функции. Так, вес функции из примера 1 равен 4 (так как из 8 бит в векторе $$\left(01101001\right)$$ 4 единицы). Обозначается $$\wt (f)$$, например, $$\wt \left(01101001\right)=4$$.
Определение 7.3 Расстоянием между двумя булевыми функциями называется вес их побитовой суммы по модулю 2 в векторном виде (число позиций вы векторах, в которых значения функции различны).
Обозначается $$\dist({f}_{1},{f}_{2})$$, например, $$\dist\left(01101001,00101111\right)=3$$, так как значения функций различаются при $$x=1,x=5$$ и $$x=6$$.
Определение 7.4 Линейной называется булева функция аналитического вида
$$f\left({x}_{0},{x}_{1},{\dots},{x}_{n-1}\right)={{a}_{0}x}_{0}\oplus {{a}_{1}x}_{1}\oplus {\dots}\oplus {a}_{n-1}{x}_{n-1}=\sum\limits_{i=0}^{n-1}{{a}_{i}{x}_{i}}.$$где $${a}_{0},{a}_{1},{\dots},{a}_{n-1}{\in}\left\{0,1\right\}$$ -- произвольные значения 0 или 1. Множество всех линейных функций от $$n$$ переменных обозначим $${L}_{n}$$.
Пример 7.2 Построим все линейные булевы функции от 2 переменных.
Для этого нам нужно перебрать все различные комбинации бит $${a}_{0},{a}_{1}{\in}\left\{0,1\right\}$$:
Таким образом, множество линейных функций от 2 переменных:
$${L}_{2}=\left\{\left(0000\right), \left(0101\right), \left(0011\right), \left(0110\right)\right\}.$$Определение 7.5 Аффинной называется булева функция аналитического вида
$$f\left({x}_{0},{x}_{1},{\dots},{x}_{n-1}\right)={{a}_{0}x}_{0}\oplus {{a}_{1}x}_{1}\oplus {\dots}\oplus {a}_{n-1}{x}_{n-1}\oplus b=\sum _{i=0}^{n-1}{{a}_{i}{x}_{i}\oplus b},$$где $${a}_{0},{a}_{1},{\dots},{a}_{n-1},b{\in}\left\{0,1\right\}$$ -- произвольные значения 0 или 1. Множество всех аффинных функций от $$n$$ переменных обозначим $${A}_{n}$$.
Как нетрудно заметить, единственным отличием общего аналитического вида аффинных функций от линейных является наличие свободного члена $$b$$, при этом если $$b=0$$, то функция является линейной, а при $$b=1$$ функция в векторном виде является побитовой инверсией соответствующей линейной в (при тех же значениях коэффициентов $${a}_{0},{a}_{1},{\dots},{a}_{n-1}$$).
Таким образом, множество всех аффинных функций от $$n$$ переменных есть объединение множества всех линейных функций от $$n$$ переменных и множества их побитовых инверсий: $${A}_{n}={L}_{n}{\cup}\left\{f:\overline{{f}}{\in}{L}_{n}\right\}$$.
Пример 7.3 Построим все аффинные булевы функции от 2 переменных.
Для этого нам нужно объединить уже построенное в примере 2 множество всех линейных булевых функций от 2 переменных с множеством их побитовых инверсий:
$${A}_{2}=\left\{\left(0000\right),\left(0101\right),\left(0011\right),\left(0110\right),\left(1111\right),\left(1010\right),\left(1100\right),\left(1001\right)\right\}.$$Нелинейностью булевой функции называется минимальное расстояние от этой функции до множества аффинных функций: $$\nl \left(f\right)=\min\limits_{c\in A_n}\dist\left(f,c\right)$$.
Нелинейность показывает, насколько хорошо функция аппроксимируется линейными приближениями, другими словами, насколько хорошо можно подобрать такую линейную функцию, которая с большой вероятностью (при большом количестве различных значений входных переменных) будет давать то же значение, что и данная функция.
Пример 7.4 ([2]) Определим нелинейность функции 2 переменных $$f\left({x}_{0},{x}_{1}\right)=\left(1101\right)$$.
Сначала необходимо построить множество всех аффинных функций от 2 переменных (мы это сделали в примере 3):
$${A}_{2}=\left\{\left(0000\right),\left(0101\right),\left(0011\right),\left(0110\right),\left(1111\right),\left(1010\right),\left(1100\right),\left(1001\right)\right\}$$Теперь поочередно вычисляем расстояние от функции $$f\left({x}_{0},{x}_{1}\right)$$ до каждой из функций этого множества и находим минимум:
$$nl \left(f\right)=\min \left\{\begin{matrix}d\left(1101,0000\right),d\left(1101,0101\right),d\left(1101,0011\right),d\left(1101,0110\right),\\ d\left(1101,1111\right),d\left(1101,1010\right),d\left(1101,1100\right),d\left(1101,1001\right)\end{matrix}\right\}=\\ \min\left\{3,1,3,3,1,3,1,1\right\}=1.$$Определение 7.6 Динамическим расстоянием $$j$$ -го порядка булевой функции $$f\left({x}_{0},{x}_{1},{\dots},{x}_{n-1}\right)$$ называется число, вычисляемое по формуле:
$$DD_j\left(f\right)=\max\limits_{\substack{d\in\{0,1\}^n\\1\leq wt (d)\leq j}} \frac{1}{2}\left|{2}^{n-1}-\sum \limits_{x{\in}{\left\{0,1\right\}}^{n}}{f\left(x\right)\oplus f\left(x\oplus d\right)}\right|.$$Динамическое расстояние характеризует степень соответствия функции критерию лавинного эффекта, который заключается в том, что при изменении бит на входе выходное значение функции должно меняться с вероятностью $$\frac{1}{2}$$. Порядок динамического расстояния характеризует число одновременно изменяемых бит. При динамическом расстоянии $$j$$ -го порядка, равном 0, говорят, что функция удовлетворяет строгому критерию лавинного эффекта $$j$$-го порядка, что означает следующее: при одновременном инвертировании любых $$j$$ бит на входе функции ее значение инвертируется с вероятностью ровно $$\frac{1}{2}$$.
Пример 7.5 ([2]) Определим динамическое расстояние 1 и 2 порядка функции 2 переменных $$f\left({x}_{0},{x}_{1}\right)=\left(1101\right)$$.
Разберемся с нашим определением. Вектор $$d$$ -- это двоичный вектор длиной $$n$$, причем такой, что его вес не превышает порядка определяемого динамического расстояния.
Таким образом, для нашей функции 2 переменных при определении динамического расстояния порядка 1 вектор $$d$$ может принимать 2 значения: $$d=\left(01\right)$$ и $$d=\left(10\right)$$.
Заметим также, что в сумме в формуле динамического расстояния суммирование ведется по всем возможным значениям аргумента функции $$x$$ -- двоичного вектора длиной $$n$$.
Теперь вычисляем динамическое расстояние по формуле:
$$\begin{align*}DD_1(f)=\max \left\{\frac{1}{2}\left|2-\sum \limits_{x{\in}{\left\0,1\right\}}^{2}}{f\left(x\right)\oplus f\left(x\oplus 01\right)}\right|,\right.\\ \left.\frac{1}{2}\left|2-\sum \limits_{x{\in}{\left\{0,1\right\}}^{2}}{f(x)\oplus f(x\oplus 10)}\right|\right\}=\end{align*} % \begin{align*}=\max \left\{\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(00\oplus 01\right)-f\left(01\right)\oplus f\left(01\oplus 01\right)-\right.\right.\\%\end{multline*} \\ \left.\left. f\left(10\right)\oplus f\left(10\oplus 01\right)-f\left(11\right)\oplus f\left(11\oplus 01\right)\right|,\right.\\ \hphantom{\max \left\{\vphantom{\frac{1}{2}}\right.} \left.\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(00\oplus 10\right)-f\left(01\right)\oplus f\left(01\oplus 10\right)-\right.\right.\\ \left.\vphantom{\frac{1}{2}}\left.-f\left(10\right)\oplus f\left(10\oplus 10\right)-f\left(11\right)\oplus f\left(11\oplus 10\right)\right|\right\}=\end{align*} % \begin{align*}=\max \left\{\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(01\right)-f\left(01\right)\oplus f\left(00\right)-f\left(10\right)\oplus f\left(11\right)-\right.\right. \\ \left.\left.f\left(11\right)\oplus f\left(10\right)\right|, \frac{1}{2}\left|2-f\left(00\right)\oplus f\left(10\right)-f\left(01\right)\oplus f\left(11\right)-\right.\right.=\\ \left.\left. f\left(10\right)\oplus f\left(00\right)-f\left(11\right)\oplus f\left(01\right)\right|\right\} = \\ \max \left\{\frac{1}{2}\left|2-1\oplus 1-1\oplus 1-0\oplus 1-1\oplus 0\right|\right.,\left.\frac{1}{2}\left|2-1\oplus 0-1\oplus 1-\right.\right.\\ \left.\left.-0\oplus 1-1\oplus 1\right|\right\}=\\ =\max \left\{\frac{1}{2}\left|2-0-0-1-1\right|;\frac{1}{2}\left|2-1-0-1-0\right|\right\}=\\ =\max \left\{0;0\right\}=0\end{align*}$$Чтобы теперь определить динамическое расстояние этой функции 2-го порядка, необходимо еще раз вычислить значение выражения, стоящего под знаком максимума, при $$d=\left(11\right)$$ -- так как максимальный вес вектора $$d$$ уже становится равным 2:
$$\begin{align*}DD_2\left(f\right)=\max \left\{DD_1\left(f\right);\frac{1}{2}\left|2-\sum \limits_{x{\in}{\left\{0,1\right\}}^{2}}{f\left(x\right)\oplus f\left(x\oplus 11\right)}\right|\right\}=\\ \max \left\{0;\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(00\oplus 11\right)-f\left(01\right)\oplus f\left(01\oplus 11\right)-\right.\right.\\ \left.\left.\vphantom{\frac{1}{2}} -f\left(10\right)\oplus f\left(10\oplus 11\right)-f\left(11\right)\oplus f\left(11\oplus 11\right)\right|\right\} =\\ \max \left\{0;\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(11\right)-f\left(01\right)\oplus f\left(10\right) -f\left(10\right)\oplus f\left(01\right)\right.\right.\\ \left.\left.\vphantom{\frac{1}{2}} -f\left(11\right)\oplus f\left(00\right)\right|\right\}=\max\left\{0;\frac{1}{2}\left|2-1\oplus 1-1\oplus 0-0\oplus 1-1\oplus 1\right|\right\}=\\ \max \left\{0;\frac{1}{2}\left|2-0-1-1-0\right|\right\}=\max \left\{0;0\right\}=0 \end{align*}$$Таким образом, $${\DD }_{1}\left(f\right)={\DD }_{2}\left(f\right)=0$$.
Определение 7.7 Блоком замен $$n\times m$$ бит называется отображение $${\left\{0,1\right\}}^{n}\rightarrow {\left\{0,1\right\}}^{m}$$, то есть отображение, однозначно сопоставляющее любому входному вектору из $$n$$ бит выходной вектор из $$m$$ бит.
Нетрудно заметить, что блок замен есть не что иное, как набор из $$m$$ булевых функций, каждый из которых задает зависимость определенного бита на выходе блока от значений бит на входе. Любая процедура преобразования бит по определенному правилу может быть представлена в виде блока замен, если выписать все значения на выходе преобразования при всех возможных значениях на входе.
Способы задания блока замен:
1) Табличный -- в виде таблицы, каждая строка которой содержит значения выходных бит блока при определенном наборе значений входных бит. Число строк такой таблицы равно $${2}^{n}$$.
Пример 7.6 Таблица 7.3 задаёт блок замен $${S:\left\{0,1\right\}}^{3}\rightarrow {\left\{0,1\right\}}^{3}$$.
| $${x}_{2}$$ | $${x}_{1}$$ | $${x}_{0}$$ | $${f}_{2}\left({x}_{2},{x}_{1},{x}_{0}\right)$$ | $${f}_{1}\left({x}_{2},{x}_{1},{x}_{0}\right)$$ | $${f}_{0}\left({x}_{2},{x}_{1},{x}_{0}\right)$$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
В данной таблице блок замен задан путем определения табличным способом трех булевых функций от трех переменных, определяющих зависимость выходных бит блока от входных.
2) Векторный -- в виде вектора, состоящего из значений блока замен, представленных в виде десятичного $$n$$-битного числа, расположенных в порядке возрастания соответствующих значений аргумента, если их представить в виде в виде числа от 0 до $${2}^{n}-1$$ (аналогично тому, как это делается при записи булевой функции в векторной форме).
Так, блок замен $$S$$ из примера 7.6 в векторной форме будет записываться следующим образом: $$\left(1,6,7,1,0,1,5,6\right)$$ (3-битовые значения на выходе блока представлены в виде целых чисел и выписаны сверзу вниз).
3) Аналитический -- в виде аналитически записанной зависимости выходных бит блока от входных. Например, в аналитической форме $$n\times m$$ битный блок замены $$S$$ путем целочисленного сложения с числом $$k$$ по модулю $${2}^{m}$$ можно записать следующим образом: $$S\left(x\right)=x+k (\mod {2}^{m})$$.
(рис 7.4) Схема представления узла замен ГОСТ 28147-89 в виде битовой матрицы
Пусть $$S$$ -- блок замен $$n\times m$$ бит, и $${f}_{0},{f}_{1},{\dots},{f}_{m-1}$$ -- булевы функции, выражающие зависимость соответствующих номерам функций выходных бит блока от входных. Иначе говоря, это столбцы правой части таблицы при записи блока замен в табличной форме (см. рис 7.4). Тогда нелинейность блока замен есть минимальная нелинейность всех возможных нетривиальных линейных комбинаций функций $${f}_{0},{f}_{1},{\dots},{f}_{m-1}$$:
$$nl\left(S\right)=\min\limits_{\substack{c\in \{0,1\}^m\\c\neq 0}} nl \left({c}_{0}{f}_{0}\oplus {c}_{1}{f}_{1}\oplus {\dots}\oplus {c}_{m-1}{f}_{m-1}\right)$$где $$c={c}_{0}+{c}_{1}{\cdot}2+{c}_{2}{\cdot}{2}^{2}+{\dots}+{c}_{m-1}{\cdot}{2}^{m-1}$$.
Например, нелинейность блока из примера 7.6 будет рассчитываться следующим образом:
$$\begin{align*}nl(S)=\min \left\{nl \left({f}_{0}\right),nl \left({f}_{1}\right),nl \left({f}_{2}\right),nl \left({f}_{0}\oplus {f}_{1}\right),nl \left({f}_{0}\oplus {f}_{2}\right),nl \left({f}_{1}\oplus {f}_{2}\right),\right.\\ \left. nl \left({f}_{0}\oplus {f}_{1}\oplus {f}_{2}\right)\right\}=\\ \min \left\{nl (10110110),nl (01100001),nl (01100011),nl (11010111),nl (11010101),\right. \\ \left. nl (00000010); nl (10110100)\right\}=\\ \min \left\{\text{1;1;2;2;1;1;2}\right\}=1\end{align*}$$\textit{Нелинейность битового блока замен есть важнейшая его характеристика с точки зрения криптостойкости блока: она показывает степень устойчивости внутренней структуры блока к линейному методу криптоанализа. Следовательно, для достижения устойчивости шифрования к линейному криптоанализу необходимо, чтобы процедуры преобразования бит в ходе шифрования обладали как можно большей нелинейностью.}
Определение 7.8 Динамическое расстояние блока замен порядка $$\left(i,j\right)$$ определяется следующим образом:
$$\begin{equation*} {\mathit{DD}}_{i,j}\left(S\right)=\underset{\begin{matrix}c{\in}{\left\{0,1\right\}}^{m}\\1{\leq}\wt \left(c\right){\leq}i\end{matrix}}{\mathit{max}}{\mathit{DD}}_{j}\left({c}_{0}{f}_{0}\oplus {c}_{1}{f}_{1}\oplus {\dots}\oplus {c}_{m-1}{f}_{m-1}\right) \end{equation*}$$Таким образом, динамическое расстояние блока порядка $$\left(i,j\right)$$ есть максимальное динамическое расстояние порядка $$j$$ всех нетривиальных линейных комбинаций не более чем из $$i$$ функций из набора $${f}_{0},{f}_{1},{\dots},{f}_{m-1}$$.
Смысл порядка динамического расстояния блока замен состоит в следующем: динамическое расстояние порядка $$(i,j)$$ характеризует степень отклонения вероятности изменения любого $$i$$ числа битов, не превышающего $$i$$, на выходе блока от значения $$1/2$$ при одновременном инвертировании не более $$j$$ битов на входе. Если динамическое расстояние блока замен порядка $$i,j$$ равно 0, то это означает, что при одновременном изменении не более $$j$$ битов на входе блока любой набор из не более чем $$i$$ бит на выходе одновременно изменится с вероятностью ровно $$1/2$$.
Например, динамическое расстояние порядка $$\left(2,1\right)$$ блока из примера 7.6 будет рассчитываться следующим образом:
$$\begin{align*} {DD}_{2,1}\left(S\right)=\max \left\{{DD}_{1}\left({f}_{0}\right),{DD}_{1}\left({f}_{1}\right),{DD}_{1}\left({f}_{2}\right),{DD}_{1}\left({f}_{0}\oplus {f}_{1}\right),\right.\\ \left. {DD}_{1}\left({f}_{0}\oplus {f}_{2}\right),{DD}_{1}\left({f}_{1}\oplus {f}_{2}\right)\right\}= \\ =\max \left\{{DD}_{1}\left(10110110\right),{DD}_{1}\left(01100001\right),{DD}_{1}\left(01100011\right),\right. \\ \left.{DD}_{1}\left(11010111\right),{DD}_{1}\left(11010101\right),{DD}_{1}\left(00000010\right)\right\}=\\ =\max \left\{1,1,2,0,1,1\}\right\}=2. \end{align*}$$А динамическое расстояния порядка $$\left(3,2\right)$$ рассчитывается так:
$$\begin{align*} {DD}_{3,2}\left(S\right)=\max \left\{{DD}_{2}\left({f}_{0}\right),{DD}_{2}\left({f}_{1}\right),{DD}_{2}\left({f}_{2}\right),{DD}_{2}\left({f}_{0}\oplus {f}_{1}\right),\right.\\ \left.{DD}_{2}\left({f}_{0}\oplus {f}_{2}\right),{DD}_{2}\left({f}_{1}\oplus {f}_{2}\right),{DD}_{2}\left({f}_{1}\oplus {f}_{2}\oplus {f}_{3}\right)\right\}= \\ =\max \left\{{DD}_{2}(10110110),{DD}_{2}(11010101),{DD}_{2}(00000010),\right. \\ \left.{DD}_{2}(10110100)\right\}= \\ = \max \{1,1,2,2,1,1,2\}=2. \end{align*}$$Таким образом, динамическое расстояние блока замен есть вторая важнейшая его характеристика с точки зрения криптостойкости: она показывает степень устойчивости внутренней структуры блока к дифференциальному методу криптоанализа. Следовательно, для достижения устойчивости шифрования к дифференциальному криптоанализу необходимо, чтобы процедуры преобразования бит в ходе шифрования обладали как можно меньшим динамическим расстоянием как можно большего порядка.
Практически все современные блочные шифры, основанные на схеме Файстеля, содержат в числе процедур преобразования данных замену бит по специальным таблицам аналогично тому, как это делается в шифре ГОСТ 28147-89. Однако в них эти таблицы определены в спецификации алгоритма и выбираются один раз (на этапе проектирования шифра). Назначение этих таблиц (в алгоритме DES они называются S-блоками) -- перемешивание битов данных в ходе раунда шифрования путем замены отрезков шифруемого блока данных по правилам, определяемым таблицами.
Общие требования к узлам замен (S-блокам) блочных шифров повторяют требования к функции шифрования в целом -- это высокое значение нелинейности и наличие лавинного эффекта (что достигается при низком динамическом расстоянии различных порядков). Существует ряд общеизвестных критериев для проектирования устойчивых к дифференциальному криптоанализу узлов замен для любых блочных шифров:
1) Строгий критерий лавинного эффекта (SAC -- Strict Avalanche Criterion) -- требует, чтобы для любых $$i$$ и $$j$$ при инвертировании входного бита $$i$$ на входе узла замен выходной бит $$j$$ изменялся с вероятностью $$1/2$$. Блок замен удовлетворяет данному критерию, если его динамическое расстояние порядка $$(1,1)$$ равно 0.
2) Критерий независимости битов (BIC -- Bit Independence Criterion) -- требует, чтобы для любых значений $$i$$, $$j$$ и $$k$$ при инвертировании входного бита $$i$$ на входе узла замен выходные биты $$j$$ и $$k$$ изменялись независимо (то есть вероятность одновременного изменения битов должна быть равна произведению вероятностей изменения отдельных бит). Блок замен удовлетворяет данному критерию, если динамическое расстояние порядка 1 {XOR} - суммы любых двух булевых функций, его составляющих, равно 0.
3) Критерий гарантированного лавинного эффекта (GAC -- Guaranteed Avalanche Criterion) порядка $$\gamma $$ -- выполняется, если при изменении одного бита на входе узла замен на выходе меняются как минимум $$\gamma$$ выходных битов.
4) Критерий XOR-значения для блока $$S$$ размерностью $$n\times m$$ бит -- основывается на построении на основе блока специальной XOR -таблицы, элементы которой вычисляются по следующей формуле:
$$\text{XOR}(S,\alpha,\beta)=\left|x\in \{0,1\}^n \mid S(x)\oplus S(x\oplus \alpha)=\beta \right|,$$где $$\alpha\in\{0,1\}^n\setminus\{0\}$$ это значение может быть представлено в виде числа от $$1$$ до $$2^n-1$$), $$\beta\in \{0,1\}^m$$ (может быть представлено в виде числа от 0 до $$2^m-1$$), $$S(x)$$ --- выходное значение блока замен $$S$$ при входном значении $$x$$.
XOR-значением блока замен называется максимальное значение в его XOR-таблице. Данный критерий требует, чтобы XOR-значение блока было как можно меньшим, в идеале -- 2.
Для построения новых высокоскоростных криптоалгоритмов интерес представляют такие блока S, которые соответствуют одновременно нескольким критериям качества, и, таким образом, позволяют эффективно противостоять одновременно разным видам атак. Одними из наиболее существенных с практической точки зрения является критерий независимости векторов выхода S-блока $$y_j$$ от векторов его входа $$x_i$$.
Более формально: обозначим через $$\{x_i\}_{i=0}^{N-1}$$ множество всевозможных входных векторов блока замен. Очевидно, $$N=2^n$$. Каждому входному вектору $$x_i$$ соответствует выходной вектор $$y_i$$. Через $$x_{ij}$$ и $$y_{ik}$$ обозначим, соответственно, $$j$$-й бит входного вектора и $$k$$-й бит выходного вектора ($$0\leq j\leq n-1$$, $$0\leq k\leq m-1$$). Биты входных векторов $$x_i$$ связаны с номером $$i$$ соотношением:
$$i=x_{i0} + 2 x_{i1} + \ldots + 2^{n-1} x_{i,n-1}.$$Мы также будем записывать выходной вектор $$y_i=S(x_i)$$ шестнадцатеричным числом, связанным с битами соотношениями:
$$y_i = y_{i0} + 2 y_{i1}+\ldots+2^{m-1} y_{i,m-1}.$$Например, если $$y_i=A8_{16}=10101000_2$$, то $$y_{i0} = 0$$, $$y_{i1}=0$$, $$\ldots$$, $$y_{i5}=1$$, $$y_{i6}=0$$, $$y_{i7}=1$$.
Коэффициент корреляции между $$j$$-м входным и $$k$$-м выходным битами узла замен вычисляется по формуле:
$$\rho_{jk}=\frac{\sum_{t=0}^{N-1} x_{tj} y_{tk}- \left(\sum_{t=0}^{N-1} x_{tj}\cdot \sum_{t=0}^{N-1} y_{tk}\right)/N}{\sqrt{\left(\sum_{t=0}^{N-1} x_{tj}^2 - \left(\sum_{t=0}^{N-1} x_{tj}\right)^2/N \right)\cdot\left(\sum_{t=0}^{N-1} y_{tk}^2 - left(\sum_{t=0}^{N-1} y_{tk}\right)^2/N \right)}}.$$Кроме того, для двоичных векторов $$x_i$$, $$y_i$$ верна более простая формула:
$$\rho_{jk}=1-2^{-(n-1)}\sum\limits_{z=0}^{N-1} (x_{z,j} \oplus y_{z,k}).$$Пример 7.7 Вычислим коэффициенты корреляции для следующего блока замен $$4\times 4$$ для алгоритма ГОСТ:
9 8 3 A C D 7 E 0 1 B 2 4 5 F 6
Более подробно: число 0 (нумерация начинается с нуля) переходит в число 9, число 1 переходит в 8, 2 в 3, число 3 в 10, 4 в 12,..., число 15 переходит в 6.
Запишем битовые представления всех чисел нашей подстановки:
| 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 1001 | 1000 | 0011 | 1010 | 1100 | 1101 | 0111 | 1110 | 0000 | 0001 | 1011 | 0010 | 0100 | 0101 | 1111 | 0110 |
Теперь, интерпретируя последовательность битов каждого разряда как множество значений случайной величины, вычислим коэффициенты корреляции между последовательностью входящих битов $$i$$-го разряда и последовательностью выходящих битов $$j$$-го разряда, $$i,j=0,1,2,3$$. Все коэффициенты корреляции посчитаны в таблице 7.4.
| j\k | 0 | 1 | 2 | 3 |
| 0 | -0,25 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | -0,5 |
Мы видим, что биты 1 и 2 группы остаются неизменными, что свидетельствует о плохом качестве данного блока.
Определение 7.9 Нелинейное преобразование назовем оптимальным, если все его коэффициенты корреляции равны нулю.
В работах [5], [2] представлена методика построения оптимальных блоков замен любого размера.
Существуют следующие наиболее распространенные подходы к построению блоков замен:
1) Случайный выбор. Элементы узлов замен выбираются с помощью генератора случайных или псевдослучайных чисел. Это наиболее простой способ, однако в случае небольшого размера блоков, как в алгоритме ГОСТ 28147-89 ($$4{\times}4$$ бит), такой способ может с высокой степенью вероятности привести к генерации таблицы замен с нежелательными с точки зрения стойкости криптостойкости характеристиками нелинейности и лавинного эффекта.
2) Случайный выбор с последующей проверкой. Элементы блоков замен выбираются случайным образом, но после этого полученные результаты проверяются на соответствие различным критериям с отсеиванием тех блоков, которые не выдержали такой проверки. Этот способ также прост, и в то же время он устраняет указанный недостаток первого способа, однако в таком случае встает вопрос о выборе набора критериев для проверки и формировании методики тестирования, так как не существует блоков, одинаково хорошо удовлетворяющих всем предъявляемым к ним требованиям одновременно. Также возможна ситуация, когда блоков замен, удовлетворяющим выбранным требованиям слишком мало по сравнению с мощностью пространства блоков, и генерация таких блоков на основе случайного выбора может требовать больших вычислительных ресурсов.
3) Выбор вручную. Элементы узлов замен выбираются вручную с использованием математических преобразований. Именно эта методика легла в основу разработки DES с его фиксированными S-блоками. Такой подход является наиболее сложным, так как требует разработки и теоретического обоснования методики выбора блоков замен.
4) Математический подход. Элементы узлов замен генерируются при помощи определенного алгоритма, основанного на тех или иных математических принципах. Такой подход при грамотной проектировании алгоритма обеспечивает выбор узлов замен, гарантирующих заданный уровень надежности по отношению к различным методам криптоанализа.
В июне 2015 года приняты два новых криптографических стандарта Российской Федерации: ГОСТ Р 34.12-2015 "Информационная технология. Криптографическая защита информации. Блочные шифры" и ГОСТ Р 34.13-2015 "Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров", которые вступают в действие с 1 января 2016 года.
ГОСТ Р 34.12-2015 содержит описание двух блочных шифров с длинами блока 128 и 64 бит. Шифр ГОСТ 28147-89 с зафиксированными блоками нелинейной подстановки включен в новый ГОСТ Р 34.12-2015 в качестве 64-битового шифра под названием "Магма" ("Magma"). Стандартом определены следующие блоки замен:
| $$S_0 = (12, 4, 6, 2, 10, 5, 11, 9, 14, 8, 13, 7, 0, 3, 15, 1);$$ |
| $$S_1 = (6, 8, 2, 3, 9, 10, 5, 12, 1, 14, 4, 7, 11, 13, 0, 15);$$ |
| $$S_2 = (11, 3, 5, 8, 2, 15, 10, 13, 14, 1, 7, 4, 12, 9, 6, 0);$$ |
| $$S_3 = (12, 8, 2, 1, 13, 4, 15, 6, 7, 0, 10, 5, 3, 14, 9, 11);$$ |
| $$S_4 = (7, 15, 5, 10, 8, 1, 6, 13, 0, 9, 3, 14, 11, 4, 2, 12);$$ |
| $$S_5 = (5, 13, 15, 6, 9, 2, 12, 10, 11, 7, 8, 1, 4, 3, 14, 0);$$ |
| $$S_6 = (8, 14, 2, 5, 6, 9, 1, 12, 15, 4, 11, 0, 13, 10, 3, 7);$$ |
| $$S_7 = (1, 7, 14, 13, 0, 5, 8, 3, 4, 15, 10, 6, 9, 12, 11, 2).$$ |
Приведенный в стандарте набор S-блоков обеспечивает наилучшие характеристики, определяющие стойкость криптоалгоритма к дифференциальному и линейному криптоанализу.
Фиксация блоков нелинейной подстановки сделает алгоритм ГОСТ 28147-89 более унифицированным и исключает использование "слабых" блоков нелинейной подстановки. Кроме того, фиксация в стандарте всех долговременных параметров шифра отвечает принятой международной практике. Новый стандарт ГОСТ Р 34.12-2015 терминологически и концептуально связан с международными стандартами ИСО/МЭК 10116 "Информационные технологии. Методы обеспечения безопасности. Режимы работы для n-битовых блочных шифров" (ISO/IEC 10116:2006 Information technology -- Security techniques - Modes of operation for an n-bit block cipher) и серии ИСО/МЭК 18033 "Информационные технологии. Методы и средства обеспечения безопасности. Алгоритмы шифрования": ИСО/МЭК 18033-1:2005 "Часть 1. Общие положения" (ISO/IEC 18033-1:2005 Information technology -- Security techniques -- Encryption algorithms -- Part 1: General) и ИСО/МЭК 18033-3:2010 "Часть 3. Блочные шифры" (ISO/IEC 18033-3:2010 (Information technology -- Security techniques -- Encryption algorithms – Part 3: Block ciphers).
В стандарт ГОСТ Р 34.12-2015 включен также новый блочный шифр ("Кузнечик") с размером блока 128 бит,см.ниже. Ожидается, что этот шифр будет устойчив ко всем известным на сегодняшний день атакам на блочные шифры.
Блочный шифр Rijndael в октябре 2000 года стал победителем проведенного Национальным Институтом Стандартов и Технологий (NIST) США конкурса на замену признанного ненадежным алгоритма шифрования DES (Data Encryption Standart). В феврале 2001 года прошел через открытое обсуждение и в апреле 2001 года был объявлен новым федеральным стандартом шифрования США AES (Advanced Encryption Standart), см. [4].
Алгоритм шифрования Rijndael имеет переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам. В стандарте AES определена длина блока данных, равная 128 битам.
Промежуточные результаты преобразований, выполняемых в рамках крипто-алгоритма, называют состояниями (State). Состояние можно представить в виде прямоугольного массива байтов.
При размере блока, равном 128 битам, этот 16-байтовый массив (таблицы 7.5, 7.6) имеет 4 строки и 4 столбца (каждая строка и каждый столбец в этом случае могут рассматриваться как 32-разрядные слова). Входные данные для шифра обозначаются как байты состояния в порядке $$S_{00}, S_{10}, S_{20}, S_{30}, S_{01}, S_{11}, \ldots$$.
После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке. В общем случае число столбцов равно длине блока, деленной на 32.
В таблице 7.5 представлен пример 128-разрядного блока данных в виде массива state.
Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками (таблица 7.6. Число столбцов этого массива равно длине ключа, деленной на 32. В стандарте определены ключи всех трех размеров ---128 бит, 192 бита и 256 бит, то есть соответственно 4, 6 и 8 32-разрядных слова (или столбца --- в табличной форме представления). В некоторых случаях ключ шифрования рассматривается как линейный массив 4-байтовых слов. Слова состоят из 4 байтов, которые находятся в одном столбце (при представлении в виде прямоугольного массива).
Зависимость числа раундов $$N_r$$ в алгоритме Rijndael от чисел $$N_b$$ и $$N_k$$ 32-битных слов, соответственно, в блоке и ключе, отражена в таблице 7.7.
| $$S_{00}$$ | $$S_{01}$$ | $$S_{02}$$ | $$S_{03}$$ |
| $$S_{10}$$ | $$S_{11}$$ | $$S_{12}$$ | $$S_{13}$$ |
| $$S_{20}$$ | $$S_{21}$$ | $$S_{22}$$ | $$S_{23}$$ |
| $$S_{30}$$ | $$S_{31}$$ | $$S_{32}$$ | $$S_{33}$$ |
| $$K_{00}$$ | $$K_{01}$$ | $$K_{02}$$ | $$K_{03}$$ |
| $$K_{10}$$ | $$K_{11}$$ | $$K_{12}$$ | $$K_{13}$$ |
| $$K_{20}$$ | $$K_{21}$$ | $$K_{22}$$ | $$K_{23}$$ |
| $$K_{30}$$ | $$K_{31}$$ | $$K_{32}$$ | $$K_{33}$$ |
| $$N_r$$ | $$N_b=4$$ | $$N_b=6$$ | $$N_b=8$$ |
| $$N_k=4$$ | 10 | 12 | 14 |
| $$N_k=6$$ | 12 | 12 | 14 |
| $$N_k=8$$ | 14 | 14 | 14 |
Раунд состоит из четырех различных преобразований:
Алгоритм Rijndael оперирует байтами, которые рассматриваются как элементы конечного поля $$GF(2^{8})$$. Для построения такого поля используется неприводимый многочлен 8-й степени над полем $$\mathbb{Z}_2$$ (см. параграф 1.12). В алгоритме Rijndael используется многочлен $$\varphi (x)=x^{8 }+x^{4 }+x^{3 }+ x+ 1$$.
Для каждого байта $$b=b_0 + b_1 \cdot 2 + \ldots + b_7 \cdot 2^7$$ построим многочлен $$A_b(x)=b_0 + b_1 x + \ldots +b_7 x^7$$, который можно считать элементом построенного нами поля $$GF(2^8)$$. Далее отождествим следующие представления байта:
$$b=A_b(x) = (\overline{b_7 b_6\ldots b_0})_2 = \{zt\},$$где $$z=b_0+2b_1+4b_2+8b_3$$, $$t = b_4+2b_5+4b_6+8b_7$$ --- цифры шестнадцатеричного представления байта.
Операция сложения над элементами поля представляет собой поразрядное сложение по модулю 2, умножение представляет собой операцию умножения со взятием результата по модулю многочлена $$\varphi$$.
Преобразование SubBytes() представляет собой нелинейную замену байтов, выполняемую независимо с каждым байтом $$b$$ состояния.
Пример 7.8 Применим преобразование SubBytes() к байту $$\{83\}$$.
Многочлен, коэффициентами которого являются биты данного числа: $$A(x) = x^7 + x + 1$$. Вначале найдём обратный к нему многочлен относительно умножения в поле $$GF(2^{8})$$. Как уже отмечалось ранее, операция умножения в поле $$GF(2^{8})$$ является операцией умножения многочленов с взятием результата по модулю неприводимого многочлена $$\varphi(x)$$ восьмой степени с использованием операции XOR (сложения по модулю 2) при приведении подобных членов. Так как авторами алгоритма шифрования Rijndael был выбран неприводимый многочлен $$\varphi (x)=x^{8}+x^{4}+x^{3}+x+1$$, то нам необходимо найти такой многочлен $$B(x)=A^{-1}(x)$$, который бы при умножении на многочлен $$x^{7}+x+1$$ по модулю $$\varphi (x) = x^{8}+x^{4}+x^{3}+x+1$$ давал единицу, то есть $$(x^{7}+x+1)\cdot B(x)=1 (\mod (x^{8}+x^{4}+x^{3}+x+1))$$.
С помощью расширенного алгоритма Евклида находим:
$$1=x^7\cdot A(x) + (x^6 + x^2 + x + 1)\cdot \varphi(x).$$Отсюда $$B(x) = A^{-1}(x) = x^7$$. Соответствующий байт: $$b'=1000 0000_2 = \{80\}$$.
Теперь совершим второй этап преобразования.
$$\left(\begin{array}{c} b_0'' \\ b_1'' \\ b_2'' \\ b_3'' \\ b_4'' \\ b_5'' \\ b_6'' \\ b_7'' \end{array}\right)=\left( \begin{array}{cccccccc} 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 1 1 1 0 0 0 1 \\ 1 1 1 1 1 0 0 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 \end{array} \right)\cdot \left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{array}\right)+\left(\begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ \end{array}\right)= \left(\begin{array}{c} 0 \\ %11101100 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{array}\right).$$Результатом проведенного преобразования является значение $$1110\ 1100_2=\{EC\}$$.
Преобразование сдвига строк ShiftRows() выглядит следующим образом: последние 3 строки состояния циклически сдвигаются влево на различное число байтов. Строка 1 сдвигается на $$C_1$$ байт, строка 2 --- на $$C_2$$ байт, и строка 3 --- на $$C_3$$ байт. Значение сдвигов $$C_1$$, $$C_2$$ и $$C_3$$ в Rijndael зависят от длины блока $$N_b$$. Их величины приведены в таблице 7.8.
| $$N_b = 4$$ | $$N_b = 6$$ | $$N_b = 8$$ | ||||||
| $$C_1$$ | $$C_2$$ | $$C_3$$ | $$C_1$$ | $$C_2$$ | $$C_3$$ | $$C_1$$ | $$C_2$$ | $$C_3$$ |
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 3 | 4 |
В стандарте AES, где определен единственный размер блока, равный 128 битам, $$C_1=1$$, $$C_2=2$$, $$C_3=3$$.
Преобразование перемешивания столбцов (MixColumns) действует отдельно на каждом $$i$$-м столбце таблицы состояния, как линейное преорбазование:
$$\begin{equation}\left(\begin{array}{c} S'_{0,i} \\ S'_{1,i} \\ S'_{2,i} \\ S'_{3,i} \end{array}\right)= \left(\begin{array}{cccc} \{02\} \{03\} \{01\} \{01\} \\ \{01\} \{02\} \{03\} \{01\} \\ \{01\} \{01\} \{02\} \{03\} \\ \{03\} \{01\} \{01\} \{02\} \\ \end{array}\right)\cdot \left(\begin{array}{c} S_{0,i} \\ S_{1,i} \\ S_{2,i} \\ S_{3,i} \end{array}\right), \end{equation}$$ $$\{02\}=x, \qquad \{03\}=x+1, \qquad \{01\}=1.$$В результате такого умножения байты $$S_{0,i}, S_{1,i}, S_{2,i}, S_{3,i}$$ заменятся, соответственно, на байты
$$S'_{0,i} = x\cdot S_{0,i} + (x+1)\cdot S_{1,i} + S_{2,i} + S_{3,i},$$ $$S'_{1,i} = S_{0,i} + x\cdot S_{1,i} + (x+1)\cdot S_{2,i} + S_{3,i},$$ $$S'_{2,i} = S_{0,i} + S_{1,i} + x\cdot S_{2,i} + (x+1)\cdot S_{3,i},$$ $$S'_{3,i} = (x+1)\cdot S_{0,i} + S_{1,i} + S_{2,i} + x\cdot S_{3,i}.$$Применение этой операции ко всем четырем столбцам состояния обозначают через MixColumns().
Пример 7.9 Применим операцию MixColumns() к столбцу: $$S_{0,0}=\{2d\}$$, $$S_{1,0}=\{26\}$$, $$S_{2,0}=\{31\}$$, $$S_{1,0}=\{4c\}$$.
Представим элементы $$S_{i,0}$$ полиномами:
$$S_{0,0}=\{2d\}=x^5+x^3+x^2+1,\qquad S_{1,0}=\{26\}=x^5+x^2+x,\\S_{2,0}=\{31\}=x^5+x^4+1,\qquad S_{3,0}=\{4c\}=x^6+x^3+x^2.$$Находим $$S_{0,0}$$ по формулам (7.3)-(7.6). Вычислим многочлен:
$$\begin{align*}x\cdot (x^5+x^3+x^2+1) + (x+1)\cdot (x^5+x^2+x) + (x^5+x^4+1) + \\(x^6+x^3+x^2) = x^6+x^3+x^2+1\end{align*}$$и возьмём остаток от его деления на $$\varphi(x)=x^8 + x^4 + x^3 + x + 1$$. Имеем:
$$S'_{0,0} = x^6+x^3+x^2+1 ~(\mod \varphi(x) ) = \{4d\}.$$Аналогично находим остальные компоненты столбца:
$$\begin{align*}S'_{1,0}=(x^5+x^3+x^2+1) + x\cdot (x^5+x^2+x) + (x+1)(x^5+x^4+1) + \\ (x^6+x^3+x^2) = x^6+x^5+x^4+x^3+x^2+x \equiv \\ \equiv x^6+x^5+x^4+x^3+x^2+x ~(\mod \varphi(x) ) = \{7e\},\end{align*} % \begin{align*}S'_{2,0}=(x^5+x^3+x^2+1) + (x^5+x^2+x) + x\cdot (x^5+x^4+1) + \\ (x+1)\cdot (x^6+x^3+x^2) = x^7+x^5+x^4+x^3+x^2+1 \equiv \\ \equiv x^7+x^5+x^4+x^3+x^2+1 ~(\mod \varphi(x) ) = \{bd\}, \end{align*} % \begin{align*}S'_{3,0}=(x+1)\cdot (x^5+x^3+x^2+1) + (x^5+x^2+x) + (x^5+x^4+1) + \\ x\cdot (x^6+x^3+x^2) = x^7 + x^6 + x^5 + x^4 + x^3 \equiv\\ \equiv x^7 + x^6 + x^5 + x^4 + x^3 ~(\mod \varphi(x) ) = \{f8\}. \end{align*}$$На рисунке 7.5 показано преобразование исходного столбца $$S_{10}$$ в столбец $$S_{10}'$$ с помощью операции MixColumns().
(рис 7.5) Применение MixColumns() к столбцу состояния
В операции добавления подключа (AddRoundKey) подключ $$K^{(r)}$$ раунда $$r$$ добавляется к данным с помощью операции побитового сложения по модулю два (операция XOR). Это сложение также можно рассматривать как сложение элементов поля $$GF(2^8)$$:
Подключи вырабатываются из исходного секретного ключа шифрования с помощью алгоритма выработки ключей (Key Schedule). Длина подключа (в 32-разрядных словах) равна длине блока $$N_b$$ слов.
Подключи, используемые в каждом раунде шифрования, получаются из исходного секретного ключа шифрования с помощью алгоритма выработки подключей. Он содержит два компонента.
Расширение ключа. При расширении ключа нам потребуются следующие операции, применяемые к словам $$v$$, состоящим из байт $$v_0, v_1, v_2, v_3$$ (будем использовать обозначение $$v=\{v_0,v_1,v_2,v_3\}$$):
$$\begin{align*}\text{RotWord}(\{v_0,v_1,v_2,v_3\}) = \{v_1,v_2,v_3,v_0\},\\ \text{SubWord}(\{v_0,v_1,v_2,v_3\}) = \{\text{SubBytes}(v_0),\text{SubBytes}(v_1),\\ \text{SubBytes}(v_2),\text{SybBytes}(v_3)\}. \end{align*}$$Кроме того, определим константы-слова $$\text{Rcon}[i]=\{x^{i-1}, 0, 0, 0\}$$. Напомним, что под байтом $$x^{i-1}$$ понимается элемент поля $$GF(2^8)$$, то байт состоит из коэффициентов из $$\mathbb{Z}_2$$ остатка $$r(x)$$ от деления $$x^{i-1}$$ на неприводимый многочлен $$\varphi(x)$$.
Под сложением слов $$u+v$$ будем понимать их побитовое сложение по модулю два, что эквивалентно побайтовому сложению в поле $$GF(2^8)$$. Иногда также пишут $$u\ \text{XOR}\ v$$.
Первые слова $$w[0], w[1],\ldots, w[N_k-1]$$ расширенного ключа совпадают со словами ключа шифрования. Последующие слова $$w[i]$$ вычисляются последовательно при $$i=N_k, N_k+1,\ldots$$ по следующему алгоритму:
Выбор раундовых подключей. Ключ $$K^{(r)}$$ $$r$$-го раунда ($$1\leq r\leq N_r$$) состоит из слов $$w[N_b\cdot i], w[N_b\cdot i + 1], \ldots w[N_b\cdot (i+1)-1]$$. Например, при $$N_b = 4$$ получаем:
$$w=\{w[0],w[1],w[2],w[3], \underbrace{w[4],w[5],w[6],w[7]}_{\text{Подключ} K^{(1)}}, \underbrace{w[8],w[9],w[10],w[11]}_{\text{Подключ} K^{(2)}},\ldots \}.$$Как известно, для оценки качества блоков замен используются различные критерии. Одним из таких критериев является максимум модуля коэффициентов корреляции, имеет значение также количество нулей корреляционной матрицы. Для выбранного в алгоритме Rijndael неприводимого многочлена $$\varphi(x)=x^{8}+x^{4}+x^{3}+x+1$$ корреляционная матрица следующая:
$$\begin{scriptsize} \left( \begin{array}{cccccccc} -0,04690,06250,0313-0,0156-0,0938-0,01560,0938-0,0938\\ 0,06250,0938-0,0625-0,0938-0,10940,015600,0781\\ 0,0313-0,0625-0,0938-0,04690,015600,07810,0625\\ -0,0156-0,0938-0,0469-0,06250,0625-0,0625-0,06250,1250\\ -0,0938-0,10940,01560,06250,09380,04690,0313-0,0156\\ -0,01560,01560-0,06250,0469-0,0313-0,0156-0,0938\\ 0,093800,0781-0,0625-0,0313-0,0156-0,0938-0,0156\\ -0,09380,07810,06250,1250-0,0156-0,0938-0,01560,0938 \end{array} \right) \end{scriptsize}$$Заметим, что за счет выбора другого неприводимого многочлена степени 8 над полем $$GF(2^8)$$ можно получить корреляционную матрицу с бОльшим количеством нулевых элементов, что затруднит корреляционный криптоанализ, однако упростит аппроксимацию шифра аффинными булевыми функциями за счет большего количества единичных значений элементов в полной матрице коэффициентов корреляции со всеми аффинными функциями.
Пример 7.10 Применение полинома (десятичный эквивалент) 355 наиболее затруднит аппроксимацию шифра аффинными булевыми функциями, а применение полинома 425 наиболее затруднит корреляционный криптоанализ, однако упростит аппроксимацию аффинными булевыми функциями.
В таблице 7.9 приведен пример оптимального по корреляционному критерию блока замен длины 256 [5].
| $$S_8$$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 5C | 58 | 04 | F2 | 02 | F9 | A1 | AE | F6 | 05 | AB | AA | 57 | 5D | F1 | 0F |
| 1 | A9 | A3 | 0D | F5 | 06 | F3 | 5F | 5E | FA | 07 | 5B | 54 | AC | A8 | F0 | 00 |
| 2 | B8 | BC | 12 | E4 | 19 | E2 | 4E | 41 | E5 | 16 | 4A | 4B | BD | B7 | EF | 11 |
| 3 | 43 | 49 | 15 | ED | 13 | E6 | BE | BF | E7 | 1A | B4 | BB | 48 | 4C | E0 | 10 |
| 4 | 98 | 9C | 32 | C4 | 39 | C2 | 6E | 61 | C5 | 36 | 6A | 6B | 9D | 97 | CF | 31 |
| 5 | 63 | 69 | 35 | CD | 33 | C6 | 9E | 9F | C7 | 3A | 94 | 9B | 68 | 6C | C0 | 30 |
| 6 | 7C | 78 | 24 | D2 | 22 | D9 | 81 | 8E | D6 | 25 | 8B | 8A | 77 | 7D | D1 | 2F |
| 7 | 89 | 83 | 2D | D5 | 26 | D3 | 7F | 7E | DA | 27 | 7B | 74 | 8C | 88 | D0 | 20 |
| 8 | D8 | DC | 72 | 84 | 79 | 82 | 2E | 21 | 85 | 76 | 2A | 2B | DD | D7 | 8F | 71 |
| 9 | 23 | 29 | 75 | 8D | 73 | 86 | DE | DF | 87 | 7A | D4 | DB | 28 | 2C | 80 | 70 |
| A | 3C | 38 | 64 | 92 | 62 | 99 | C1 | CE | 96 | 65 | CB | CA | 37 | 3D | 91 | 6F |
| B | C9 | C3 | 6D | 95 | 66 | 93 | 3F | 3E | 9A | 67 | 3B | 34 | CC | C8 | 90 | 60 |
| C | 1C | 18 | 44 | B2 | 42 | B9 | E1 | EE | B6 | 45 | EB | EA | 17 | 1D | B1 | 4F |
| D | E9 | E3 | 4D | B5 | 46 | B3 | 1F | 1E | BA | 47 | 1B | 14 | EC | E8 | B0 | 40 |
| E | F8 | FC | 52 | A4 | 59 | A2 | 0E | 01 | A5 | 56 | 0A | 0B | FD | F7 | AF | 51 |
| F | 03 | 09 | 55 | AD | 53 | A6 | FE | FF | A7 | 5A | F4 | FB | 08 | 0C | A0 | 50 |
См. ([3])
Структура шифра "Кузнечик" является вариантом подстановочно-перестановочной сети (SP-сети). Каждый раунд состоит из наложения ключа с помощью операции побитового XOR, нелинейной подстановки (S-блоков замен) и линейного перемешивания.
За счет преобразования всего блока данных на каждом шаге обеспечивается гораздо более быстрое перемешивание входных данных по сравнению со схемой Фейстеля. Кроме того, слой линейного преобразования конструируется таким образом, чтобы обеспечить максимально возможное рассеивание. Для этих целей используется так называемая MDS матрица --- используемая в качестве линейного преобразования $$f(x): F^n \rightarrow F^m$$ матрица над конечным полем $$F$$, такая, что любые два вектора вида $$(x, f(x)) \in F^{n+m}$$ имеют как минимум $$m + 1$$ различающихся компонент. То есть набор векторов вида $$(x, f(x))$$ обладает свойством максимальной разнесенности (maximum distance separable). Поэтому адекватная стойкость таких алгоритмов достигается за меньшее, по сравнению со схемой Фейстеля, число раундов.
Как и в алгоритме AES, линейное преобразование алгоритма "Кузнечик" использует операции с байтами, представляя их как элементы поля Галуа $$F=GF(2^8)$$. В "Кузнечике" оно построенного с помощью неприводимого полинома $$m(x) = x^8 + x^7 + x^6 + x + 1$$. SP-сети с линейным преобразованием, состоящим из двух частей, первая из которых похожа на операцию MixColumns, а вторая --- на операцию ShiftRows алгоритма AES, называют AES-подобными (like AES).
Байты-константы нам будет удобно зававать целыми числами, двоичные разряды которых есть соответствующие коэффициенты полинома. Например, под числом $$130 = 128 + 2 = 2^7 + 2^1$$ мы будем понимать байт $$x^7 + x^1 \in GF(2^8)$$.
Шифр "Кузнечик" имеет размер входного блока данных 128 бит, длину ключа 256 бит и выполняет 10 раундов шифрования. В последнем раунде выполняется только одна операция --- наложения раундового ключа.
Первой выполняется операция наложения ключа раунда с помощью побитового XOR: $$X[k](a) = k\oplus a$$.
Затем входной 128-битовый блок $$a$$ алгоритма шифрования представляется в виде последовательности 16 байтов, которые нумеруются справа налево, начиная с 0: $$a=a_{15} || a_{14} || \ldots || a_1 || a_0$$, где знаком $$||$$ обозначена операция конкатенации строк.
К каждому байту применяется нелинейная подстановка, задаваемая массивом
$$S$$ = (252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241. 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182).
Поскольку каждый байт $$a_i$$ может принимать значение от 0 до 255, массив $$S$$ имеет 256 элементов. Это значит, что при $$a_i=0$$ значение $$a_i$$ будет заменено на $$S(0)= 252$$, при $$a_i = 1$$ --- на $$S(1)=238$$, и так далее (все числа записаны в десятеричном виде). Для выходного блока в целом нелинейная подстановка может быть определена как
$$S(a)=S(a_{15}||\ldots ||a_0) = S(a_{15})||\ldots ||S(a_0).$$Линейное перемешивание $$L$$ шифра "Кузнечик" может быть описано с помощью линейного регистра сдвига $$R$$:
Шифрование 128-битного входного блока $$a$$ описывается следующей формулой:
$$E(a) = X[K_{10}LSX[K_9]LSX[K_8]\ldots LSX[K_1](a).$$Здесь $$K_i$$ --- раундовые ключи, записанные подряд преобразования $$LSX[K_i]$$ обозначают последовательное применение преобразований справа налево. То есть, сначала выполняется прибавление ключа, затем нелинейная подстановка $$S$$, затем линейное перемешивание $$L$$.
См. ([6])
В настоящее время используется большое количество самых разных алгоритмов блочного шифрования. Из всего многообразия мы расскажем лишь о тех алгоритмах, которые либо являются очень надежными, либо своим появлением оказали влияние на развитие криптографии. Одним из таких алгоритмов является IDEA.
Первый вариант шифра IDEA, предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey), появился в 1990 году. Он назывался PES (Proposed Encryption Standard, предложенный стандарт шифрования). В следующем году, после демонстрации Бихамом и Шамиром возможностей дифференциального криптоанализа, авторы усилили свой шифр против такого вскрытия и назвали новый алгоритм IPES (Improved Proposed Encryption Standard, улучшенный предложенный стандарт шифрования). В 1992 году название IPES было изменено на IDEA (International Data Encryption Algorithm, международный алгоритм шифрования данных).
IDEA основывается на некоторых впечатляющих теоретических положениях и, хотя криптоанализ добился некоторых успехов в отношении вариантов с уменьшенным количеством этапов, алгоритм все еще кажется сильным.
Его сегодняшняя известность объясняется тем, что он является частью PGP.
IDEA является блочным шифром, он работает с 64-битовыми блоками открытого текста. Длина ключа - 128 битов. Для шифрования и дешифрирования используется один и тот же алгоритм.
Как и другие, уже рассмотренные блочные шифры IDEA использует и запутывание, и рассеяние. Философия, лежащая в основе проекта, представляет собой "объединение операций из различных алгебраических групп". Смешиваются три алгебраические операции, и все они могут быть легко реализованы как аппаратно, так и программно.
Все операции выполняются над 16-битовыми субблоками. Эти три операции несогласованы в том смысле, что:
Комбинирование этих трех операций обеспечивает комплексное преобразование входа, существенно затрудняя криптоанализ IDEA по сравнению с DES, который базируется исключительно на операции "исключающее ИЛИ".
Все эти операции (а в алгоритме используются только они, перестановки на битовом уровне не применяются) работают с 16-битовыми подблоками. (Этот алгоритм даже эффективнее на 16-битовых процессорах.)
Схема IDEA представлена на рисунке 7.6. 64-битовый блок данных делится на четыре 16-битовых подблока: $$X_1$$, $$X_2$$, $$X_3$$, $$X_4$$. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алгоритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умножениям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец, четыре подблока объединяются с четырьмя подключами в окончательном преобразовании.
На каждом этапе события происходят в следующей последовательности:
(рис 7.6) Схема алгоритма IDEA
Выходом этапа являются четыре подблока - результаты действий (11), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.
Затем выполняется заключительный, 9-й этап преобразования:
Наконец четыре подблока снова соединяются, образуя шифртекст.
Пример 7.11 Выполнить первый раунд зашифрования алгоритмом IDEA. Ключ: 1D52 34BC 891C 9C9B 1CC2 4363 A32B 132C, блок открытого текста: 89C1 B11D 63F0 FF23. Ключ и открытый текст задаются шестнадцатеричными последовательностями. Каждые четыре последовательных шестнадцатеричных разряда $$WXYZ$$ обозначают 16-битный блок $$Z+16(Y+16(X+16W))$$.
Решение.
Вначале выберем подключи первого раунда. Это первые 6 16-битных блоков ключа.
В обозначениях рисунка 7.6 имеем: $$X_1=89C1$$, $$X_2=B11D$$, $$X_3=63F0$$, $$X_4=FF23$$, $$Z_1^{(1)}=1D52$$, $$Z_2^{(1)}=34BC$$, $$Z_3^{(1)}=891C$$, $$Z_4^{(1)}=9C9B$$, $$Z_5^{(1)}=1CC2$$, $$Z_6^{(1)}=4363$$.
Будем обозначать результат $$i$$-го шага в алгоритме параграфа 7.7.2 через $$A_i$$.
Все операции будем проводить в шестнадцатеричной системе счисления. Результат применения одного раунда обозначим через $$X'_1$$, $$X'_2$$, $$X'_3$$, $$X'_4$$.
| $$A_1 = X_1 \odot Z_1^{(1)} = 89C1\odot 1D52 = (89C1\cdot 1D52)~(\mod 10001) = ED0C$$; |
| $$A_2 = X_2 \boxplus Z_2^{(1)} = B11D \boxplus 34BC = (B11D+34BC)~(\mod 10000) = E5D9$$; |
| $$A_3 = X_3 \boxplus Z_3^{(1)} = 5E1B \boxplus 891C = (63F0+891C)~(\mod 10000) = ED0C$$; |
| $$A_4 = X_4 \odot Z_4^{(1)} = FF23 \odot 9C9B = (FF23\cdot 9C9B)~(\mod 10001) = 321E$$; |
| $$A_5 = A_1 \oplus A_3 = ED0C \oplus ED0C = 0000$$; |
| $$A_6 = A_2 \oplus A_4 = E5D9 \oplus 321E = D7C7$$; |
| $$A_7 = A_5 \odot Z_5^{(1)} = 0000 \odot 1CC2 = (10000\cdot 1CC2)~(\mod 10001) = E33F$$; |
| $$A_8 = A_6\boxplus A_7 = D7C7\boxplus E33F =(D7C7+E33F)~(\mod 10000) = BB06$$; |
| $$A_9 = A_8 \odot Z_6^{(1)} = BB16\odot 4363 = (BB06\cdot 4363)~(\mod 10001) = B418$$; |
| $$A_{10} = A_7 \boxplus A_9 = E33F\boxplus B418 = (E33F+B418)~(\mod 10000) = 9757$$; |
| $$X'_1 = A_{11} = A_1 \oplus A_9 = ED0C \oplus B418 = 5914$$; |
| $$X'_2 = A_{12} = A_3 \oplus A_9 = ED0C \oplus B418 = 5914$$; |
| $$X'_3 = A_{13} = A_2 \oplus A_{10} = E5D9 \oplus 9757 = 728E$$; |
| $$X'_4 = A_{14} = A_4 \oplus A_{10} = 321E \oplus 9757 = A549$$. |
Создание подключей $$Z^{(i)}_j$$ также относительно несложно. Алгоритм использует всего 52 подключа (по шесть для каждого из восьми циклов и еще четыре для заключительного этапа). Сначала 128-битовый ключ делят на восемь 16-битовых подключей. Это -- первые восемь подключей для алгоритма (шесть подключей -- для первого цикла и первые два подключа -- для второго цикла). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей. Первые четыре из них используют во втором цикле; последние четыре -- в третьем цикле. Ключ снова циклически сдвигается влево еще на 25 бит для получения следующих восьми подключей и т.д., пока выполнение алгоритма не завершится.
Расшифрование осуществляют аналогичным образом, за исключением того, что порядок использования подключей --- обратный, и ряд значений подключей заменяется на обратные значения. Порядок использования подключей при зашифровании и расшифровании приведён в таблице 7.10. Через $$-a$$ обозначается противоположный к $$a$$ по модулю $$65536$$ элемент, через $$a^{-1}$$ --- обратный по умножению по модулю $$65537$$.
| Цикл | Подключи зашифрования | Подключи расшифрования |
|---|---|---|
| 1 | $$Z_1^{(1)},Z_2^{(1)},Z_3^{(1)},Z_4^{(1)},Z_5^{(1)},Z_6^{(1)}$$ | $${Z_1^{(9)}}^{-1},-Z_2^{(9)},-Z_3^{(9)},{Z_4^{(9)}}^{-1},Z_5^{(8)},Z_6^{(8)}$$ |
| 2 | $$Z_1^{(2)},Z_2^{(2)},Z_3^{(2)},Z_4^{(2)},Z_5^{(2)},Z_6^{(2)}$$ | $${Z_1^{(8)}}^{-1},-Z_2^{(8)},-Z_3^{(8)},{Z_4^{(8)}}^{-1},Z_5^{(7)},Z_6^{(7)}$$ |
| 3 | $$Z_1^{(3)},Z_2^{(3)},Z_3^{(3)},Z_4^{(3)},Z_5^{(3)},Z_6^{(3)}$$ | $${Z_1^{(7)}}^{-1},-Z_2^{(7)},-Z_3^{(7)},{Z_4^{(7)}}^{-1},Z_5^{(6)},Z_6^{(6)}$$ |
| 4 | $$Z_1^{(4)},Z_2^{(4)},Z_3^{(4)},Z_4^{(4)},Z_5^{(4)},Z_6^{(4)}$$ | $${Z_1^{(6)}}^{-1},-Z_2^{(6)},-Z_3^{(6)},{Z_4^{(6)}}^{-1},Z_5^{(5)},Z_6^{(5)}$$ |
| 5 | $$Z_1^{(5)},Z_2^{(5)},Z_3^{(5)},Z_4^{(5)},Z_5^{(5)},Z_6^{(5)}$$ | $${Z_1^{(5)}}^{-1},-Z_2^{(5)},-Z_3^{(5)},{Z_4^{(5)}}^{-1},Z_5^{(4)},Z_6^{(4)}$$ |
| 6 | $$Z_1^{(6)},Z_2^{(6)},Z_3^{(6)},Z_4^{(6)},Z_5^{(6)},Z_6^{(6)}$$ | $${Z_1^{(4)}}^{-1},-Z_2^{(4)},-Z_3^{(4)},{Z_4^{(4)}}^{-1},Z_5^{(3)},Z_6^{(3)}$$ |
| 7 | $$Z_1^{(7)},Z_2^{(7)},Z_3^{(7)},Z_4^{(7)},Z_5^{(7)},Z_6^{(7)}$$ | $${Z_1^{(3)}}^{-1},-Z_2^{(3)},-Z_3^{(3)},{Z_4^{(3)}}^{-1},Z_5^{(2)},Z_6^{(2)}$$ |
| 8 | $$Z_1^{(8)},Z_2^{(8)},Z_3^{(8)},Z_4^{(8)},Z_5^{(8)},Z_6^{(8)}$$ | $${Z_1^{(2)}}^{-1},-Z_2^{(2)},-Z_3^{(2)},{Z_4^{(2)}}^{-1},Z_5^{(1)},Z_6^{(1)}$$ |
| 9 | $$Z_1^{(9)},Z_2^{(9)},Z_3^{(9)},Z_4^{(9)}$$ | $${Z_1^{(1)}}^{-1},-Z_2^{(1)},-Z_3^{(1)},{Z_4^{(1)}}^{-1}$$ |
Пример 7.12 Имея ключ 1D52 34BC 891C 9C9B 1CC2 4363 A32B 132C для алгоритма IDEA, найти подключи четвертого раунда расшифровки. Порядок записи бит числа --- от младшего к старшему.
Отметим, что существует два способа записи бит в памяти ЭВМ: от старшего к младшему (Big-Endian) и от младшего к старшему (Little-Endian). Big-Endian использовался в ранних архитектурах ЭВМ, и для сохранения обратной совместимости остался в сетевых протоколах и некоторых форматах файлов. Little-Endian используется практически во всех современных архитектурах, поэтому мы используем его в нашей задаче.
Решение. Согласно таблице 7.10, нам нужно найти подключи $${Z_1^{(6)}}^{-1}$$, $$-Z_2^{(6)}$$, $$-Z_3^{(6)}$$, $${Z_4^{(6)}}^{-1}$$, $$Z_5^{(5)}$$, $$Z_6^{(5)}$$.
Поэтому необходимо сначала найти необходимые нам подключи для 5-го и 6-го раундов $$Z_1^{(6)}$$, $$Z_2^{(6)}$$, $$Z_3^{(6)}$$, $$Z_4^{(6)}$$, $$Z_5^{(5)}$$, $$Z_6^{(5)}$$.
Обозначим $$i$$-й 16-битный блок ключа, $$n$$ раз циклически сдвинутого влево на 25 бит, через $$K_i^{(n)}$$. Тогда данный нам исходный ключ состоит из блоков $$K_1^{(0)},\ K_2^{(0)},\ \ldots,\ K_8^{(0)}$$; нужный нам подключ $$Z_i^{(j)}$$ равен некоторому блоку $$K_m^{(n)}$$. Выпишем это соответствие, записывая индексы друг под другом:
| $$n:$$ | 000000001111111122222222333333334444444455555555 |
| $$m:$$ | 123456781234567812345678123456781234567812345678 |
| $$j:$$ | 111111222222333333444444555555666666777777888888 |
| $$i:$$ | 123456123456123456123456123456123456123456123456 |
В таблице отмечены требуемые нам подключи зашифрования. Имеем:
$$Z_1^{(6)}=K_7^{(3)},\ Z_2^{(6)}=K_8^{(3)}, Z_3^{(6)}=K_1^{(4)}, Z_4^{(6)}=K_2^{(4)}, Z_5^{(5)}=K_5^{(3)}, Z_6^{(5)}=K_6^{(3)}.$$Для выполнения циклического сдвига запишем наш ключ в бинарном виде. Для этого переведём каждый шестнадцатеричный блок в двоичную систему счисления:
$$1D52_{16} = 0001110101010010_2; \quad 34BC_{16}=0011010010111100_2;\quad \ldots$$и выпишем блоки последовательно, начиная от младшего бита к старшему:
$$0100101010111000\quad 0011110100101100\quad 0011100010010001\quad 1101100100111001 \\ 0100001100111000\quad 1100011011000010\quad 1101010011000101\quad 0011010011001000$$Для получения блока $$K_5^{(3)}$$ нужно сдвинуть ключ на $$3\cdot 25=75$$ бит влево. В полученной битовой последовательности биты с 1 по 16 --- блок $$K_1^{(3)}$$, c 17 по 32 --- блок $$K_2^{(3)}$$, ..., с 65 по 80 --- блок $$K_5^{(3)}$$. Таким образом, в исходном ключе блок $$K_5^{(3)}$$ располагается с $$75+65 - 128 = 12$$ по $$75+80 - 128 = 28$$ биты: 1100000111101001. Итак, $$K_5^{(3)} = 1001011110000011_2 = 38787_{10}=9383_{16}$$. Следующие 16 бит (0110000111000100) составляют ключ $$K_6^{(3)} = 0010001110000110_2 = 9094_{10}=2386_{16}$$. Следом идут $$K_7^{(3)} = 1001001101110001_2 = 37745_{10}=9371_{16}$$, $$K_8^{(3)}=1001100001010011_2 = 38995_{10}=9853_{16}$$.
Для получения $$K_1^{(4)}$ и $K_2^{(4)}$$ нужно сдвинуть ключ на 100 бит влево. В полученной битовой последовательности биты с 1 по 16 --- блок $$K_1^{(4)}$$, а с 17 по 32 --- блок $$K_2^{(4)}$$. Имеем:
| $$K_1^{(4)} = 1100101000110010_2 = 51762_{10}=CA32_{16},$$ |
| $$K_2^{(4)} = 0010000100110010_2 = 8498_{10}=2132_{16}.$$ |
Теперь мы можем найти подключи для расшифрования:
| $${Z_1^{(6)}}^{-1} = {K_7^{(3)}}^{-1} = 37745^{-1}~\mod 65537 = 53013_{10} = CF15_{16};$$ |
| $$-Z_2^{(6)} = -K_8^{(3)} = -38995~\mod 65536 = 26541_{10}=67AD_{16};$$ |
| $$-Z_3^{(6)} = -K_1^{(4)} = -51762~\mod 65536 = 13774_{10}=35CE_{16};$$ |
| $${Z_4^{(6)}}^{-1} = {K_2^{(4)}}^{-1} = 8498^{-1}~\mod 65537 = 4928_{10}=1340_{16};$$ |
| $$Z_5^{(5)} = K_5^{(3)} =9383_{16};$$ |
| $$Z_6^{(5)} = K_6^{(3)}=2386_{16}.$$ |
См. [1]
Через $$P_i$$ и $$C_i$$ обозначим открытый текст и соответствующий шифртекст, $$E$$ --- алгоритм шифрования.
Величины $$C_0$$ в режимах CBC и CFB и $$K_0$$ в режиме $$OFB$$ необходимо инициализировать некоторой величиной $$IV$$, називаемой вектором инициализации.
| Режим | Формула | Типичные области применения |
|---|---|---|
| Электронная кодовая книга (ЕСВ -- Electronic Code-book) | $$C_i = E_K(P_i)$$ | Защищенная передача отдельных значений (например, ключа шифрования) |
| Сцепление шифрованных блоков (СВС --- Cipher Block Chaining) | $$C_i = E_K(P_i\oplus C_{i-1})$$ | Поблочная передача данных общего назначения. Аутентификация |
| Шифрованная обратная связь (CFB -- Cipher Feedback) | $$C_i = E_K(C_{i-1}) \oplus P_i$$ | Потоковая передача данных общего назначения. Аутентификация |
| Обратная связь по выходу (OFB -- Output Feedback) | $$T_i = E_K(T_{i-1})$, $C_i = K_i\oplus P_i$$ | Потоковая передача данных по каналам с помехами (например, по спутниковой связи) |
| a) | Перечислите основные недостатки алгоритма DES и предложите пути их устранения. |
| b) | Выпишите в явном виде подстановку $$IP^{-1}$$. Найдите её разложение в произведение независимых циклов и вычислите её порядок. |
| c) | Докажите, что все преобразования стандарта DES являются четными подстановками на \ множестве всех 64-битовых слов. |
| d) | Докажите свойство дополнительности DES: $$E_{\overline{k}}(\overline{x})=\overline{E_k(x)},$$ где черта означает взятие дополнительного вектора, т.е. $$x\oplus \overline{x} = 0$$. |
Перечислите отличия ГОСТ 28147-89 от DES. Докажите, что всякое преобразование стандарта ГОСТ 28147-89 обратимо и является четной подстановкой на множестве всех 64-битовых слов.
| a) | Какова вероятность того, что $$E_k$$ и $$E_{K'}$$ на самом деле являются разными отображениями? |
| b) | Какова вероятность того, что $$E_k$$ и $$E_{K'}$$ согласуются на другом наборе из $$t'$$ соответствующих пар открытого и шифрованного текста, где $$0\leq t'\leq N-1$$? |
| a) | нужно, чтобы возможные \ искажения битов при передаче данных не распространялись на последующие порции данных? |
| b) | нужна большая надежность в отношении нарушений типа модификации потока данных? |
| c) | Почему при передаче достаточно длинных сообщений режим ECB может не обеспечивать необходимый уровень защиты? |
| d) | Обоснуйте необходимость защиты инициализующего вектора (IV) в режиме сцепления шифрованных блоков (CBC). |
| e) | Алгоритм DES -- это блочный шифр с размером блока 64 бит. |
Однако бывает необходимо каждый символ шифровать и сразу передавать адресату, не дожидаясь окончания шифрования остальной части сообщения. Предложите способ использовать DES для этого.
| a) | $$f={x}_{1} {x}_{2}\oplus {x}_{1} {x}_{3} \oplus {x}_{2} {x}_{3}\oplus {x}_{1} {x}_{2} {x}_{3}$$; |
| b) | $$f={x}_{1}\oplus {x}_{2}\oplus {x}_{2} {x}_{3}$$; |
| c) | $$f={x}_{1} {x}_{2}\oplus {x}_{3}\oplus {x}_{1} {x}_{2} {x}_{4}$$. |
| a) | Почему операция умножения в IDEA выполняется по модулю $$2^{16}+1$$, а не по модулю $$2^{16}$$? |
| b) | Почему операция сложения в IDEA выполняется по модулю $$2^{16}$$, а не по модулю $$2^{16}+1$$? |
| c) | Докажите, что никакие две из трех операций IDEA не подчиняются дистрибутивному закону. Например: $$a\oplus (b\odot c)\neq (a\oplus b)\odot (a\oplus c)$$. |
| d) | Докажите,что никакие две из трех операций IDEA не подчиняются ассоциативному закону. Например: $$a\boxplus(b\oplus c)\neq (a\boxplus b)\oplus c$$. |
Мы здесь приведем краткое описание алгоритма DES, подробное изложение можно найти в [1], [2], [3], [4].
DES представляет собой блочный шифр, он шифрует данные 64-битовыми блоками. На вход алгоритма подается 64-битовый блок открытого текста, а выходит 64-битовый блок шифртекста. DES является симметричным алгоритмом: для шифрования и расшифрования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа).
Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определяется ключом.
Алгоритм является комбинацией двух основных методов шифрования: смещения и диффузии. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз.
Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-x.
Схема алгоритма представлена на рисунке 7.1.
(рис 7.1) DES
| 58 | 50 | 42 | 34 | 26 | 18 | 10 | 2 | 60 | 52 | 44 | 36 | 28 | 20 | 12 | 4 |
| 62 | 54 | 46 | 38 | 30 | 22 | 14 | 6 | 64 | 56 | 48 | 40 | 32 | 24 | 16 | 8 |
| 57 | 49 | 41 | 33 | 25 | 17 | 9 | 1 | 59 | 51 | 43 | 35 | 27 | 19 | 14 | 3 |
| 61 | 53 | 45 | 37 | 29 | 21 | 13 | 5 | 63 | 55 | 47 | 39 | 31 | 23 | 15 | 7 |
Биты входных данных нумеруются по порядку, начиная с 1, и переставляются подстановкой $$IP$$ согласно таблице 7.1. Таблица трактуется следующим образом: значение 58 бита входной последовательности перемещается в битовую позицию 1, бит 50 -- в битовую позицию 2, бит 42 -- в битовую позицию 3, и так далее.
После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называемых функцией $$f$$, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая половины объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной).
На каждом этапе (см. рис 7.2) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией $$f$$. Затем результат функции $$f$$ объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов DES.
(рис 7.2) Один раунд шифра DES
Если $$B_i$$ --- результат $$i$$-ой итерации, $$L_i$$ и $$R_i$$ --- левая и правая половины $$B_i$$, $$K_i$$ --- 48-битовый ключ для этапа $$i$$, a $$f$$ - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:
$$L_i = R_{i-1}, \qquad R_i = L_{i-1}\oplus f(R_{i-1},K_i).$$В алгоритме ГОСТ ключевая информация состоит из двух структур данных. Помимо собственно ключа, необходимого для всех шифров, она содержит еще и таблицу замен. Ниже приведены основные характеристики ключевых структур ГОСТа.
Ключ является массивом из восьми 32-битовых элементов кода, далее в настоящей работе он обозначается $$K: K=\{K_i\}_{i=0}^7$$.
В ГОСТе элементы ключа используются как 32-разрядные целые числа без знака: $$0\leq K_i<2^{32}$$. Таким образом, размер ключа составляет $$32\cdot 8=256$$ бит, или 32 байта.
Таблица замен может быть представлена в виде $$8\times 16$$-матрицы, содержащей 4-битовые элементы, которые можно представить в виде целых чисел от 0 до 15. Строки таблицы замен называются узлами замен, они должны содержать различные значения, то есть каждый узел замен должен содержать 16 различных чисел от 0 до 15 в произвольном порядке.
Основной шаг криптопреобразования по своей сути является оператором, определяющим преобразование 64-битового блока данных. Дополнительным параметром этого оператора является 32-битовый блок, в качестве которого используется какой-либо элемент ключа. Схема алгоритма основного шага приведена на рисунке 7.3.
Ниже даны пояснения к алгоритму основного шага.
(рис 7.3) Схема одного раунда преобразования по алгоритму ГОСТ 28147-89
Шаг 0. Определяет исходные данные для основного шага криптопреобразования: $$N_i$$ -- преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая ($$A_i$$) и старшая ($$B_i$$) части обрабатываются как отдельные 32-битовые целые числа без знака. Таким образом, можно записать $$N_i=(A_i, B_i)$$. $$K_i$$ -- 32-битовый элемент ключа;
Шаг 1. Сложение с ключом. Младшая половина преобразуемого блока складывается по модулю $$2^{32}$$ с используемым на шаге элементом ключа, результат передается на следующий шаг;
Шаг 2. Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: $$S=(S_i)_{i=0}^7$$. Далее значение каждого из восьми блоков заменяется новым, которое выбирается по таблице замен следующим образом: значение блока $$S_i$$ меняется на $$S_i$$ - ый по порядку элемент (нумерация с нуля) $$i$$-того узла замен (т.е. $$i$$ -той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Теперь становится понятным размер таблицы замен: число строк в ней равно числу 4-битовых элементов в 32-битовом блоке данных, то есть восьми, а число столбцов равно числу различных значений 4-битового блока данных, равному шестнадцати.
Шаг 3. Циклический сдвиг на 11 бит влево. Результат предыдущего шага сдвигается циклически на 11 бит в сторону старших разрядов и передается на следующий шаг.
Шаг 4. Побитовое сложение: значение, полученное на шаге 3, побитно складывается по модулю 2 со старшей половиной преобразуемого блока.
Шаг 5. Сдвиг по цепочке: младшая часть преобразуемого блока сдвигается на место старшей, а на ее место помещается результат выполнения предыдущего шага.
Шаг 6. Полученное значение преобразуемого блока возвращается как результат выполнения алгоритма основного шага криптопреобразования.
Для количественного анализа устойчивости процедур преобразования данных в ходе шифрования используется их представление в виде структур, состоящих из булевых функций. Этот же метод позволяет оценивать зависимость криптостойкости шифрования от выбранной ключевой информации, определяя, таким образом, критерии выбора "сильных" ключей и блоков замен (в случае ГОСТ 28147-89 и других, менее распространенных шифров с секретными блоками замен).Здесь мы кратко изложим метод исследования устойчивости алгоритма блочного шифрования к наиболее распространенным атакам, подробнее см. [2].
Определение 7.1 Булевой функцией называется отображение $${\left\{0,1\right\}}^{n}\rightarrow \left\{0,1\right\}$$, то есть правило, однозначно сопоставляющее вектору из $$n$$ бит значение 0 или 1.
Способы задания булевой функции [2]:
1) Табличный -- в виде таблицы, каждая строка которой задает значение функции при определенном наборе значений входных переменных. Число строк такой таблицы равно $${2}^{n}$$.
Пример 7.1 Таблица 7.2 задаёт булеву функцию $$f\left({x}_{0},{x}_{1},{x}_{2}\right)$$.
| $${x}_{2}$$ | $${x}_{1}$$ | $${x}_{0}$$ | $$f\left({x}_{0},{x}_{1},{x}_{2}\right)$$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
2) Векторный -- в виде вектора, состоящего из значений булевой функции, выписанных в порядке возрастания аргумента, если его представить в виде числа от 0 до $$2^n-1$$. В самом деле, вместо $$n$$ логических переменных $${x}_{0},{x}_{1},{{\dots},x}_{n-1}$$ в качестве аргумента функции можно использовать $$n$$-битное целое число
$$x={x}_{0}+{x}_{1}{\cdot}2+{x}_{2}{\cdot}{2}^{2}+{\dots}+{x}_{n-1}{\cdot}{2}^{n-1}=\sum\limits_{i=0}^{n-1}{{x}_{i}{\cdot}{2}^{i}}.$$Функция из примера 1 в векторном виде будет представлена следующим образом: $$f\left({x}_{0},{x}_{1},{x}_{2}\right)=\left(01101001\right)$$ (последний столбец таблицы выписан сверху вниз).
3) Аналитический -- в виде формулы, выражающей зависимость значения функции от значений ее аргументов.
Функция из примера 7.1 в аналитическом виде можно представить следующим образом: $$f\left({x}_{0},{x}_{1},{x}_{2}\right)={x}_{0}\oplus {x}_{1}\oplus {x}_{2}$$, где $$\oplus$$ - операция сложения бит по модулю 2 (XOR).
Определение 7.2 Весом булевой функции называется количество наборов значений входных переменных, при которых она принимает значение 1.
Проще говоря, это число единиц в векторном представлении булевой функции. Так, вес функции из примера 1 равен 4 (так как из 8 бит в векторе $$\left(01101001\right)$$ 4 единицы). Обозначается $$\wt (f)$$, например, $$\wt \left(01101001\right)=4$$.
Определение 7.3 Расстоянием между двумя булевыми функциями называется вес их побитовой суммы по модулю 2 в векторном виде (число позиций вы векторах, в которых значения функции различны).
Обозначается $$\dist({f}_{1},{f}_{2})$$, например, $$\dist\left(01101001,00101111\right)=3$$, так как значения функций различаются при $$x=1,x=5$$ и $$x=6$$.
Определение 7.4 Линейной называется булева функция аналитического вида
$$f\left({x}_{0},{x}_{1},{\dots},{x}_{n-1}\right)={{a}_{0}x}_{0}\oplus {{a}_{1}x}_{1}\oplus {\dots}\oplus {a}_{n-1}{x}_{n-1}=\sum\limits_{i=0}^{n-1}{{a}_{i}{x}_{i}}.$$где $${a}_{0},{a}_{1},{\dots},{a}_{n-1}{\in}\left\{0,1\right\}$$ -- произвольные значения 0 или 1. Множество всех линейных функций от $$n$$ переменных обозначим $${L}_{n}$$.
Пример 7.2 Построим все линейные булевы функции от 2 переменных.
Для этого нам нужно перебрать все различные комбинации бит $${a}_{0},{a}_{1}{\in}\left\{0,1\right\}$$:
Таким образом, множество линейных функций от 2 переменных:
$${L}_{2}=\left\{\left(0000\right), \left(0101\right), \left(0011\right), \left(0110\right)\right\}.$$Определение 7.5 Аффинной называется булева функция аналитического вида
$$f\left({x}_{0},{x}_{1},{\dots},{x}_{n-1}\right)={{a}_{0}x}_{0}\oplus {{a}_{1}x}_{1}\oplus {\dots}\oplus {a}_{n-1}{x}_{n-1}\oplus b=\sum _{i=0}^{n-1}{{a}_{i}{x}_{i}\oplus b},$$где $${a}_{0},{a}_{1},{\dots},{a}_{n-1},b{\in}\left\{0,1\right\}$$ -- произвольные значения 0 или 1. Множество всех аффинных функций от $$n$$ переменных обозначим $${A}_{n}$$.
Как нетрудно заметить, единственным отличием общего аналитического вида аффинных функций от линейных является наличие свободного члена $$b$$, при этом если $$b=0$$, то функция является линейной, а при $$b=1$$ функция в векторном виде является побитовой инверсией соответствующей линейной в (при тех же значениях коэффициентов $${a}_{0},{a}_{1},{\dots},{a}_{n-1}$$).
Таким образом, множество всех аффинных функций от $$n$$ переменных есть объединение множества всех линейных функций от $$n$$ переменных и множества их побитовых инверсий: $${A}_{n}={L}_{n}{\cup}\left\{f:\overline{{f}}{\in}{L}_{n}\right\}$$.
Пример 7.3 Построим все аффинные булевы функции от 2 переменных.
Для этого нам нужно объединить уже построенное в примере 2 множество всех линейных булевых функций от 2 переменных с множеством их побитовых инверсий:
$${A}_{2}=\left\{\left(0000\right),\left(0101\right),\left(0011\right),\left(0110\right),\left(1111\right),\left(1010\right),\left(1100\right),\left(1001\right)\right\}.$$Нелинейностью булевой функции называется минимальное расстояние от этой функции до множества аффинных функций: $$\nl \left(f\right)=\min\limits_{c\in A_n}\dist\left(f,c\right)$$.
Нелинейность показывает, насколько хорошо функция аппроксимируется линейными приближениями, другими словами, насколько хорошо можно подобрать такую линейную функцию, которая с большой вероятностью (при большом количестве различных значений входных переменных) будет давать то же значение, что и данная функция.
Пример 7.4 ([2]) Определим нелинейность функции 2 переменных $$f\left({x}_{0},{x}_{1}\right)=\left(1101\right)$$.
Сначала необходимо построить множество всех аффинных функций от 2 переменных (мы это сделали в примере 3):
$${A}_{2}=\left\{\left(0000\right),\left(0101\right),\left(0011\right),\left(0110\right),\left(1111\right),\left(1010\right),\left(1100\right),\left(1001\right)\right\}$$Теперь поочередно вычисляем расстояние от функции $$f\left({x}_{0},{x}_{1}\right)$$ до каждой из функций этого множества и находим минимум:
$$nl \left(f\right)=\min \left\{\begin{matrix}d\left(1101,0000\right),d\left(1101,0101\right),d\left(1101,0011\right),d\left(1101,0110\right),\\ d\left(1101,1111\right),d\left(1101,1010\right),d\left(1101,1100\right),d\left(1101,1001\right)\end{matrix}\right\}=\\ \min\left\{3,1,3,3,1,3,1,1\right\}=1.$$Определение 7.6 Динамическим расстоянием $$j$$ -го порядка булевой функции $$f\left({x}_{0},{x}_{1},{\dots},{x}_{n-1}\right)$$ называется число, вычисляемое по формуле:
$$DD_j\left(f\right)=\max\limits_{\substack{d\in\{0,1\}^n\\1\leq wt (d)\leq j}} \frac{1}{2}\left|{2}^{n-1}-\sum \limits_{x{\in}{\left\{0,1\right\}}^{n}}{f\left(x\right)\oplus f\left(x\oplus d\right)}\right|.$$Динамическое расстояние характеризует степень соответствия функции критерию лавинного эффекта, который заключается в том, что при изменении бит на входе выходное значение функции должно меняться с вероятностью $$\frac{1}{2}$$. Порядок динамического расстояния характеризует число одновременно изменяемых бит. При динамическом расстоянии $$j$$ -го порядка, равном 0, говорят, что функция удовлетворяет строгому критерию лавинного эффекта $$j$$-го порядка, что означает следующее: при одновременном инвертировании любых $$j$$ бит на входе функции ее значение инвертируется с вероятностью ровно $$\frac{1}{2}$$.
Пример 7.5 ([2]) Определим динамическое расстояние 1 и 2 порядка функции 2 переменных $$f\left({x}_{0},{x}_{1}\right)=\left(1101\right)$$.
Разберемся с нашим определением. Вектор $$d$$ -- это двоичный вектор длиной $$n$$, причем такой, что его вес не превышает порядка определяемого динамического расстояния.
Таким образом, для нашей функции 2 переменных при определении динамического расстояния порядка 1 вектор $$d$$ может принимать 2 значения: $$d=\left(01\right)$$ и $$d=\left(10\right)$$.
Заметим также, что в сумме в формуле динамического расстояния суммирование ведется по всем возможным значениям аргумента функции $$x$$ -- двоичного вектора длиной $$n$$.
Теперь вычисляем динамическое расстояние по формуле:
$$\begin{align*}DD_1(f)=\max \left\{\frac{1}{2}\left|2-\sum \limits_{x{\in}{\left\0,1\right\}}^{2}}{f\left(x\right)\oplus f\left(x\oplus 01\right)}\right|,\right.\\ \left.\frac{1}{2}\left|2-\sum \limits_{x{\in}{\left\{0,1\right\}}^{2}}{f(x)\oplus f(x\oplus 10)}\right|\right\}=\end{align*} % \begin{align*}=\max \left\{\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(00\oplus 01\right)-f\left(01\right)\oplus f\left(01\oplus 01\right)-\right.\right.\\%\end{multline*} \\ \left.\left. f\left(10\right)\oplus f\left(10\oplus 01\right)-f\left(11\right)\oplus f\left(11\oplus 01\right)\right|,\right.\\ \hphantom{\max \left\{\vphantom{\frac{1}{2}}\right.} \left.\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(00\oplus 10\right)-f\left(01\right)\oplus f\left(01\oplus 10\right)-\right.\right.\\ \left.\vphantom{\frac{1}{2}}\left.-f\left(10\right)\oplus f\left(10\oplus 10\right)-f\left(11\right)\oplus f\left(11\oplus 10\right)\right|\right\}=\end{align*} % \begin{align*}=\max \left\{\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(01\right)-f\left(01\right)\oplus f\left(00\right)-f\left(10\right)\oplus f\left(11\right)-\right.\right. \\ \left.\left.f\left(11\right)\oplus f\left(10\right)\right|, \frac{1}{2}\left|2-f\left(00\right)\oplus f\left(10\right)-f\left(01\right)\oplus f\left(11\right)-\right.\right.=\\ \left.\left. f\left(10\right)\oplus f\left(00\right)-f\left(11\right)\oplus f\left(01\right)\right|\right\} = \\ \max \left\{\frac{1}{2}\left|2-1\oplus 1-1\oplus 1-0\oplus 1-1\oplus 0\right|\right.,\left.\frac{1}{2}\left|2-1\oplus 0-1\oplus 1-\right.\right.\\ \left.\left.-0\oplus 1-1\oplus 1\right|\right\}=\\ =\max \left\{\frac{1}{2}\left|2-0-0-1-1\right|;\frac{1}{2}\left|2-1-0-1-0\right|\right\}=\\ =\max \left\{0;0\right\}=0\end{align*}$$Чтобы теперь определить динамическое расстояние этой функции 2-го порядка, необходимо еще раз вычислить значение выражения, стоящего под знаком максимума, при $$d=\left(11\right)$$ -- так как максимальный вес вектора $$d$$ уже становится равным 2:
$$\begin{align*}DD_2\left(f\right)=\max \left\{DD_1\left(f\right);\frac{1}{2}\left|2-\sum \limits_{x{\in}{\left\{0,1\right\}}^{2}}{f\left(x\right)\oplus f\left(x\oplus 11\right)}\right|\right\}=\\ \max \left\{0;\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(00\oplus 11\right)-f\left(01\right)\oplus f\left(01\oplus 11\right)-\right.\right.\\ \left.\left.\vphantom{\frac{1}{2}} -f\left(10\right)\oplus f\left(10\oplus 11\right)-f\left(11\right)\oplus f\left(11\oplus 11\right)\right|\right\} =\\ \max \left\{0;\frac{1}{2}\left|2-f\left(00\right)\oplus f\left(11\right)-f\left(01\right)\oplus f\left(10\right) -f\left(10\right)\oplus f\left(01\right)\right.\right.\\ \left.\left.\vphantom{\frac{1}{2}} -f\left(11\right)\oplus f\left(00\right)\right|\right\}=\max\left\{0;\frac{1}{2}\left|2-1\oplus 1-1\oplus 0-0\oplus 1-1\oplus 1\right|\right\}=\\ \max \left\{0;\frac{1}{2}\left|2-0-1-1-0\right|\right\}=\max \left\{0;0\right\}=0 \end{align*}$$Таким образом, $${\DD }_{1}\left(f\right)={\DD }_{2}\left(f\right)=0$$.
Определение 7.7 Блоком замен $$n\times m$$ бит называется отображение $${\left\{0,1\right\}}^{n}\rightarrow {\left\{0,1\right\}}^{m}$$, то есть отображение, однозначно сопоставляющее любому входному вектору из $$n$$ бит выходной вектор из $$m$$ бит.
Нетрудно заметить, что блок замен есть не что иное, как набор из $$m$$ булевых функций, каждый из которых задает зависимость определенного бита на выходе блока от значений бит на входе. Любая процедура преобразования бит по определенному правилу может быть представлена в виде блока замен, если выписать все значения на выходе преобразования при всех возможных значениях на входе.
Способы задания блока замен:
1) Табличный -- в виде таблицы, каждая строка которой содержит значения выходных бит блока при определенном наборе значений входных бит. Число строк такой таблицы равно $${2}^{n}$$.
Пример 7.6 Таблица 7.3 задаёт блок замен $${S:\left\{0,1\right\}}^{3}\rightarrow {\left\{0,1\right\}}^{3}$$.
| $${x}_{2}$$ | $${x}_{1}$$ | $${x}_{0}$$ | $${f}_{2}\left({x}_{2},{x}_{1},{x}_{0}\right)$$ | $${f}_{1}\left({x}_{2},{x}_{1},{x}_{0}\right)$$ | $${f}_{0}\left({x}_{2},{x}_{1},{x}_{0}\right)$$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
В данной таблице блок замен задан путем определения табличным способом трех булевых функций от трех переменных, определяющих зависимость выходных бит блока от входных.
2) Векторный -- в виде вектора, состоящего из значений блока замен, представленных в виде десятичного $$n$$-битного числа, расположенных в порядке возрастания соответствующих значений аргумента, если их представить в виде в виде числа от 0 до $${2}^{n}-1$$ (аналогично тому, как это делается при записи булевой функции в векторной форме).
Так, блок замен $$S$$ из примера 7.6 в векторной форме будет записываться следующим образом: $$\left(1,6,7,1,0,1,5,6\right)$$ (3-битовые значения на выходе блока представлены в виде целых чисел и выписаны сверзу вниз).
3) Аналитический -- в виде аналитически записанной зависимости выходных бит блока от входных. Например, в аналитической форме $$n\times m$$ битный блок замены $$S$$ путем целочисленного сложения с числом $$k$$ по модулю $${2}^{m}$$ можно записать следующим образом: $$S\left(x\right)=x+k (\mod {2}^{m})$$.
(рис 7.4) Схема представления узла замен ГОСТ 28147-89 в виде битовой матрицы
Пусть $$S$$ -- блок замен $$n\times m$$ бит, и $${f}_{0},{f}_{1},{\dots},{f}_{m-1}$$ -- булевы функции, выражающие зависимость соответствующих номерам функций выходных бит блока от входных. Иначе говоря, это столбцы правой части таблицы при записи блока замен в табличной форме (см. рис 7.4). Тогда нелинейность блока замен есть минимальная нелинейность всех возможных нетривиальных линейных комбинаций функций $${f}_{0},{f}_{1},{\dots},{f}_{m-1}$$:
$$nl\left(S\right)=\min\limits_{\substack{c\in \{0,1\}^m\\c\neq 0}} nl \left({c}_{0}{f}_{0}\oplus {c}_{1}{f}_{1}\oplus {\dots}\oplus {c}_{m-1}{f}_{m-1}\right)$$где $$c={c}_{0}+{c}_{1}{\cdot}2+{c}_{2}{\cdot}{2}^{2}+{\dots}+{c}_{m-1}{\cdot}{2}^{m-1}$$.
Например, нелинейность блока из примера 7.6 будет рассчитываться следующим образом:
$$\begin{align*}nl(S)=\min \left\{nl \left({f}_{0}\right),nl \left({f}_{1}\right),nl \left({f}_{2}\right),nl \left({f}_{0}\oplus {f}_{1}\right),nl \left({f}_{0}\oplus {f}_{2}\right),nl \left({f}_{1}\oplus {f}_{2}\right),\right.\\ \left. nl \left({f}_{0}\oplus {f}_{1}\oplus {f}_{2}\right)\right\}=\\ \min \left\{nl (10110110),nl (01100001),nl (01100011),nl (11010111),nl (11010101),\right. \\ \left. nl (00000010); nl (10110100)\right\}=\\ \min \left\{\text{1;1;2;2;1;1;2}\right\}=1\end{align*}$$\textit{Нелинейность битового блока замен есть важнейшая его характеристика с точки зрения криптостойкости блока: она показывает степень устойчивости внутренней структуры блока к линейному методу криптоанализа. Следовательно, для достижения устойчивости шифрования к линейному криптоанализу необходимо, чтобы процедуры преобразования бит в ходе шифрования обладали как можно большей нелинейностью.}
Определение 7.8 Динамическое расстояние блока замен порядка $$\left(i,j\right)$$ определяется следующим образом:
$$\begin{equation*} {\mathit{DD}}_{i,j}\left(S\right)=\underset{\begin{matrix}c{\in}{\left\{0,1\right\}}^{m}\\1{\leq}\wt \left(c\right){\leq}i\end{matrix}}{\mathit{max}}{\mathit{DD}}_{j}\left({c}_{0}{f}_{0}\oplus {c}_{1}{f}_{1}\oplus {\dots}\oplus {c}_{m-1}{f}_{m-1}\right) \end{equation*}$$Таким образом, динамическое расстояние блока порядка $$\left(i,j\right)$$ есть максимальное динамическое расстояние порядка $$j$$ всех нетривиальных линейных комбинаций не более чем из $$i$$ функций из набора $${f}_{0},{f}_{1},{\dots},{f}_{m-1}$$.
Смысл порядка динамического расстояния блока замен состоит в следующем: динамическое расстояние порядка $$(i,j)$$ характеризует степень отклонения вероятности изменения любого $$i$$ числа битов, не превышающего $$i$$, на выходе блока от значения $$1/2$$ при одновременном инвертировании не более $$j$$ битов на входе. Если динамическое расстояние блока замен порядка $$i,j$$ равно 0, то это означает, что при одновременном изменении не более $$j$$ битов на входе блока любой набор из не более чем $$i$$ бит на выходе одновременно изменится с вероятностью ровно $$1/2$$.
Например, динамическое расстояние порядка $$\left(2,1\right)$$ блока из примера 7.6 будет рассчитываться следующим образом:
$$\begin{align*} {DD}_{2,1}\left(S\right)=\max \left\{{DD}_{1}\left({f}_{0}\right),{DD}_{1}\left({f}_{1}\right),{DD}_{1}\left({f}_{2}\right),{DD}_{1}\left({f}_{0}\oplus {f}_{1}\right),\right.\\ \left. {DD}_{1}\left({f}_{0}\oplus {f}_{2}\right),{DD}_{1}\left({f}_{1}\oplus {f}_{2}\right)\right\}= \\ =\max \left\{{DD}_{1}\left(10110110\right),{DD}_{1}\left(01100001\right),{DD}_{1}\left(01100011\right),\right. \\ \left.{DD}_{1}\left(11010111\right),{DD}_{1}\left(11010101\right),{DD}_{1}\left(00000010\right)\right\}=\\ =\max \left\{1,1,2,0,1,1\}\right\}=2. \end{align*}$$А динамическое расстояния порядка $$\left(3,2\right)$$ рассчитывается так:
$$\begin{align*} {DD}_{3,2}\left(S\right)=\max \left\{{DD}_{2}\left({f}_{0}\right),{DD}_{2}\left({f}_{1}\right),{DD}_{2}\left({f}_{2}\right),{DD}_{2}\left({f}_{0}\oplus {f}_{1}\right),\right.\\ \left.{DD}_{2}\left({f}_{0}\oplus {f}_{2}\right),{DD}_{2}\left({f}_{1}\oplus {f}_{2}\right),{DD}_{2}\left({f}_{1}\oplus {f}_{2}\oplus {f}_{3}\right)\right\}= \\ =\max \left\{{DD}_{2}(10110110),{DD}_{2}(11010101),{DD}_{2}(00000010),\right. \\ \left.{DD}_{2}(10110100)\right\}= \\ = \max \{1,1,2,2,1,1,2\}=2. \end{align*}$$Таким образом, динамическое расстояние блока замен есть вторая важнейшая его характеристика с точки зрения криптостойкости: она показывает степень устойчивости внутренней структуры блока к дифференциальному методу криптоанализа. Следовательно, для достижения устойчивости шифрования к дифференциальному криптоанализу необходимо, чтобы процедуры преобразования бит в ходе шифрования обладали как можно меньшим динамическим расстоянием как можно большего порядка.
Практически все современные блочные шифры, основанные на схеме Файстеля, содержат в числе процедур преобразования данных замену бит по специальным таблицам аналогично тому, как это делается в шифре ГОСТ 28147-89. Однако в них эти таблицы определены в спецификации алгоритма и выбираются один раз (на этапе проектирования шифра). Назначение этих таблиц (в алгоритме DES они называются S-блоками) -- перемешивание битов данных в ходе раунда шифрования путем замены отрезков шифруемого блока данных по правилам, определяемым таблицами.
Общие требования к узлам замен (S-блокам) блочных шифров повторяют требования к функции шифрования в целом -- это высокое значение нелинейности и наличие лавинного эффекта (что достигается при низком динамическом расстоянии различных порядков). Существует ряд общеизвестных критериев для проектирования устойчивых к дифференциальному криптоанализу узлов замен для любых блочных шифров:
1) Строгий критерий лавинного эффекта (SAC -- Strict Avalanche Criterion) -- требует, чтобы для любых $$i$$ и $$j$$ при инвертировании входного бита $$i$$ на входе узла замен выходной бит $$j$$ изменялся с вероятностью $$1/2$$. Блок замен удовлетворяет данному критерию, если его динамическое расстояние порядка $$(1,1)$$ равно 0.
2) Критерий независимости битов (BIC -- Bit Independence Criterion) -- требует, чтобы для любых значений $$i$$, $$j$$ и $$k$$ при инвертировании входного бита $$i$$ на входе узла замен выходные биты $$j$$ и $$k$$ изменялись независимо (то есть вероятность одновременного изменения битов должна быть равна произведению вероятностей изменения отдельных бит). Блок замен удовлетворяет данному критерию, если динамическое расстояние порядка 1 {XOR} - суммы любых двух булевых функций, его составляющих, равно 0.
3) Критерий гарантированного лавинного эффекта (GAC -- Guaranteed Avalanche Criterion) порядка $$\gamma $$ -- выполняется, если при изменении одного бита на входе узла замен на выходе меняются как минимум $$\gamma$$ выходных битов.
4) Критерий XOR-значения для блока $$S$$ размерностью $$n\times m$$ бит -- основывается на построении на основе блока специальной XOR -таблицы, элементы которой вычисляются по следующей формуле:
$$\text{XOR}(S,\alpha,\beta)=\left|x\in \{0,1\}^n \mid S(x)\oplus S(x\oplus \alpha)=\beta \right|,$$где $$\alpha\in\{0,1\}^n\setminus\{0\}$$ это значение может быть представлено в виде числа от $$1$$ до $$2^n-1$$), $$\beta\in \{0,1\}^m$$ (может быть представлено в виде числа от 0 до $$2^m-1$$), $$S(x)$$ --- выходное значение блока замен $$S$$ при входном значении $$x$$.
XOR-значением блока замен называется максимальное значение в его XOR-таблице. Данный критерий требует, чтобы XOR-значение блока было как можно меньшим, в идеале -- 2.
Для построения новых высокоскоростных криптоалгоритмов интерес представляют такие блока S, которые соответствуют одновременно нескольким критериям качества, и, таким образом, позволяют эффективно противостоять одновременно разным видам атак. Одними из наиболее существенных с практической точки зрения является критерий независимости векторов выхода S-блока $$y_j$$ от векторов его входа $$x_i$$.
Более формально: обозначим через $$\{x_i\}_{i=0}^{N-1}$$ множество всевозможных входных векторов блока замен. Очевидно, $$N=2^n$$. Каждому входному вектору $$x_i$$ соответствует выходной вектор $$y_i$$. Через $$x_{ij}$$ и $$y_{ik}$$ обозначим, соответственно, $$j$$-й бит входного вектора и $$k$$-й бит выходного вектора ($$0\leq j\leq n-1$$, $$0\leq k\leq m-1$$). Биты входных векторов $$x_i$$ связаны с номером $$i$$ соотношением:
$$i=x_{i0} + 2 x_{i1} + \ldots + 2^{n-1} x_{i,n-1}.$$Мы также будем записывать выходной вектор $$y_i=S(x_i)$$ шестнадцатеричным числом, связанным с битами соотношениями:
$$y_i = y_{i0} + 2 y_{i1}+\ldots+2^{m-1} y_{i,m-1}.$$Например, если $$y_i=A8_{16}=10101000_2$$, то $$y_{i0} = 0$$, $$y_{i1}=0$$, $$\ldots$$, $$y_{i5}=1$$, $$y_{i6}=0$$, $$y_{i7}=1$$.
Коэффициент корреляции между $$j$$-м входным и $$k$$-м выходным битами узла замен вычисляется по формуле:
$$\rho_{jk}=\frac{\sum_{t=0}^{N-1} x_{tj} y_{tk}- \left(\sum_{t=0}^{N-1} x_{tj}\cdot \sum_{t=0}^{N-1} y_{tk}\right)/N}{\sqrt{\left(\sum_{t=0}^{N-1} x_{tj}^2 - \left(\sum_{t=0}^{N-1} x_{tj}\right)^2/N \right)\cdot\left(\sum_{t=0}^{N-1} y_{tk}^2 - left(\sum_{t=0}^{N-1} y_{tk}\right)^2/N \right)}}.$$Кроме того, для двоичных векторов $$x_i$$, $$y_i$$ верна более простая формула:
$$\rho_{jk}=1-2^{-(n-1)}\sum\limits_{z=0}^{N-1} (x_{z,j} \oplus y_{z,k}).$$Пример 7.7 Вычислим коэффициенты корреляции для следующего блока замен $$4\times 4$$ для алгоритма ГОСТ:
9 8 3 A C D 7 E 0 1 B 2 4 5 F 6
Более подробно: число 0 (нумерация начинается с нуля) переходит в число 9, число 1 переходит в 8, 2 в 3, число 3 в 10, 4 в 12,..., число 15 переходит в 6.
Запишем битовые представления всех чисел нашей подстановки:
| 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 1001 | 1000 | 0011 | 1010 | 1100 | 1101 | 0111 | 1110 | 0000 | 0001 | 1011 | 0010 | 0100 | 0101 | 1111 | 0110 |
Теперь, интерпретируя последовательность битов каждого разряда как множество значений случайной величины, вычислим коэффициенты корреляции между последовательностью входящих битов $$i$$-го разряда и последовательностью выходящих битов $$j$$-го разряда, $$i,j=0,1,2,3$$. Все коэффициенты корреляции посчитаны в таблице 7.4.
| j\k | 0 | 1 | 2 | 3 |
| 0 | -0,25 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | -0,5 |
Мы видим, что биты 1 и 2 группы остаются неизменными, что свидетельствует о плохом качестве данного блока.
Определение 7.9 Нелинейное преобразование назовем оптимальным, если все его коэффициенты корреляции равны нулю.
В работах [5], [2] представлена методика построения оптимальных блоков замен любого размера.
Существуют следующие наиболее распространенные подходы к построению блоков замен:
1) Случайный выбор. Элементы узлов замен выбираются с помощью генератора случайных или псевдослучайных чисел. Это наиболее простой способ, однако в случае небольшого размера блоков, как в алгоритме ГОСТ 28147-89 ($$4{\times}4$$ бит), такой способ может с высокой степенью вероятности привести к генерации таблицы замен с нежелательными с точки зрения стойкости криптостойкости характеристиками нелинейности и лавинного эффекта.
2) Случайный выбор с последующей проверкой. Элементы блоков замен выбираются случайным образом, но после этого полученные результаты проверяются на соответствие различным критериям с отсеиванием тех блоков, которые не выдержали такой проверки. Этот способ также прост, и в то же время он устраняет указанный недостаток первого способа, однако в таком случае встает вопрос о выборе набора критериев для проверки и формировании методики тестирования, так как не существует блоков, одинаково хорошо удовлетворяющих всем предъявляемым к ним требованиям одновременно. Также возможна ситуация, когда блоков замен, удовлетворяющим выбранным требованиям слишком мало по сравнению с мощностью пространства блоков, и генерация таких блоков на основе случайного выбора может требовать больших вычислительных ресурсов.
3) Выбор вручную. Элементы узлов замен выбираются вручную с использованием математических преобразований. Именно эта методика легла в основу разработки DES с его фиксированными S-блоками. Такой подход является наиболее сложным, так как требует разработки и теоретического обоснования методики выбора блоков замен.
4) Математический подход. Элементы узлов замен генерируются при помощи определенного алгоритма, основанного на тех или иных математических принципах. Такой подход при грамотной проектировании алгоритма обеспечивает выбор узлов замен, гарантирующих заданный уровень надежности по отношению к различным методам криптоанализа.
В июне 2015 года приняты два новых криптографических стандарта Российской Федерации: ГОСТ Р 34.12-2015 "Информационная технология. Криптографическая защита информации. Блочные шифры" и ГОСТ Р 34.13-2015 "Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров", которые вступают в действие с 1 января 2016 года.
ГОСТ Р 34.12-2015 содержит описание двух блочных шифров с длинами блока 128 и 64 бит. Шифр ГОСТ 28147-89 с зафиксированными блоками нелинейной подстановки включен в новый ГОСТ Р 34.12-2015 в качестве 64-битового шифра под названием "Магма" ("Magma"). Стандартом определены следующие блоки замен:
| $$S_0 = (12, 4, 6, 2, 10, 5, 11, 9, 14, 8, 13, 7, 0, 3, 15, 1);$$ |
| $$S_1 = (6, 8, 2, 3, 9, 10, 5, 12, 1, 14, 4, 7, 11, 13, 0, 15);$$ |
| $$S_2 = (11, 3, 5, 8, 2, 15, 10, 13, 14, 1, 7, 4, 12, 9, 6, 0);$$ |
| $$S_3 = (12, 8, 2, 1, 13, 4, 15, 6, 7, 0, 10, 5, 3, 14, 9, 11);$$ |
| $$S_4 = (7, 15, 5, 10, 8, 1, 6, 13, 0, 9, 3, 14, 11, 4, 2, 12);$$ |
| $$S_5 = (5, 13, 15, 6, 9, 2, 12, 10, 11, 7, 8, 1, 4, 3, 14, 0);$$ |
| $$S_6 = (8, 14, 2, 5, 6, 9, 1, 12, 15, 4, 11, 0, 13, 10, 3, 7);$$ |
| $$S_7 = (1, 7, 14, 13, 0, 5, 8, 3, 4, 15, 10, 6, 9, 12, 11, 2).$$ |
Приведенный в стандарте набор S-блоков обеспечивает наилучшие характеристики, определяющие стойкость криптоалгоритма к дифференциальному и линейному криптоанализу.
Фиксация блоков нелинейной подстановки сделает алгоритм ГОСТ 28147-89 более унифицированным и исключает использование "слабых" блоков нелинейной подстановки. Кроме того, фиксация в стандарте всех долговременных параметров шифра отвечает принятой международной практике. Новый стандарт ГОСТ Р 34.12-2015 терминологически и концептуально связан с международными стандартами ИСО/МЭК 10116 "Информационные технологии. Методы обеспечения безопасности. Режимы работы для n-битовых блочных шифров" (ISO/IEC 10116:2006 Information technology -- Security techniques - Modes of operation for an n-bit block cipher) и серии ИСО/МЭК 18033 "Информационные технологии. Методы и средства обеспечения безопасности. Алгоритмы шифрования": ИСО/МЭК 18033-1:2005 "Часть 1. Общие положения" (ISO/IEC 18033-1:2005 Information technology -- Security techniques -- Encryption algorithms -- Part 1: General) и ИСО/МЭК 18033-3:2010 "Часть 3. Блочные шифры" (ISO/IEC 18033-3:2010 (Information technology -- Security techniques -- Encryption algorithms – Part 3: Block ciphers).
В стандарт ГОСТ Р 34.12-2015 включен также новый блочный шифр ("Кузнечик") с размером блока 128 бит,см.ниже. Ожидается, что этот шифр будет устойчив ко всем известным на сегодняшний день атакам на блочные шифры.
Блочный шифр Rijndael в октябре 2000 года стал победителем проведенного Национальным Институтом Стандартов и Технологий (NIST) США конкурса на замену признанного ненадежным алгоритма шифрования DES (Data Encryption Standart). В феврале 2001 года прошел через открытое обсуждение и в апреле 2001 года был объявлен новым федеральным стандартом шифрования США AES (Advanced Encryption Standart), см. [4].
Алгоритм шифрования Rijndael имеет переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам. В стандарте AES определена длина блока данных, равная 128 битам.
Промежуточные результаты преобразований, выполняемых в рамках крипто-алгоритма, называют состояниями (State). Состояние можно представить в виде прямоугольного массива байтов.
При размере блока, равном 128 битам, этот 16-байтовый массив (таблицы 7.5, 7.6) имеет 4 строки и 4 столбца (каждая строка и каждый столбец в этом случае могут рассматриваться как 32-разрядные слова). Входные данные для шифра обозначаются как байты состояния в порядке $$S_{00}, S_{10}, S_{20}, S_{30}, S_{01}, S_{11}, \ldots$$.
После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке. В общем случае число столбцов равно длине блока, деленной на 32.
В таблице 7.5 представлен пример 128-разрядного блока данных в виде массива state.
Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками (таблица 7.6. Число столбцов этого массива равно длине ключа, деленной на 32. В стандарте определены ключи всех трех размеров ---128 бит, 192 бита и 256 бит, то есть соответственно 4, 6 и 8 32-разрядных слова (или столбца --- в табличной форме представления). В некоторых случаях ключ шифрования рассматривается как линейный массив 4-байтовых слов. Слова состоят из 4 байтов, которые находятся в одном столбце (при представлении в виде прямоугольного массива).
Зависимость числа раундов $$N_r$$ в алгоритме Rijndael от чисел $$N_b$$ и $$N_k$$ 32-битных слов, соответственно, в блоке и ключе, отражена в таблице 7.7.
| $$S_{00}$$ | $$S_{01}$$ | $$S_{02}$$ | $$S_{03}$$ |
| $$S_{10}$$ | $$S_{11}$$ | $$S_{12}$$ | $$S_{13}$$ |
| $$S_{20}$$ | $$S_{21}$$ | $$S_{22}$$ | $$S_{23}$$ |
| $$S_{30}$$ | $$S_{31}$$ | $$S_{32}$$ | $$S_{33}$$ |
| $$K_{00}$$ | $$K_{01}$$ | $$K_{02}$$ | $$K_{03}$$ |
| $$K_{10}$$ | $$K_{11}$$ | $$K_{12}$$ | $$K_{13}$$ |
| $$K_{20}$$ | $$K_{21}$$ | $$K_{22}$$ | $$K_{23}$$ |
| $$K_{30}$$ | $$K_{31}$$ | $$K_{32}$$ | $$K_{33}$$ |
| $$N_r$$ | $$N_b=4$$ | $$N_b=6$$ | $$N_b=8$$ |
| $$N_k=4$$ | 10 | 12 | 14 |
| $$N_k=6$$ | 12 | 12 | 14 |
| $$N_k=8$$ | 14 | 14 | 14 |
Раунд состоит из четырех различных преобразований:
Алгоритм Rijndael оперирует байтами, которые рассматриваются как элементы конечного поля $$GF(2^{8})$$. Для построения такого поля используется неприводимый многочлен 8-й степени над полем $$\mathbb{Z}_2$$ (см. параграф 1.12). В алгоритме Rijndael используется многочлен $$\varphi (x)=x^{8 }+x^{4 }+x^{3 }+ x+ 1$$.
Для каждого байта $$b=b_0 + b_1 \cdot 2 + \ldots + b_7 \cdot 2^7$$ построим многочлен $$A_b(x)=b_0 + b_1 x + \ldots +b_7 x^7$$, который можно считать элементом построенного нами поля $$GF(2^8)$$. Далее отождествим следующие представления байта:
$$b=A_b(x) = (\overline{b_7 b_6\ldots b_0})_2 = \{zt\},$$где $$z=b_0+2b_1+4b_2+8b_3$$, $$t = b_4+2b_5+4b_6+8b_7$$ --- цифры шестнадцатеричного представления байта.
Операция сложения над элементами поля представляет собой поразрядное сложение по модулю 2, умножение представляет собой операцию умножения со взятием результата по модулю многочлена $$\varphi$$.
Преобразование SubBytes() представляет собой нелинейную замену байтов, выполняемую независимо с каждым байтом $$b$$ состояния.
Пример 7.8 Применим преобразование SubBytes() к байту $$\{83\}$$.
Многочлен, коэффициентами которого являются биты данного числа: $$A(x) = x^7 + x + 1$$. Вначале найдём обратный к нему многочлен относительно умножения в поле $$GF(2^{8})$$. Как уже отмечалось ранее, операция умножения в поле $$GF(2^{8})$$ является операцией умножения многочленов с взятием результата по модулю неприводимого многочлена $$\varphi(x)$$ восьмой степени с использованием операции XOR (сложения по модулю 2) при приведении подобных членов. Так как авторами алгоритма шифрования Rijndael был выбран неприводимый многочлен $$\varphi (x)=x^{8}+x^{4}+x^{3}+x+1$$, то нам необходимо найти такой многочлен $$B(x)=A^{-1}(x)$$, который бы при умножении на многочлен $$x^{7}+x+1$$ по модулю $$\varphi (x) = x^{8}+x^{4}+x^{3}+x+1$$ давал единицу, то есть $$(x^{7}+x+1)\cdot B(x)=1 (\mod (x^{8}+x^{4}+x^{3}+x+1))$$.
С помощью расширенного алгоритма Евклида находим:
$$1=x^7\cdot A(x) + (x^6 + x^2 + x + 1)\cdot \varphi(x).$$Отсюда $$B(x) = A^{-1}(x) = x^7$$. Соответствующий байт: $$b'=1000 0000_2 = \{80\}$$.
Теперь совершим второй этап преобразования.
$$\left(\begin{array}{c} b_0'' \\ b_1'' \\ b_2'' \\ b_3'' \\ b_4'' \\ b_5'' \\ b_6'' \\ b_7'' \end{array}\right)=\left( \begin{array}{cccccccc} 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 1 1 1 0 0 0 1 \\ 1 1 1 1 1 0 0 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 \end{array} \right)\cdot \left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{array}\right)+\left(\begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ \end{array}\right)= \left(\begin{array}{c} 0 \\ %11101100 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{array}\right).$$Результатом проведенного преобразования является значение $$1110\ 1100_2=\{EC\}$$.
Преобразование сдвига строк ShiftRows() выглядит следующим образом: последние 3 строки состояния циклически сдвигаются влево на различное число байтов. Строка 1 сдвигается на $$C_1$$ байт, строка 2 --- на $$C_2$$ байт, и строка 3 --- на $$C_3$$ байт. Значение сдвигов $$C_1$$, $$C_2$$ и $$C_3$$ в Rijndael зависят от длины блока $$N_b$$. Их величины приведены в таблице 7.8.
| $$N_b = 4$$ | $$N_b = 6$$ | $$N_b = 8$$ | ||||||
| $$C_1$$ | $$C_2$$ | $$C_3$$ | $$C_1$$ | $$C_2$$ | $$C_3$$ | $$C_1$$ | $$C_2$$ | $$C_3$$ |
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 3 | 4 |
В стандарте AES, где определен единственный размер блока, равный 128 битам, $$C_1=1$$, $$C_2=2$$, $$C_3=3$$.
Преобразование перемешивания столбцов (MixColumns) действует отдельно на каждом $$i$$-м столбце таблицы состояния, как линейное преорбазование:
$$\begin{equation}\left(\begin{array}{c} S'_{0,i} \\ S'_{1,i} \\ S'_{2,i} \\ S'_{3,i} \end{array}\right)= \left(\begin{array}{cccc} \{02\} \{03\} \{01\} \{01\} \\ \{01\} \{02\} \{03\} \{01\} \\ \{01\} \{01\} \{02\} \{03\} \\ \{03\} \{01\} \{01\} \{02\} \\ \end{array}\right)\cdot \left(\begin{array}{c} S_{0,i} \\ S_{1,i} \\ S_{2,i} \\ S_{3,i} \end{array}\right), \end{equation}$$ $$\{02\}=x, \qquad \{03\}=x+1, \qquad \{01\}=1.$$В результате такого умножения байты $$S_{0,i}, S_{1,i}, S_{2,i}, S_{3,i}$$ заменятся, соответственно, на байты
$$S'_{0,i} = x\cdot S_{0,i} + (x+1)\cdot S_{1,i} + S_{2,i} + S_{3,i},$$ $$S'_{1,i} = S_{0,i} + x\cdot S_{1,i} + (x+1)\cdot S_{2,i} + S_{3,i},$$ $$S'_{2,i} = S_{0,i} + S_{1,i} + x\cdot S_{2,i} + (x+1)\cdot S_{3,i},$$ $$S'_{3,i} = (x+1)\cdot S_{0,i} + S_{1,i} + S_{2,i} + x\cdot S_{3,i}.$$Применение этой операции ко всем четырем столбцам состояния обозначают через MixColumns().
Пример 7.9 Применим операцию MixColumns() к столбцу: $$S_{0,0}=\{2d\}$$, $$S_{1,0}=\{26\}$$, $$S_{2,0}=\{31\}$$, $$S_{1,0}=\{4c\}$$.
Представим элементы $$S_{i,0}$$ полиномами:
$$S_{0,0}=\{2d\}=x^5+x^3+x^2+1,\qquad S_{1,0}=\{26\}=x^5+x^2+x,\\S_{2,0}=\{31\}=x^5+x^4+1,\qquad S_{3,0}=\{4c\}=x^6+x^3+x^2.$$Находим $$S_{0,0}$$ по формулам (7.3)-(7.6). Вычислим многочлен:
$$\begin{align*}x\cdot (x^5+x^3+x^2+1) + (x+1)\cdot (x^5+x^2+x) + (x^5+x^4+1) + \\(x^6+x^3+x^2) = x^6+x^3+x^2+1\end{align*}$$и возьмём остаток от его деления на $$\varphi(x)=x^8 + x^4 + x^3 + x + 1$$. Имеем:
$$S'_{0,0} = x^6+x^3+x^2+1 ~(\mod \varphi(x) ) = \{4d\}.$$Аналогично находим остальные компоненты столбца:
$$\begin{align*}S'_{1,0}=(x^5+x^3+x^2+1) + x\cdot (x^5+x^2+x) + (x+1)(x^5+x^4+1) + \\ (x^6+x^3+x^2) = x^6+x^5+x^4+x^3+x^2+x \equiv \\ \equiv x^6+x^5+x^4+x^3+x^2+x ~(\mod \varphi(x) ) = \{7e\},\end{align*} % \begin{align*}S'_{2,0}=(x^5+x^3+x^2+1) + (x^5+x^2+x) + x\cdot (x^5+x^4+1) + \\ (x+1)\cdot (x^6+x^3+x^2) = x^7+x^5+x^4+x^3+x^2+1 \equiv \\ \equiv x^7+x^5+x^4+x^3+x^2+1 ~(\mod \varphi(x) ) = \{bd\}, \end{align*} % \begin{align*}S'_{3,0}=(x+1)\cdot (x^5+x^3+x^2+1) + (x^5+x^2+x) + (x^5+x^4+1) + \\ x\cdot (x^6+x^3+x^2) = x^7 + x^6 + x^5 + x^4 + x^3 \equiv\\ \equiv x^7 + x^6 + x^5 + x^4 + x^3 ~(\mod \varphi(x) ) = \{f8\}. \end{align*}$$На рисунке 7.5 показано преобразование исходного столбца $$S_{10}$$ в столбец $$S_{10}'$$ с помощью операции MixColumns().
(рис 7.5) Применение MixColumns() к столбцу состояния
В операции добавления подключа (AddRoundKey) подключ $$K^{(r)}$$ раунда $$r$$ добавляется к данным с помощью операции побитового сложения по модулю два (операция XOR). Это сложение также можно рассматривать как сложение элементов поля $$GF(2^8)$$:
Подключи вырабатываются из исходного секретного ключа шифрования с помощью алгоритма выработки ключей (Key Schedule). Длина подключа (в 32-разрядных словах) равна длине блока $$N_b$$ слов.
Подключи, используемые в каждом раунде шифрования, получаются из исходного секретного ключа шифрования с помощью алгоритма выработки подключей. Он содержит два компонента.
Расширение ключа. При расширении ключа нам потребуются следующие операции, применяемые к словам $$v$$, состоящим из байт $$v_0, v_1, v_2, v_3$$ (будем использовать обозначение $$v=\{v_0,v_1,v_2,v_3\}$$):
$$\begin{align*}\text{RotWord}(\{v_0,v_1,v_2,v_3\}) = \{v_1,v_2,v_3,v_0\},\\ \text{SubWord}(\{v_0,v_1,v_2,v_3\}) = \{\text{SubBytes}(v_0),\text{SubBytes}(v_1),\\ \text{SubBytes}(v_2),\text{SybBytes}(v_3)\}. \end{align*}$$Кроме того, определим константы-слова $$\text{Rcon}[i]=\{x^{i-1}, 0, 0, 0\}$$. Напомним, что под байтом $$x^{i-1}$$ понимается элемент поля $$GF(2^8)$$, то байт состоит из коэффициентов из $$\mathbb{Z}_2$$ остатка $$r(x)$$ от деления $$x^{i-1}$$ на неприводимый многочлен $$\varphi(x)$$.
Под сложением слов $$u+v$$ будем понимать их побитовое сложение по модулю два, что эквивалентно побайтовому сложению в поле $$GF(2^8)$$. Иногда также пишут $$u\ \text{XOR}\ v$$.
Первые слова $$w[0], w[1],\ldots, w[N_k-1]$$ расширенного ключа совпадают со словами ключа шифрования. Последующие слова $$w[i]$$ вычисляются последовательно при $$i=N_k, N_k+1,\ldots$$ по следующему алгоритму:
Выбор раундовых подключей. Ключ $$K^{(r)}$$ $$r$$-го раунда ($$1\leq r\leq N_r$$) состоит из слов $$w[N_b\cdot i], w[N_b\cdot i + 1], \ldots w[N_b\cdot (i+1)-1]$$. Например, при $$N_b = 4$$ получаем:
$$w=\{w[0],w[1],w[2],w[3], \underbrace{w[4],w[5],w[6],w[7]}_{\text{Подключ} K^{(1)}}, \underbrace{w[8],w[9],w[10],w[11]}_{\text{Подключ} K^{(2)}},\ldots \}.$$Как известно, для оценки качества блоков замен используются различные критерии. Одним из таких критериев является максимум модуля коэффициентов корреляции, имеет значение также количество нулей корреляционной матрицы. Для выбранного в алгоритме Rijndael неприводимого многочлена $$\varphi(x)=x^{8}+x^{4}+x^{3}+x+1$$ корреляционная матрица следующая:
$$\begin{scriptsize} \left( \begin{array}{cccccccc} -0,04690,06250,0313-0,0156-0,0938-0,01560,0938-0,0938\\ 0,06250,0938-0,0625-0,0938-0,10940,015600,0781\\ 0,0313-0,0625-0,0938-0,04690,015600,07810,0625\\ -0,0156-0,0938-0,0469-0,06250,0625-0,0625-0,06250,1250\\ -0,0938-0,10940,01560,06250,09380,04690,0313-0,0156\\ -0,01560,01560-0,06250,0469-0,0313-0,0156-0,0938\\ 0,093800,0781-0,0625-0,0313-0,0156-0,0938-0,0156\\ -0,09380,07810,06250,1250-0,0156-0,0938-0,01560,0938 \end{array} \right) \end{scriptsize}$$Заметим, что за счет выбора другого неприводимого многочлена степени 8 над полем $$GF(2^8)$$ можно получить корреляционную матрицу с бОльшим количеством нулевых элементов, что затруднит корреляционный криптоанализ, однако упростит аппроксимацию шифра аффинными булевыми функциями за счет большего количества единичных значений элементов в полной матрице коэффициентов корреляции со всеми аффинными функциями.
Пример 7.10 Применение полинома (десятичный эквивалент) 355 наиболее затруднит аппроксимацию шифра аффинными булевыми функциями, а применение полинома 425 наиболее затруднит корреляционный криптоанализ, однако упростит аппроксимацию аффинными булевыми функциями.
В таблице 7.9 приведен пример оптимального по корреляционному критерию блока замен длины 256 [5].
| $$S_8$$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 5C | 58 | 04 | F2 | 02 | F9 | A1 | AE | F6 | 05 | AB | AA | 57 | 5D | F1 | 0F |
| 1 | A9 | A3 | 0D | F5 | 06 | F3 | 5F | 5E | FA | 07 | 5B | 54 | AC | A8 | F0 | 00 |
| 2 | B8 | BC | 12 | E4 | 19 | E2 | 4E | 41 | E5 | 16 | 4A | 4B | BD | B7 | EF | 11 |
| 3 | 43 | 49 | 15 | ED | 13 | E6 | BE | BF | E7 | 1A | B4 | BB | 48 | 4C | E0 | 10 |
| 4 | 98 | 9C | 32 | C4 | 39 | C2 | 6E | 61 | C5 | 36 | 6A | 6B | 9D | 97 | CF | 31 |
| 5 | 63 | 69 | 35 | CD | 33 | C6 | 9E | 9F | C7 | 3A | 94 | 9B | 68 | 6C | C0 | 30 |
| 6 | 7C | 78 | 24 | D2 | 22 | D9 | 81 | 8E | D6 | 25 | 8B | 8A | 77 | 7D | D1 | 2F |
| 7 | 89 | 83 | 2D | D5 | 26 | D3 | 7F | 7E | DA | 27 | 7B | 74 | 8C | 88 | D0 | 20 |
| 8 | D8 | DC | 72 | 84 | 79 | 82 | 2E | 21 | 85 | 76 | 2A | 2B | DD | D7 | 8F | 71 |
| 9 | 23 | 29 | 75 | 8D | 73 | 86 | DE | DF | 87 | 7A | D4 | DB | 28 | 2C | 80 | 70 |
| A | 3C | 38 | 64 | 92 | 62 | 99 | C1 | CE | 96 | 65 | CB | CA | 37 | 3D | 91 | 6F |
| B | C9 | C3 | 6D | 95 | 66 | 93 | 3F | 3E | 9A | 67 | 3B | 34 | CC | C8 | 90 | 60 |
| C | 1C | 18 | 44 | B2 | 42 | B9 | E1 | EE | B6 | 45 | EB | EA | 17 | 1D | B1 | 4F |
| D | E9 | E3 | 4D | B5 | 46 | B3 | 1F | 1E | BA | 47 | 1B | 14 | EC | E8 | B0 | 40 |
| E | F8 | FC | 52 | A4 | 59 | A2 | 0E | 01 | A5 | 56 | 0A | 0B | FD | F7 | AF | 51 |
| F | 03 | 09 | 55 | AD | 53 | A6 | FE | FF | A7 | 5A | F4 | FB | 08 | 0C | A0 | 50 |
См. ([3])
Структура шифра "Кузнечик" является вариантом подстановочно-перестановочной сети (SP-сети). Каждый раунд состоит из наложения ключа с помощью операции побитового XOR, нелинейной подстановки (S-блоков замен) и линейного перемешивания.
За счет преобразования всего блока данных на каждом шаге обеспечивается гораздо более быстрое перемешивание входных данных по сравнению со схемой Фейстеля. Кроме того, слой линейного преобразования конструируется таким образом, чтобы обеспечить максимально возможное рассеивание. Для этих целей используется так называемая MDS матрица --- используемая в качестве линейного преобразования $$f(x): F^n \rightarrow F^m$$ матрица над конечным полем $$F$$, такая, что любые два вектора вида $$(x, f(x)) \in F^{n+m}$$ имеют как минимум $$m + 1$$ различающихся компонент. То есть набор векторов вида $$(x, f(x))$$ обладает свойством максимальной разнесенности (maximum distance separable). Поэтому адекватная стойкость таких алгоритмов достигается за меньшее, по сравнению со схемой Фейстеля, число раундов.
Как и в алгоритме AES, линейное преобразование алгоритма "Кузнечик" использует операции с байтами, представляя их как элементы поля Галуа $$F=GF(2^8)$$. В "Кузнечике" оно построенного с помощью неприводимого полинома $$m(x) = x^8 + x^7 + x^6 + x + 1$$. SP-сети с линейным преобразованием, состоящим из двух частей, первая из которых похожа на операцию MixColumns, а вторая --- на операцию ShiftRows алгоритма AES, называют AES-подобными (like AES).
Байты-константы нам будет удобно зававать целыми числами, двоичные разряды которых есть соответствующие коэффициенты полинома. Например, под числом $$130 = 128 + 2 = 2^7 + 2^1$$ мы будем понимать байт $$x^7 + x^1 \in GF(2^8)$$.
Шифр "Кузнечик" имеет размер входного блока данных 128 бит, длину ключа 256 бит и выполняет 10 раундов шифрования. В последнем раунде выполняется только одна операция --- наложения раундового ключа.
Первой выполняется операция наложения ключа раунда с помощью побитового XOR: $$X[k](a) = k\oplus a$$.
Затем входной 128-битовый блок $$a$$ алгоритма шифрования представляется в виде последовательности 16 байтов, которые нумеруются справа налево, начиная с 0: $$a=a_{15} || a_{14} || \ldots || a_1 || a_0$$, где знаком $$||$$ обозначена операция конкатенации строк.
К каждому байту применяется нелинейная подстановка, задаваемая массивом
$$S$$ = (252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241. 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182).
Поскольку каждый байт $$a_i$$ может принимать значение от 0 до 255, массив $$S$$ имеет 256 элементов. Это значит, что при $$a_i=0$$ значение $$a_i$$ будет заменено на $$S(0)= 252$$, при $$a_i = 1$$ --- на $$S(1)=238$$, и так далее (все числа записаны в десятеричном виде). Для выходного блока в целом нелинейная подстановка может быть определена как
$$S(a)=S(a_{15}||\ldots ||a_0) = S(a_{15})||\ldots ||S(a_0).$$Линейное перемешивание $$L$$ шифра "Кузнечик" может быть описано с помощью линейного регистра сдвига $$R$$:
Шифрование 128-битного входного блока $$a$$ описывается следующей формулой:
$$E(a) = X[K_{10}LSX[K_9]LSX[K_8]\ldots LSX[K_1](a).$$Здесь $$K_i$$ --- раундовые ключи, записанные подряд преобразования $$LSX[K_i]$$ обозначают последовательное применение преобразований справа налево. То есть, сначала выполняется прибавление ключа, затем нелинейная подстановка $$S$$, затем линейное перемешивание $$L$$.
См. ([6])
В настоящее время используется большое количество самых разных алгоритмов блочного шифрования. Из всего многообразия мы расскажем лишь о тех алгоритмах, которые либо являются очень надежными, либо своим появлением оказали влияние на развитие криптографии. Одним из таких алгоритмов является IDEA.
Первый вариант шифра IDEA, предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey), появился в 1990 году. Он назывался PES (Proposed Encryption Standard, предложенный стандарт шифрования). В следующем году, после демонстрации Бихамом и Шамиром возможностей дифференциального криптоанализа, авторы усилили свой шифр против такого вскрытия и назвали новый алгоритм IPES (Improved Proposed Encryption Standard, улучшенный предложенный стандарт шифрования). В 1992 году название IPES было изменено на IDEA (International Data Encryption Algorithm, международный алгоритм шифрования данных).
IDEA основывается на некоторых впечатляющих теоретических положениях и, хотя криптоанализ добился некоторых успехов в отношении вариантов с уменьшенным количеством этапов, алгоритм все еще кажется сильным.
Его сегодняшняя известность объясняется тем, что он является частью PGP.
IDEA является блочным шифром, он работает с 64-битовыми блоками открытого текста. Длина ключа - 128 битов. Для шифрования и дешифрирования используется один и тот же алгоритм.
Как и другие, уже рассмотренные блочные шифры IDEA использует и запутывание, и рассеяние. Философия, лежащая в основе проекта, представляет собой "объединение операций из различных алгебраических групп". Смешиваются три алгебраические операции, и все они могут быть легко реализованы как аппаратно, так и программно.
Все операции выполняются над 16-битовыми субблоками. Эти три операции несогласованы в том смысле, что:
Комбинирование этих трех операций обеспечивает комплексное преобразование входа, существенно затрудняя криптоанализ IDEA по сравнению с DES, который базируется исключительно на операции "исключающее ИЛИ".
Все эти операции (а в алгоритме используются только они, перестановки на битовом уровне не применяются) работают с 16-битовыми подблоками. (Этот алгоритм даже эффективнее на 16-битовых процессорах.)
Схема IDEA представлена на рисунке 7.6. 64-битовый блок данных делится на четыре 16-битовых подблока: $$X_1$$, $$X_2$$, $$X_3$$, $$X_4$$. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алгоритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умножениям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец, четыре подблока объединяются с четырьмя подключами в окончательном преобразовании.
На каждом этапе события происходят в следующей последовательности:
(рис 7.6) Схема алгоритма IDEA
Выходом этапа являются четыре подблока - результаты действий (11), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.
Затем выполняется заключительный, 9-й этап преобразования:
Наконец четыре подблока снова соединяются, образуя шифртекст.
Пример 7.11 Выполнить первый раунд зашифрования алгоритмом IDEA. Ключ: 1D52 34BC 891C 9C9B 1CC2 4363 A32B 132C, блок открытого текста: 89C1 B11D 63F0 FF23. Ключ и открытый текст задаются шестнадцатеричными последовательностями. Каждые четыре последовательных шестнадцатеричных разряда $$WXYZ$$ обозначают 16-битный блок $$Z+16(Y+16(X+16W))$$.
Решение.
Вначале выберем подключи первого раунда. Это первые 6 16-битных блоков ключа.
В обозначениях рисунка 7.6 имеем: $$X_1=89C1$$, $$X_2=B11D$$, $$X_3=63F0$$, $$X_4=FF23$$, $$Z_1^{(1)}=1D52$$, $$Z_2^{(1)}=34BC$$, $$Z_3^{(1)}=891C$$, $$Z_4^{(1)}=9C9B$$, $$Z_5^{(1)}=1CC2$$, $$Z_6^{(1)}=4363$$.
Будем обозначать результат $$i$$-го шага в алгоритме параграфа 7.7.2 через $$A_i$$.
Все операции будем проводить в шестнадцатеричной системе счисления. Результат применения одного раунда обозначим через $$X'_1$$, $$X'_2$$, $$X'_3$$, $$X'_4$$.
| $$A_1 = X_1 \odot Z_1^{(1)} = 89C1\odot 1D52 = (89C1\cdot 1D52)~(\mod 10001) = ED0C$$; |
| $$A_2 = X_2 \boxplus Z_2^{(1)} = B11D \boxplus 34BC = (B11D+34BC)~(\mod 10000) = E5D9$$; |
| $$A_3 = X_3 \boxplus Z_3^{(1)} = 5E1B \boxplus 891C = (63F0+891C)~(\mod 10000) = ED0C$$; |
| $$A_4 = X_4 \odot Z_4^{(1)} = FF23 \odot 9C9B = (FF23\cdot 9C9B)~(\mod 10001) = 321E$$; |
| $$A_5 = A_1 \oplus A_3 = ED0C \oplus ED0C = 0000$$; |
| $$A_6 = A_2 \oplus A_4 = E5D9 \oplus 321E = D7C7$$; |
| $$A_7 = A_5 \odot Z_5^{(1)} = 0000 \odot 1CC2 = (10000\cdot 1CC2)~(\mod 10001) = E33F$$; |
| $$A_8 = A_6\boxplus A_7 = D7C7\boxplus E33F =(D7C7+E33F)~(\mod 10000) = BB06$$; |
| $$A_9 = A_8 \odot Z_6^{(1)} = BB16\odot 4363 = (BB06\cdot 4363)~(\mod 10001) = B418$$; |
| $$A_{10} = A_7 \boxplus A_9 = E33F\boxplus B418 = (E33F+B418)~(\mod 10000) = 9757$$; |
| $$X'_1 = A_{11} = A_1 \oplus A_9 = ED0C \oplus B418 = 5914$$; |
| $$X'_2 = A_{12} = A_3 \oplus A_9 = ED0C \oplus B418 = 5914$$; |
| $$X'_3 = A_{13} = A_2 \oplus A_{10} = E5D9 \oplus 9757 = 728E$$; |
| $$X'_4 = A_{14} = A_4 \oplus A_{10} = 321E \oplus 9757 = A549$$. |
Создание подключей $$Z^{(i)}_j$$ также относительно несложно. Алгоритм использует всего 52 подключа (по шесть для каждого из восьми циклов и еще четыре для заключительного этапа). Сначала 128-битовый ключ делят на восемь 16-битовых подключей. Это -- первые восемь подключей для алгоритма (шесть подключей -- для первого цикла и первые два подключа -- для второго цикла). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей. Первые четыре из них используют во втором цикле; последние четыре -- в третьем цикле. Ключ снова циклически сдвигается влево еще на 25 бит для получения следующих восьми подключей и т.д., пока выполнение алгоритма не завершится.
Расшифрование осуществляют аналогичным образом, за исключением того, что порядок использования подключей --- обратный, и ряд значений подключей заменяется на обратные значения. Порядок использования подключей при зашифровании и расшифровании приведён в таблице 7.10. Через $$-a$$ обозначается противоположный к $$a$$ по модулю $$65536$$ элемент, через $$a^{-1}$$ --- обратный по умножению по модулю $$65537$$.
| Цикл | Подключи зашифрования | Подключи расшифрования |
|---|---|---|
| 1 | $$Z_1^{(1)},Z_2^{(1)},Z_3^{(1)},Z_4^{(1)},Z_5^{(1)},Z_6^{(1)}$$ | $${Z_1^{(9)}}^{-1},-Z_2^{(9)},-Z_3^{(9)},{Z_4^{(9)}}^{-1},Z_5^{(8)},Z_6^{(8)}$$ |
| 2 | $$Z_1^{(2)},Z_2^{(2)},Z_3^{(2)},Z_4^{(2)},Z_5^{(2)},Z_6^{(2)}$$ | $${Z_1^{(8)}}^{-1},-Z_2^{(8)},-Z_3^{(8)},{Z_4^{(8)}}^{-1},Z_5^{(7)},Z_6^{(7)}$$ |
| 3 | $$Z_1^{(3)},Z_2^{(3)},Z_3^{(3)},Z_4^{(3)},Z_5^{(3)},Z_6^{(3)}$$ | $${Z_1^{(7)}}^{-1},-Z_2^{(7)},-Z_3^{(7)},{Z_4^{(7)}}^{-1},Z_5^{(6)},Z_6^{(6)}$$ |
| 4 | $$Z_1^{(4)},Z_2^{(4)},Z_3^{(4)},Z_4^{(4)},Z_5^{(4)},Z_6^{(4)}$$ | $${Z_1^{(6)}}^{-1},-Z_2^{(6)},-Z_3^{(6)},{Z_4^{(6)}}^{-1},Z_5^{(5)},Z_6^{(5)}$$ |
| 5 | $$Z_1^{(5)},Z_2^{(5)},Z_3^{(5)},Z_4^{(5)},Z_5^{(5)},Z_6^{(5)}$$ | $${Z_1^{(5)}}^{-1},-Z_2^{(5)},-Z_3^{(5)},{Z_4^{(5)}}^{-1},Z_5^{(4)},Z_6^{(4)}$$ |
| 6 | $$Z_1^{(6)},Z_2^{(6)},Z_3^{(6)},Z_4^{(6)},Z_5^{(6)},Z_6^{(6)}$$ | $${Z_1^{(4)}}^{-1},-Z_2^{(4)},-Z_3^{(4)},{Z_4^{(4)}}^{-1},Z_5^{(3)},Z_6^{(3)}$$ |
| 7 | $$Z_1^{(7)},Z_2^{(7)},Z_3^{(7)},Z_4^{(7)},Z_5^{(7)},Z_6^{(7)}$$ | $${Z_1^{(3)}}^{-1},-Z_2^{(3)},-Z_3^{(3)},{Z_4^{(3)}}^{-1},Z_5^{(2)},Z_6^{(2)}$$ |
| 8 | $$Z_1^{(8)},Z_2^{(8)},Z_3^{(8)},Z_4^{(8)},Z_5^{(8)},Z_6^{(8)}$$ | $${Z_1^{(2)}}^{-1},-Z_2^{(2)},-Z_3^{(2)},{Z_4^{(2)}}^{-1},Z_5^{(1)},Z_6^{(1)}$$ |
| 9 | $$Z_1^{(9)},Z_2^{(9)},Z_3^{(9)},Z_4^{(9)}$$ | $${Z_1^{(1)}}^{-1},-Z_2^{(1)},-Z_3^{(1)},{Z_4^{(1)}}^{-1}$$ |
Пример 7.12 Имея ключ 1D52 34BC 891C 9C9B 1CC2 4363 A32B 132C для алгоритма IDEA, найти подключи четвертого раунда расшифровки. Порядок записи бит числа --- от младшего к старшему.
Отметим, что существует два способа записи бит в памяти ЭВМ: от старшего к младшему (Big-Endian) и от младшего к старшему (Little-Endian). Big-Endian использовался в ранних архитектурах ЭВМ, и для сохранения обратной совместимости остался в сетевых протоколах и некоторых форматах файлов. Little-Endian используется практически во всех современных архитектурах, поэтому мы используем его в нашей задаче.
Решение. Согласно таблице 7.10, нам нужно найти подключи $${Z_1^{(6)}}^{-1}$$, $$-Z_2^{(6)}$$, $$-Z_3^{(6)}$$, $${Z_4^{(6)}}^{-1}$$, $$Z_5^{(5)}$$, $$Z_6^{(5)}$$.
Поэтому необходимо сначала найти необходимые нам подключи для 5-го и 6-го раундов $$Z_1^{(6)}$$, $$Z_2^{(6)}$$, $$Z_3^{(6)}$$, $$Z_4^{(6)}$$, $$Z_5^{(5)}$$, $$Z_6^{(5)}$$.
Обозначим $$i$$-й 16-битный блок ключа, $$n$$ раз циклически сдвинутого влево на 25 бит, через $$K_i^{(n)}$$. Тогда данный нам исходный ключ состоит из блоков $$K_1^{(0)},\ K_2^{(0)},\ \ldots,\ K_8^{(0)}$$; нужный нам подключ $$Z_i^{(j)}$$ равен некоторому блоку $$K_m^{(n)}$$. Выпишем это соответствие, записывая индексы друг под другом:
| $$n:$$ | 000000001111111122222222333333334444444455555555 |
| $$m:$$ | 123456781234567812345678123456781234567812345678 |
| $$j:$$ | 111111222222333333444444555555666666777777888888 |
| $$i:$$ | 123456123456123456123456123456123456123456123456 |
В таблице отмечены требуемые нам подключи зашифрования. Имеем:
$$Z_1^{(6)}=K_7^{(3)},\ Z_2^{(6)}=K_8^{(3)}, Z_3^{(6)}=K_1^{(4)}, Z_4^{(6)}=K_2^{(4)}, Z_5^{(5)}=K_5^{(3)}, Z_6^{(5)}=K_6^{(3)}.$$Для выполнения циклического сдвига запишем наш ключ в бинарном виде. Для этого переведём каждый шестнадцатеричный блок в двоичную систему счисления:
$$1D52_{16} = 0001110101010010_2; \quad 34BC_{16}=0011010010111100_2;\quad \ldots$$и выпишем блоки последовательно, начиная от младшего бита к старшему:
$$0100101010111000\quad 0011110100101100\quad 0011100010010001\quad 1101100100111001 \\ 0100001100111000\quad 1100011011000010\quad 1101010011000101\quad 0011010011001000$$Для получения блока $$K_5^{(3)}$$ нужно сдвинуть ключ на $$3\cdot 25=75$$ бит влево. В полученной битовой последовательности биты с 1 по 16 --- блок $$K_1^{(3)}$$, c 17 по 32 --- блок $$K_2^{(3)}$$, ..., с 65 по 80 --- блок $$K_5^{(3)}$$. Таким образом, в исходном ключе блок $$K_5^{(3)}$$ располагается с $$75+65 - 128 = 12$$ по $$75+80 - 128 = 28$$ биты: 1100000111101001. Итак, $$K_5^{(3)} = 1001011110000011_2 = 38787_{10}=9383_{16}$$. Следующие 16 бит (0110000111000100) составляют ключ $$K_6^{(3)} = 0010001110000110_2 = 9094_{10}=2386_{16}$$. Следом идут $$K_7^{(3)} = 1001001101110001_2 = 37745_{10}=9371_{16}$$, $$K_8^{(3)}=1001100001010011_2 = 38995_{10}=9853_{16}$$.
Для получения $$K_1^{(4)}$ и $K_2^{(4)}$$ нужно сдвинуть ключ на 100 бит влево. В полученной битовой последовательности биты с 1 по 16 --- блок $$K_1^{(4)}$$, а с 17 по 32 --- блок $$K_2^{(4)}$$. Имеем:
| $$K_1^{(4)} = 1100101000110010_2 = 51762_{10}=CA32_{16},$$ |
| $$K_2^{(4)} = 0010000100110010_2 = 8498_{10}=2132_{16}.$$ |
Теперь мы можем найти подключи для расшифрования:
| $${Z_1^{(6)}}^{-1} = {K_7^{(3)}}^{-1} = 37745^{-1}~\mod 65537 = 53013_{10} = CF15_{16};$$ |
| $$-Z_2^{(6)} = -K_8^{(3)} = -38995~\mod 65536 = 26541_{10}=67AD_{16};$$ |
| $$-Z_3^{(6)} = -K_1^{(4)} = -51762~\mod 65536 = 13774_{10}=35CE_{16};$$ |
| $${Z_4^{(6)}}^{-1} = {K_2^{(4)}}^{-1} = 8498^{-1}~\mod 65537 = 4928_{10}=1340_{16};$$ |
| $$Z_5^{(5)} = K_5^{(3)} =9383_{16};$$ |
| $$Z_6^{(5)} = K_6^{(3)}=2386_{16}.$$ |
См. [1]
Через $$P_i$$ и $$C_i$$ обозначим открытый текст и соответствующий шифртекст, $$E$$ --- алгоритм шифрования.
Величины $$C_0$$ в режимах CBC и CFB и $$K_0$$ в режиме $$OFB$$ необходимо инициализировать некоторой величиной $$IV$$, називаемой вектором инициализации.
| Режим | Формула | Типичные области применения |
|---|---|---|
| Электронная кодовая книга (ЕСВ -- Electronic Code-book) | $$C_i = E_K(P_i)$$ | Защищенная передача отдельных значений (например, ключа шифрования) |
| Сцепление шифрованных блоков (СВС --- Cipher Block Chaining) | $$C_i = E_K(P_i\oplus C_{i-1})$$ | Поблочная передача данных общего назначения. Аутентификация |
| Шифрованная обратная связь (CFB -- Cipher Feedback) | $$C_i = E_K(C_{i-1}) \oplus P_i$$ | Потоковая передача данных общего назначения. Аутентификация |
| Обратная связь по выходу (OFB -- Output Feedback) | $$T_i = E_K(T_{i-1})$, $C_i = K_i\oplus P_i$$ | Потоковая передача данных по каналам с помехами (например, по спутниковой связи) |
| a) | Перечислите основные недостатки алгоритма DES и предложите пути их устранения. |
| b) | Выпишите в явном виде подстановку $$IP^{-1}$$. Найдите её разложение в произведение независимых циклов и вычислите её порядок. |
| c) | Докажите, что все преобразования стандарта DES являются четными подстановками на \ множестве всех 64-битовых слов. |
| d) | Докажите свойство дополнительности DES: $$E_{\overline{k}}(\overline{x})=\overline{E_k(x)},$$ где черта означает взятие дополнительного вектора, т.е. $$x\oplus \overline{x} = 0$$. |
Перечислите отличия ГОСТ 28147-89 от DES. Докажите, что всякое преобразование стандарта ГОСТ 28147-89 обратимо и является четной подстановкой на множестве всех 64-битовых слов.
| a) | Какова вероятность того, что $$E_k$$ и $$E_{K'}$$ на самом деле являются разными отображениями? |
| b) | Какова вероятность того, что $$E_k$$ и $$E_{K'}$$ согласуются на другом наборе из $$t'$$ соответствующих пар открытого и шифрованного текста, где $$0\leq t'\leq N-1$$? |
| a) | нужно, чтобы возможные \ искажения битов при передаче данных не распространялись на последующие порции данных? |
| b) | нужна большая надежность в отношении нарушений типа модификации потока данных? |
| c) | Почему при передаче достаточно длинных сообщений режим ECB может не обеспечивать необходимый уровень защиты? |
| d) | Обоснуйте необходимость защиты инициализующего вектора (IV) в режиме сцепления шифрованных блоков (CBC). |
| e) | Алгоритм DES -- это блочный шифр с размером блока 64 бит. |
Однако бывает необходимо каждый символ шифровать и сразу передавать адресату, не дожидаясь окончания шифрования остальной части сообщения. Предложите способ использовать DES для этого.
| a) | $$f={x}_{1} {x}_{2}\oplus {x}_{1} {x}_{3} \oplus {x}_{2} {x}_{3}\oplus {x}_{1} {x}_{2} {x}_{3}$$; |
| b) | $$f={x}_{1}\oplus {x}_{2}\oplus {x}_{2} {x}_{3}$$; |
| c) | $$f={x}_{1} {x}_{2}\oplus {x}_{3}\oplus {x}_{1} {x}_{2} {x}_{4}$$. |
| a) | Почему операция умножения в IDEA выполняется по модулю $$2^{16}+1$$, а не по модулю $$2^{16}$$? |
| b) | Почему операция сложения в IDEA выполняется по модулю $$2^{16}$$, а не по модулю $$2^{16}+1$$? |
| c) | Докажите, что никакие две из трех операций IDEA не подчиняются дистрибутивному закону. Например: $$a\oplus (b\odot c)\neq (a\oplus b)\odot (a\oplus c)$$. |
| d) | Докажите,что никакие две из трех операций IDEA не подчиняются ассоциативному закону. Например: $$a\boxplus(b\oplus c)\neq (a\boxplus b)\oplus c$$. |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.