В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел 10.5.1 Источники энтропии Будем исходить из предположения, что в нашем окружении находится несколько источников энтропии. Каждый источник может генерировать со- бытия, содержащие энтропию, в любой момент времени. Нас не интересу- ет то, что конкретно будет использоваться в качестве источников энтропии. Достаточно, чтобы как минимум один источник генерировал данные, кото- рые не будут предсказуемыми для злоумышленника. Поскольку мы не зна- ем, как именно будет действовать злоумышленник, имеет смысл превращать в источники энтропии все данные, которые будто бы не являются предска- зуемыми. В частности, в качестве неплохих источников случайных данных можно порекомендовать время нажатия клавиш и время перемещения мы- ши. Постарайтесь найти как можно больше временн ´ ых источников энтропии. Вы можете использовать (желательно одновременно) точное время нажатия клавиш, перемещений и щелчков кнопкой мыши, а также откликов жестких дисков и принтеров. Не страшно, если злоумышленник сможет предсказать или скопировать данные из некоторых источников; достаточно, чтобы он не мог этого сделать для всех источников сразу. Реализация источников энтропии может потребовать от разработчика много времени и усилий. Как правило, источники энтропии должны быть встроены в драйверы аппаратного обеспечения операционной системы. Это практически невозможно осуществить на уровне пользователя. Идентифицировать каждый источник мы будем с помощью его уникаль- ного номера, находящегося в диапазоне от 0 до 255. Разработчики могут са- ми решать, как выделять номера источников — статически или динамически. Данные каждого события представляют собой короткую последовательность байтов. Источники энтропии должны включать в себя только те данные со- бытий, которые невозможно предсказать. Например, информация о времени может быть представлена двумя или четырьмя наименее значимыми байта- ми точного таймера. Включать в эти данные год, месяц или число не имеет смысла — злоумышленник их и так знает. Мы будем выполнять конкатенацию событий, собранных из различных ис- точников. Чтобы гарантировать, что строка, полученная в результате подоб- ной конкатенации, будет кодировать события уникальным образом, ее нужно жестко структурировать. Каждое событие кодируется тремя или более байта- ми данных. Первый содержит номер источника случайных данных; второй — количество дополнительных байтов данных; следующие байты содержат дан- ные, полученные от источника. Разумеется, злоумышленник будет получать информацию о событиях, сгенерированных некоторыми источниками энтропии. Чтобы смоделировать подобную ситуацию, предположим, что некоторые источники находятся в 10.5. Аккумулятор 191 полной власти злоумышленника. Последний выбирает, когда и какие события будут генерироваться этими источниками. Кроме того, как и все остальные пользователи, злоумышленник может в любой момент запросить случайные данные у генератора псевдослучайных чисел. 10.5.2 Пулы Чтобы обновить начальное число генератора, события нужно накапли- вать в пуле. Последний должен быть достаточно большим для того, чтобы злоумышленник не смог перебрать возможные значения содержащихся в пу- ле событий. Обновление начального числа с помощью “достаточно большого” пула случайных событий сделает бессмысленной всю ту информацию о состо- янии генератора, которой мог обладать злоумышленник. К сожалению, мы не знаем, сколько событий нужно накопить в пуле, прежде чем обновлять начальное число генератора. В Yarrow мы пытались решить эту проблему путем использования оценок энтропии и различных эвристических правил. Fortuna же поступает гораздо более удачным способом. У нас есть 32 пула: P 0 , . . . , P 31 . Теоретически каждый пул содержит стро- ку байтов неограниченной длины. На практике же все обстоит немного по- другому. Полученная строка будет использоваться лишь в качестве входных данных для функции хэширования. По этой причине реализациям ГПСЧ Fortuna не нужно сохранять строку неограниченной длины — они могут под- считывать хэш-код строки по мере накопления данных в пуле. Каждый источник энтропии распределяет свои случайные события меж- ду пулами по циклическому принципу. Это гарантирует, что энтропия, полу- ченная от каждого источника, будет распределена между пулами более или менее равномерно. Каждое случайное событие, попавшее в тот или иной пул, присоединяется к строке, которая уже содержится в этом пуле. Мы будем обновлять начальное число генератора каждый раз, когда объ- ем содержимого пула P 0 станет достаточно большим. Процедуры обновления начального числа будут пронумерованы как 1 , 2 , 3 , . . . . В зависимости от но- мера обновления r в процесс обновления включаются один или более пулов. Пул P i участвует в обновлении, если 2 i является делителем r . Таким образом, пул P 0 будет участвовать в каждом обновлении, пул P 1 — в каждом втором обновлении, пул P 2 — в каждом четвертом обновлении и т.п. После того как пул принял участие в обновлении, его содержимое сбрасывается и заменяется пустой строкой. Описанная система способна автоматически адаптироваться к конкретной ситуации. Если злоумышленник практически ничего не знает об источниках случайных данных, он не сможет предсказать содержимое пула P 0 при следу- ющем обновлении. Но что, если злоумышленник имеет много информации об |