Шифрование с симметричным ключом используется повсеместно в современном мире - хранение и передача информации, электронная почта, даже просмотр видео на YouTube. Сильные симметричные шифры включают в себя правильно построенные S-блоки. В своей статье я разберу различные способы создания S-блоков и сравню их.

1. Что такое S-блок

S-блок - функция, принимающая на входе n бит, преобразующая их по определённому алгоритму и возвращающая на выходе m бит. S-блоки широко используются в большинстве блочных шифров. Они могут различаться по входным и выходным размерам (n и m), могут создаваться детерминировано или случайно, а также могут быть неизменными (фиксированными) или генерироваться на основе ключа. S-блоки могут быть представлены или в виде таблицы (как в DES), или в качестве алгебраической булевой функции (как в AES). Важными критериями при составлении S-блока являются его нелинейность и критерий распространения булевых функций. Для того, чтобы рассматривать S-блок как последовательность булевых функций, сначала поймём, какое вообще отношение имеют булевы функции к криптографии.

2. Булевы функции в криптографии

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

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

Стандартно секретный ключ размножается до гаммы с помощью устройств, называемых регистрами сдвига с линейной обратной связью (Linear Feedback Shift Register, сокращённо LSFR).

По К. Шеннону шифрование должно использовать принципы рассеивания (распространение влияния одного знака открытого текста на много знаков шифртекста и одного элемента ключа на много знаков шифртекста) и запутывания (усложнения взаимосвязи между элементами данных). Устройство LSFR реализует принцип рассеивания, но не запутывания, поэтому общепринято для запутывания использовать несколько регистров LSFR.

Пусть, например, длина секретного ключа равна L. Этот ключ можно разделить между несколькими регистрами длин L_i так, чтобы L_1 + L_2 + ... + L_n = L , и комбинировать выходы всех регистров посредством булевой функции .

Чтобы идти дальше, нужно ввести несколько терминов.

3. Немного булевой линейной алгебры

Пусть F_2 -поле Галуа порядка 2 (или просто набор $\{ 0, 1\}$ ), а F_2^j - j -размерное векторное пространство над полем F_2 .

S-блок размерами $s \times t$ может быть представлен в качестве отображения:

$S: F_2^{s} \longrightarrow F_2^{t}$

Булева функция аргументов это отображение:

$f: F_2^{s} \longrightarrow F_2$

Таким образом, S-блок может быть представлен в виде последовательности булевых функций:

Пусть для булевой функции аргументов $f_i: F_2^{s} \longrightarrow F_2, i = 1, 2, ..., t$ целое число - десятичное представление её аргументов ( x_1, x_2, ..., x_s ). Пусть y_z = f(x_1, x_2, ..., x_s) . Обозначим таблицу истинности функции как

$[y_0, y_1, ..., y_{2^{s} минус 1}]$ .

Булева функция также может быть представлена в виде алгебраической нормальной формы (полинома Жегалкина) с 2^s коэффициентами:

$\displaystyle f(x) = a_o \oplus \sum_{i = 1}^{s}a_{i}x_{i} \oplus \sum_{1 \leq i < j \leq s}{}a_{ij}x_{i}x_{j} \oplus ... \oplus a_{12..s}x_{1}x_{2}...x_{s},$

где $\sum$ обозначает суммирование по модулю 2.

Булева функция аргументов называется аффинной, если её можно представить в виде:

$f(x_1, x_2, ..., x_{s}) = a_{0} \oplus a_{1}x_{1} \oplus a_{2}x_{2} \oplus ... \oplus a_{s}x_{s}, a_{i} \in F_{2}.$

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

4.Нелинейные булевы функции

Булева функция $f: F_2^s \longrightarrow F_2$ , не являющаяся аффинной, называется нелинейной булевой функцией.

Вес Хэмминга бинарного вектора $x \in F_2^s$ , обозначаемый как hwt(x) - это количество единиц в этом векторе. Расстояние Хэмминга между двумя булевыми функциями $f, g: F_{2}^{s} \longrightarrow F_2$ определяется как:

