В. Р. Гинзбург Перевод с английского

Глава 10
Генерация случайных чисел
Чтобы сгенерировать ключ, нам нужен
генератор случайных чисел (ran-
dom number generator — RNG)
. Генерация действительно хорошей случайно-
сти — неотъемлемая и к тому же наиболее сложная часть многих криптогра-
фических операций.
Мы не будем вдаваться в подробное обсуждение того, что же в действи-
тельности представляет собой случайность. Существует масса красивых ма-
тематических определений данного термина, но все они слишком сложны для
рассмотрения в этой книге. С неформальной же точки зрения случайность
можно определить как непредсказуемость значений данных для злоумышлен-
ника, даже если тот предпримет активные шаги для борьбы со случайностью.
Многим криптографическим функциям требуются хорошие генераторы
случайных чисел. В части 1, “Наша философия проектирования”, рассмотрен
безопасный канал общения и его компоненты. Мы предположили, что у нас
существует ключ, известный пользователям А и Б. Этот ключ должен быть
где-нибудь сгенерирован. Для выбора ключей системы управления ключами
используют генераторы случайных чисел. Если генератор не слишком хорош,
будет получен слабый ключ. Именно это произошло с одной из ранних версий
обозревателя Netscape [37].
Мера случайности называется
энтропией (entropy)
[90]. Мы не будем при-
водить здесь математические детали этого вопроса, просто попытаемся сде-
лать все, чтобы вы получили представление о том, что же такое энтропия.
Если у нас есть 32-битовое слово, которое выбирается совершенно случайным
образом, значит, оно имеет 32 бита энтропии. Если же 32-битовое слово может
принимать только четыре значения, вероятность появления каждого из кото-
рых составляет 25%, тогда это слово обладает лишь двумя битами энтропии.
Энтропия показывает не количество битов в значении, а то, насколько вы
не
уверены
в этом значении. Для большей наглядности энтропию можно пред-
ставить в качестве среднего числа битов, необходимых для того, чтобы задать
176

10.1. Истинно случайные числа
177
значение при использовании идеального алгоритма сжатия. Обратите внима-
ние, что энтропия значения зависит от того, сколько вы знаете об этом значе-
нии. Случайное 32-битовое слово обладает 32 битами энтропии. Теперь пред-
положим, что о значении этого слова точно известно следующее: 18 бит слова
равны 0, а 14 бит — 1. Таким требованиям удовлетворяют около
2
28
,
8
значе-
ний, а следовательно, энтропия слова будет составлять лишь 28,8 бит. Дру-
гими словами, чем больше известно о значении, тем меньше его энтропия.
Несколько сложнее подсчитать энтропию для значений, не имеющих рав-
номерного вероятностного распределения. Наиболее распространенное опре-
деление энтропии переменной
X
формулируется следующим образом:
H
(
X
) :=
−
X
x
P
(
X
=
x
) log
2
P
(
X
=
x
)
,
где
P
(
X
=
x
)
— вероятность того, что переменная
X
принимает значение
x
.
Мы не будем пользоваться этой формулой, поэтому запоминать ее нет необ-
ходимости. Именно на это определение ссылаются математики, когда говорят
об энтропии. В математике существует еще несколько определений энтропии;
выбор того или иного определения зависит от того, чем занимается конкрет-
ный ученый. И не путайте нашу энтропию с понятием энтропии в физике,
где этот термин касается термодинамики.
10.1
Истинно случайные числа
В идеальном мире следовало бы использовать “истинно случайные” числа.
К сожалению, наш мир не идеален и найти в нем действительно случайные
данные весьма сложно.
Обычные компьютеры имеют несколько источников энтропии. В качестве
примеров таких источников часто приводят точное время нажатия клавиши
и точное время перемещения мыши. В свое время некоторыми учеными даже
проводились исследования по поводу случайности колебаний времени досту-
па к жесткому диску, вызванных турбулентностью внутри его корпуса [19].
Все эти источники энтропии несколько сомнительны, так как в определенных
ситуациях злоумышленник может выполнить измерения над источником слу-
чайности или повлиять на этот источник.
Многие разработчики весьма оптимистично относятся к количеству эн-
тропии, которое может быть извлечено из разных источников. Мы видели
программное обеспечение, которое генерировало 1-2 байта случайных данных
на основе времени одного нажатия клавиши. К сожалению, мы не разделяем
этого оптимизма. Время нажатия клавиш профессиональной машинисткой
можно предсказать с точностью до нескольких миллисекунд. А частота ска-
нирования клавиатуры ограничивает точность, с которой можно измерить

178

жүктеу/скачать 2,74 Mb.

Достарыңызбен бөлісу: