Подпись Лэмпорта

Подпись Лэмпорта (англ. Lamport signature) — это криптосистема цифровой подписи с открытым ключом. Может быть построена на любой односторонней функции. Была предложена в 1979 году и названа в честь её автора, американского учёного, Лесли Лэмпорта.

Описание

Пусть у Алисы есть 256-битная криптографическая хеш-функция и криптографически стойкий генератор псевдослучайных чисел. Она хочет создать и использовать пару ключей Лэмпорта — секретный ключ и соответствующий ему открытый ключ.

Создание пары ключей

Чтобы создать секретный ключ, Алиса использует генератор случайных чисел для получения 256 пар случайных чисел (всего 2×256 чисел). Каждое число состоит из 256 бит, то есть общий размер равен 2×256×256 бит = 16 КиБ. Эти числа будут секретным ключом Алисы, и она будет хранить их в секретном месте, чтобы использовать в дальнейшем.

Чтобы создать открытый ключ, Алиса хеширует каждое из 512 чисел секретного ключа, таким образом получая 512 хешей по 256 бит каждый. Эти 512 хешей составляют открытый ключ Алисы, который она публикует.

Подпись сообщения

Теперь Алиса хочет подписать сообщение. Для начала она хеширует сообщение и получает 256-битный хеш. Затем, для каждого бита в этом хеше, она берёт соответствующее число из секретного ключа. Если, например, первый бит в хеше сообщения равен нулю, она берёт первое число из первой пары секретного ключа. Если же первый бит равен единице, она использует второе число из первой пары. И так далее. В итоге получается 256 случайных чисел, размер которых составляет 256×256 бит = 8 КиБ. Эти числа и составляют подпись, которую Алиса отправляет вместе с сообщением.

Стоит обратить внимание, что после того как Алиса использовала свой секретный ключ, он никогда не должен быть использован снова. Остальные 256 чисел, которые она не использовала в подписи, Алиса никогда не должна публиковать или использовать. Предпочтительно, чтобы она их удалила, так как иначе кто-то может получить к ним доступ и сгенерировать с их помощью поддельную подпись.

Проверка подписи

Боб хочет проверить подпись, которым Алиса подписала сообщение. Он также хеширует сообщение и получает 256-битный хеш. Затем для каждого бита в этом хеше он выбирает число из открытого ключа Алисы. Эти числа выбираются по такому же принципу, по какому Алиса выбирала числа для составления подписи. То есть, если первый бит хеша сообщения равен нулю, Боб выбирает первое число из первой пары в отрытом ключе. И так далее.

Затем Боб хеширует каждое из 256 чисел из подписи Алисы и получает 256 хешей. Если эти 256 хешей в точности соответствуют 256 хешам, которые он только что получил из открытого ключа Алисы, Боб считает подпись подлинной. Если не соответствуют — то фальшивой.

Стоит обратить внимание, что до того, как Алиса опубликует подпись к сообщению, никто не знает 2×256 случайных чисел в секретном ключе. Таким образом, никто не может создать правильный набор из 256 чисел для подписи. После того, как Алиса опубликует подпись, никто всё ещё не знает остальные 256 чисел, и, таким, образом, не может создать подпись для сообщений, имеющих иной хеш.

Пример

Пусть Алиса передаёт сообщение M = «Lamport» Бобу, подписывая его подписью Лэмпорта и используя при этом 8-битную хеш-функцию. То есть, изначальное сообщение будет преобразовано в 8-битный хеш.

Генерация ключей

Используя генератор случайных чисел, Алиса получает восемь пар случайных чисел. Эти 16 чисел являются закрытым ключом Алисы.

Закрытый ключ: <math>(13,</math> <math>134)</math> <math>(128,</math> <math>67)</math> <math>(25,</math> <math>90 ) (78,</math> <math>156 )</math> <math>(89,</math> <math>37)</math> <math>(234,</math> <math>29)</math> <math>(199,</math> <math>74)</math> <math>(12,</math> <math>3)</math>

Чтобы получить открытый ключ, Алиса вычисляет хеш-значение для каждого числа из закрытого ключа.

Открытый ключ:

<math>(00101010,</math> <math>10010101)</math>

<math>(01100111,</math> <math>11010101)</math>

<math>(00101110,</math> <math>11110111)</math>

<math>(00100101,</math> <math>11011101)</math>

<math>(11100001,</math> <math>00011000)</math>

<math>(11000110,</math> <math>11001110)</math>

<math>(11001101,</math> <math>11001001)</math>

<math>(11100011,</math> <math>11111101)</math>

Получившийся открытый ключ Алиса публикует в общий доступ.

Подпись сообщения

Алиса хочет подписать сообщение M = «Lamport». Для этого она вычисляет значение хеш-функции от этого сообщения <math>H(M)=01011010</math> и ставит в соответствие каждому биту хеша одно из значений в парах закрытого ключа, тем самым формируя подпись.

Подпись сообщения «Lamport»: <math>(13,</math> <math>67,</math> <math>25,</math> <math>156,</math> <math>37,</math> <math>234,</math> <math>74,</math> <math>12)</math>

Проверка подписи

Боб получает подписанное сообщение «Lamport» и хочет проверить, действительно ли его послала Алиса. Для этого он использует открытый ключ, который опубликовала Алиса. Он преобразует полученное сообщение в хеш и каждому биту в получившемся хеше ставит в соответствие число из пары в открытом ключе. Затем он хеширует подпись сообщения и сравнивает два получившихся набора чисел. Если они равны, то подпись настоящая, и сообщения действительно посылала Алиса.

Набор чисел, полученный из открытого ключа:

<math>00101010,</math>

<math>11010101,</math>

<math>00101110,</math>

<math>11011101,</math>

<math>00011000,</math>

<math>11000110,</math>

<math>11001001,</math>

<math>11100011</math>

Хеш подписи:

<math>00101010,</math>

<math>11010101,</math>

<math>00101110,</math>

<math>11011101,</math>

<math>00011000,</math>

<math>11000110,</math>

<math>11001001,</math>

<math>11100011</math>

Так как данные наборы равны — подпись настоящая.

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

Ключи

Пусть <math>k</math> — положительное число, пусть <math>P=\{0,1\}^k</math> — набор сообщений и пусть <math>f:\,Y\rightarrow Z</math> — односторонняя функция.

Для каждого <math>1\leq i\leq k</math> и <math>j\in \{0,1\}</math>, сторона, подписывающая сообщение, случайно выбирает <math>y_{i,j}\in Y</math> и вычисляет <math>z_{i,j}=f(y_{i,j})</math>.

Секретный ключ <math>K</math> состоит из <math>2k</math> значений <math>y_{i,j}</math>. Открытый ключ состоит из <math>2k</math> значений <math>z_{i,j}</math>.

Подпись сообщения

Пусть <math>m = m_1\ldots m_k \in\{0,1\}^k</math> — сообщение.

Подпись сообщения — это <math>sign(m_1\ldots m_k)=(y_{1,m_1},\ldots, y_{k,m_k})=(s_1,\ldots,s_k)</math>.

Проверка подписи

Сторона, валидирующая подпись, проверяет <math>f(s_i) = z_{i,m_i}</math> для всех <math>1\leq i\leq k</math>.

Чтобы подделать подпись сообщения криптоаналитику придется инвертировать одностороннюю функцию <math>f</math>, а это предполагается вычислительно невозможным.

Криптостойкость

Криптостойкость подписей Лэмпорта основана на криптостойкости хеш-функции.

Для каждой хеш-функции, которая генерирует n-битный дайджест, идеальная стойкость к восстановлению прообраза и к восстановлению второго прообраза подразумевает для каждого выполнения хеш-функции 2ⁿ операций и 2ⁿ бит памяти в классической вычислительной модели. Используя алгоритм Гровера, восстановление прообраза значения идеальной хеш-функции ограничено сверху O(2^n/2) операциями в квантовой вычислительной модели.

Подпись нескольких сообщений

Одним секретным ключом Лэмпорта может быть подписано только одно единственное сообщение. Это значит, что если подписано какое-то количество сообщений, должно быть опубликовано такое же количество открытых ключей. Но, если использовать дерево Меркла, составленное из открытых ключей, то вместо публикации всех открытых ключей, можно публиковать только вершину дерева. Это увеличивает размер подписи, так как часть хеш-дерева приходиться включать в подпись, но это даёт возможность использовать один-единственный хеш для проверки множества подписей. По такой схеме можно подписать <math>N=2^n</math> сообщений, где <math>n</math> — глубина дерева Меркла. То есть теоретически мы можем использовать один открытый ключ для любого количества сообщений.

Генерация ключей

Для начала необходимо сгенерировать <math>2^n</math> закрытых одноразовых ключей Лэмпорта <math>X_i</math> и открытых одноразовых ключей Лэмпорта <math>Y_i</math>. Далее для каждого открытого ключа <math>X_i</math>, где <math>1 \leq i \leq 2^n</math>, вычисляется его хеш <math>h_i=H(X_i)</math>. И на основе этих значений <math>h_i</math> строится дерево Меркла.

Пронумеруем узлы дерева <math>a_{i,j}</math> таким образом, что индекс <math>i</math> обозначает расстояние от этого узла до листового элемента, а индекс <math>j</math> обозначает порядковый номер узла слева направо на одном уровне <math>i</math>.

В нашем дереве хеш значения <math>h_i</math> являются листовыми элементами, то есть <math>h_i=a_{0,i}</math>. Каждый нелистовой узел дерева представляет из себя хеш-значение от соединения вместе двух детей, то есть <math>a_{1,0}=H(a_{0,0}||a_{0,1})</math>, <math>a_{2,0}=H(a_{1,0}||a_{1,1})</math> и так далее.

Таким образом, мы имеем дерево, корневой элемент которого и является нашим открытым ключом <math>pub</math>.

Подпись сообщения и его проверка

Чтобы подписать сообщение по нашей схеме, сначала нужно подписать его одноразовой подписью Лэмпорта <math>sig'</math>. Это делается, используя одну из пар открытых/закрытых ключей <math>(X_i, Y_i,)</math>.

<math>a_{0,i}=H(X_i)</math> — соответствующий открытому ключу <math>X_i</math> листовой элемент дерева. Путь от листового элемента <math>a_{0,i}</math> дерева к его вершине состоит из элементов <math>A_0, ... A_n</math>, где <math>A_0=a_{0,i}</math> — листовой элемент, а <math>A_n=a_{n,0}=pub</math> — вершина дерева. Чтобы вычислить этот путь, нам необходимы все дети узлов <math>A_{1}, ..., A_{n}</math>. Мы знаем, что узел <math>A_i</math> — дочерний элемент узла <math>A_{i+1}</math>. Чтобы вычислить следующий узел на пути к вершине нам нужны оба дочерних элемента узла <math>A_{i+1}</math>. Поэтому нам нужно знать «брата» узла <math>A_i</math>. Назовём его <math>auth_i</math>. Итак, <math>A_{i+1}=H(A_i||auth_i)</math>. Следовательно, нам нужны <math>n</math> узлов <math>auth_0,...,auth_{n-1}</math>, чтобы вычислить вершину дерева. Мы вычисляем их и сохраняем.

Эти узлы в совокупности с одноразовой подписью <math>sig'</math> сообщения <math>M</math> составляют итоговую подпись <math>sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})</math>.

Получатель сообщения имеет в распоряжении открытый ключ <math>pub</math>, сообщение <math>M</math> и подпись <math>sig=(sig'||X_i||auth_0||auth_1||...||auth_{n-1})</math>. Сначала он проверяет одноразовую подпись <math>sig'</math> сообщения <math>M</math>. Если она подлинна, получатель вычисляет <math>A_0=H(X_i)</math>. И далее для <math>j=1,..,n-1</math> вычисляет <math>A_j=H(A_{j-1}||auth_{j-1})</math>. Если <math>A_n</math> оказывается равна <math>pub</math>, то подпись считается подлинной.

Различные оптимизации и реализации

Короткий секретный ключ

Вместо создания и хранения всех случайных чисел секретного ключа, можно хранить одно единственно число соответствующего размера. Обычно размер выбирается таким же, как и размер одного случайного числа в закрытом ключе. Этот ключ можно использовать как зерно для генератора случайных чисел (CSPRNG), чтобы можно было воссоздать всю последовательность случайных чисел секретного ключа, когда это понадобиться.

Тем же способом ключ может быть использован вместе с CSPRNG, чтобы создать множество ключей Лэмпорта. Предпочтительны CSPRNG, имеющие высокую криптостойкость, такие как BBS.

Короткий открытый ключ

Подпись Лэмпорта может быть использована вместе со списком хешей, что делает возможным включать в открытый ключ только один хеш. То есть, вместо <math>2k</math> значений — <math>z_{ij}</math>. Чтобы иметь возможность сравнивать случайные числа в подписи с хешем в открытом ключе, все неиспользуемые в открытом ключе хеши, то есть, значения <math>(z_{ij})</math> для любого <math>j\neq m_i</math>, должны быть включены в подпись. В результате открытый ключ становится существенно короче, а размер подписи увеличивается примерно в два раза.

Хеширование сообщения

Схема цифровой подписи Лэмпорта не требует, чтобы сообщение m было захешировано перед тем, как оно будет подписано. Хеширование может быть использовано, например, для подписания длинных сообщений, где подписываться будет хеш сообщения, а не оно само.

Сравнение с другими криптосистемами

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

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

Литература

• Lamport L. [research.microsoft.com/en-us/um/people/lamport/pubs/dig-sig.pdf Constructing digital signatures from a one-way function]. — SRI International Computer Science Laboratory, 1979.
• Peikert K. [wiki.cc.gatech.edu/theory/images/6/6d/Lec13.pdf Theoretical Foundations of Cryptography]. — Georgia Tech, 2010.
• Katz J. [www.cs.umd.edu/~jkatz/crypto/f02/lectures/lecture36.pdf Introduction to Cryptography]. — University of Maryland.
• Zaverucha G. Stinson R. Cheriton R. [eprint.iacr.org/2010/446.pdf Short One-Time Signatures]. — University of Waterloo, 2010.
• Garcia L. [citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.4272&rep=rep1&type=pdf On security and efficiency of the Merkle signature scheme]. — Darmstadt.

Отрывок, характеризующий Подпись Лэмпорта

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


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


Пьер, со времени исчезновения своего из дома, ужа второй день жил на пустой квартире покойного Баздеева. Вот как это случилось.