SIMD (хеш-функция)

Криптографическая</br>хеш-функция
Название	SIMD
Создан	2008
Опубликован	Октябрь 2008
Размер хеша	256 или 512 бит
Число раундов	4
Тип	хеш-функция

SIMD — итеративная криптографическая хеш-функция, разработанная Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque. Была выдвинута как кандидат на конкурс стандарта SHA-3, проводимый Национальным институтом стандартов и технологий (США), где прошла во второй раунд. Существуют два варианта хеш-функции: SIMD-256 и SIMD-512, преобразующие сообщение произвольной длины в 256 или 512-битное хеш-значение, называемое также дайджестом сообщения. Кроме того возможно определить хеш-функции SIMD-n как усечение функций SIMD-256 и SIMD-512 для n<256 и 256<n<512 соответственною. Как утверждают создатели, главной особенностью хеш функции является значительное расширение сообщения, которое позволяет защититься от дифференциального криптоанализа.

Алгоритм

Общее описание и параметры

Главной частью хеш-функции h является функция сжатия <math>C\colon \{0,1\}^p \times \{0,1\}^m \to \{0,1\}^p</math>. Чтобы вычислить h(M), сообщение M разбивается на k частей <math>M_i</math> по m бит. Затем к частям сообщения итеративно применяется функция сжатия: <math>H_{i+1} = C(H_i, M_i)</math>. Начальное состояние <math>H_0</math> или вектор инициализации (en:Initialization vector) обозначается <math>IV</math> и является фиксированным для каждой функции семейства SIMD. Окончательный результат работы хеш-функции получается применением финализирующей функции (finalization function) <math>D\colon \{0,1\}^p \to \{0,1\}^n</math> к <math>H_{k-1}</math>.

Функция сжатия C в режиме Дэвиса-Мейера обычно строится с использованием функции блочного шифрования <math>E_m</math>: <math>C(h,m) = E_m(h) \otimes h</math>, однако для хеш-функции SIMD используются несколько улучшений.

Семейство хеш-функций SIMD использует следующие параметры:

	Размер хеша, n	Размер блока сообщения, m	Размер внутреннего состояния(<math>H_{i}</math>), p
SIMD-256	256	512	512
SIMD-512	512	1024	1024

Внутреннее состояние представлено матрицей 32-х битных слов размером 4x4 для SIMD-256 и 8x4 для SIMD-512.

<math> S_{256} = \begin{bmatrix}

 A_0 & B_0 & C_0 & D_0 \\
 A_1 & B_1 & C_1 & D_1 \\
 A_2 & B_2 & C_2 & D_2 \\
 A_3 & B_3 & C_3 & D_3 

\end{bmatrix}

\qquad

S_{512} = \begin{bmatrix}

 A_0 & B_0 & C_0 & D_0 \\
 A_1 & B_1 & C_1 & D_1 \\
 A_2 & B_2 & C_2 & D_2 \\
 A_3 & B_3 & C_3 & D_3 \\
 A_4 & B_4 & C_4 & D_4 \\
 A_5 & B_5 & C_5 & D_5 \\
 A_6 & B_6 & C_6 & D_6 \\
 A_7 & B_7 & C_7 & D_7 

\end{bmatrix} </math>

Функция сжатия

Функция сжатия SIMD построена на основе конструкции Дэвиса-Мейера с некоторыми изменениями.

Во-первых, вместо функции сжатия <math>C(h,m) = E_m(h) \otimes h</math> используется функция <math>C(h,m) = E_m(h \otimes m) \otimes h</math>.

Во-вторых, вместо операции XOR для <math>E_m(h \otimes m)</math> и <math>h</math> в SIMD применяются несколько дополнительных раундов Фейстеля с h в качестве входного ключа. Это действие выполняет функция <math>P\colon \{0,1\}^p \times \{0,1\}^p \to \{0,1\}^p</math>.

Таким образом, функция сжатия определена как <math>C(h,m) = P(h, E_m(h \otimes m))</math>. Как утверждают авторы хеш-функции SIMD, эти модификации обеспечивают такой же уровень безопасности, как и оригинальная конструкция Дэвиса-Мейера, но в то же время предотвращают некоторые виды атак множественных блоков (multi-block attacks).

Расширение сообщения

