Сеть Фейстеля

Сеть Фе́йстеля, конструкция Фейстеля (англ. Feistel network, Feistel cipher) — один из методов построения блочных шифров. Сеть состоит из ячеек, называемых ячейками Фейстеля. На вход каждой ячейки поступают данные и ключ. На выходе каждой ячейки получают изменённые данные и изменённый ключ. Все ячейки однотипны, и говорят, что сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру. Ключ выбирается в зависимости от алгоритма шифрования/расшифрования и меняется при переходе от одной ячейки к другой. При шифровании и расшифровании выполняются одни и те же операции; отличается только порядок ключей. Ввиду простоты операций сеть Фейстеля легко реализовать как программно, так и аппаратно. Большинство современных блочных шифров (DES, RC2, RC5, RC6, Blowfish, FEAL, CAST-128, TEA, XTEA, XXTEA и др.) используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть (AES и др.).

История

В 1971 году Хорст Фейстель (англ. Horst Feistel) запатентовал два устройства, реализующие различные алгоритмы шифрования, позже получившие название «Люцифер» («Lucifer»). Одно из этих устройств использовало конструкцию, впоследствии названную «сетью Фейстеля» («Feistel cipher», «Feistel network»). Тогда Фейстель работал над созданием новых криптосистем в стенах IBM вместе с Доном Копперсмитом (англ. Don Coppersmith). Проект «Люцифер» был скорее экспериментальным, но стал основой для алгоритма DES (англ. data encryption standard). В 1973 году журнал «Scientific American» опубликовал статью Фейстеля «Криптография и компьютерная безопасность» («Cryptography and computer privacy»), в которой раскрыты некоторые важные аспекты шифрования и приведено описание первой версии проекта «Люцифер». В первой версии проекта «Люцифер» сеть Фейстеля не использовалась.

На основе сети Фейстеля был спроектирован алгоритм DES. В 1977 году власти США приняли стандарт FIPS 46-3, признающий DES стандартным методом шифрования данных. DES некоторое время широко использовался в криптографических системах. Итеративная структура алгоритма позволяла создавать простые программные и аппаратные реализации.

Согласно некоторым данным, в СССР уже в 1970-е годы КГБ разрабатывала блочный шифр, использовавший сеть Фейстеля, и, вероятно, именно этот шифр в 1990 году был принят в качестве ГОСТ 28147-89.

В 1987 году были разработаны алгоритмы FEAL и RC2. Сети Фейстеля получили широкое распространение в 1990-е годы — в годы появления таких алгоритмов, как Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) и других.

2 января 1997 года институт NIST объявил конкурс по созданию нового алгоритма шифрования данных, призванного заменить DES. Новый блочный шифр получил название AES (англ. advanced encryption standard) и был утверждён 26 мая 2002 года. В AES вместо сети Фейстеля используется подстановочно-перестановочная сеть.

Конструкция блочного шифра на основе сетей Фейстеля

Простое описание

Шифрование

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

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

• Информация разбивается на блоки одинаковой (фиксированной) длины. Полученные блоки называются входными, так как поступают на вход алгоритма. В случае, если длина входного блока меньше, чем размер, который выбранный алгоритм шифрования способен зашифровать единовременно (размер блока), то блок удлиняется каким-либо способом. Как правило длина блока является степенью двойки, например, составляет 64 бита или 128 бит.

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

• Выбранный блок делится на два подблока одинакового размера — «левый» (<math>L_0</math>) и «правый» (<math>R_0</math>).
• «Левый подблок» <math>L_0</math> изменяется функцией f с использованием раундового ключа <math>K_0</math>:

<math>x = f( L_0, K_0 ).</math>

• Результат складывается по модулю 2 («xor») с «правым подблоком» <math>R_0</math>:

<math>x = x \oplus R_0.</math>

• Результат будет использован в следующем раунде в роли «левого подблока» <math>L_1</math>:

<math>L_1 = x.</math>

• «Левый подблок» <math>L_0</math> текущего раунда будет использован в следующем раунде в роли «правого подблока» <math>R_1</math>:

<math> R_1 = L_0. </math>

• По какому-либо математическому правилу вычисляется раундовый ключ <math>K_1</math> — ключ, который будет использоваться в следующем раунде.

Перечисленные операции выполняются N-1 раз, где N — количество раундов в выбранном алгоритме шифрования. При этом между переходами от одного раунда (этапа) к другому изменяются ключи: <math>K_0</math> заменяется на <math>K_1</math>, <math>K_1</math> — на <math>K_2</math> и т. д.).

Расшифрование

Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке, то есть не от первого к N-му, а от N-го к первому.

Алгоритмическое описание

• Блок открытого текста делится на две равные части: <math>( L_0, \ R_0 )</math>.
• В каждом раунде вычисляются:

<math> L_i\ =\ R_{i-1} \oplus f( L_{i-1}, K_{i-1} );</math>

<math> R_i\ =\ L_{i-1},</math>

где:

• i — номер раунда; <math> i = 1 \ldots N ;</math>
• N — количество раундов в выбранном алгоритме шифрования;
• <math>f</math> — некоторая функция;
• <math> K_{i-1} </math> — ключ i-1-го раунда (раундовый ключ).

Результатом выполнения <math>N</math> раундов является <math>( L_N,\ R_N )</math>. В N-м раунде перестановка <math>L_N</math> и <math>R_N</math> не производится, чтобы была возможность использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования ключей (<math>K_N, K_{N-1}, \ldots, K_0</math> вместо <math>K_0, K_1, \ldots, K_N</math>):

<math> L_{i-1}\ = \ R_{i} \oplus f( L_{i},\ K_{i-1} )</math>

<math> R_{i-1}\ = \ L_i.</math>

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

Достоинства:

• обратимость алгоритма независимо от используемой функции f;
• возможность выбора сколь угодно сложной функции f.

Математическое описание

Рассмотрим пример. Пусть:

• X — блок данных, поступающий на вход (входной блок);
• A — некоторое инволютивное преобразование (или инволюция) — взаимно-однозначное преобразование, которое является обратным самому себе, то есть для каждого (∀) X справедливо выражение:

<math> A A X = A^2 X = X, \forall X;</math>

• Y — блок данных, получаемый на выходе (результат).

При однократном применении преобразования A к входному блоку X получится выходной блок Y:

<math> Y = A X .</math>

При применении преобразования A к результату предыдущего преобразования — Y получится:

<math> A Y = A A X = X, \forall X .</math>

Пусть входной блок X состоит из двух подблоков L и R равной длины:

<math> X = ( L, R ) . </math>

Определим два преобразования:

• <math>G( X, K )</math> — шифрование данных X с ключом K:

<math> G( X, K ) = G( ( L, R ), K ) = ( L \oplus F( K, R ), R );</math>

• <math>T( L, R )</math> — перестановка подблоков L и R:

<math> T( L, R ) = ( R, L ) . </math>

Введём обозначения:

• однократное применение преобразования G:

<math> \tilde{X} = ( \tilde{L}, \tilde{R} ) = GX ; </math>

• двукратное применение преобразования G:

