NTRUEncrypt

NTRUEncrypt (аббревиатура Nth-degree TRUncated polynomial ring или Number Theorists aRe Us) — это криптографическая система с открытым ключом, ранее называвшаяся NTRU.

Криптосистема NTRUEncrypt, основанная на решётчатой криптосистеме, создана в качестве альтернативы RSA и криптосистемам на эллиптических кривых (ECC). Стойкость алгоритма обеспечивается трудностью поиска кратчайшего вектора решётки (англ.), которая более стойкая к атакам, осуществляемым на квантовых компьютерах. В отличие от своих конкурентов RSA, ECC, Elgamal, алгоритм использует операции над кольцом <math>\mathbb{Z}[X]/(X^N-1)</math> усечённых многочленов степени, не превосходящей <math>N-1</math>:

<math> \textbf{a}(X) = \textbf{a} = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-2} X^{N-2} + a_{N-1} X^{N-1} </math>

Такой многочлен можно также представить вектором

<math> \vec{a}(X) = \vec{a} = \sum_{i=0}^{N-1} a_i X^i = [a_0, a_1, a_2, \cdots, a_{N-2}, a_{N-1}] </math>

Как и любой молодой алгоритм, NTRUEncrypt плохо изучен, хотя и был официально утверждён для использования в сфере финансов комитетом Accredited Standards Committee X9.

Существует реализации NTRUEncrypt с открытым исходным кодом.

История

NTRUEncrypt, изначально называвшийся NTRU, был изобретён в 1996 году и представлен миру на конференциях CRYPTO (англ.), Конференция RSA, Eurocrypt (англ.). Причиной, послужившей началом разработки алгоритма в 1994 году, стала статья, в которой говорилось о лёгкости взлома существующих алгоритмов на квантовых компьютерах, которые, как показало время, не за горами. В этом же году, математики Jeffrey Hoffstein, Jill Pipher и Joseph H. Silverman, разработавшие систему вместе с основателем компании NTRU Cryptosystems, Inc. (позже переименованной в SecurityInnovation), Даниелем Лиеманом (Daniel Lieman) запатентовали своё изобретение.

Кольца усечённых многочленов

NTRU оперирует над многочленами степени не превосходящей <math>N-1</math>

<math> \textbf{a} = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-2} X^{N-2} + a_{N-1} X^{N-1}, </math>

где коэффициенты <math>a_0, \cdots, a_{N-1} </math> — целые числа. Относительно операций сложения и умножения по модулю многочлена <math>X^N - 1</math> такие многочлены образуют кольцо R, называемое кольцом усечённых многочленов, которое изоморфно кольцу отношений <math>\mathbb{Z}[X]/(X^N-1).</math>

NTRU использует кольцо усечённых многочленов R совместно с делением по модулю на взаимно простые числа p и q для уменьшения коэффициентов многочленов.

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

В качестве примера будут выбраны следующие параметры:

Обозначения параметров	N	q	p
Значения параметров	11	32	3

Генерация открытого ключа

Для передачи сообщения от Алисы к Бобу необходимы открытый и закрытый ключи. Открытый знают как Боб, так и Алиса, закрытый ключ знает только Боб, который он использует для генерации открытого ключа. Для этого Боб выбирает два «маленьких» полинома f g из R. «Малость» полиномов подразумевается в том смысле, что он маленький относительно произвольного полинома по модулю q: в произвольном полиноме коэффициенты должны быть примерно равномерно распределены по модулю q, а в малом полиноме они много меньше q. Малость полиномов определяется с помощью чисел df и dg:

• Полином f имеет df коэффициентов равных «1» и df-1 коэффициентов равных «-1», а остальные — «0». В этом случае говорят, что <math> \textbf{f} \in \mathcal{L}_f </math>
• Полином g имеет dg коэффициентов равных «1» и столько же равных «-1», остальные — «0» В этом случае говорят, что <math> \textbf{g} \in \mathcal{L}_g </math>

Причина, по которой полиномы выбираются именно таким образом, заключается в том, что f , возможно, будет иметь обратный, а g — однозначно нет (g (1) = 0, а нулевой элемент не имеет обратного).

Боб должен хранить эти полинома в секрете. Далее Боб вычисляет обратные полиномы <math> \textbf{f}_p</math> и <math>\textbf{f}_q</math>, то есть такие, что:

<math> \ \textbf{f} \cdot \textbf{f}_p \equiv 1 \pmod p </math> и <math> \ \textbf{f} \cdot \textbf{f}_q \equiv 1 \pmod q </math>.