Расширение сообщения (message expansion) хеш-функции SIMD-256 (соотв. SIMD-512) преобразует блок сообщения в 512 бит (соотв. 1024 бита) в расширенное сообщение размером 4096 бит (соотв. 8192 бит) с минимальным расстоянием в 520 (соотв. 1032).

Использование сети Фейстеля

Использование структуры Фейстеля хеш-функцией SIMD построено аналогично семейству хеш-функций MD/SHA:

<math> A_j^{(i)} = \left(D_j^{(i-1)} \boxplus W_j^{(i)} \boxplus \phi_i(A_j^{(i-1)} , B_j^{(i-1)} , C_j^{(i-1)}) \right)^{\lll s_i} \boxplus A_{p_i(j)}^{(i-1)^{\lll r_i}} </math>

<math> B_j^{(i)} = A_j^{(i-1)^{\lll r_i}} </math>

<math> C_j^{(i)} = B_j^{(i-1)} </math>

<math> D_j^{(i)} = C_j^{(i-1)} </math>

или в более удобном формате:

<math> Step \left ( \begin{bmatrix}

 A_0 & B_0 & C_0 & D_0 \\
 A_1 & B_1 & C_1 & D_1 \\
 A_2 & B_2 & C_2 & D_2 \\
 A_3 & B_3 & C_3 & D_3 

\end{bmatrix} , \begin{bmatrix}

 W_0 \\
 W_1 \\
 W_2 \\
 W_3

\end{bmatrix} , \phi, r, s, p \right ) = \begin{bmatrix}

 \left(D_0 \boxplus W_0 \boxplus \phi_i(A_0 , B_0 , C_0) \right)^{\lll s} \boxplus A_{p(0)}^{\lll r} & A_0^{\lll r} & B_0 & C_0 \\
 \left(D_1 \boxplus W_1 \boxplus \phi_i(A_1 , B_1 , C_1) \right)^{\lll s} \boxplus A_{p(1)}^{\lll r} & A_1^{\lll r} & B_1 & C_1 \\
 \left(D_2 \boxplus W_2 \boxplus \phi_i(A_2 , B_2 , C_2) \right)^{\lll s} \boxplus A_{p(2)}^{\lll r} & A_2^{\lll r} & B_2 & C_2 \\
 \left(D_3 \boxplus W_3 \boxplus \phi_i(A_3 , B_3 , C_3) \right)^{\lll s} \boxplus A_{p(3)}^{\lll r} & A_3^{\lll r} & B_3 & c_3 

\end{bmatrix} </math> для SIMD-256

<math> Step \left ( \begin{bmatrix}

 A_0 & B_0 & C_0 & D_0 \\
 A_1 & B_1 & C_1 & D_1 \\
 A_2 & B_2 & C_2 & D_2 \\
 A_3 & B_3 & C_3 & D_3 \\
 A_4 & B_4 & C_4 & D_4 \\
 A_5 & B_5 & C_5 & D_5 \\
 A_6 & B_6 & C_6 & D_6 \\
 A_7 & B_7 & C_7 & D_7 

\end{bmatrix} , \begin{bmatrix}

 W_0 \\
 W_1 \\
 W_2 \\
 W_3 \\
 W_4 \\
 W_5 \\
 W_6 \\
 W_7

\end{bmatrix} , \phi, r, s, p \right ) = \begin{bmatrix}

 \left(D_0 \boxplus W_0 \boxplus \phi_i(A_0 , B_0 , C_0) \right)^{\lll s} \boxplus A_{p(0)}^{\lll r} & A_0^{\lll r} & B_0 & C_0 \\
 \left(D_1 \boxplus W_1 \boxplus \phi_i(A_1 , B_1 , C_1) \right)^{\lll s} \boxplus A_{p(1)}^{\lll r} & A_1^{\lll r} & B_1 & C_1 \\
 \left(D_2 \boxplus W_2 \boxplus \phi_i(A_2 , B_2 , C_2) \right)^{\lll s} \boxplus A_{p(2)}^{\lll r} & A_2^{\lll r} & B_2 & C_2 \\
 \left(D_3 \boxplus W_3 \boxplus \phi_i(A_3 , B_3 , C_3) \right)^{\lll s} \boxplus A_{p(3)}^{\lll r} & A_3^{\lll r} & B_3 & c_3 \\
 \left(D_4 \boxplus W_4 \boxplus \phi_i(A_4 , B_4 , C_4) \right)^{\lll s} \boxplus A_{p(4)}^{\lll r} & A_4^{\lll r} & B_4 & C_4 \\
 \left(D_5 \boxplus W_5 \boxplus \phi_i(A_5 , B_5 , C_5) \right)^{\lll s} \boxplus A_{p(5)}^{\lll r} & A_5^{\lll r} & B_5 & C_5 \\
 \left(D_6 \boxplus W_6 \boxplus \phi_i(A_6 , B_6 , C_6) \right)^{\lll s} \boxplus A_{p(6)}^{\lll r} & A_6^{\lll r} & B_6 & C_6 \\
 \left(D_7 \boxplus W_7 \boxplus \phi_i(A_7 , B_7 , C_7) \right)^{\lll s} \boxplus A_{p(7)}^{\lll r} & A_7^{\lll r} & B_7 & c_7 

\end{bmatrix} </math> для SIMD-512

где <math>\phi_i</math> - логическая функция, <math>\boxplus</math> - сложение по модулю <math>2^{32}</math> и <math>\lll s_i</math> - циклический сдвиг влево на <math>s_i</math> бит.

Используются 4 параллельные ячейки Фейстеля для SIMD-256 (соотв. 8 для SIMD-512), которые взаимодействуют между собой из-за перестановок <math>p_i</math>. Перестановки выбираются таким образом, чтобы обеспечить хорошее перемешивание.

Для SIMD-256 определено:

<math> p^{(i)}(x) = \begin{cases}

 {x + 1} \pmod 4, & \mbox{if } i \mbox{ is even} \\
 {x + 2} \pmod 4, & \mbox{if } i \mbox{ is odd}

\end{cases} </math>

Соответственно для SIMD-512:

<math> p^{(0)}(x) = \begin{cases}

 {x + 1} \pmod 8,  & \mbox{if } x=0 \pmod 2 \\
 {x - 1} \pmod 8, & \mbox{otherwise}

\end{cases} </math>

В целом функция сжатия отрабатывает за 4 раунда, каждый из которых состоит из 8 шагов (step), плюс один дополнительный финальный раунд.

Финальная функция сжатия

После того как все блоки сообщения были сжаты совершается еще один дополнительный вызов функции сжатия с размером сообщения в качестве входного параметра. При этом длина сообщения вычисляется в битах по модулю <math>2^{2^m}</math> если необходимо.

Для финальной функции сжатия используется немного измененный метод расширения сообщения:

для SIMD-256 вместо <math>O(M) = NTT_{128}(M + X^{127})</math> используется <math>O(M) = NTT_{128}(M + X^{127}+ X^{125})</math>.

Соответственно, для SIMD-512 вместо <math>O(M) = NTT_{256}(M + X^{255})</math> используется <math>O(M) = NTT_{256}(M + X^{255}+ X^{253})</math>

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

После применения финальной функции сжатия на выход подается следующее строковой представление:

<math>A_0, A_1, A_2, A_3, B_0, B_1, B_2, B_3</math> для SIMD-256

<math>A_0, A_1, A_2, A_3, A_4, A_5, A_6, A_7, B_0, B_1, B_2, B_3, B_4, B_5, B_6, B_7</math> для SIMD-512

В случай SIMD-n на выход подаются первые n бит SIMD-256 (n < 256) или SIMD 512 (256 < n < 512). Например, для SIMD-384 на выходе будет <math>A_0, A_1, A_2, A_3, A_4, A_5, A_6, A_7, B_0, B_1, B_2, B_3</math>

Вектор инициализации

Каждая хеш-функция семейства SIMD использует собственный вектор инициализации IV, чтобы избежать связей между выходными результатами различных функций SIMD-n. IV для функции SIMD-n определяется следующим образом:

IV = SIMD-Compress(0, "SIMD-(i)" v1.0, 0), где строка записана в ASCII и дополнена нулями, а (i) - десятичное представление n.

Значения IV для различных хеш-функций семейства SIMD:

<math> \begin{array}{|c c c c c|}

 \hline
 & & SIMD-224 IV & & \\
 \hline
 A_{0..3} & 0xeebfea74 & 0x70c30346 & 0x4b538718 & 0x4f06a655 \\
 B_{0..3} & 0xa22aad99 & 0x434a528c & 0x355e2a29 & 0x8523b76e \\
 C_{0..3} & 0x20bcf05e & 0x9eb5b91a & 0x4ddc22e8 & 0xce0ae099 \\
 D_{0..3} & 0x9d4dda03 & 0xae00fc41 & 0x40279fc8 & 0x9f0ec1f5 \\
 \hline

\end{array} \begin{array}{|c c c c c|}

 \hline
 & & SIMD-256 IV & & \\
 \hline
 A_{0..3} & 0x99dae06a & 0xc3d43239 & 0x4979de73 & 0x3ee5d052 \\
 B_{0..3} & 0xda4d98d0 & 0xcf5c52be & 0x655cbaf9 & 0x2a9d238e \\
 C_{0..3} & 0xfd892a60 & 0x8a471f8c & 0x86ce033f & 0x0ff768d3 \\
 D_{0..3} & 0xfad01f14 & 0x9eeef3b3 & 0x68aec37a & 0x6b209d72 \\
 \hline

\end{array} </math>

<math> \begin{array}{|c c c c c|}

 \hline
 & & SIMD-384 IV & & \\
 \hline
 A_{0..3} & 0x3a8f3d6f & 0x756a1087 & 0x5d5318aa & 0xbbca76f7 \\
 A_{4..7} & 0x26a3a959 & 0xaca1e37e & 0xb40c4642 & 0x904085d9 \\
 B_{0..3} & 0xf46f6c9b & 0x9ab248ef & 0xdbbfc9cc & 0xcc8821fa \\
 B_{4..7} & 0x354d3c2e & 0xda334fb1 & 0x68ed79ce & 0xa5bc107d \\
 C_{0..3} & 0x2da6fdc3 & 0xfbafce00 & 0x4c9a6954 & 0xb61f0faf \\
 C_{4..7} & 0xf56099b5 & 0xa3a5bdfb & 0xf83e0977 & 0x7eb15372 \\
 D_{0..3} & 0x91195b41 & 0xfcb9404e & 0x214e6c84 & 0x88740b3a \\
 D_{4..7} & 0xba03a4b1 & 0xa82202fc & 0x994fddfb & 0xb2e1a1de \\
 \hline

\end{array} \begin{array}{|c c c c c|}

 \hline
 & & SIMD-512 IV & & \\
 \hline
 A_{0..3} & 0xb314b806 & 0x676cf96e & 0xed91a471 & 0x5f306791 \\
 A_{4..7} & 0x4ea515ee & 0xde2a06cf & 0xc9c96851 & 0x4f49a403 \\
 B_{0..3} & 0xf778d95b & 0x6e5e21da & 0xad570671 & 0x4584c064 \\
 B_{4..7} & 0xac201a0f & 0xd4ce2a86 & 0xc6d663f4 & 0x8ec5d766 \\
 C_{0..3} & 0x14c1303a & 0xb5b890d5 & 0x82e61e95 & 0x94f47683 \\
 C_{4..7} & 0x6ebc9ce7 & 0xf9af5b29 & 0xf4177798 & 0xf6cec3ee \\
 D_{0..3} & 0xd10eca9e & 0xea3c1b82 & 0x5061c319 & 0x0c2a9f5c \\
 D_{4..7} & 0xfcfc980e & 0xbab373c6 & 0x1699d7c9 & 0x0822d6af \\
 \hline

\end{array} </math>

Улучшения для второго раунда конкурса SHA-3

Изменениям подверглись 2 части алгоритма: перестановки (permutations) <math>p^{(i)}</math> и циклические сдвиги (rotations).

При выборе новых перестановок авторы хеш-функции руководствовались следующими критериями:

• Перестановки должны обеспечивать полное перемешивание после трех раундов (соотв. двух для SIMD-256)
• Необходимо использовать нечетное число перестановок
• Результат композиции любых двух перестановок не должен быть фиксированным
• Результат четырех последовательных перестановок не должен давать исходный результат

SIMD-256. Исходные перестановки:

<math> p^{(i)}(x) = \begin{cases}

 {x + 1} \pmod 4, & \mbox{if } i \mbox{ is even} \\
 {x + 2} \pmod 4, & \mbox{if } i \mbox{ is odd}