<math> \tilde{ \tilde{X} } = ( \tilde{ \tilde{L} }, \tilde{ \tilde{R} } ) = G^2 X . </math>

Докажем инволютивность двукратного преобразования G (<math>G^2</math>).

Несложно заметить, что преобразование G меняет только левый подблок L, оставляя правый R неизменным:

<math> \tilde{ L } = L \oplus F( K, R ) ; </math>

<math> \tilde{ R } = R . </math>

Поэтому далее будем рассматривать только подблок L. После двукратного применения преобразования G к L получим:

<math> \tilde{ \tilde{L} } = \tilde{L} \oplus F( K, \tilde{R} ) = \tilde{L} \oplus F( K, R ) = L \oplus F( K, R ) \oplus F( K, R ) = L.</math>

Таким образом:

<math> G^2 L = L ; </math>

<math> G^2 R = R , </math>

следовательно

<math> G^2 X = X</math>

и G — инволюция.

Докажем инволютивность двукратного преобразования T (<math>T^2</math>).

<math> T^2 X = T^2( L, R ) = T( R, L ) = ( L, R ) = X .</math>

Рассмотрим процесс шифрования. Пусть:

• X — входное значение;
• <math>G_i</math> — преобразование с ключом <math>K_i</math>;
• <math>Y_i</math> — выходное значение, результат i-го раунда.

Тогда преобразование, выполняемое на i+1-м раунде, можно записать в виде:

<math> Y_{i+1} = T G_i Y_i </math>.

Преобразование, выполняемое на 1-м раунде:

<math> Y_1 = T G_1 X . </math>

Следовательно, выходное значение после m раундов шифрования будет равно:

<math> Y_m = T G_m Y_{m-1} = T G_m T G_{m-1} \ldots T G_1 X . </math>

Можно заметить, что на последнем этапе не обязательно выполнять перестановку T.

Расшифрование ведётся применением всех преобразований в обратном порядке. В силу инволютивности каждого из преобразований обратный порядок даёт исходный результат:

<math> X = G_1 T G_2 T \ldots G_{m-1} T G_m T( Y_m ) = G_1 T G_2 T \ldots G_{m-1} T( Y_{m-1} ) = \ldots = G_1 T( Y_1 ) = X .</math>

Функции, используемые в сетях Фейстеля

В своей работе «Криптография и компьютерная безопасность» Хорст Фейстель описывает два блока преобразований (функций <math>f( L_{i},\ K_{i} )</math>):

• блок подстановок (s-блок, англ. s-box);
• блок перестановок (p-блок, англ. p-box).

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

Термин «блок» в оригинальной статье используется вместо термина «функция» вследствие того, что речь идёт о блочном шифре и предполагалось, что s- и p-блоки будут цифровыми микросхемами (цифровыми блоками).

S-блок

Блок подстановок (s-блок, англ. s-box) состоит из следующих частей:

• дешифратор — преобразователь n-разрядного двоичного сигнала в одноразрядный сигнал по основанию <math>2^n</math>;
• система коммутаторов — внутренние соединения (всего возможных соединений <math>2^n!</math>);
• шифратор — преобразователь сигнала из одноразрядного <math>2^n</math>-ричного в n-разрядный двоичный.

Анализ n-разрядного S-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений крайне велико (<math>2^n</math>). На практике блок подстановок используется как часть более сложных систем.

В общем случае s-блок может иметь несовпадающее число входов/выходов, в этом случае в системе коммутации от каждого выхода дешифратора может идти не строго одно соединение, а 2 или более или не идти вовсе. То же самое справедливо и для входов шифратора.

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

Таблица замены для приведённого 3-разрядного s-блока

№ комбинации	0	1	2	3	4	5	6	7
Вход	000	001	010	011	100	101	110	111
Выход	011	000	001	100	110	111	010	101

P-блок

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

Криптоанализ ключа для n-разрядного p-блока проводится путём подачи на вход n-1 различных сообщений, каждое из которых состоит из n-1 нуля («0») и 1 единицы («1») (или наоборот, из единиц и нуля).

Циклический сдвиг

Можно показать, что циклический сдвиг является частным случаем p-блока.

В простейшем случае (сдвиг на 1 бит), крайний бит отщепляется и перемещается на другой конец регистра или шины. В зависимости от того какой бит берётся, правый или левый, сдвиг называется вправо или влево. Сдвиги на большее число бит можно рассматривать, как многократное применение сдвига на 1.

Циклический сдвиг на m бит для n-разрядного входа (m < n)

Направление сдвига	Порядок следования битов до сдвига	Порядок следования битов после сдвига
Влево	<math>b_0,b_1,b_2, ... , b_{n-1}</math>	<math>b_m, b_{m+1}, ... b_{n-1}, b_0, b_1, ... , b_{m-1}</math>
Вправо	<math>b_0,b_1,b_2, ... , b_{n-1}</math>	<math>b_{n-m}, b_{n-m+1}, ... b_{n-1}, b_0, b_1, ... , b_{n-m-1}</math>

Сложение по модулю n

Операция «сложение по модулю n» обозначается как

( A + B ) mod n

и представляет собой остаток от деления суммы A + B на n, где A и B — числа.

Можно показать, что сложение двух чисел по модулю n представляется в двоичной системе счисления в виде s-блока, у которого на вход подаётся число A, а в качестве системы коммутации s-блока используется циклический сдвиг влево на B разрядов.

В компьютерной технике и электронике операция сложения, как правило, реализована как сложение по модулю <math>n = 2 ^ m</math>, где m — целое (обычно m равно разрядности машины). Для получения в двоичной системе

A + B mod <math>2^m</math>

достаточно сложить числа, после чего отбросить разряды начиная с m-того и старше.

Умножение по модулю n

Умножение по модулю n обозначается как

( A * B ) mod n

и представляет собой остаток от деления произведения A * B на n, где A и B — числа.

В персональных компьютерах на платформе x86 при перемножении двух m-разрядных чисел получается число разрядностью 2*m. Чтобы получить остаток от деления на <math>2^m</math> нужно отбросить m старших бит.

Пример реализации на языке Си

Общий вид алгоритма шифрования, использующего сеть Фейстеля:

/* Функция, выполняющая преобразование подблока с учётом значения ключа (по ключу). 
Реализация зависит от выбранного алгоритма блочного шифрования. */
int f (
        int subblock,  /* преобразуемый подблок */
        int key        /* ключ */
);  /* возвращаемое значение - преобразованный блок */

/* Функция, выполняющая шифрование открытого текста */
void crypt (
        int * left,   /* левый входной подблок */
        int * right,  /* правый входной подблок */
        int rounds,   /* количество раундов */
        int * key     /* массив ключей (по ключу на раунд) */
) {
    int i, temp;
    for ( i = 0; i < rounds; i++ )
    {
        temp = *right ^ f( *left, key[i] );
        *right = *left;
        *left = temp;
    }
}

/* Функция, выполняющая расшифрование текста */
void decrypt (
        int * left,   /* левый зашифрованный подблок */
        int * right,  /* правый зашифрованный подблок */
        int rounds,   /* количество раундов */
        int * key     /* массив ключей (по ключу на раунд) */
) {
    int i, temp;
    for ( i = rounds - 1; i >= 0; i-- )
    {
        temp = *left ^ f( *right, key[i] );
        *left = *right;
        *right = temp;
    }
}