$\displaystyle d(f, g) = \sum_{x \in \{ 0, 1 \}^s}f(x) \oplus g(x).$

Порядок нелинейности (обозначается как ord(f) булевой функции f(x) - это максимальное количество переменных в произведении с ненулевым коэффициентом a_J , где - подмножество множества $\{1,2,...,s\}$ . Если - пустое множество, этот коэффициент обозначается как a_0 и называется коэффициентом нулевого порядка. a_1, a_2, ..., a_s - коэффициенты первого порядка, $a_{12}, a_{13}, ..., a_{(s-1)s}$ - коэффициенты второго порядка. Число всех коэффициентов АНФ - 2^s .

Обозначим число всех (нулевых и ненулевых) коэффициентов порядка функции как $\sigma_{i}(f)$ . Для функции аргументов есть столько коэффициентов заданного порядка, сколько есть комбинаций из элементов в элементном множестве,

$\sigma_{i}(f) = \binom{s}i.$

Расстояние от булевой функции до множества X_s булевых функций аргументов

$\displaystyle \delta(f) = min_{g \in X_s} d(f, g).$

Расстояние от функции до множества A_s аффинных функций - это расстояние от функции до ближайшей функции $g \in A_s.$ Расстояние от функции до множества всех аффинных функций называется нелинейностью функции и обозначается как N_f,

$\displaystyle N_f = min_{g \in A_{s}} d(f, g).$

Известно, что $\displaystyle N_f \leq min_{g \in A_{s}} d(f, g).$ Если - чётное, тогда существуют функции с $N_f = 2^{s - 1} - 2^{s/2 - 1}$ . Эти функции называются бент-функциями.

Рассмотрим бент-функции поподробнее.

5.Бент-функции

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

Для того, чтобы рассмотреть некоторые алгоритмы генерирования бент-функций, введём ещё несколько определений.

Пусть $N_0[y_0, y_1, ..., y_{{2^s} - 1}]$ - число нулей в таблице истинности $[y_0, y_1, ..., y_{2^s - 1}]$ функции , а $N_1[y_0, y_1, ..., y_{2^s - 1}]$ - число единиц. Булева функция называется сбалансированной, если $N_0[y_0, y_1, ..., y_{2^s - 1}] = N_1[y_0, y_1, ..., y_{2^s - 1}]$ .

Булева функция $f: F_2^{s} \longrightarrow F_2$ называется идеально нелинейной тогда и только тогда, когда $f(x) \oplus f(x \oplus \alpha)$ сбалансирована для любого $\alpha \in F_2^{s}$ такого, что $1 \leq hwt(\alpha) \leq s$ . Для идеальной нелинейной булевой функции любое изменение входных данных приводит к изменению выходных данных с вероятностью $\frac{1}{2}$ .

6. Алгоритмы генерирования бент-функций

6.1 Детерминированные алгоритмы

Пусть B_s - множество идеальных нелинейных функций аргументов с чётным .

Алгоритм 1.

Вход: $a, b \in B_6, a \neq b$ .

Выход: бент-функции в множестве B_8 бент-функций 8 аргументов.

Метод: функция $g: F_2^8 \longrightarrow F_2$ , определённая как:

$\begin{equation*} g(x_0, ..., x_7) = \begin{cases} a(x_0, ..., x_5), x_6 = 0, x_7 = 0\\ a(x_0, ..., x_5), x_6 = 0, x_7 = 1\\ b(x_0, ..., x_5), x_6 = 1, x_7 = 0\\ b(x_0, ..., x_5) \oplus 1, x_6 = 1, x_7 = 1 \end{cases} \end{equation*}$

Алгоритм 2.

Вход: бент-функции аргументов a(x) , b(x) и c(x) такие, что $a(x) \oplus b(x) \oplus c(x)$ - бент-функция.

Выход: бент-функция s+2 аргументов.

Метод:

$g(x, x_{s + 1}, x_{s + 2}) = a(x)b(x) \oplus b(x)c(x) \oplus c(x)a(x) \oplus [a(x)b(x)]x_{s + 1} \oplus [a(x) \oplus c(x)]x_{s + 2} \oplus x_{s + 1}x_{s + 2}$

Большинство известных конструкторов идеальных (или бент-) функций берут на входе идеальные нелинейные функции аргументов и генерируют идеальные нелинейные функции s+2 аргументов. Большим недостатком этих методов является их детерминированность. Только идеальные нелинейные функции 4 и 6 аргументов выбираются случайно и результирующая функция получается по одной и той же детерминированной формуле каждый раз. Даже если есть какой-то "случайный" элемент в таком генерировании (например, добавочный линейный элемент), это не добавляет никакой новой особенности к сгенерированной функции.

Алгоритм 3.

Вход: биективное отображение $\pi: F_2^{s/2} \longrightarrow F_2^{s/2}$ , функция $g: F_2^{s/2} \longrightarrow F_2$ , - чётное.

Выход: бент-функция $f_M:F_2^{s} \longrightarrow F_2$ , называемая функцией Майорана.

Метод: $f_M(x||y) = \pi(x) * y \oplus g(x),$ где $x, y \in F_2^{s/2}$ , - конкатенация и $(a_{s/2 - 1}, a_{s/2 - 2}, ..., a_0) * (b_{s/2 - 1}, b_{s/2 - 2}, ..., b_0) = a_{s/2 - 1}b_{s/2 - 1} \oplus a_{s/2 - 2}b_{s/2 - 2} \oplus ... \oplus a_0b_0$

Пусть (a_0, a_1, ..., a_7) - перестановка $\{0, 1, ..., 7\}$ . Функция $\widehat{f}(x_0, x_1, ..., x_7)= f_{M}(x_{a0}, x_{a1}, ..., x_{a7}),$ где f_M - функция Майорана, является бент-функцией. Я буду отсылаться к этим функциям как к функциям с переставленными входными данными.

6.2 Случайное генерирование бент-функций

Построенные "руками" бент-функции имеют некоторые врождённые особенности, вызванные методикой их создания. Это, очевидно, нежелательно в силу того, что эти особенности могут быть использованы для криптоаналитических атак.

Однако, найти все бент-функции случайным поиском по булевым функциям 6 аргументов невозможно. Здесь может пригодиться представление функции в виде полинома Жегалкина. Работа с ним позволяет контролировать нелинейные характеристики сгенерированных функций. Базовые особенности бент-функций могут быть использованы для того, чтобы существенно сузить область поиска, что делает генерирование бент-функций возможным даже на обычном ПК.

Алгоритм генерирования бент-функций в области определения полинома Жегалкина берёт на вход минимальное и максимальное количество коэффициентов каждого порядка, которое итоговая функция может иметь. Так как нелинейный порядок бент-функций меньше или равен s/2 , в полиноме Жегалкина бент-функции не может быть порядка выше s/2 . Это ограничение значительно уменьшает область поиска.

Количество коэффициентов степеней меньше или равных s/2 может быть зафиксировано или случайно выбрано внутри допустимого диапазона. Если количество коэффициентов для заданного порядка зафиксировано, тогда все сгенерированные функции будут иметь такое же количество коэффициентов этого порядка, но сами коэффициенты будут разными в каждой сгенерированной функции. Если количество коэффициентов для заданного порядка выбрано случайно, тогда все сгенерированные функции будут иметь не только разные коэффициенты, но и разное количество этих коэффициентов порядка .

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

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

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

Также у этого подхода есть свои ограничения. Во-первых, количество возможных функций растёт вместе с числом коэффициентов высших порядков (i > 2) и генерирование бент-функции становится невыполнимым. Поэтому алгоритм хорошо работает с небольшим количеством коэффициентов высших порядков (например, менее 6 для s = 8, i = 3, 4 ). Во-вторых, этот метод не генерирует все возможные бент-функции с равными вероятностями.

Алгоритм 4. (случайно сгенерированные бент-функции)

Вход:

- число аргументов ( - чётное)
для каждого порядка такого, что $0 \leq s/2$ определим минимальное $cmin_{ord}$ и максимальное $cmax_{ord}$ количество коэффициентов полинома Жегалкина,

$0 \leq cmin_{ord} \leq cmax_{ord} \leq \binom{s}{ord}.$

Выход:

Повторять шаги (1.1) и (1.2) для каждого порядка такого, что $0 \leq ord \leq s/2$ :

-случайно сгенерированная идеальная нелинейная функция $f_{ANF}$ в представлении полинома Жегалкина
случайно сгенерированная идеальная нелинейная функция $f_{TT}$ в форме таблицы истинности.

Метод:

Повторять шаги (1.1) и (1.2) для каждого порядка такого, что $0 \leq ord \leq s/2$ :
- 1.1 генерировать случайное количество коэффициентов $c_{ord}$ полинома Жегалкина для заданного порядка такого, что $cmin_{ord} \leq c_{ord} \leq cmax_{ord}$ ,
  1.2 для полинома Жегалкина зафиксировать случайно значение 1 для коэффициентов порядка .
Преобразовать $f_{ANF}$ к $f_{TT}$ .
Вычислить расстояние от $f_{TT}$ до множества аффинных функций.
Если расстояние, вычисленное в шаге (3), равно $2^{s -1} - 2^{{s/2} - 1}$ , тогда $f_{TT}$ и $f_{ANF}$ - бент-функции, останавливаемся; иначе идём к (1).

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

7. Нелинейность S-блоков

Нелинейность S-блока - функции $S: F_2^s \longrightarrow F_2^t$ такой, что S(x_1, x_2, ..., x_s) = (f_1(x_1, x_2, ..., x_s), f_2(x_1, x_2, ..., x_s), ..., f_t(x_1, x_2, ..., x_s)) , вычисляется как минимальная нелинейность всех линейных комбинаций функций, являющихся компонентами . То есть,

$N_S = min\{ N_{f_{J}} | f_{J} = \sum_{i \in J}, J \subseteq (1, 2, ..., t)\}.$

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

На графиках ниже изображены графики распределения нелинейностей S-блоков, построенных из шести 8-аргументных функций.

График 1. Зависимость числа S-блоков, построенных из случайных булевых функций, от их нелинейности

График 2. Зависимость числа S-блоков, построенных из случайных сбалансированных булевых функций, от их нелинейности

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

График 3. Зависимость числа S-блоков, построенных из сконструированных булевых функций, от их нелинейности

Немного лучше, чем S-блоки из случайных сбалансированных булевых функций, справляются S-блоки из сконструированных бент-функций (Алгоритм 2) (см. График 3). Только при высокой нелинейности, равной 98, немного больше S-блоков строится с использованием сконструированных функций.

График 4. Зависимость числа S-блоков, построенных из случайно сгенерированных бент-функций, от их нелинейности

Другое распределение нелинейности характеризует S-блоки, построенные из случайно сгенерированных бент-функций (см. График 4). В этой группе существуют S-блоки наибольшей нелинейности 112, их около $5\%$ (их не видно на графике, так там наибольшее значение 104). Также здесь примерно в 20 раз больше S-блоков очень высокой нелинейности 100, чем в случае S-блоков, построенных из сконструированных бент-функций или из случайных сбалансированных функций.

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

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

8. Заключение

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

Мои источники

И. Агафонова - Криптографические свойства нелинейных булевых функций
Anna Grocholewska-Czurylo and Janusz Stoklosa - Random Generation of S-Boxes for Block Ciphers
Meier, W., Staffelbach, O - Nonlinearity criteria for cryptographic functions
Википедия - S-блок(информатика)
Wikipedia - S-box
Wikipedia - Bent functions

Как создаются S-блоки