Если f не имеет обратного полинома, то Боб выбирает другой полином f.

Секретный ключ — это пара <math>\left( \textbf{f}, \textbf{f}_p \right)</math>, а открытый ключ h вычисляется по формуле:

<math> \textbf{h} = (p\textbf{f}_q \cdot \textbf{g})\,\bmod\,q. </math>

Пример

Для примера возьмем df=4, а dg=3. Тогда в качестве полиномов можно выбрать

<math> \textbf{f} = -1 + X + X^2 - X^4 + X^6 +X^9 - X^{10} </math>

<math> \textbf{g} = -1 + X^2 +X^3 + X^5 -X^8 - X^{10} </math>

Далее для полинома f ищутся обратные полиномы по модулю p=3 и q=32:

<math> \textbf{f}_p = 1 + 2X + 2X^3 +2X^4 + X^5 +2X^7 + X^8+2X^9</math>

<math> \textbf{f}_q = 5 + 9X +6X^2+16X^3 + 4X^4 +15X^5 +16X^6+22X^7+20X^8+18X^9+30X^{10}</math>

Заключительным этапом является вычисление самого открытого ключа h:

<math> \textbf{h} = (p\textbf{f}_q \cdot \textbf{g})\,\bmod\,{32} = 8 + 25X +22X^2+20X^3 + 12X^4 +24X^5 +15X^6+19X^7+12X^8+19X^9+16X^{10}.</math>

Шифрование

Теперь, когда у Алисы есть открытый ключ, она может отправить зашифрованное сообщение Бобу. Для этого нужно сообщение представить в виде полинома m с коэффициентами по модулю p, выбранными из диапазона (-p/2, p/2]. То есть m является «малым» полиномом по модулю q. Далее Алисе необходимо выбрать другой «малый» полином r, который называется «ослепляющим», определяемый с помощью числа dr:

• Полином r имеет dr коэффициентов равных «1» и столько же равных «-1», остальные — «0». В этом случае говорят, что <math> \textbf{r} \in \mathcal{L}_r.</math>

Используя эти полиномы, зашифрованное сообщение получается по формуле:

<math> \textbf{e} = (\textbf{r} \cdot \textbf{h} + \textbf{m})\,\bmod\,q.</math>

При этом любой, кто знает (или может вычислить) ослепляющий полином r, сможет прочесть сообщение m.

Пример

Предположим, что Алиса хочет послать сообщение, представленное в виде полинома

<math> \textbf{m} = -1 + X^3 - X^4-X^8+X^9+X^{10} </math>

и выбрала «ослепляющий» полином, для которого dr=3:

<math> \textbf{r} = -1+X^2+X^3+X^4-X^5-X^7.</math>

Тогда шифротекст e, готовый для передачи Бобу будет:

<math> \textbf{e} = (\textbf{r} \cdot \textbf{h} + \textbf{m})\,\bmod\,{32} = 14 + 11X+26X^2+24X^3+14X^4+16X^5+30X^6+7X^7+25X^8+6X^9+19X^{10}.</math>

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

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

<math> \textbf{a} = (\textbf{f} \cdot \textbf{e})\,\bmod\,q.</math>

Если расписать шифротекст, то получим цепочку:

<math> \textbf{a} = (\textbf{f} \cdot \textbf{e})\,\bmod\,q = (\textbf{f} \cdot (\textbf{r} \cdot \textbf{h}+\textbf{m}))\,\bmod\,q = (\textbf{f} \cdot (\textbf{r} \cdot p\textbf{f}_q \cdot \textbf{g} + \textbf{m}))\,\bmod\,q</math>

и окончательно:

<math> \textbf{a} = (p\textbf{r} \cdot \textbf{g} + \textbf{f} \cdot \textbf{m})\,\bmod\,q.</math>

После того, как Боб вычислил полином a по модулю q, он должен выбрать его коэффициенты из диапазона (-q/2, q/2] и далее вычислить полином b, получаемый из полинома a приведением по модулю p:

<math> \textbf{b} = \textbf{a}\,\bmod\,p = (\textbf{f} \cdot \textbf{m})\,\bmod\,p,</math>

так как <math>(p\textbf{r} \cdot \textbf{g})\,\bmod\,p = 0</math>.

Теперь, используя вторую половину секретного ключа и полученный полином b, Боб может расшифровать сообщение:

<math> \textbf{c} = (\textbf{f}_p \cdot \textbf{b})\,\bmod\,p.</math>

Нетрудно видеть, что

<math> \textbf{c} \equiv \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \equiv \textbf{m} \pmod{p}.</math>

