В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел tuna, но и как часть его интерфейса. Взять хотя бы программу, которая вы- полняет моделирование методом Монте-Карло 4 . Мы хотим, чтобы это моде- лирование было случайным. Вместе с тем желательно, чтобы при необходимо- сти мы могли воспроизвести нужные вычисления (например, для отладки или проверки). Для этого в начале программы можно единоразово вызвать встро- енный генератор случайных чисел операционной системы. С его помощью мы получим случайное начальное число. Это число может быть зафиксировано как часть выходных данных программы, а затем использовано нашим гене- ратором для вычисления всех оставшихся случайных данных, необходимых для моделирования. Зная исходное начальное число генератора, можно про- контролировать правильность всех вычислений. Для этого достаточно еще раз запустить программу с теми же входными данными и начальным чис- лом. А для отладки один и тот же процесс моделирования может запускать- ся снова и снова, причем его поведение всегда будет одинаковым — лишь бы исходное начальное число оставалось неизменным. Теперь рассмотрим функционирование генератора подробнее. 10.4.1 Инициализация Она довольно проста. Мы устанавливаем значения ключа и счетчика рав- ными нулю, чтобы показать, что генератору еще не было передано начальное число. функция InitializeGenerator выход: G Состояние генератора. Установим значения ключа K и счетчика C равными нулю. ( K, C ) ← (0 , 0) Сформируем состояние. G ← ( K, C ) return G 10.4.2 Изменение начального числа Функция Reseed обновляет состояние генератора с помощью входной строки произвольной длины. На этом уровне нас не волнует, что будет содер- жать входная строка. Чтобы гарантировать тщательное перемешивание вход- ной строки с существующим ключом, мы применим функцию хэширования. функция Reseed вход: G Состояние генератора; изменяется этой функцией. 4 Моделирование методом Монте–Карло — это моделирование, управляемое случайным выбором некоторых величин. 10.4. Генератор 187 s Новое или дополнительное начальное число. Вычислим новый ключ с помощью функции хэширования. K ← SHA d − 256( K k s ) Увеличим на единицу значение счетчика, чтобы оно стало ненулевым, и пометим, что генератору было передано начальное число. В дан- ном случае C рассматривается как 16-байтовое целое число, пред- ставленное в формате, в котором наименее значимый байт запи- сывается первым. C ← C + 1 Здесь значение счетчика C рассматривается как целое число. Позднее он будет выступать в качестве блока открытого текста. Для преобразования одного значения в другое будем использовать соглашение о формате записи целых чисел, при котором наименее значимый байт записывается первым. Блок открытого текста — это блок, состоящий из 16 байт: p 0 , . . . , p 15 . Он соответствует целочисленному значению 15 X t =0 p i 2 8 i . Используя это соглашение, мы можем рассматривать C и как 16-байтовую строку, и как целое число. 10.4.3 Генерация блоков Следующая функция генерирует заданное количество блоков случайных данных. Это внутренняя функция, которая будет использоваться только са- мим генератором псевдослучайных чисел. Любой объект за пределами гене- ратора не должен иметь доступа к этой функции. функция GenerateBlocks вход: G Состояние генератора; изменяется этой функцией. k Количество блоков, которое необходимо сгенерировать. выход: r Псевдослучайная строка длиной 16 k байт. assert C 6 = 0 Начнем с пустой строки. r ← ² Присоединим к ней нужное количество блоков. for i = 1 , . . . , k do r ← r k E ( K, C ) C ← C + 1 |