Достоинства и недостатки

Достоинства:

• простота аппаратной реализации на современной электронной базе;
• простота программной реализации в силу того, что значительная часть функций поддерживается на аппаратном уровне в современных компьютерах (например, сложение по модулю 2 («xor»), сложение по модулю <math>2^n</math>, умножение по модулю <math>2^n</math>, и т. д.);
• хорошая изученность алгоритмов, построенных на основе сетей Фейстеля.

Недостатки:

• за один раунд шифруется только половина входного блока.

Теоретические исследования

Сети Фейстеля были широко изучены криптографами в силу их обширного распространения. В 1988 году Майкл Люби (англ. Michael Luby) и Чарльз Ракофф (англ. Charles Rackoff) провели исследования сети Фейстеля и доказали, что если раундовая функция является криптостойкой псевдослучайной, и используемые ключи независимы в каждом раунде, то 3 раундов будет достаточно для того, чтобы блочный шифр являлся псевдослучайной перестановкой, тогда как четырёх раундов будет достаточно для того, чтобы сделать сильную псевдослучайную перестановку.

«Псевдослучайной перестановкой» Люби и Ракофф назвали такую, которая устойчива к атаке с адаптивным выбором открытого текста, а «сильной псевдослучайной перестановкой» — псевдослучайную перестановку, устойчивую к атаке с использованием выбранного шифрованного текста.

Иногда в западной литературе сеть Фейстеля называют «Luby-Rackoff block cipher» в честь Люби и Ракоффа, которые проделали большой объём теоретических исследований в этой области.

В дальнейшем, в 1997 году, Мони Наор (англ. Moni Naor) и Омер Рейнголд (англ. Omer Reingold) предложили упрощённый вариант конструкции Люби — Ракоффа, состоящий из четырёх раундов. В этом варианте в качестве первого и последнего раунда используются две попарно-независимые перестановки. Два средних раунда конструкции Наора — Рейнголда идентичны раундам в конструкции Люби — Ракоффа.

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

Модификации сети Фейстеля

При большом размере блоков шифрования (128 бит и более) реализация такой конструкции Фейстеля на 32-разрядных архитектурах может вызвать затруднения, поэтому применяются модифицированные варианты этой конструкции. Обычно используются сети с четырьмя ветвями. На рисунке показаны наиболее распространённые модификации. Также существуют схемы, в которых длины половинок <math>L_0</math> и <math>R_0</math> не совпадают. Такие сети называются несбалансированными.

• Модификации сети Фейстеля
• Feistel type one.png

  Тип 1
• Feistel type2.png

  Тип 2
• Feistel type three.png

  Тип 3

Алгоритм IDEA

Источник:

Схема одной итерации полного раунда алгоритма IDEA

В алгоритме IDEA используется глубоко модифицированная сеть Фейстеля. В нём 64-битные входные блоки данных (обозначим за <math>X_0</math>) делятся на 4 подблока длиной 16 бит <math>X_0 = \{ X^{(0)}X^{(1)}X^{(2)}X^{(3)}\}</math>. На каждом этапе используется 6 16-битных ключей. Всего используется 8 основных этапов и 1 укороченный.

Формулы для вычисления значения подблоков на i-м раунде (для раундов c 1-го по 8-й):

• предварительные вычисления:

<math>A_{i} = ((X_{i-1}^{(0)}*K_{i}^{(1)}) \oplus (X_{i-1}^{(2)}+K_{i}^{(3)}))*K_{i}^{(5)} ; </math>

<math>B_{i} = (((X_{i-1}^{(1)}+K_{i}^{(2)} ) \oplus (X_{i-1}^{(3)}*K_{i}^{(4)}) + A_{i})*K_{i}^{(6)}) ; </math>

<math>C_{i} = ((X_{i-1}^{(1)}+K_{i}^{(2)}) \oplus (X_{i-1}^{(3)}*K_{i}^{(4)}) + ((X_{i-1}^{(0)}*K_{i}^{(1)}) \oplus (X_{i-1}^{(2)}+K_{i}^{(3)}))*K_{i}^{(5)})*K_{i}^{(6)} ; </math>

• финальные вычисления:

<math>X_{i}^{(0)}\ =\ ( X_{i-1}^{(0)}*K_{i}^{(1)} ) \oplus B_{i} ; </math>

<math>X_{i}^{(1)}\ =\ ( X_{i-1}^{(2)}+K_{i}^{(3)} ) \oplus B_{i} ; </math>

<math>X_{i}^{(2)}\ =\ ( X_{i-1}^{(1)}+K_{i}^{(2)} ) \oplus (A_{i}+C_{i}) ; </math>

<math>X_{i}^{(3)}\ =\ ( X_{i-1}^{(3)}*K_{i}^{(4)} ) \oplus (A_{i}+C_{i}) , </math>

где <math>K_{i}^{(j)}</math> — j-й ключ на i-м раунде.

Формула для вычисления 9-го раунда:

<math>X_{9}^{(0)}\ =\ X_{8}^{(0)}*K_{9}^{(1)} ; </math>

<math>X_{9}^{(1)}\ =\ X_{8}^{(2)}+K_{9}^{(2)} ; </math>

<math>X_{9}^{(2)}\ =\ X_{8}^{(1)}+K_{9}^{(3)} ; </math>

<math>X_{9}^{(3)}\ =\ X_{8}^{(3)}*K_{9}^{(4)} . </math>

Выходом функции будет

<math>Y=\{X_{9}^{(0)}X_{9}^{(1)}X_{9}^{(2)}X_{9}^{(3)}\} . </math>

Можно заметить, что s- и p-блоки в чистом виде не используются. В качестве основных операций используются:

• умножение по модулю <math>2^{16} + 1 = 65537</math>;
• сложение по модулю <math>2^{16} = 65536</math>.

Шифры на основе сети Фейстеля

Люцифер (Lucifer)

Исторически, первым алгоритмом, использующим сеть Фейстеля, был алгоритм «Люцифер», при работе над которым Фейстелем и была, собственно, разработана структура, впоследствии получившая название «сеть Фейстеля». В июне 1971 года Фейстелем был получен американский патент № 3798359.

Первая версия «Люцифера» использовала блоки и ключи длиной по 48 бит и не использовала конструкцию «сеть Фейстеля». Последующая модификация алгоритма была запатентована на имя Джона Л. Смитта (англ. John Lynn Smith) в ноябре 1971 года (US Patent 3,796,830; Nov 1971), и в патенте содержится как описание собственно самой «сети Фейстеля», так и конкретной функции шифрования. В ней использовались 64-разрядные ключи и 32-битные блоки. И, наконец, последняя версия предложена в 1973 году и оперировала с 128-битными блоками и ключами. Наиболее полное описание алгоритма «Люцифер» было приведено в статье Артура Соркина (англ. Arthur Sorkin) «Люцифер. Криптографический алгоритм» («Lucifer, A Cryptographic Algorithm») в журнале «Криптология» («Cryptologia») за январь 1984.

