Хеширование

Хеширование или хэширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

Хеширование применяется в следующих случаях:

• при построении ассоциативных массивов;
• при поиске дубликатов в сериях наборов данных;
• при построении уникальных идентификаторов для наборов данных;
• при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в них ошибок (возникших случайно или внесённых намеренно), возникающих при хранении и/или передаче данных;
• при сохранении паролей в системах защиты в виде хеш-кода (для восстановления пароля по хеш-коду требуется функция, являющаяся обратной по отношению к использованной хеш-функции);
• при выработке электронной подписи (на практике часто подписывается не само сообщение, а его «хеш-образ»);
• и др.

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

Существует множество алгоритмов хеширования, отличающихся различными свойствами. Примеры свойств:

• разрядность;
• вычислительная сложность;
• криптостойкость.

Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшим примером хеш-функции может служить «обрамление» данных циклическим избыточным кодом (англ. CRC, cyclic redundancy code).

История

В январе 1953 года Ханс Петер Лун (нем. Hans Peter Luhn) (сотрудник фирмы IBM) предложил «хеш-кодирование». Дональд Кнут считает, что Ханс первым выдвинул систематическую идею «хеширования».

В 1956 году Арнольд Думи (англ. Arnold Dumey) в своей работе «Computers and automation» первым описал идею «хеширования» такой, какой её знает большинство программистов сейчас. Думи рассматривал «хеширование» как решение «проблемы словаря», предложил использовать в качестве «хеш-адреса» остаток от деления на простое число.

В 1957 году в журнале «IBM Journal of Research and Development» была опубликована статья Уэсли Питерсона (англ. W. Wesley Peterson) о поиске текста в больших файлах. Эта работа считается первой «серьёзной» работой по «хешированию». В статье Уэсли определил «открытую адресацию», указал на уменьшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz), в которой было проведено обширное исследование «хеш-функций». В течение нескольких последующих лет «хеширование» широко использовалось, однако никаких значимых работ не публиковалось.

В 1967 году «хеширование» в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ. Robert Morris) опубликовал в журнале «Communications of the ACM» большой обзор по «хешированию». Эта работа считается «ключевой» публикацией, вводящей понятие о «хешировании» в научный оборот, и закрепившей термин «хеш», ранее применявшийся только специалистами (жаргон).

До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование», благодаря работам Андрея Петровича Ершова, использовалось слово «расстановка», а для «коллизий» использовался термин «конфликт» (А. П. Ершов использовал «расстановку» с 1956 года). В русскоязычном издании книги Никлауса Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка». Предлагалось, также, назвать метод другим русским словом: «окрошка». Однако ни один из этих вариантов не прижился, и в русской литературе используется преимущественно термин «хеширование».

Виды «хеш-функций»

«Хорошая» хеш-функция должна удовлетворять двум свойствам:

• быстрое вычисление;
• минимальное количество «коллизий».

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

• <math>K</math> — количество «ключей» (входных данных);
• <math>h(k)</math> — хеш-функция, имеющая не более <math>M</math> различных значений (выходных данных).

То есть:

<math>\forall k\in (0;\,K): h(k) < M</math>.

В качестве примера «плохой» хеш-функции можно привести функцию с <math>M=1000</math>, которая десятизначному натуральному числу <math>K</math> сопоставляет три цифры, выбранные из середины двадцатизначного квадрата числа <math>K</math>. Казалось бы, значения «хеш-кодов» должны равномерно распределяться между «000» и «999», но для «реальных» данных это справедливо лишь в том случае, если «ключи» не имеют «большого» количества нулей слева или справа.

Рассмотрим несколько простых и надёжных реализаций «хеш-функций».

«Хеш-функции», основанные на делении

1. «Хеш-код» как остаток от деления на число всех возможных «хешей»

Хеш-функция может вычислять «хеш» как остаток от деления входных данных на <math>M</math>:

<math> h(k) = k \mod M </math>

где <math>M</math> — количество всех возможных «хешей» (выходных данных).

При этом очевидно, что при чётном <math>M</math> значение функции будет чётным при чётном <math>k</math> и нечётным — при нечётном <math>k</math>. Также не следует использовать в качестве <math>M</math> степень основания системы счисления компьютера, так как «хеш-код» будет зависеть только от нескольких цифр числа <math>k</math>, расположенных справа, что приведёт к большому количеству коллизий. На практике обычно выбирают простое <math>M</math>; в большинстве случаев этот выбор вполне удовлетворителен.

2. «Хеш-код» как набор коэффициентов получаемого полинома

Хеш-функция может выполнять деление входных данных на полином по модулю два. В данном методе <math>M</math> должна являться степенью двойки, а бинарные ключи (<math>K=k_{n-1}k_{n-2}...k_{0}</math>) представляются в виде полиномов, в качестве «хеш-кода» «берутся» значения коэффициентов полинома, полученного как остаток от деления входных данных <math>K</math> на заранее выбранный полином <math>P</math> степени <math>m</math>:

<math>K(x) \mod P(x) = h_{m-1}x^{m-1} + \dots + h_{1}x + h_{0} </math>

<math> h(x) = h_{m-1} ... h_{1} h_{0}</math>

При правильном выборе <math>P(x)</math> гарантируется отсутствие коллизий между почти одинаковыми ключами.

«Хеш-функции», основанные на умножении

Обозначим символом <math>w</math> количество чисел, представимых машинным словом. Например, для 32-разрядных компьютеров, совместимых с IBM PC, <math> w = 2^{32} </math>.

Выберем некую константу <math>A</math> так, чтобы <math>A</math> была взаимно простой с <math>w</math>. Тогда хеш-функция, использующая умножение, может иметь следующий вид:

<math>h(K) = \left[ M \left\lfloor \frac{A}{w}*K \right\rfloor \right]</math>

В этом случае на компьютере с двоичной системой счисления <math>M</math> является степенью двойки, и <math>h(K)</math> будет состоять из старших битов правой половины произведения <math>A*K</math>.

Среди преимуществ хеш-функций, основанных на делении и умножении, стоит отметить выгодное использование неслучайности реальных ключей. Например, если ключи представляют собой арифметическую прогрессию (например, последовательность имён «Имя 1», «Имя 2», «Имя 3»), хеш-функция, использующая умножение, отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшит количество коллизий по сравнению со случайной ситуацией.

Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи. Хеширование Фибоначчи основано на свойствах золотого сечения. В качестве константы <math>A</math> здесь выбирается целое число, ближайшее к <math>\varphi^{-1}*w</math> и взаимно простое с <math>w</math>, где <math>\varphi</math> — это золотое сечение.

Хеширование строк переменной длины

Вышеизложенные методы применимы и в том случае, если необходимо рассматривать ключи, состоящие из нескольких слов, или ключи переменной длины. Например, можно скомбинировать слова в одно при помощи сложения по модулю <math>w</math> или операции «исключающее или». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона.

Хеширование Пирсона (англ. Pearson hashing) — алгоритм, предложенный Питером Пирсоном (англ. Peter Pearson) для процессоров с 8-битовыми регистрами, задачей которого является быстрое преобразование строки произвольной длины в хеш-код. На вход функция получает слово <math>W</math>, состоящее из <math>n</math> символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. При этом значение хеш-кода зависит от каждого символа входного слова.

Алгоритм можно описать следующим псевдокодом, который получает на вход строку <math>W</math> и использует таблицу перестановок <math>T</math>:

h := 0
for each c in W loop
  index := h xor c
  h := T[index]
end loop
return h

Среди преимуществ алгоритма следует отметить:

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

В качестве альтернативного способа хеширования ключей <math>K</math>, состоящих из <math>l</math> символов (<math>K=x_{1}x_{2}...x_{l}</math>), можно предложить вычисление

<math>h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l})) \mod M</math>

Идеальное хеширование

Идеальной хеш-функцией (англ. perfect hash function) называется такая функция, которая отображает каждый ключ из набора <math>S</math> во множество целых чисел без коллизий. В математике такое преобразование называется инъективным отображением.

Описание

1. Функция <math>h(k) \colon U \to [m]</math> называется идеальной хеш-функцией для <math>S \subseteq U</math>, если она инъективна на <math>S</math>.
2. Функция <math>h(k) \colon U \to [m]</math> называется минимальной идеальной хеш-функцией для <math>S\subseteq U</math>, если она является идеальной хеш-функцией и <math>m = n = |S|</math>.
3. Для целого <math>k \ge 1</math> функция <math>h(k) \colon U \to [m]</math> называется <math>k</math>-идеальной хеш-функцией (k-PHF) для <math>S \subseteq U</math>, если для каждого <math>j \in [m]</math> имеем <math>|\{x \in S | h(x) = j\}| \le k</math>.

Идеальное хеширование применяется, если требуется присвоить уникальный идентификатор ключу без сохранения какой-либо информации о ключе. Пример использования идеального (или скорее <math>k</math>-идеального) хеширования: размещение хешей, связанных с данными, хранящимися в большой и медленной памяти, в небольшой и быстрой памяти. Размер блока можно выбрать таким, чтобы необходимые данные считывались из медленной памяти за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, если представление графа не умещается в основной памяти. .

Универсальное хеширование

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

Описание

Предположим, что требуется отобразить ключи из пространства <math>U</math> в числа <math>[m]</math>. На входе алгоритм получает данные из некоторого набора <math>S \in U</math> размерностью <math>n</math>. Набор заранее неизвестен. Как правило, алгоритм должен обеспечить наименьшее число коллизий, чего трудно добиться, используя какую-то определённую хеш-функцию. Число коллизий можно уменьшить, если каждый раз при хешировании выбирать хеш-функцию случайным образом. Хеш-функция выбирается из определённого набора хеш-функций, называемого универсальным семейством <math>H = \{ h : U \to [m] \}</math>.

Методы борьбы с коллизиями

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

Методы борьбы с коллизиями в хеш-таблицах

Большинство первых работ, описывающих хеширование, посвящено методам борьбы с коллизиями в хеш-таблицах. Тогда хеш-функции применялись при поиске текста в файлах большого размера. Существует два основных метода борьбы с коллизиями в хеш-таблицах:

1. метод цепочек (метод прямого связывания);
2. метод открытой адресации.

При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» — «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе, создаётся новая пара «список ключей» — «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется <math>N</math> ключей и <math>M</math> списков, средний размер хеш-таблицы составит <math>\frac{N}{M}</math>. В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в <math>M</math> раз.

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

Криптографическая соль

Для защиты паролей и цифровых подписей от подделки создано несколько методов, работающих даже в том случае, если криптоаналитику известны способы построения коллизий для используемой хеш-функции. Одним из таких методов является добавление к входным данным так называемой криптографической «соли» — строки случайных данных; иногда «соль» добавляется и к хеш-коду. Добавление случайных данных значительно затрудняет анализ итоговых хеш-таблиц. Данный метод, к примеру, используется при сохранении паролей в UNIX-подобных операционных системах.

Применение хеш-функций

Хеш-функции широко используются в криптографии, а также во многих структурах данных — хеш-таблицаx, фильтрах Блума и декартовых деревьях.

Криптографические хеш-функции

Среди множества существующих хеш-функций принято выделять криптографически стойкие, применяемые в криптографии, так как на них накладываются дополнительные требования. Для того, чтобы хеш-функция <math>H</math> считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

• необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных <math>X</math>, для которого <math>H(X) = m</math>;
• стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого <math>H(N) = H(M)</math>;
• стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений <math>(M, M')</math>, имеющих одинаковый хеш.

Данные требования не являются независимыми:

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

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

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

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

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

Контрольные суммы

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

Алгоритмы вычисления контрольных сумм по скорости вычисления в десятки и сотни раз быстрее, чем криптографические хеш-функции, и значительно проще в аппаратном исполнении.

Платой за столь высокую скорость является отсутствие криптостойкости — возможность легко «подогнать» сообщение под заранее известную контрольную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем разрядность криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.

Простейшим алгоритмом вычисления контрольной суммы является деление сообщения (входных данных) на 32- или 16-битовые слова с последующим суммированием слов. Такой алгоритм применяется, например, в протоколах TCP/IP.

Как правило, алгоритмы вычисления контрольных сумм должны обнаруживать типичные аппаратные ошибки, например, должны обнаруживать несколько подряд идущих ошибочных бит до заданной длины. Семейство алгоритмов так называемых «циклических избыточных кодов» удовлетворяет этим требованиям. К ним относится, например, алгоритм CRC32, применяемый в устройствах Ethernet и в формате сжатия данных ZIP.

Контрольная сумма, например, может быть передана по каналу связи вместе с основным текстом (данными). На приёмном конце, контрольная сумма может быть рассчитана заново и может сравниваться с переданным значением. Если будет обнаружено расхождение, то при передаче возникли искажения, и можно запросить повторную передачу.

Пример применения хеширования в быту — подсчёт количества чемоданов, перевозимых в багаже. Для проверки сохранности чемоданов не требуется проверять сохранность каждого чемодана, достаточно посчитать количество чемоданов при погрузке и выгрузке. Совпадение чисел будет означать, что ни один чемодан не потерян. То есть, число чемоданов является хеш-кодом.

Данный метод можно дополнить для защиты передаваемой информации от фальсификации (метод MAC). В этом случае хеширование производится криптостойкой функцией над сообщением, объединённым с секретным ключом, известным только отправителю и получателю сообщения. Криптоаналитик, перехватив сообщение и значение хеш-функции, не сможет восстановить код, то есть, не сможет подделать сообщение (см. имитозащита).

Геометрическое хеширование

Геометрическое хеширование (англ. geometric hashing) — метод, широко применяемый в компьютерной графике и вычислительной геометрии для решения задач на плоскости или в трёхмерном пространстве, например для нахождения ближайших пар точек среди множества точек или для поиска одинаковых изображений. Хеш-функция в данном методе обычно получает на вход какое-либо метрическое пространство и разделяет его, создавая сетку из клеток. Хеш-таблица в данном случае является массивом с двумя или более индексами и называется «файлом сетки» (англ. grid file). Геометрическое хеширование применяется в телекоммуникациях при работе с многомерными сигналами.

Ускорение поиска данных

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

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

Литература

• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: Триумф, 2002. — ISBN 5-89392-055-4.

• Дональд Кнут. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е издание. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.

• Никлаус Вирт. Алгоритмы и структуры данных. — М.: «Мир», 1989. — ISBN 5-03-001045-9.

Ссылки

• [masteroid.ru/content/view/1322/49/ Теория хеш-функций]
• [protect.htmlweb.ru/ecp.htm Информация по электронной цифровой подписи]

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

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


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

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


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