Разработка приложений в среде Linux. Второе издание

Троан Эрик В.

Однако некоторые приложения (включая криптографические) для достижения наилучших результатов требуют использования действительно случайных чисел. Ядро Linux для предоставления криптографически устойчивых случайных чисел производит выборку событий из непредсказуемого внешнего мира.

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

19.1. Псевдослучайные числа

В некоторых ситуациях все же требуется обеспечить невозможность прогнозирования.

Библиотека С содержит функции для генерирования ожидаемых последовательностей псевдослучайных чисел. Эти функции легки в применении и являются одинаковыми на всех платформах Unix. Рассмотрим пример типичного использования данных функций.

#include <stdlib.h>

#include <time.h>...

srand(time(NULL) +getpid);

for (...;...;...) {

 do_something(rand);

}

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

time

. Последняя возвращает количество секунд, прошедших с 1 января 1970 года, поэтому начальное значение изменяется каждую секунду. Таким образом, оно может считаться уникальным в течение достаточно длинного интервала времени (приблизительно 49 710 дней на 32-разрядном компьютере). Если необходимо предотвратить возможность одинаковой активизации программы для двух пользователей, которые запускают ее в одну и ту же секунду, добавьте в начальном значении ко времени идентификатор текущего процесса.

Числа, возвращаемые функцией

rand

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

Обратите внимание на то, что при отладке вам потребуется сохранить начальное значение, с которым была вызвана функция

srand

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

rand

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

19.2. Криптография и случайные числа

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

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

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

Если вы недостаточно хорошо знакомы с криптографией, однако вынуждены ее применять, мы рекомендуем [30] в качестве превосходного вводного руководства по этой теме.

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

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

Не лучшим способом решения проблемы является обращение к человеку для создания ключа. Чаще всего люди выбирают ключи, которые трудно назвать случайными. Подбор ключа, как правило, имеет отношение к естественному языку, словарный запас которого в терминах теории информации достаточно предсказуем. Говорят, что естественный язык обладает низкой энтропией; действительно случайный ключ имеет высокую энтропию.

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

Поскольку компьютеры не оснащены подобными устройствами, в системе Linux предлагается выход из ситуации. Тед Тсо (Ted Ts'o) написал код, который измеряет временные диаграммы внешних событий (щелчок мыши, нажатие кнопки клавиатуры и так далее), извлекает из них информацию и сохраняет ее в пуле энтропии. Некоторые компоненты человеческого (и другого внешнего) взаимодействия с компьютером являются в высшей степени случайными. Код, заполняющий пул энтропии, старается некоторым образом охарактеризовать величину добавленной энтропии, что позволяет программисту оценить степень неупорядоченности при генерировании случайной информации. В последнее время во многих компьютерах предусматриваются аппаратные источники криптографически случайных данных. В Linux такие случайные данные подаются в системном пуле энтропии, поэтому все программы Linux могут применять один и тот же интерфейс в зависимости от оборудования, которое они используют.

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

/dev/random

и

/dev/urandom

. Устройство

/dev/random

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

/dev/urandom

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

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

• Не используйте ни

/dev/random

, ни

/dev/urandom

для тех данных, которые потребуется продублировать. Они также являются крайне неподходящими источниками данных для методов Монте-Карло. Даже последовательность 1, 2, …, n–1, n для них более приемлема; ее, по крайней мере, можно воспроизвести.