Хотя изначальная модификация «Люцифера» обходилась без «ячеек Фейстеля», она хорошо демонстрирует то, как только применением s- и p-блоков можно сильно исказить исходный текст. Структура алгоритма «Люцифер» образца июня 1971 года представляет собой «сэндвич» из слоёв двух типов, используемых по очереди — так называемые SP-сети (или подстановочно-перестановочные сети). Первый тип слоя — p-блок разрядности 128 бит, за ним идёт второй слой, представляющий собой 32 модуля, каждый из которых состоит их двух четырёхбитных s-блоков, чьи соответствующие входы закорочены и на них подаётся одно и то же значение с выхода предыдущего слоя. Но сами блоки подстановок различны (отличаются таблицами замен). На выход модуля подаются значения только с одного из s-блоков, какого конкретно — определяется одним из битов в ключе, номер которого соответствовал номеру s-блока в структуре. Упрощённая схема алгоритма меньшей разрядности и неполным числом раундов приведена на рисунке. В ней используется 16 модулей выбора s-блоков (всего 32 s-блока), таким образом такая схема использует 16-битный ключ.

Рассмотрим теперь, как будет меняться шифротекст, в приведённом выше алгоритме, при изменении всего одного бита. Для простоты возьмём таблицы замен s-блоков такими, что если на вход s-блока подаются все нули, то и на выходе будут все нули. В силу нашего выбора s-блоков, если на вход шифрующего устройства подаются все нули, то и на выходе устройства будут все нули. В реальных системах такие таблицы замен не используются, так как они сильно упрощают работу криптоаналитика, но в нашем примере они наглядно иллюстрируют сильную межсимвольную взаимосвязь при изменении одного бита шифруемого сообщения. Видно, что благодаря первому p-блоку единственная единица сдвигается перемещается в центр блока, затем следующий нелинейный s-блок «размножает» её, и уже две единицы за счёт следующего p-блока изменяют своё положение и т. д. В конце устройства шифрования, благодаря сильной межсимвольной связи, выходные биты стали сложной функцией от входных и от используемого ключа. В среднем на выходе половина бит будет равна «0» и половина — «1».

По своей сути сеть Фейстеля является альтернативой сложным SP-сетям и используется намного шире. С теоретической точки зрения раундовая функция шифрования может быть сведена к SP-сети, однако сеть Фейстеля является более практичной, так как шифрование и дешифрование может вестись одним и тем же устройством, но с обратным порядком используемых ключей. Вторая и третья версия алгоритма (использующие сеть Фейстеля) оперировали над 32-битными блоками с 64-битным ключом и 128-битными блоками со 128-битными ключами. В последней (третьей) версии раундовая функция шифрования была устроена очень просто — сначала шифруемый подблок пропускался через слой 4-битных s-блоков (аналогично слоям в SP-сетях, только s-блок является константным и не зависит от ключа), затем к нему по модулю 2 добавлялся раундовый ключ, после чего результат пропускался через p-блок.

DES

Функция <math>f( L_i, K_i )</math> (где:

• <math>L_i</math> — 32-разрядный входной блок на i-й итерации;
• <math>K_i</math> — 48-разрядный ключ на данной итерации)

в алгоритме DES состоит из следующих операций:

• расширение входного блока L до 48 разрядов (некоторые входные разряды могут повторяться);
• Сложение по модулю 2 с ключом <math>K_i</math>:

<math> \tilde{L_i} = L_i \oplus K_i ; </math>

• деление результата на 8 блоков длиной по 6 бит каждый:

<math> \tilde{L_i} = \{ \tilde{L_i}^{(0)} \tilde{L_i}^{(1)}\tilde{L_i}^{(2)} \tilde{L_i}^{(3)}\tilde{L_i}^{(4)} \tilde{L_i}^{(5)}\tilde{L_i}^{(6)} \tilde{L_i}^{(7)}\} ; </math>

• полученные блоки информации <math> \tilde{ L_i^{(j)} }</math> подаются на блоки подстановок, имеющие 6-разрядные входы и 4-разрядные выходы;
• на выходе 4-битные блоки объединяются в 32-битный, который и является результатом функции <math>f( L_i, K_i )</math>.

Полное число раундов в алгоритме DES — 16.

ГОСТ

Функция <math>f( L_i, K_i )</math> (где <math>L_i</math> и <math>K_i</math> — 32-битные числа) вычисляется следующим образом:

• складываются <math>L_i</math> и <math>K_i</math> по модулю <math>2^{32}</math>:

<math> \tilde{L_i} = ( L_i + K_i )\ \bmod\ 2^{32} ; </math>

• результат разбивается на 8 4-битных блоков, которые подаются на вход 4-разрядных s-блоков (которые могут быть различными);
• выходы s-блоков объединяют в 32-битное число, которое затем сдвигается циклически на 11 битов влево;
• полученный результат является выходом функции.

Количество раундов в алгоритме ГОСТ 28147—89 равно 32.

Сравнительный список алгоритмов

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

Алгоритм	Год	Число раундов	Длина ключа	Размер блока	Количество подблоков
Blowfish	1993	16	от 32 до 448	64	2
Camellia	2000	18/24	128/192/256	128	2
CAST-128	1996	12/16	40-128	64	2
CAST-256	1998	12×4=48	128/192/256	128	2
CIPHERUNICORN-A	2000	16	128/192/256	128	2
CIPHERUNICORN-E	1998	16	128	64	2
CLEFIA	2007	16	128/192/256	128	16
DEAL	1998	6 (8)	(128/192) 256	128	2
DES	1977	16	56	64	2
DFC	1998	8	128/192/256	128	?
FEAL	1987	4-32	64	64	2
ГОСТ 28147-89	1989	32/16	256	64	2
IDEA	1991	8+1	128	64	4
KASUMI	1999	8	128	64	2
Khufu	1990	16-32/64	512	64	2
LOKI97	1997	16	128/192/256	128	2
Lucifer	1971	16	48/64/128	48/32/128	2
MacGuffin	1994	32	128	64	4
MAGENTA	1998	6/8	128/192/256	128	2
MARS	1998	32	128—1248	128	2
Mercy	2000	6	128	4096	?
MISTY1	1995	4×n(8)	128	64	4
Raiden	2006	16	128	64	2
RC2	1987	16+2	8-128	64	4
RC5	1994	1-255(12)	0-2040(128)	32/64/128	2
RC6	1998	20	128/192/256	128	4
RTEA	2007	48/64	128/256	64	2
SEED	1998	16	128	128	2
Sinople	2003	64	128	128	4
Skipjack	1998	23	80	64	4
TEA	1994	64	128	64	2
Triple DES	1978	32/48	112/168	64	2
Twofish	1998	16	128/192/256	128	4
XTEA	1997	64	128	64	2
XTEA-3	1999	64	256	128	4
XXTEA	1998	12-64	128	64	2

Отрывок, характеризующий Сеть Фейстеля

– Уж лошади ж были! – продолжал рассказ Балага. – Я тогда молодых пристяжных к каурому запрег, – обратился он к Долохову, – так веришь ли, Федор Иваныч, 60 верст звери летели; держать нельзя, руки закоченели, мороз был. Бросил вожжи, держи, мол, ваше сиятельство, сам, так в сани и повалился. Так ведь не то что погонять, до места держать нельзя. В три часа донесли черти. Издохла левая только.