Таким образом полученный полином c действительно является исходным сообщением m.

Пример: Боб получил от Алисы шифрованное сообщение e

<math> \textbf{e} = 14 + 11X+26X^2+24X^3+14X^4+16X^5+30X^6+7X^7+25X^8+6X^9+19X^{10} </math>

Используя секретный ключ f Боб получает полином a

<math> \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod {32} = 3 -7X-10X^2-11X^3+10X^4+7X^5+6X^6+7X^7+5X^8-3X^9-7X^{10} \pmod {32}, </math>

с коэффициентами, принадлежащими промежутку (-q/2, q/2]. Далее преобразует полином a в полином b, уменьшая коэффициенты по модулю p.

<math> \textbf{b} = \textbf{a} \pmod 3 = -X-X^2+X^3+X^4+X^5+X^7-X^8-X^{10} \pmod 3 </math>

Заключительный шаг — перемножение полинома b со второй половиной закрытого ключа <math> \textbf{f}_p </math>

<math> \textbf{c} = \textbf{f}_p \cdot \textbf{b} = \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \pmod 3 = \textbf{m} \pmod 3 </math>

<math> \textbf{c} = -1+X^3-X^4-X^8+X^9+X^{10} </math>

Который является исходным сообщением, которое передавала Алиса.

Стойкость к атакам

Полный перебор

Первая из возможных атак — атака перебором. Тут возможно несколько вариантов перебора: либо перебирать все <math> \textbf{f} \in \mathcal{L}_f </math>, и проверять на малость коэффициенты полученных результатов <math> \textbf{f} \cdot \textbf{h} \pmod q = \textbf{g} \pmod q</math>, которые, по задумке, должны был быть малыми, либо перебирать все <math> \textbf{g} \in \mathcal{L}_g </math>, также проверяя на малость коэффициенты результата <math> \textbf{f} \pmod q = \textbf{f} \cdot \textbf{h} \cdot \textbf{h}^{-1} \pmod q = \textbf{f} \cdot \textbf{f}_q \cdot \textbf{g} \cdot \textbf{h}^{-1} \pmod q = \textbf{g} \cdot \textbf{h}^{-1} \pmod q</math>. На практике пространство <math>\mathcal{L}_g </math> меньше пространства <math> \mathcal{L}_f </math>, следовательно стойкость определяется пространством <math> \mathcal{L}_g </math>. А стойкость отдельного сообщения определяется пространством <math> \mathcal{L}_r </math>.

Встреча посередине

Существует более оптимальный вариант перебора встреча посередине (англ.), предложенный Андрю Одлыжко (Andrew Odlyzko). Этот метод уменьшает количество вариантов до квадратного корня:

Стойкости закрытого ключа = <math>\sqrt{\mathcal{L}_g}</math> = <math>\frac {1} {d_g !} \sqrt {\frac {N !}{(N-2d_g)!}} </math>,

И стойкости отдельного сообщения = <math>\sqrt{\mathcal{L}_r}</math> = <math>\frac {1} {d !} \sqrt {\frac {N !}{(N-2d)!}} </math>.

Атака «встреча посередине» позволяет разменять время, необходимое для вычислений на память, необходимую для хранения временных результатов. Таким образом, если мы хотим обеспечить стойкость системы <math> 2^n</math>, нужно выбрать ключ размера <math> 2^{2n}</math>.

Атака на основе множественной передачи сообщения

Довольно серьёзная атака на отдельное сообщение, которую можно избежать, следуя простому правилу не пересылать многократно одно и то же сообщение. Суть атаки заключается в нахождении части коэффициентов ослепляющего многочлена r. А остальные коэффициенты можно просто перебрать, тем самым прочитав сообщение. Так как зашифрованное одно и то же сообщение с разными ослепляющими многочленами это <math> e_i = r_i \cdot h + m\ \bmod\ q </math>, где i=1, … n. Можно вычислить выражение <math> (e_i - e_1) \cdot h_q \ \bmod\ q </math>, которое в точности равно <math>\textbf{r}_i - \textbf{r}_1\ \bmod\ q </math>. Для достаточно большого количества переданных сообщений (скажем, для n = 4, 5, 6), можно восстановить, исходя из малости коэффициентов, большую часть ослепляющего многочлена <math> \textbf{r}_1 </math>.

Атака на основе решётки

Рассмотрим решётку, порождённую строками матрицы размера 2N×2N с детерминантом <math> \mathbf{\alpha}^N q^N</math>, состоящей из четырёх блоков размера N×N:

