В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел В контексте криптографической системы к генераторам псевдослучай- ных чисел предъявляются гораздо более строгие требования. Даже если зло- умышленник знает целый ряд случайных чисел, созданных генератором, у него не должно быть возможности предугадать какую-либо информацию об остальных случайных числах. Мы называем такой генератор псевдослучай- ных чисел криптографически сильным. Поскольку нам не нужны классиче- ские генераторы псевдослучайных чисел, в дальнейшем будем говорить толь- ко о криптографически сильных генераторах. Забудьте об обычных случайных функциях, имеющихся в ваших про- граммных библиотеках. Практически ни одна из них не подходит для приме- нения в криптографических системах. Большинство программных библиотек поставляются с генераторами псевдослучайных чисел, которые проваливают даже простые статистические тесты. Никогда не используйте библиотечные генераторы, если в документации к ним явно не сказано, что они являются криптографически сильными. 10.1.3 Истинно случайные числа и генераторы псевдослучайных чисел Истинно случайные числа будут использоваться нами только для того, чтобы получить начальное число, подающееся на вход генератора псевдослу- чайных чисел. После того как у нас появится начальное число, генератор сможет произвести на свет любое нужное количество случайных (а точнее, псевдослучайных) чисел. При необходимости мы можем прибавлять истин- но случайные числа к начальному числу генератора псевдослучайных чисел. Это гарантирует, что выходные данные последнего никогда не станут полно- стью предсказуемыми, даже если злоумышленник каким-либо образом узнает начальное число. Существует теоретическое мнение, что истинно случайные числа лучше, чем псевдослучайные. Для некоторых криптографических протоколов мож- но доказать, что при использовании истинно случайных чисел определенные типы атак становятся невозможными. Такой протокол называется безусловно защищенным (unconditionally secure) . Если же использовать генератор псев- дослучайных чисел, протокол будет безопасным только при условии, что зло- умышленник не сможет взломать этот генератор. Такой протокол называется защищенным по вычислениям (computationally secure) . Это различие, одна- ко, имеет значение только для закостенелых теоретиков. Все криптографиче- ские протоколы почти всегда основаны на вычислительных приближениях. Устранение такого приближения для одного конкретного типа атак не при- несет существенного улучшения. Более того, генерация истинно случайных чисел, необходимых для обеспечения безусловной защищенности, настолько 10.2. Модели атак на генератор псевдослучайных чисел 181 сложна, что попытка использовать такие числа может только ухудшить без- опасность системы. Любое слабое место генератора истинно случайных чисел моментально приведет к потере безопасности. С другой стороны, если исполь- зовать истинно случайные числа только для того, чтобы получить начальное число для генератора псевдослучайных чисел, можно позволить себе гораздо более придирчиво выбирать источники энтропии, что, безусловно, повышает наши шансы на создание действительно безопасной системы. 10.2 Модели атак на генератор псевдослучайных чисел Генераторы псевдослучайных чисел исследованы сравнительно мало. Са- ма задача генерации случайных (псевдослучайных) чисел на основе некоторо- го начального числа довольно проста. Проблема состоит в том, где взять слу- чайное начальное число и как сохранить его в секрете [47]. Наилучшее реше- ние этой проблемы, известное нам на данный момент, называется Yarrow [46]. Этот генератор псевдослучайных чисел, который пытается защитить систе- му от всех известных типов атак, был разработан нами несколько лет назад вместе с Джоном Келси (John Kelsey). В каждый момент времени у генератора псевдослучайных чисел есть внутреннее состояние. Запросы на получение случайных чисел обслужива- ются криптографическим алгоритмом, который генерирует псевдослучайные числа. Этот алгоритм также обновляет внутреннее состояние генератора, что- бы гарантировать, что в следующий раз генератор не возвратит те же самые случайные числа. Этот процесс не слишком сложен; с выполнением данной задачи вполне справится любая функция хэширования или блочный шифр. Существуют различные формы атак на генераторы псевдослучайных чи- сел. Прежде всего следует отметить прямую атаку, где злоумышленник пы- тается воссоздать внутреннее состояние генератора на основе его выходных данных. Это классический тип криптоатаки, которому довольно легко про- тивостоять, используя современные приемы криптографии. Ситуация усложняется, если злоумышленник на каком-то этапе сможет заполучить внутреннее состояние генератора. Пока что нас не интересует, как это произойдет. Возможно, утечка информации была вызвана каким-то изъ- яном в программном обеспечении, либо компьютер загружался в первый раз и еще не имел случайного начального числа, либо, скажем, злоумышленнику удалось считать файл начального числа с диска. Во всех этих случаях с гене- ратором начнут происходить довольно неприятные вещи. Если злоумышлен- нику удастся узнать внутреннее состояние классического генератора псевдо- случайных чисел, он сможет воспроизвести значения всех последующих вы- |