\end{cases} </math>

Новые перестановки:

<math> \begin{cases} p^{(0)}(j) = j \otimes 1 \\ p^{(1)}(j) = j \otimes 2 \\ p^{(2)}(j) = j \otimes 3 \end{cases} </math>

где <math>p^{(i)} = p^{i \mod 3}</math>. Таким образом, количество перестановок увеличилось с 2 до 3.

SIMD-512. Исходные перестановки:

<math> p^{(0)}(x) = \begin{cases}

 {x + 1} \pmod 8,  & \mbox{if } x=0 \pmod 2 \\
 {x - 1} \pmod 8, & \mbox{otherwise}

\end{cases} </math>

Новые перестановки:

<math> \begin{cases} p^{(0)}(j) = j \otimes 1 \\ p^{(1)}(j) = j \otimes 6 \\ p^{(2)}(j) = j \otimes 2 \\ p^{(3)}(j) = j \otimes 3 \\ p^{(4)}(j) = j \otimes 5 \\ p^{(5)}(j) = j \otimes 7 \\ p^{(6)}(j) = j \otimes 4 \end{cases} </math>

где <math>p^{(i)} = p^{i \mod 7}</math>. Таким образом, количество перестановок увеличилось с 4 до 7.

Псевдокод SIMD

1:  function MessageExpansion(M, f)   		        //f помечает финальную функцию сжатия
2:      if f = 0 then
3:          y(i) = NTT(M + X127) 			//соответственно X255 для SIMD-512
4:      else
5:          y(i) = NTT(M + X127 + X125)  		//соответственно X255 + X253 для SIMD-512
6:      end if
7:      Вычислить Z(i,j) применяя внутренние коды I(185) и I(233) к y(i).
8:      Вычислить W(i,j) применяя перестановки для Z(i,j)
9:      Вернуть W(i,j)
10: end function
11:
12: function Round(S, i, r)
13:     S = Step(S; W(8i+0); IF; r0; r1)
14:     S = Step(S; (W8i+1); IF; r1; r2)
15:     S = Step(S; W(8i+2); IF; r2; r3)
16:     S = Step(S; W(8i+3); IF; r3; r0)
17:     S = Step(S; W(8i+4);MAJ; r0; r1)
18:     S = Step(S; W(8i+5);MAJ; r1; r2)
19:     S = Step(S; W(8i+6);MAJ; r2; r3)
20:     S = Step(S; W(8i+7);MAJ; r3; r0)
21:     return S
22: end function
23:
24: function SIMD-Compress(IV, M, f)
25:     W = MessageExpansion(M; f)
26:     S = IV xor M
27:     S = Round(S; 0; [3; 20; 14; 27])
28:     S = Round(S; 1; [26; 4; 23; 11])
29:     S = Round(S; 2; [19; 28; 7; 22])
30:     S = Round(S; 3; [15; 5; 29; 9])
31:     S = Step(S; IV(0); IF; 15; 5)
32:     S = Step(S; IV(1); IF; 5; 29)
33:     S = Step(S; IV(2); IF; 29; 9)
34:     S = Step(S; IV(3); IF; 9; 15)
35:     return S
36: end function
37:
38: function SIMD(M)
39:     Разделить сообщение M на части M(i); 0 =< i < k.
40:     M(k-1) дополняется нулями.
41:     S  = IV
42:     for 0 =< i < k do
43:         S = SIMD-Compress(S; M(i); 0)
44:     end for
45:     S = SIMD-Compress(S; ||M||; 1)
46:     return Truncate(S)
47: end function

Примеры результатов

Сообщение M	SIMD-256(M)
Пустое сообщение	8029e81e7320e13ed9001dc3d8021fec695b7a25cd43ad805260181c35fcaea8
0x00; 0x01; 0x02; ... 0x3f	5bebdb816cd3e6c8c2b5a42867a6f41570c4b917f1d3b15aabc17f24679e6acd

Сообщение M	SIMD-512(M)
Пустое сообщение	51a5af7e243cd9a5989f7792c880c4c3168c3d60c4518725fe5757d1f7a69c63 66977eaba7905ce2da5d7cfd07773725f0935b55f3efb954996689a49b6d29e0
0x00; 0x01; 0x02; ... 0x3f	8851ad0a57426b4af57af3294706c0448fa6accf24683fc239871be58ca913fb ee53e35c1dedd88016ebd131f2eb0761e97a3048de6e696787fd5f54981d6f2c

Быстродействие

Независимые тесты производительности алгоритма SIMD, проведенные с помощью бенчмарка eBASH, показали следующие результаты (скорость указана в циклах на байт (cpb)):

Процессор	Core i5	Core 2 (45 nm)	Core 2 (65 nm)
SIMD-256	7.51 cpb	9.18 cpb	11.34 cpb
SIMD-512	8.63 cpb	10.02 cpb	12.05 cpb

При этом около половины времени работы хеш-функции уходит на операцию расширения сообщения: Number-Theoretic Transform (NTT) является самой дорогостоящей в плане производительности частью алгоритма.

Функция сжатия SIMD обладает частично параллельной архитектурой, что позволяет создавать эффективные реализации алгоритма с использованием векторных инструкций (SIMD). Данные инструкции доступны на многих широко-известных архитектурах: SSE на x86, Altivec на PowerPC, IwMMXt на ARM.

Что касается требований, предъявляемых к RAM, хеш-функции SIMD необходима память для хранения внутреннего состояния (64 байта для SIMD-256 и 128 байт для SIMD-512) и память для выходных значений NTT (4*64 = 256 байт для SIMD-256 и 4*128 = 512 байт для SIMD-512).

Результаты конкурса SHA-3 для SIMD

Хеш-функция SIMD не была отобрана в качестве финалиста конкурса SHA-3.

Эксперты конкурса отметили, что, хотя хеш-функция SIMD во многом повторяет алгоритмы семейств MD/SHA, но улучшения, сделанные авторами, действительно позволили защитить SIMD от многих типов атак (например multi-collision attack). Кроме того, изменения, проведенные для второго раунда, смогли защитить хеш-функцию SIMD от атаки на основе дифференциального криптоанализа, проведенную Mendel и Nad, которой была подвержена SIMD в своей изначальной реализации.

Однако, высокие требования к RAM и наличию SIMD инструкций для хорошей производительности делают хеш-функцию плохим кандидатом для реализации на FPGA. Главным образом по этой причине хеш-функция SIMD не попала в финальную стадию конкурса.

Литература

• [www.di.ens.fr/~leurent/simd.html The SIMD Hash Function official website] (англ.). Проверено 18 декабря 2013.
• [csrc.nist.gov/groups/ST/hash/sha-3/ SHA-3 competition(2007-2012)] (англ.). Проверено 18 декабря 2013.
• [csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html SHA-3 second round candidates] (англ.). Проверено 18 декабря 2013.
• [bench.cr.yp.to/results-hash.html eBASH: Encrypt benchmark official site] (англ.). Проверено 18 декабря 2013.
• Meltem Sönmez Turan, Ray Perlner [csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Round2_Report_NISTIR_7764.pdf Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition] (англ.).
• Ga?etan Leurent [www.di.ens.fr/~leurent/files/SIMD.pdf SHA-3 submission SIMD Is a Message Digest] (англ.).
• Ga?etan Leurent [www.di.ens.fr/~leurent/files/SIMD-slides.pdf SIMD Is a Message Digest: Presentation] (англ.).
• Ga?etan Leurent [www.di.ens.fr/~leurent/files/SIMD-tweak.pdf Tweaking SIMD] (англ.).
• Charles Bouillaguet, Pierre-Alain Fouque, Gaëtan Leurent [eprint.iacr.org/2010/323.pdf Security Analysis of SIMD] (англ.).
• Hongbo Yu and Xiaoyun Wang [eprint.iacr.org/2010/304.pdf Cryptanalysis of the Compression Function of SIMD] (англ.).

Отрывок, характеризующий SIMD (хеш-функция)