<math>\left(\begin{array}{cccc|cccc}

 \alpha & 0 & \cdots &  0 &  h_0  &  h_1 & \cdots & h_{N-1}\\
 0 & \alpha & \cdots & 0 &  h_{N-1} & h_0 & \cdots & h_{N-2}\\
 \vdots & \vdots & \ddots & \vdots &  \vdots & \vdots & \ddots & \vdots \\
 0 & 0 & \cdots & \alpha &  h_1 & h_2 & \cdots &  h_0 \\
 \hline
 0 & 0 & \cdots & 0 & q & 0 & \cdots & 0\\
 0 & 0 & \cdots & 0 & 0 & q & \cdots & 0\\
 \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & q\\

\end{array}\right).</math>

Так как открытый ключ <math> \textbf{h} = (p\textbf{g} \cdot \textbf{f}_q)\,\bmod\,q</math>, то <math> \textbf{g} \equiv \textbf{h} \cdot \textbf{f}\pmod{q}</math>, следовательно в этой решётке содержится вектор <math> \mathbf{\tau} = ( \alpha f, g )</math> размера 2N, в котором идут сначала коэффициенты вектора f, помноженные на коэффициент <math> \mathbf{\alpha}</math>, затем коэффициенты вектора g. Задача поиска такого вектора, при больших N и правильно подобранных параметрах, считается трудно разрешимой.

Атака на основе подобранного шифротекста

Атака на основе подобранного шифротекста является наиболее опасной атакой. Её предложили Éliane Jaulmes и Antoine Joux в 2000 году на конференции CRYPTO. Суть этой атаки заключается в подборе такого многочлена a(x), чтобы <math> \textbf{a}(x) \pmod q \ \ne \ \textbf{a}(x)</math>. При этом Ева не взаимодействует ни с Бобом, ни с Алисой.

Если взять шифротекст <math> \textbf{e}^* = \ y \textbf{h} \ + \ p y </math>, где <math> y \in \mathbb{Z} </math>, то получим многочлен <math> \textbf{a}^* = \textbf{f} \cdot \textbf{e}^* \pmod q =\ y p \textbf{g} \ + \ y p \textbf{f} \pmod q </math>. Так как коэффициенты многочленов f и g принимают значения «0», «1» и «-1», то коэффициенты многочлена a будут принадлежать множеству {-2py , -py , 0, py, 2py}. Если py выбрать таким, что <math>\frac{q}{4} < py < \frac{q}{2} </math>, то при сведении по модулю полинома a(x) приведутся только коэффициенты равные -2py или 2py. Пусть теперь i-ый коэффициент равен 2py, тогда многочлен a(x) после приведения по модулю запишется как:

<math> \textbf{a}^* = \textbf{f} \cdot \textbf{e}^* \pmod q =\ y p \textbf{g} \ + \ y p \textbf{f} -\ q \cdot \ x^i </math>,

а многочлен b(x):

<math> \textbf{b}^* = \textbf{a}^* \pmod p =\ y p \textbf{g} \ + \ y p \textbf{f} -\ q \cdot \ x^i \pmod p = -\ q \cdot \ x^i </math>,

окончательно вычислим:

<math> \textbf{c}^* = \textbf{z}(x) = \textbf{b}^* \cdot \textbf{f}_p \pmod p = -\ q \cdot \ x^I \cdot \textbf{f}_p \pmod p</math>.

Теперь, если рассмотреть все возможные i, то вместо отдельных <math> x^i </math>, можно составить полином K и расшифрованное сообщение примет вид:

<math> \textbf{c} = -\ q \textbf{K} \cdot \textbf{f}_p \pmod p</math>,

или, секретный ключ:

<math> \textbf{f} = -\ q \textbf{K} \cdot \textbf{c}^{-1} \pmod p</math>,

Вероятность таким образом отыскать составляющие ключа составляет порядка 0,1 … 0,3 для ключа размера 100. Для ключей большого размера (~500) эта вероятность очень мала. Применив данный метод достаточное количество раз, можно полностью восстановить ключ.

Для защиты от атаки такого типа используется расширенный метод шифрования NTRU-FORST. Для шифрования используется ослепляющий многочлен <math> \textbf{r}(x) = H(\textbf{m}(x), \ R ) </math>, где H — криптографически-стойкая хэш-функция, а R — случайный набор бит. Получив сообщение, Боб расшифровывает его. Далее Боб шифрует только что расшифрованное сообщение, таким же образом, что и Алиса. После сверяет его на соответствие с полученным. Если сообщения идентичные, то Боб принимает сообщение, иначе отбраковывает.