Анатоль вышел из комнаты и через несколько минут вернулся в подпоясанной серебряным ремнем шубке и собольей шапке, молодцовато надетой на бекрень и очень шедшей к его красивому лицу. Поглядевшись в зеркало и в той самой позе, которую он взял перед зеркалом, став перед Долоховым, он взял стакан вина.
– Ну, Федя, прощай, спасибо за всё, прощай, – сказал Анатоль. – Ну, товарищи, друзья… он задумался… – молодости… моей, прощайте, – обратился он к Макарину и другим.
Несмотря на то, что все они ехали с ним, Анатоль видимо хотел сделать что то трогательное и торжественное из этого обращения к товарищам. Он говорил медленным, громким голосом и выставив грудь покачивал одной ногой. – Все возьмите стаканы; и ты, Балага. Ну, товарищи, друзья молодости моей, покутили мы, пожили, покутили. А? Теперь, когда свидимся? за границу уеду. Пожили, прощай, ребята. За здоровье! Ура!.. – сказал он, выпил свой стакан и хлопнул его об землю.
– Будь здоров, – сказал Балага, тоже выпив свой стакан и обтираясь платком. Макарин со слезами на глазах обнимал Анатоля. – Эх, князь, уж как грустно мне с тобой расстаться, – проговорил он.
– Ехать, ехать! – закричал Анатоль.
Балага было пошел из комнаты.
– Нет, стой, – сказал Анатоль. – Затвори двери, сесть надо. Вот так. – Затворили двери, и все сели.
– Ну, теперь марш, ребята! – сказал Анатоль вставая.
Лакей Joseph подал Анатолю сумку и саблю, и все вышли в переднюю.
– А шуба где? – сказал Долохов. – Эй, Игнатка! Поди к Матрене Матвеевне, спроси шубу, салоп соболий. Я слыхал, как увозят, – сказал Долохов, подмигнув. – Ведь она выскочит ни жива, ни мертва, в чем дома сидела; чуть замешкаешься, тут и слезы, и папаша, и мамаша, и сейчас озябла и назад, – а ты в шубу принимай сразу и неси в сани.
Лакей принес женский лисий салоп.
– Дурак, я тебе сказал соболий. Эй, Матрешка, соболий! – крикнул он так, что далеко по комнатам раздался его голос.
Красивая, худая и бледная цыганка, с блестящими, черными глазами и с черными, курчавыми сизого отлива волосами, в красной шали, выбежала с собольим салопом на руке.
– Что ж, мне не жаль, ты возьми, – сказала она, видимо робея перед своим господином и жалея салопа.
Долохов, не отвечая ей, взял шубу, накинул ее на Матрешу и закутал ее.
– Вот так, – сказал Долохов. – И потом вот так, – сказал он, и поднял ей около головы воротник, оставляя его только перед лицом немного открытым. – Потом вот так, видишь? – и он придвинул голову Анатоля к отверстию, оставленному воротником, из которого виднелась блестящая улыбка Матреши.
– Ну прощай, Матреша, – сказал Анатоль, целуя ее. – Эх, кончена моя гульба здесь! Стешке кланяйся. Ну, прощай! Прощай, Матреша; ты мне пожелай счастья.
– Ну, дай то вам Бог, князь, счастья большого, – сказала Матреша, с своим цыганским акцентом.
У крыльца стояли две тройки, двое молодцов ямщиков держали их. Балага сел на переднюю тройку, и, высоко поднимая локти, неторопливо разобрал вожжи. Анатоль и Долохов сели к нему. Макарин, Хвостиков и лакей сели в другую тройку.
– Готовы, что ль? – спросил Балага.
– Пущай! – крикнул он, заматывая вокруг рук вожжи, и тройка понесла бить вниз по Никитскому бульвару.
– Тпрру! Поди, эй!… Тпрру, – только слышался крик Балаги и молодца, сидевшего на козлах. На Арбатской площади тройка зацепила карету, что то затрещало, послышался крик, и тройка полетела по Арбату.
Дав два конца по Подновинскому Балага стал сдерживать и, вернувшись назад, остановил лошадей у перекрестка Старой Конюшенной.
Молодец соскочил держать под уздцы лошадей, Анатоль с Долоховым пошли по тротуару. Подходя к воротам, Долохов свистнул. Свисток отозвался ему и вслед за тем выбежала горничная.
– На двор войдите, а то видно, сейчас выйдет, – сказала она.
Долохов остался у ворот. Анатоль вошел за горничной на двор, поворотил за угол и вбежал на крыльцо.
Гаврило, огромный выездной лакей Марьи Дмитриевны, встретил Анатоля.
– К барыне пожалуйте, – басом сказал лакей, загораживая дорогу от двери.
– К какой барыне? Да ты кто? – запыхавшимся шопотом спрашивал Анатоль.
– Пожалуйте, приказано привесть.
– Курагин! назад, – кричал Долохов. – Измена! Назад!
Долохов у калитки, у которой он остановился, боролся с дворником, пытавшимся запереть за вошедшим Анатолем калитку. Долохов последним усилием оттолкнул дворника и схватив за руку выбежавшего Анатоля, выдернул его за калитку и побежал с ним назад к тройке.