Несмотря на то, что прежде у нее была досада на Наташу за то, что она в Петербурге отбила у нее Бориса, она теперь и не думала об этом, и всей душой, по своему, желала добра Наташе. Уезжая от Ростовых, она отозвала в сторону свою protegee.
– Вчера брат обедал у меня – мы помирали со смеху – ничего не ест и вздыхает по вас, моя прелесть. Il est fou, mais fou amoureux de vous, ma chere. [Он сходит с ума, но сходит с ума от любви к вам, моя милая.]
Наташа багрово покраснела услыхав эти слова.
– Как краснеет, как краснеет, ma delicieuse! [моя прелесть!] – проговорила Элен. – Непременно приезжайте. Si vous aimez quelqu'un, ma delicieuse, ce n'est pas une raison pour se cloitrer. Si meme vous etes promise, je suis sure que votre рromis aurait desire que vous alliez dans le monde en son absence plutot que de deperir d'ennui. [Из того, что вы любите кого нибудь, моя прелестная, никак не следует жить монашенкой. Даже если вы невеста, я уверена, что ваш жених предпочел бы, чтобы вы в его отсутствии выезжали в свет, чем погибали со скуки.]
«Стало быть она знает, что я невеста, стало быть и oни с мужем, с Пьером, с этим справедливым Пьером, думала Наташа, говорили и смеялись про это. Стало быть это ничего». И опять под влиянием Элен то, что прежде представлялось страшным, показалось простым и естественным. «И она такая grande dame, [важная барыня,] такая милая и так видно всей душой любит меня, думала Наташа. И отчего не веселиться?» думала Наташа, удивленными, широко раскрытыми глазами глядя на Элен.
К обеду вернулась Марья Дмитриевна, молчаливая и серьезная, очевидно понесшая поражение у старого князя. Она была еще слишком взволнована от происшедшего столкновения, чтобы быть в силах спокойно рассказать дело. На вопрос графа она отвечала, что всё хорошо и что она завтра расскажет. Узнав о посещении графини Безуховой и приглашении на вечер, Марья Дмитриевна сказала:
– С Безуховой водиться я не люблю и не посоветую; ну, да уж если обещала, поезжай, рассеешься, – прибавила она, обращаясь к Наташе.