Параметры стойкости и быстродействие

Несмотря на то, что существуют быстрые алгоритмы поиска обратного полинома, разработчики предложили для коммерческого применения в качестве секретного ключа f брать:

<math> \textbf{f} = 1\ +\ p \textbf{F} </math>,

где F — малый полином. Таким образом выбранный ключ обладает следующими преимуществами:

• f всегда имеет обратный по модулю p, а именно <math> \textbf{f}^{-1} =\textbf{f}_p = 1 \pmod p </math>.
• Так как <math>\textbf{f}_p = 1 \pmod p </math> нам больше не нужно при расшифровке умножать на обратный полином <math>\textbf{f}_p</math>, и он выпадает из разряда секретного ключа.

Одно из [homes.esat.kuleuven.be/~fvercaut/papers/ntru_gpu.pdf исследований] показало, что NTRU на 4 порядка быстрее RSA и на 3 порядка — ECC.

Как уже упоминалось ранее разработчики, для обеспечения высокой стойкости алгоритма, предлагают использовать только рекомендованные параметры, обозначенные в таблице:

Рекомендованные параметры

Обозначение	N	q	p	df	dg	dr	Гарантированная стойкость
NTRU167:3	167	128	3	61	20	18	Умеренный уровень стойкости
NTRU251:3	251	128	3	50	24	16	Стандартный уровень стойкости
NTRU503:3	503	256	3	216	72	55	Высочайший уровень стойкости
NTRU167:2	167	127	2	45	35	18	Умеренный уровень стойкости
NTRU251:2	251	127	2	35	35	22	Стандартный уровень стойкости
NTRU503:2	503	253	2	155	100	65	Высочайший уровень стойкости

Ссылки

• [www.ntru.com/cryptolab/ NTRU Cryptosystems’s technical website]
• [www.ntru.com/ NTRU Cryptosystems, Inc.]
• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. [www.ntru.com/cryptolab/pdf/ANTS97.pdf NTRU: A Ring Based Public Key Cryptosystem]. In Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267—288.
• Howgrave-Graham, N., Silverman, J.H. & Whyte, W., [www.ntru.com/cryptolab/pdf/NTRUTech004v2.pdf Meet-In-The-Middle Attack on a NTRU Private Key].
• J. Hoffstein, J. Silverman. [www.ntru.com/cryptolab/pdf/TECH_ARTICLE_OPT.pdf Optimizations for NTRU]. Public-Key Cryptography and Computational Number Theory (Warsaw, September 11-15, 2000), DeGruyter, to appear.
• A. C. Atici, L. Batina, J. Fan & I. Verbauwhede. [www.cosic.esat.kuleuven.be/publications/article-1122.pdf Low-cost implementations of NTRU for pervasive security].

Отрывок, характеризующий NTRUEncrypt