Марья Дмитриевна, застав заплаканную Соню в коридоре, заставила ее во всем признаться. Перехватив записку Наташи и прочтя ее, Марья Дмитриевна с запиской в руке взошла к Наташе.
– Мерзавка, бесстыдница, – сказала она ей. – Слышать ничего не хочу! – Оттолкнув удивленными, но сухими глазами глядящую на нее Наташу, она заперла ее на ключ и приказав дворнику пропустить в ворота тех людей, которые придут нынче вечером, но не выпускать их, а лакею приказав привести этих людей к себе, села в гостиной, ожидая похитителей.
Когда Гаврило пришел доложить Марье Дмитриевне, что приходившие люди убежали, она нахмурившись встала и заложив назад руки, долго ходила по комнатам, обдумывая то, что ей делать. В 12 часу ночи она, ощупав ключ в кармане, пошла к комнате Наташи. Соня, рыдая, сидела в коридоре.
– Марья Дмитриевна, пустите меня к ней ради Бога! – сказала она. Марья Дмитриевна, не отвечая ей, отперла дверь и вошла. «Гадко, скверно… В моем доме… Мерзавка, девчонка… Только отца жалко!» думала Марья Дмитриевна, стараясь утолить свой гнев. «Как ни трудно, уж велю всем молчать и скрою от графа». Марья Дмитриевна решительными шагами вошла в комнату. Наташа лежала на диване, закрыв голову руками, и не шевелилась. Она лежала в том самом положении, в котором оставила ее Марья Дмитриевна.
– Хороша, очень хороша! – сказала Марья Дмитриевна. – В моем доме любовникам свидания назначать! Притворяться то нечего. Ты слушай, когда я с тобой говорю. – Марья Дмитриевна тронула ее за руку. – Ты слушай, когда я говорю. Ты себя осрамила, как девка самая последняя. Я бы с тобой то сделала, да мне отца твоего жалко. Я скрою. – Наташа не переменила положения, но только всё тело ее стало вскидываться от беззвучных, судорожных рыданий, которые душили ее. Марья Дмитриевна оглянулась на Соню и присела на диване подле Наташи.
– Счастье его, что он от меня ушел; да я найду его, – сказала она своим грубым голосом; – слышишь ты что ли, что я говорю? – Она поддела своей большой рукой под лицо Наташи и повернула ее к себе. И Марья Дмитриевна, и Соня удивились, увидав лицо Наташи. Глаза ее были блестящи и сухи, губы поджаты, щеки опустились.
– Оставь… те… что мне… я… умру… – проговорила она, злым усилием вырвалась от Марьи Дмитриевны и легла в свое прежнее положение.
– Наталья!… – сказала Марья Дмитриевна. – Я тебе добра желаю. Ты лежи, ну лежи так, я тебя не трону, и слушай… Я не стану говорить, как ты виновата. Ты сама знаешь. Ну да теперь отец твой завтра приедет, что я скажу ему? А?
Опять тело Наташи заколебалось от рыданий.
– Ну узнает он, ну брат твой, жених!
– У меня нет жениха, я отказала, – прокричала Наташа.
– Всё равно, – продолжала Марья Дмитриевна. – Ну они узнают, что ж они так оставят? Ведь он, отец твой, я его знаю, ведь он, если его на дуэль вызовет, хорошо это будет? А?
– Ах, оставьте меня, зачем вы всему помешали! Зачем? зачем? кто вас просил? – кричала Наташа, приподнявшись на диване и злобно глядя на Марью Дмитриевну.
– Да чего ж ты хотела? – вскрикнула опять горячась Марья Дмитриевна, – что ж тебя запирали что ль? Ну кто ж ему мешал в дом ездить? Зачем же тебя, как цыганку какую, увозить?… Ну увез бы он тебя, что ж ты думаешь, его бы не нашли? Твой отец, или брат, или жених. А он мерзавец, негодяй, вот что!
– Он лучше всех вас, – вскрикнула Наташа, приподнимаясь. – Если бы вы не мешали… Ах, Боже мой, что это, что это! Соня, за что? Уйдите!… – И она зарыдала с таким отчаянием, с каким оплакивают люди только такое горе, которого они чувствуют сами себя причиной. Марья Дмитриевна начала было опять говорить; но Наташа закричала: – Уйдите, уйдите, вы все меня ненавидите, презираете. – И опять бросилась на диван.
Марья Дмитриевна продолжала еще несколько времени усовещивать Наташу и внушать ей, что всё это надо скрыть от графа, что никто не узнает ничего, ежели только Наташа возьмет на себя всё забыть и не показывать ни перед кем вида, что что нибудь случилось. Наташа не отвечала. Она и не рыдала больше, но с ней сделались озноб и дрожь. Марья Дмитриевна подложила ей подушку, накрыла ее двумя одеялами и сама принесла ей липового цвета, но Наташа не откликнулась ей. – Ну пускай спит, – сказала Марья Дмитриевна, уходя из комнаты, думая, что она спит. Но Наташа не спала и остановившимися раскрытыми глазами из бледного лица прямо смотрела перед собою. Всю эту ночь Наташа не спала, и не плакала, и не говорила с Соней, несколько раз встававшей и подходившей к ней.
На другой день к завтраку, как и обещал граф Илья Андреич, он приехал из Подмосковной. Он был очень весел: дело с покупщиком ладилось и ничто уже не задерживало его теперь в Москве и в разлуке с графиней, по которой он соскучился. Марья Дмитриевна встретила его и объявила ему, что Наташа сделалась очень нездорова вчера, что посылали за доктором, но что теперь ей лучше. Наташа в это утро не выходила из своей комнаты. С поджатыми растрескавшимися губами, сухими остановившимися глазами, она сидела у окна и беспокойно вглядывалась в проезжающих по улице и торопливо оглядывалась на входивших в комнату. Она очевидно ждала известий об нем, ждала, что он сам приедет или напишет ей.
Когда граф взошел к ней, она беспокойно оборотилась на звук его мужских шагов, и лицо ее приняло прежнее холодное и даже злое выражение. Она даже не поднялась на встречу ему.
– Что с тобой, мой ангел, больна? – спросил граф. Наташа помолчала.
– Да, больна, – отвечала она.
На беспокойные расспросы графа о том, почему она такая убитая и не случилось ли чего нибудь с женихом, она уверяла его, что ничего, и просила его не беспокоиться. Марья Дмитриевна подтвердила графу уверения Наташи, что ничего не случилось. Граф, судя по мнимой болезни, по расстройству дочери, по сконфуженным лицам Сони и Марьи Дмитриевны, ясно видел, что в его отсутствие должно было что нибудь случиться: но ему так страшно было думать, что что нибудь постыдное случилось с его любимою дочерью, он так любил свое веселое спокойствие, что он избегал расспросов и всё старался уверить себя, что ничего особенного не было и только тужил о том, что по случаю ее нездоровья откладывался их отъезд в деревню.


