Feistel_cipher_without_s_blocks.tex

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

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

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

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


\subsubsection[Схема Фейстеля в ГОСТ 28147-89 без s-блоков]{Схема Фейстеля в~ГОСТ~28147-89 без~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 г. не был взломан.