Молодой человек в лисьем тулупчике стоял в покорной позе, сложив кисти рук вместе перед животом и немного согнувшись. Исхудалое, с безнадежным выражением, изуродованное бритою головой молодое лицо его было опущено вниз. При первых словах графа он медленно поднял голову и поглядел снизу на графа, как бы желая что то сказать ему или хоть встретить его взгляд. Но Растопчин не смотрел на него. На длинной тонкой шее молодого человека, как веревка, напружилась и посинела жила за ухом, и вдруг покраснело лицо.
Все глаза были устремлены на него. Он посмотрел на толпу, и, как бы обнадеженный тем выражением, которое он прочел на лицах людей, он печально и робко улыбнулся и, опять опустив голову, поправился ногами на ступеньке.
– Он изменил своему царю и отечеству, он передался Бонапарту, он один из всех русских осрамил имя русского, и от него погибает Москва, – говорил Растопчин ровным, резким голосом; но вдруг быстро взглянул вниз на Верещагина, продолжавшего стоять в той же покорной позе. Как будто взгляд этот взорвал его, он, подняв руку, закричал почти, обращаясь к народу: – Своим судом расправляйтесь с ним! отдаю его вам!
Народ молчал и только все теснее и теснее нажимал друг на друга. Держать друг друга, дышать в этой зараженной духоте, не иметь силы пошевелиться и ждать чего то неизвестного, непонятного и страшного становилось невыносимо. Люди, стоявшие в передних рядах, видевшие и слышавшие все то, что происходило перед ними, все с испуганно широко раскрытыми глазами и разинутыми ртами, напрягая все свои силы, удерживали на своих спинах напор задних.
– Бей его!.. Пускай погибнет изменник и не срамит имя русского! – закричал Растопчин. – Руби! Я приказываю! – Услыхав не слова, но гневные звуки голоса Растопчина, толпа застонала и надвинулась, но опять остановилась.
– Граф!.. – проговорил среди опять наступившей минутной тишины робкий и вместе театральный голос Верещагина. – Граф, один бог над нами… – сказал Верещагин, подняв голову, и опять налилась кровью толстая жила на его тонкой шее, и краска быстро выступила и сбежала с его лица. Он не договорил того, что хотел сказать.
– Руби его! Я приказываю!.. – прокричал Растопчин, вдруг побледнев так же, как Верещагин.
– Сабли вон! – крикнул офицер драгунам, сам вынимая саблю.
Другая еще сильнейшая волна взмыла по народу, и, добежав до передних рядов, волна эта сдвинула переднии, шатая, поднесла к самым ступеням крыльца. Высокий малый, с окаменелым выражением лица и с остановившейся поднятой рукой, стоял рядом с Верещагиным.
– Руби! – прошептал почти офицер драгунам, и один из солдат вдруг с исказившимся злобой лицом ударил Верещагина тупым палашом по голове.
«А!» – коротко и удивленно вскрикнул Верещагин, испуганно оглядываясь и как будто не понимая, зачем это было с ним сделано. Такой же стон удивления и ужаса пробежал по толпе.
«О господи!» – послышалось чье то печальное восклицание.
Но вслед за восклицанием удивления, вырвавшимся У Верещагина, он жалобно вскрикнул от боли, и этот крик погубил его. Та натянутая до высшей степени преграда человеческого чувства, которая держала еще толпу, прорвалось мгновенно. Преступление было начато, необходимо было довершить его. Жалобный стон упрека был заглушен грозным и гневным ревом толпы. Как последний седьмой вал, разбивающий корабли, взмыла из задних рядов эта последняя неудержимая волна, донеслась до передних, сбила их и поглотила все. Ударивший драгун хотел повторить свой удар. Верещагин с криком ужаса, заслонясь руками, бросился к народу. Высокий малый, на которого он наткнулся, вцепился руками в тонкую шею Верещагина и с диким криком, с ним вместе, упал под ноги навалившегося ревущего народа.
Одни били и рвали Верещагина, другие высокого малого. И крики задавленных людей и тех, которые старались спасти высокого малого, только возбуждали ярость толпы. Долго драгуны не могли освободить окровавленного, до полусмерти избитого фабричного. И долго, несмотря на всю горячечную поспешность, с которою толпа старалась довершить раз начатое дело, те люди, которые били, душили и рвали Верещагина, не могли убить его; но толпа давила их со всех сторон, с ними в середине, как одна масса, колыхалась из стороны в сторону и не давала им возможности ни добить, ни бросить его.
«Топором то бей, что ли?.. задавили… Изменщик, Христа продал!.. жив… живущ… по делам вору мука. Запором то!.. Али жив?»
Только когда уже перестала бороться жертва и вскрики ее заменились равномерным протяжным хрипеньем, толпа стала торопливо перемещаться около лежащего, окровавленного трупа. Каждый подходил, взглядывал на то, что было сделано, и с ужасом, упреком и удивлением теснился назад.
«О господи, народ то что зверь, где же живому быть!» – слышалось в толпе. – И малый то молодой… должно, из купцов, то то народ!.. сказывают, не тот… как же не тот… О господи… Другого избили, говорят, чуть жив… Эх, народ… Кто греха не боится… – говорили теперь те же люди, с болезненно жалостным выражением глядя на мертвое тело с посиневшим, измазанным кровью и пылью лицом и с разрубленной длинной тонкой шеей.
Полицейский старательный чиновник, найдя неприличным присутствие трупа на дворе его сиятельства, приказал драгунам вытащить тело на улицу. Два драгуна взялись за изуродованные ноги и поволокли тело. Окровавленная, измазанная в пыли, мертвая бритая голова на длинной шее, подворачиваясь, волочилась по земле. Народ жался прочь от трупа.
В то время как Верещагин упал и толпа с диким ревом стеснилась и заколыхалась над ним, Растопчин вдруг побледнел, и вместо того чтобы идти к заднему крыльцу, у которого ждали его лошади, он, сам не зная куда и зачем, опустив голову, быстрыми шагами пошел по коридору, ведущему в комнаты нижнего этажа. Лицо графа было бледно, и он не мог остановить трясущуюся, как в лихорадке, нижнюю челюсть.
– Ваше сиятельство, сюда… куда изволите?.. сюда пожалуйте, – проговорил сзади его дрожащий, испуганный голос. Граф Растопчин не в силах был ничего отвечать и, послушно повернувшись, пошел туда, куда ему указывали. У заднего крыльца стояла коляска. Далекий гул ревущей толпы слышался и здесь. Граф Растопчин торопливо сел в коляску и велел ехать в свой загородный дом в Сокольниках. Выехав на Мясницкую и не слыша больше криков толпы, граф стал раскаиваться. Он с неудовольствием вспомнил теперь волнение и испуг, которые он выказал перед своими подчиненными. «La populace est terrible, elle est hideuse, – думал он по французски. – Ils sont сошше les loups qu'on ne peut apaiser qu'avec de la chair. [Народная толпа страшна, она отвратительна. Они как волки: их ничем не удовлетворишь, кроме мяса.] „Граф! один бог над нами!“ – вдруг вспомнились ему слова Верещагина, и неприятное чувство холода пробежало по спине графа Растопчина. Но чувство это было мгновенно, и граф Растопчин презрительно улыбнулся сам над собою. „J'avais d'autres devoirs, – подумал он. – Il fallait apaiser le peuple. Bien d'autres victimes ont peri et perissent pour le bien publique“, [У меня были другие обязанности. Следовало удовлетворить народ. Много других жертв погибло и гибнет для общественного блага.] – и он стал думать о тех общих обязанностях, которые он имел в отношении своего семейства, своей (порученной ему) столице и о самом себе, – не как о Федоре Васильевиче Растопчине (он полагал, что Федор Васильевич Растопчин жертвует собою для bien publique [общественного блага]), но о себе как о главнокомандующем, о представителе власти и уполномоченном царя. „Ежели бы я был только Федор Васильевич, ma ligne de conduite aurait ete tout autrement tracee, [путь мой был бы совсем иначе начертан,] но я должен был сохранить и жизнь и достоинство главнокомандующего“.
Слегка покачиваясь на мягких рессорах экипажа и не слыша более страшных звуков толпы, Растопчин физически успокоился, и, как это всегда бывает, одновременно с физическим успокоением ум подделал для него и причины нравственного успокоения. Мысль, успокоившая Растопчина, была не новая. С тех пор как существует мир и люди убивают друг друга, никогда ни один человек не совершил преступления над себе подобным, не успокоивая себя этой самой мыслью. Мысль эта есть le bien publique [общественное благо], предполагаемое благо других людей.
Для человека, не одержимого страстью, благо это никогда не известно; но человек, совершающий преступление, всегда верно знает, в чем состоит это благо. И Растопчин теперь знал это.
Он не только в рассуждениях своих не упрекал себя в сделанном им поступке, но находил причины самодовольства в том, что он так удачно умел воспользоваться этим a propos [удобным случаем] – наказать преступника и вместе с тем успокоить толпу.
«Верещагин был судим и приговорен к смертной казни, – думал Растопчин (хотя Верещагин сенатом был только приговорен к каторжной работе). – Он был предатель и изменник; я не мог оставить его безнаказанным, и потом je faisais d'une pierre deux coups [одним камнем делал два удара]; я для успокоения отдавал жертву народу и казнил злодея».
Приехав в свой загородный дом и занявшись домашними распоряжениями, граф совершенно успокоился.
Через полчаса граф ехал на быстрых лошадях через Сокольничье поле, уже не вспоминая о том, что было, и думая и соображая только о том, что будет. Он ехал теперь к Яузскому мосту, где, ему сказали, был Кутузов. Граф Растопчин готовил в своем воображении те гневные в колкие упреки, которые он выскажет Кутузову за его обман. Он даст почувствовать этой старой придворной лисице, что ответственность за все несчастия, имеющие произойти от оставления столицы, от погибели России (как думал Растопчин), ляжет на одну его выжившую из ума старую голову. Обдумывая вперед то, что он скажет ему, Растопчин гневно поворачивался в коляске и сердито оглядывался по сторонам.
Сокольничье поле было пустынно. Только в конце его, у богадельни и желтого дома, виднелась кучки людей в белых одеждах и несколько одиноких, таких же людей, которые шли по полю, что то крича и размахивая руками.
Один вз них бежал наперерез коляске графа Растопчина. И сам граф Растопчин, и его кучер, и драгуны, все смотрели с смутным чувством ужаса и любопытства на этих выпущенных сумасшедших и в особенности на того, который подбегал к вим.
Шатаясь на своих длинных худых ногах, в развевающемся халате, сумасшедший этот стремительно бежал, не спуская глаз с Растопчина, крича ему что то хриплым голосом и делая знаки, чтобы он остановился. Обросшее неровными клочками бороды, сумрачное и торжественное лицо сумасшедшего было худо и желто. Черные агатовые зрачки его бегали низко и тревожно по шафранно желтым белкам.
– Стой! Остановись! Я говорю! – вскрикивал он пронзительно и опять что то, задыхаясь, кричал с внушительными интонациями в жестами.
Он поравнялся с коляской и бежал с ней рядом.
– Трижды убили меня, трижды воскресал из мертвых. Они побили каменьями, распяли меня… Я воскресну… воскресну… воскресну. Растерзали мое тело. Царствие божие разрушится… Трижды разрушу и трижды воздвигну его, – кричал он, все возвышая и возвышая голос. Граф Растопчин вдруг побледнел так, как он побледнел тогда, когда толпа бросилась на Верещагина. Он отвернулся.
– Пош… пошел скорее! – крикнул он на кучера дрожащим голосом.
Коляска помчалась во все ноги лошадей; но долго еще позади себя граф Растопчин слышал отдаляющийся безумный, отчаянный крик, а перед глазами видел одно удивленно испуганное, окровавленное лицо изменника в меховом тулупчике.
Как ни свежо было это воспоминание, Растопчин чувствовал теперь, что оно глубоко, до крови, врезалось в его сердце. Он ясно чувствовал теперь, что кровавый след этого воспоминания никогда не заживет, но что, напротив, чем дальше, тем злее, мучительнее будет жить до конца жизни это страшное воспоминание в его сердце. Он слышал, ему казалось теперь, звуки своих слов:
«Руби его, вы головой ответите мне!» – «Зачем я сказал эти слова! Как то нечаянно сказал… Я мог не сказать их (думал он): тогда ничего бы не было». Он видел испуганное и потом вдруг ожесточившееся лицо ударившего драгуна и взгляд молчаливого, робкого упрека, который бросил на него этот мальчик в лисьем тулупе… «Но я не для себя сделал это. Я должен был поступить так. La plebe, le traitre… le bien publique», [Чернь, злодей… общественное благо.] – думал он.
У Яузского моста все еще теснилось войско. Было жарко. Кутузов, нахмуренный, унылый, сидел на лавке около моста и плетью играл по песку, когда с шумом подскакала к нему коляска. Человек в генеральском мундире, в шляпе с плюмажем, с бегающими не то гневными, не то испуганными глазами подошел к Кутузову и стал по французски говорить ему что то. Это был граф Растопчин. Он говорил Кутузову, что явился сюда, потому что Москвы и столицы нет больше и есть одна армия.
– Было бы другое, ежели бы ваша светлость не сказали мне, что вы не сдадите Москвы, не давши еще сражения: всего этого не было бы! – сказал он.
Кутузов глядел на Растопчина и, как будто не понимая значения обращенных к нему слов, старательно усиливался прочесть что то особенное, написанное в эту минуту на лице говорившего с ним человека. Растопчин, смутившись, замолчал. Кутузов слегка покачал головой и, не спуская испытующего взгляда с лица Растопчина, тихо проговорил:
– Да, я не отдам Москвы, не дав сражения.
Думал ли Кутузов совершенно о другом, говоря эти слова, или нарочно, зная их бессмысленность, сказал их, но граф Растопчин ничего не ответил и поспешно отошел от Кутузова. И странное дело! Главнокомандующий Москвы, гордый граф Растопчин, взяв в руки нагайку, подошел к мосту и стал с криком разгонять столпившиеся повозки.


В четвертом часу пополудни войска Мюрата вступали в Москву. Впереди ехал отряд виртембергских гусар, позади верхом, с большой свитой, ехал сам неаполитанский король.
Около середины Арбата, близ Николы Явленного, Мюрат остановился, ожидая известия от передового отряда о том, в каком положении находилась городская крепость «le Kremlin».
Вокруг Мюрата собралась небольшая кучка людей из остававшихся в Москве жителей. Все с робким недоумением смотрели на странного, изукрашенного перьями и золотом длинноволосого начальника.
– Что ж, это сам, что ли, царь ихний? Ничево! – слышались тихие голоса.
Переводчик подъехал к кучке народа.
– Шапку то сними… шапку то, – заговорили в толпе, обращаясь друг к другу. Переводчик обратился к одному старому дворнику и спросил, далеко ли до Кремля? Дворник, прислушиваясь с недоумением к чуждому ему польскому акценту и не признавая звуков говора переводчика за русскую речь, не понимал, что ему говорили, и прятался за других.