Граф Илья Андреич повез своих девиц к графине Безуховой. На вечере было довольно много народу. Но всё общество было почти незнакомо Наташе. Граф Илья Андреич с неудовольствием заметил, что всё это общество состояло преимущественно из мужчин и дам, известных вольностью обращения. M lle Georges, окруженная молодежью, стояла в углу гостиной. Было несколько французов и между ними Метивье, бывший, со времени приезда Элен, домашним человеком у нее. Граф Илья Андреич решился не садиться за карты, не отходить от дочерей и уехать как только кончится представление Georges.
Анатоль очевидно у двери ожидал входа Ростовых. Он, тотчас же поздоровавшись с графом, подошел к Наташе и пошел за ней. Как только Наташа его увидала, тоже как и в театре, чувство тщеславного удовольствия, что она нравится ему и страха от отсутствия нравственных преград между ею и им, охватило ее. Элен радостно приняла Наташу и громко восхищалась ее красотой и туалетом. Вскоре после их приезда, m lle Georges вышла из комнаты, чтобы одеться. В гостиной стали расстанавливать стулья и усаживаться. Анатоль подвинул Наташе стул и хотел сесть подле, но граф, не спускавший глаз с Наташи, сел подле нее. Анатоль сел сзади.
M lle Georges с оголенными, с ямочками, толстыми руками, в красной шали, надетой на одно плечо, вышла в оставленное для нее пустое пространство между кресел и остановилась в ненатуральной позе. Послышался восторженный шопот. M lle Georges строго и мрачно оглянула публику и начала говорить по французски какие то стихи, где речь шла о ее преступной любви к своему сыну. Она местами возвышала голос, местами шептала, торжественно поднимая голову, местами останавливалась и хрипела, выкатывая глаза.
– Adorable, divin, delicieux! [Восхитительно, божественно, чудесно!] – слышалось со всех сторон. Наташа смотрела на толстую Georges, но ничего не слышала, не видела и не понимала ничего из того, что делалось перед ней; она только чувствовала себя опять вполне безвозвратно в том странном, безумном мире, столь далеком от прежнего, в том мире, в котором нельзя было знать, что хорошо, что дурно, что разумно и что безумно. Позади ее сидел Анатоль, и она, чувствуя его близость, испуганно ждала чего то.
После первого монолога всё общество встало и окружило m lle Georges, выражая ей свой восторг.
– Как она хороша! – сказала Наташа отцу, который вместе с другими встал и сквозь толпу подвигался к актрисе.
– Я не нахожу, глядя на вас, – сказал Анатоль, следуя за Наташей. Он сказал это в такое время, когда она одна могла его слышать. – Вы прелестны… с той минуты, как я увидал вас, я не переставал….
– Пойдем, пойдем, Наташа, – сказал граф, возвращаясь за дочерью. – Как хороша!
Наташа ничего не говоря подошла к отцу и вопросительно удивленными глазами смотрела на него.
После нескольких приемов декламации m lle Georges уехала и графиня Безухая попросила общество в залу.
Граф хотел уехать, но Элен умоляла не испортить ее импровизированный бал. Ростовы остались. Анатоль пригласил Наташу на вальс и во время вальса он, пожимая ее стан и руку, сказал ей, что она ravissante [обворожительна] и что он любит ее. Во время экосеза, который она опять танцовала с Курагиным, когда они остались одни, Анатоль ничего не говорил ей и только смотрел на нее. Наташа была в сомнении, не во сне ли она видела то, что он сказал ей во время вальса. В конце первой фигуры он опять пожал ей руку. Наташа подняла на него испуганные глаза, но такое самоуверенно нежное выражение было в его ласковом взгляде и улыбке, что она не могла глядя на него сказать того, что она имела сказать ему. Она опустила глаза.
– Не говорите мне таких вещей, я обручена и люблю другого, – проговорила она быстро… – Она взглянула на него. Анатоль не смутился и не огорчился тем, что она сказала.
– Не говорите мне про это. Что мне зa дело? – сказал он. – Я говорю, что безумно, безумно влюблен в вас. Разве я виноват, что вы восхитительны? Нам начинать.
Наташа, оживленная и тревожная, широко раскрытыми, испуганными глазами смотрела вокруг себя и казалась веселее чем обыкновенно. Она почти ничего не помнила из того, что было в этот вечер. Танцовали экосез и грос фатер, отец приглашал ее уехать, она просила остаться. Где бы она ни была, с кем бы ни говорила, она чувствовала на себе его взгляд. Потом она помнила, что попросила у отца позволения выйти в уборную оправить платье, что Элен вышла за ней, говорила ей смеясь о любви ее брата и что в маленькой диванной ей опять встретился Анатоль, что Элен куда то исчезла, они остались вдвоем и Анатоль, взяв ее за руку, нежным голосом сказал:
– Я не могу к вам ездить, но неужели я никогда не увижу вас? Я безумно люблю вас. Неужели никогда?… – и он, заслоняя ей дорогу, приближал свое лицо к ее лицу.
Блестящие, большие, мужские глаза его так близки были от ее глаз, что она не видела ничего кроме этих глаз.
– Натали?! – прошептал вопросительно его голос, и кто то больно сжимал ее руки.
– Натали?!
«Я ничего не понимаю, мне нечего говорить», сказал ее взгляд.
Горячие губы прижались к ее губам и в ту же минуту она почувствовала себя опять свободною, и в комнате послышался шум шагов и платья Элен. Наташа оглянулась на Элен, потом, красная и дрожащая, взглянула на него испуганно вопросительно и пошла к двери.
– Un mot, un seul, au nom de Dieu, [Одно слово, только одно, ради Бога,] – говорил Анатоль.
Она остановилась. Ей так нужно было, чтобы он сказал это слово, которое бы объяснило ей то, что случилось и на которое она бы ему ответила.
– Nathalie, un mot, un seul, – всё повторял он, видимо не зная, что сказать и повторял его до тех пор, пока к ним подошла Элен.
Элен вместе с Наташей опять вышла в гостиную. Не оставшись ужинать, Ростовы уехали.
Вернувшись домой, Наташа не спала всю ночь: ее мучил неразрешимый вопрос, кого она любила, Анатоля или князя Андрея. Князя Андрея она любила – она помнила ясно, как сильно она любила его. Но Анатоля она любила тоже, это было несомненно. «Иначе, разве бы всё это могло быть?» думала она. «Ежели я могла после этого, прощаясь с ним, улыбкой ответить на его улыбку, ежели я могла допустить до этого, то значит, что я с первой минуты полюбила его. Значит, он добр, благороден и прекрасен, и нельзя было не полюбить его. Что же мне делать, когда я люблю его и люблю другого?» говорила она себе, не находя ответов на эти страшные вопросы.


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