Со дня приезда своей жены в Москву Пьер сбирался уехать куда нибудь, только чтобы не быть с ней. Вскоре после приезда Ростовых в Москву, впечатление, которое производила на него Наташа, заставило его поторопиться исполнить свое намерение. Он поехал в Тверь ко вдове Иосифа Алексеевича, которая обещала давно передать ему бумаги покойного.
Когда Пьер вернулся в Москву, ему подали письмо от Марьи Дмитриевны, которая звала его к себе по весьма важному делу, касающемуся Андрея Болконского и его невесты. Пьер избегал Наташи. Ему казалось, что он имел к ней чувство более сильное, чем то, которое должен был иметь женатый человек к невесте своего друга. И какая то судьба постоянно сводила его с нею.
«Что такое случилось? И какое им до меня дело? думал он, одеваясь, чтобы ехать к Марье Дмитриевне. Поскорее бы приехал князь Андрей и женился бы на ней!» думал Пьер дорогой к Ахросимовой.
На Тверском бульваре кто то окликнул его.
– Пьер! Давно приехал? – прокричал ему знакомый голос. Пьер поднял голову. В парных санях, на двух серых рысаках, закидывающих снегом головашки саней, промелькнул Анатоль с своим всегдашним товарищем Макариным. Анатоль сидел прямо, в классической позе военных щеголей, закутав низ лица бобровым воротником и немного пригнув голову. Лицо его было румяно и свежо, шляпа с белым плюмажем была надета на бок, открывая завитые, напомаженные и осыпанные мелким снегом волосы.
«И право, вот настоящий мудрец! подумал Пьер, ничего не видит дальше настоящей минуты удовольствия, ничто не тревожит его, и оттого всегда весел, доволен и спокоен. Что бы я дал, чтобы быть таким как он!» с завистью подумал Пьер.
В передней Ахросимовой лакей, снимая с Пьера его шубу, сказал, что Марья Дмитриевна просят к себе в спальню.
Отворив дверь в залу, Пьер увидал Наташу, сидевшую у окна с худым, бледным и злым лицом. Она оглянулась на него, нахмурилась и с выражением холодного достоинства вышла из комнаты.
– Что случилось? – спросил Пьер, входя к Марье Дмитриевне.
– Хорошие дела, – отвечала Марья Дмитриевна: – пятьдесят восемь лет прожила на свете, такого сраму не видала. – И взяв с Пьера честное слово молчать обо всем, что он узнает, Марья Дмитриевна сообщила ему, что Наташа отказала своему жениху без ведома родителей, что причиной этого отказа был Анатоль Курагин, с которым сводила ее жена Пьера, и с которым она хотела бежать в отсутствие своего отца, с тем, чтобы тайно обвенчаться.
Пьер приподняв плечи и разинув рот слушал то, что говорила ему Марья Дмитриевна, не веря своим ушам. Невесте князя Андрея, так сильно любимой, этой прежде милой Наташе Ростовой, променять Болконского на дурака Анатоля, уже женатого (Пьер знал тайну его женитьбы), и так влюбиться в него, чтобы согласиться бежать с ним! – Этого Пьер не мог понять и не мог себе представить.
Милое впечатление Наташи, которую он знал с детства, не могло соединиться в его душе с новым представлением о ее низости, глупости и жестокости. Он вспомнил о своей жене. «Все они одни и те же», сказал он сам себе, думая, что не ему одному достался печальный удел быть связанным с гадкой женщиной. Но ему всё таки до слез жалко было князя Андрея, жалко было его гордости. И чем больше он жалел своего друга, тем с большим презрением и даже отвращением думал об этой Наташе, с таким выражением холодного достоинства сейчас прошедшей мимо него по зале. Он не знал, что душа Наташи была преисполнена отчаяния, стыда, унижения, и что она не виновата была в том, что лицо ее нечаянно выражало спокойное достоинство и строгость.
– Да как обвенчаться! – проговорил Пьер на слова Марьи Дмитриевны. – Он не мог обвенчаться: он женат.
– Час от часу не легче, – проговорила Марья Дмитриевна. – Хорош мальчик! То то мерзавец! А она ждет, второй день ждет. По крайней мере ждать перестанет, надо сказать ей.
Узнав от Пьера подробности женитьбы Анатоля, излив свой гнев на него ругательными словами, Марья Дмитриевна сообщила ему то, для чего она вызвала его. Марья Дмитриевна боялась, чтобы граф или Болконский, который мог всякую минуту приехать, узнав дело, которое она намерена была скрыть от них, не вызвали на дуэль Курагина, и потому просила его приказать от ее имени его шурину уехать из Москвы и не сметь показываться ей на глаза. Пьер обещал ей исполнить ее желание, только теперь поняв опасность, которая угрожала и старому графу, и Николаю, и князю Андрею. Кратко и точно изложив ему свои требования, она выпустила его в гостиную. – Смотри же, граф ничего не знает. Ты делай, как будто ничего не знаешь, – сказала она ему. – А я пойду сказать ей, что ждать нечего! Да оставайся обедать, коли хочешь, – крикнула Марья Дмитриевна Пьеру.
Пьер встретил старого графа. Он был смущен и расстроен. В это утро Наташа сказала ему, что она отказала Болконскому.
– Беда, беда, mon cher, – говорил он Пьеру, – беда с этими девками без матери; уж я так тужу, что приехал. Я с вами откровенен буду. Слышали, отказала жениху, ни у кого не спросивши ничего. Оно, положим, я никогда этому браку очень не радовался. Положим, он хороший человек, но что ж, против воли отца счастья бы не было, и Наташа без женихов не останется. Да всё таки долго уже так продолжалось, да и как же это без отца, без матери, такой шаг! А теперь больна, и Бог знает, что! Плохо, граф, плохо с дочерьми без матери… – Пьер видел, что граф был очень расстроен, старался перевести разговор на другой предмет, но граф опять возвращался к своему горю.
Соня с встревоженным лицом вошла в гостиную.
– Наташа не совсем здорова; она в своей комнате и желала бы вас видеть. Марья Дмитриевна у нее и просит вас тоже.
– Да ведь вы очень дружны с Болконским, верно что нибудь передать хочет, – сказал граф. – Ах, Боже мой, Боже мой! Как всё хорошо было! – И взявшись за редкие виски седых волос, граф вышел из комнаты.
Марья Дмитриевна объявила Наташе о том, что Анатоль был женат. Наташа не хотела верить ей и требовала подтверждения этого от самого Пьера. Соня сообщила это Пьеру в то время, как она через коридор провожала его в комнату Наташи.
Наташа, бледная, строгая сидела подле Марьи Дмитриевны и от самой двери встретила Пьера лихорадочно блестящим, вопросительным взглядом. Она не улыбнулась, не кивнула ему головой, она только упорно смотрела на него, и взгляд ее спрашивал его только про то: друг ли он или такой же враг, как и все другие, по отношению к Анатолю. Сам по себе Пьер очевидно не существовал для нее.
– Он всё знает, – сказала Марья Дмитриевна, указывая на Пьера и обращаясь к Наташе. – Он пускай тебе скажет, правду ли я говорила.
Наташа, как подстреленный, загнанный зверь смотрит на приближающихся собак и охотников, смотрела то на того, то на другого.
– Наталья Ильинична, – начал Пьер, опустив глаза и испытывая чувство жалости к ней и отвращения к той операции, которую он должен был делать, – правда это или не правда, это для вас должно быть всё равно, потому что…
– Так это не правда, что он женат!
– Нет, это правда.
– Он женат был и давно? – спросила она, – честное слово?
Пьер дал ей честное слово.
– Он здесь еще? – спросила она быстро.
– Да, я его сейчас видел.
Она очевидно была не в силах говорить и делала руками знаки, чтобы оставили ее.


