Feistel_cipher_without_s_blocks.tex

\subsection{Схема Фейстеля без $s$-блоков}
\selectlanguage{russian}

Пусть функция $F$ является простой линейной комбинацией некоторых битов правой части и ключа раунда относительно операции XOR. Тогда можно записать систему линейных уравнений битов выхода $y_i$ относительно битов входа $x_i$ и ключа $k_i$ после всех 16 раундов в виде
    \[ y_i = (\sum_{i=0}^{n_1} a_i x_i) \oplus (\sum_{i=0}^{n_2} b_i k_i), \]
где суммирование производится по модулю 2, коэффициенты $a_i$ и $b_i$ известны и равны 0, 1,  количество битов в блоке открытого текста равно $n_1$, количество битов ключа равно $n_2$.

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

$s$-блоки замены создают нелинейность в уравнениях выхода $y_i$ относительно сообщения и ключа.


\subsubsection[Схема Фейстеля в ГОСТ 28147-89 без $s$-блоков]{Схема Фейстеля в ГОСТ 28147-89 без \protect\\ $s$-блоков}

В отличие от устаревшего алгоритма DES блоковый шифр ГОСТ без $s$-блоков намного сложнее для взлома, так как для него нельзя записать систему линейных уравнений:
\[
    \begin{array}{l}
        L_1 = R_0, \\
        R_1 = L_0 \oplus ((R_0 \boxplus K_1) \lll 11), \\
    \end{array}
\] \[
    \begin{array}{l}
        L_2 = R_1 = L_0 \oplus ((R_0 \boxplus K_1) \lll 11), \\
        R_2 = L_1 \oplus (R_1 \boxplus K_2)  = \\
        ~~~~~= R_0 \oplus (((L_0 \oplus ((R_0 \boxplus K_1) \lll 11)) \boxplus K_2) \lll 11). \\
    \end{array}
\]

Операция $\boxplus$ нелинейна по XOR. Например, только на трех операциях $\oplus$, $\boxplus$ и $\lll f(R_i)$ без использования $s$-блоков построен блоковый шифр RC5, который по состоянию на  2010 г. не был взломан.