В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел for i = 0 , . . . , 31 do if 2 i | ReseedCNT then s ← s k SHA d − 256( P i ) P i ← ² fi od Получив данные, мы можем выполнить обновление. Reseed ( G , s ) fi Обновление, если таковое требовалось, выполнено. Теперь в дело мо- жет вступать генератор, состояние которого является частью R . return PseudoRandomData ( G , n ) Вначале функция RandomData сравнивает размер пула P 0 с парамет- ром MinPoolSize , чтобы узнать, нужно ли выполнять обновление. Мы мо- жем использовать оптимистическую оценку того, каким должен быть размер пула, чтобы он мог содержать 128 бит энтропии. Предполагая, что каждое событие содержит 8 бит энтропии и занимает 4 байта в пуле (как вы помните, это соответствует 2 байтам данных события), разумным значением параметра MinPoolSize можно считать 64 байт. Вообще-то точное значение этого па- раметра не играет особой роли, хотя использовать значение, меньшее 32 байт, все же не рекомендуется. Не следует выбирать и слишком большое значение, потому что тогда обновление будет отложено на слишком долгий срок даже при наличии очень хороших источников энтропии. Следующий шаг состоит в увеличении счетчика обновлений. В процессе инициализации счетчику ReseedCNT было присвоено значение 0, поэтому первое обновление будет пронумеровано как 1. Это автоматически гаранти- рует, что в первой операции обновления, как мы и планировали, будет участ- вовать только пул P 0 . Цикл for ... do выполняет конкатенацию хэш-кодов строк, содержа- щихся в пулах. Мы могли бы выполнять конкатенацию и самих строк пу- лов, однако в этом случае программе вместо простого хэширования содер- жимого каждого пула пришлось бы сохранять все строки полностью. Запись 2 i | ReseedCNT означает проверку делимости. Это выражение истинно, если 2 i является делителем значения ReseedCNT . Дотошные читатели, конечно же, обратят внимание на следующий факт: как только условие делимости не будет выполняться для какого-то i , оно не будет выполняться и для всех следующих i , поэтому все оставшиеся итерации цикла заведомо не нужны. Как видите, наша программа определенно требует оптимизации. 10.5. Аккумулятор 199 10.5.6 Добавление события Источники энтропии вызывают функцию AddRandomEvent , когда у них появляется очередное случайное событие. Обратите внимание, что каж- дый источник энтропии идентифицируется уникальным номером. Мы не бу- дем описывать, как система выделяет номера источников, так как это зависит от конкретной ситуации. функция AddRandomEvent вход: R Состояние ГПСЧ; изменяется этой функцией. s Номер источника в диапазоне 0 , . . . , 255 . i Номер пула в диапазоне 0 , . . . , 31 . Каждый источник должен распределять свои события между пулами по циклическому принципу. e Данные события. Строка байтов, длина которой находится в диапазоне 1 , . . . , 32 . Вначале выполним проверку параметров. assert 1 ≤ length ( e ) ≤ 32 ∧ 0 ≤ s ≤ 255 ∧ 0 ≤ i ≤ 31 Добавим данные в пул. P i ← P i k s k length ( e ) k e Напомним, что каждое событие кодируется с помощью 2 + length ( e ) байт, причем на каждую из величин s и length ( e ) отводится по одному байту. После этого полученная конкатенация присоединяется к содержимому пула. Об- ратите внимание, что в наших примерах мы просто присоединяем данные к содержимому пула и не выполняем никакого хэширования. Хэширование содержимого пула происходит только тогда, когда пользователь запрашивает случайные данные. В реальной системе хэширование данных должно выпол- няться “на лету” по мере их поступления. Это функционально эквивалентно нашему решению, к тому же проще в реализации, однако непосредственно описывать этот процесс в книге было бы гораздо сложнее. Мы ограничили длину данных события 32 байтами. События большей длины довольно бесполезны. Источники энтропии должны передавать акку- мулятору не все свои данные, а лишь те несколько байтов, которые и со- держат непредсказуемые случайные данные. Если же энтропия разбросана по большому объему данных, источник должен провести предварительное хэширование передаваемых данных. Функция AddRandomEvent должна выполняться как можно быстрее. Это особенно важно, поскольку многие ис- точники энтропии в силу своей специфики работают в режиме реального времени. Такие источники не могут тратить слишком много драгоценного времени на вызов функции AddRandomEvent . Даже если источник выдает небольшие события, он не должен ждать, пока функция AddRandomEvent |