Пьер не остался обедать, а тотчас же вышел из комнаты и уехал. Он поехал отыскивать по городу Анатоля Курагина, при мысли о котором теперь вся кровь у него приливала к сердцу и он испытывал затруднение переводить дыхание. На горах, у цыган, у Comoneno – его не было. Пьер поехал в клуб.
В клубе всё шло своим обыкновенным порядком: гости, съехавшиеся обедать, сидели группами и здоровались с Пьером и говорили о городских новостях. Лакей, поздоровавшись с ним, доложил ему, зная его знакомство и привычки, что место ему оставлено в маленькой столовой, что князь Михаил Захарыч в библиотеке, а Павел Тимофеич не приезжали еще. Один из знакомых Пьера между разговором о погоде спросил у него, слышал ли он о похищении Курагиным Ростовой, про которое говорят в городе, правда ли это? Пьер, засмеявшись, сказал, что это вздор, потому что он сейчас только от Ростовых. Он спрашивал у всех про Анатоля; ему сказал один, что не приезжал еще, другой, что он будет обедать нынче. Пьеру странно было смотреть на эту спокойную, равнодушную толпу людей, не знавшую того, что делалось у него в душе. Он прошелся по зале, дождался пока все съехались, и не дождавшись Анатоля, не стал обедать и поехал домой.
Анатоль, которого он искал, в этот день обедал у Долохова и совещался с ним о том, как поправить испорченное дело. Ему казалось необходимо увидаться с Ростовой. Вечером он поехал к сестре, чтобы переговорить с ней о средствах устроить это свидание. Когда Пьер, тщетно объездив всю Москву, вернулся домой, камердинер доложил ему, что князь Анатоль Васильич у графини. Гостиная графини была полна гостей.
Пьер не здороваясь с женою, которую он не видал после приезда (она больше чем когда нибудь ненавистна была ему в эту минуту), вошел в гостиную и увидав Анатоля подошел к нему.
– Ah, Pierre, – сказала графиня, подходя к мужу. – Ты не знаешь в каком положении наш Анатоль… – Она остановилась, увидав в опущенной низко голове мужа, в его блестящих глазах, в его решительной походке то страшное выражение бешенства и силы, которое она знала и испытала на себе после дуэли с Долоховым.
– Где вы – там разврат, зло, – сказал Пьер жене. – Анатоль, пойдемте, мне надо поговорить с вами, – сказал он по французски.
Анатоль оглянулся на сестру и покорно встал, готовый следовать за Пьером.
Пьер, взяв его за руку, дернул к себе и пошел из комнаты.
– Si vous vous permettez dans mon salon, [Если вы позволите себе в моей гостиной,] – шопотом проговорила Элен; но Пьер, не отвечая ей вышел из комнаты.
Анатоль шел за ним обычной, молодцоватой походкой. Но на лице его было заметно беспокойство.
Войдя в свой кабинет, Пьер затворил дверь и обратился к Анатолю, не глядя на него.
– Вы обещали графине Ростовой жениться на ней и хотели увезти ее?
– Мой милый, – отвечал Анатоль по французски (как и шел весь разговор), я не считаю себя обязанным отвечать на допросы, делаемые в таком тоне.
Лицо Пьера, и прежде бледное, исказилось бешенством. Он схватил своей большой рукой Анатоля за воротник мундира и стал трясти из стороны в сторону до тех пор, пока лицо Анатоля не приняло достаточное выражение испуга.
– Когда я говорю, что мне надо говорить с вами… – повторял Пьер.
– Ну что, это глупо. А? – сказал Анатоль, ощупывая оторванную с сукном пуговицу воротника.
– Вы негодяй и мерзавец, и не знаю, что меня воздерживает от удовольствия разможжить вам голову вот этим, – говорил Пьер, – выражаясь так искусственно потому, что он говорил по французски. Он взял в руку тяжелое пресспапье и угрожающе поднял и тотчас же торопливо положил его на место.
– Обещали вы ей жениться?
– Я, я, я не думал; впрочем я никогда не обещался, потому что…
Пьер перебил его. – Есть у вас письма ее? Есть у вас письма? – повторял Пьер, подвигаясь к Анатолю.
Анатоль взглянул на него и тотчас же, засунув руку в карман, достал бумажник.
Пьер взял подаваемое ему письмо и оттолкнув стоявший на дороге стол повалился на диван.
– Je ne serai pas violent, ne craignez rien, [Не бойтесь, я насилия не употреблю,] – сказал Пьер, отвечая на испуганный жест Анатоля. – Письма – раз, – сказал Пьер, как будто повторяя урок для самого себя. – Второе, – после минутного молчания продолжал он, опять вставая и начиная ходить, – вы завтра должны уехать из Москвы.
– Но как же я могу…
– Третье, – не слушая его, продолжал Пьер, – вы никогда ни слова не должны говорить о том, что было между вами и графиней. Этого, я знаю, я не могу запретить вам, но ежели в вас есть искра совести… – Пьер несколько раз молча прошел по комнате. Анатоль сидел у стола и нахмурившись кусал себе губы.
– Вы не можете не понять наконец, что кроме вашего удовольствия есть счастье, спокойствие других людей, что вы губите целую жизнь из того, что вам хочется веселиться. Забавляйтесь с женщинами подобными моей супруге – с этими вы в своем праве, они знают, чего вы хотите от них. Они вооружены против вас тем же опытом разврата; но обещать девушке жениться на ней… обмануть, украсть… Как вы не понимаете, что это так же подло, как прибить старика или ребенка!…
Пьер замолчал и взглянул на Анатоля уже не гневным, но вопросительным взглядом.
– Этого я не знаю. А? – сказал Анатоль, ободряясь по мере того, как Пьер преодолевал свой гнев. – Этого я не знаю и знать не хочу, – сказал он, не глядя на Пьера и с легким дрожанием нижней челюсти, – но вы сказали мне такие слова: подло и тому подобное, которые я comme un homme d'honneur [как честный человек] никому не позволю.
Пьер с удивлением посмотрел на него, не в силах понять, чего ему было нужно.
– Хотя это и было с глазу на глаз, – продолжал Анатоль, – но я не могу…
– Что ж, вам нужно удовлетворение? – насмешливо сказал Пьер.
– По крайней мере вы можете взять назад свои слова. А? Ежели вы хотите, чтоб я исполнил ваши желанья. А?
– Беру, беру назад, – проговорил Пьер и прошу вас извинить меня. Пьер взглянул невольно на оторванную пуговицу. – И денег, ежели вам нужно на дорогу. – Анатоль улыбнулся.
Это выражение робкой и подлой улыбки, знакомой ему по жене, взорвало Пьера.
– О, подлая, бессердечная порода! – проговорил он и вышел из комнаты.
На другой день Анатоль уехал в Петербург.


Пьер поехал к Марье Дмитриевне, чтобы сообщить об исполнении ее желанья – об изгнании Курагина из Москвы. Весь дом был в страхе и волнении. Наташа была очень больна, и, как Марья Дмитриевна под секретом сказала ему, она в ту же ночь, как ей было объявлено, что Анатоль женат, отравилась мышьяком, который она тихонько достала. Проглотив его немного, она так испугалась, что разбудила Соню и объявила ей то, что она сделала. Во время были приняты нужные меры против яда, и теперь она была вне опасности; но всё таки слаба так, что нельзя было думать везти ее в деревню и послано было за графиней. Пьер видел растерянного графа и заплаканную Соню, но не мог видеть Наташи.
Пьер в этот день обедал в клубе и со всех сторон слышал разговоры о попытке похищения Ростовой и с упорством опровергал эти разговоры, уверяя всех, что больше ничего не было, как только то, что его шурин сделал предложение Ростовой и получил отказ. Пьеру казалось, что на его обязанности лежит скрыть всё дело и восстановить репутацию Ростовой.
Он со страхом ожидал возвращения князя Андрея и каждый день заезжал наведываться о нем к старому князю.
Князь Николай Андреич знал через m lle Bourienne все слухи, ходившие по городу, и прочел ту записку к княжне Марье, в которой Наташа отказывала своему жениху. Он казался веселее обыкновенного и с большим нетерпением ожидал сына.
Чрез несколько дней после отъезда Анатоля, Пьер получил записку от князя Андрея, извещавшего его о своем приезде и просившего Пьера заехать к нему.
Князь Андрей, приехав в Москву, в первую же минуту своего приезда получил от отца записку Наташи к княжне Марье, в которой она отказывала жениху (записку эту похитила у княжны Марьи и передала князю m lle Вourienne) и услышал от отца с прибавлениями рассказы о похищении Наташи.