Случайные и псевдослучайные числа.

Чтобы ответить на этот вопрос, попробуем прояснить, что означает слово “случайный”. Чтобы сделать ин­туитивное представление более точным, можно поставить вопрос следую­щим образом: “Если известны текущие значения чисел, можно ли Предсказать последующие значения чисел?”. Криптографы предпочитают следующее определение: случайные значения представляют собой наборы чисел, которые прошли статистические тесты на случайность и являются неповторяющимися.

Рис. 24. Проверка чисел на случай­ность Здесь фрагмент 011 по­является слишком часто, по­этому тест не проходит.

Предположим, что вы выбрали несколько тысяч чисел и задали вопрос математику, являются ли эти числа случайными. Чтобы упростить задачу для компьютеров, пусть это будут двоичные числа, т.е. каждое число пред­ставляется в виде последовательности 1 и 0. Математик выдаст заключе­ние, основываясь на наборе тестов. При выполнении этих тестов (см. рис. 24) задаются такие вопросы: совпадает ли приблизительно количест­во 1 и 0? Не появляются ли некоторые фрагменты последовательностей 1 и 0 “слишком часто”? Есть ли некоторые фрагменты последовательностей 1 и 0, которые появляются “недостаточно часто”? Если числа выдерживают тесты, мы говорим, что числа, вероятно, являются случайными. Но мы не можем утверждать, что числа “определен­но” являются случайными.

Если у вас есть несколько тысяч чисел, можно проверить их на случай­ность. Но откуда взять эти несколько тысяч чисел? Одним из источников является генераторы случайных чисел (RNG — random number genera­tor), Такие устройства работают, получая числа из различного вида не­предсказуемых входных данных, например, измеряя параметры радиоак­тивного распада, изучая окружающие атмосферные условия либо вычис­ляя незначительные изменения электрического тока. Эти последователь­ности чисел проходят тесты на случайность.

Если вы запросите вторую последовательность чисел, то практически никогда не получите ту же самую последовательность снова. Дело в том, что выходной результат основывается на входных данных, которые всегда меняются. Числа являются неповторяющимися.

Итак, возвращаясь к нашему исходному определению, мы можем спро­сить: “Способен ли кто-либо предсказать, каким будет следующее число?” Для этого нужно иметь возможность предсказать малейшие вариации в процессе радиоактивного распада, в атмосферных условиях или в изме­нениях электрического тока. Предполагается, что этого никто не в состоя­нии сделать.

Компания Intel создала генератор случайных чисел, который использу­ет тепловой шум системы в качестве источника непредсказуемых входных значений. В настоящий момент это устройство еще не П9ставляется с каж­дым ПК на базе процессора Pentium, хотя это вполне возможно в будущем. Другие компании (такие как nCipher, Chrysalis и Rainbow) продают уст­ройства, известные как криптографические акселераторы. Эти устройства имеют в своем составе генераторы случай­ных чисел.

Как можно получить случайные числа, если нет аппаратного генератора случайных чисел? Тут помогут алгоритмы, которые называются генерато­рами псевдослучайных чисел (PRNG —pseudo-random number generators). Наряду с алгоритмами, которые преобразуют открытый текст в шифротекст, имеются алгоритмы, которые генерируют так называемые псевдо­случайные числа.

Если вы воспользуетесь одним из таких алгоритмов для генерирования нескольких тысяч чисел и примените статистические тесты, числа прой­дут тесты. Эти числа являются псевдослучайными, а не случайными, по­скольку они повторяющиеся. Если вы установите ту же программу-генера­тор псевдослучайных чисел на другой компьютер, то получите те же самые результаты. Если вы запустите программу двумя неделями позже, резуль­таты все равно будут такими же.

Это одна из причин, по которой мы говорим, что числа, прошедшие ста­тистические тесты на случайность, являются “возможно” случайными. Даже если числа выдержали тесты, можем ли мы знать, являются ли они повторяющимися? Тесты на случайность дают только часть ответа.

Если числа являются повторяющимися, чем же хороши генераторы псевдослучайных чисел? Дело в том, что можно изменять выходные ре­зультаты с помощью начального множества значений. Подобно тому, как генераторы случайных чисел используют входные данные (характеристи­ки радиоактивного распада, атмосферные условия, флуктуации электри­ческого тока), генераторы псевдослучайных чисел также используют вход­ные данные (начальное множество значений). Если вы измените входные данные, выходные данные также изменятся. При использовании генерато­ров случайных чисел входные данные постоянно изменяются сами по себе непредсказуемым образом. При использовании генераторов псевдослучай­ных чисел нужно обеспечить, чтобы входные данные изменялись каждый раз, когда нужно сформировать новую последовательность чисел.

Что представляет собой начальное множество? В реальном мире в каче­стве начального множества могут быть использованы различные характе­ристики: время суток, измеренное в миллисекундах, некоторые постоянно меняющиеся параметры состояния компьютера, ввод данных пользовате­лем и другие значения. Возможно, вы сталкивались с программой получе­ния начального множества значений на основе ввода пользователя. Прило­жение может предложить вам подвигать мышью. Через определенные ин­тервалы времени программа определяет, где на экране находится указатель мыши. Это значение представляется парой чисел: число пиксе­лов от верхнего и левого края экрана. Один отдельно взятый ввод не имеет какого-либо значения, но если объединить их вместе, то получится резуль­тат, который является непредсказуемым (см. рис. 25).

Рис. 25. Генератор случайных чисел (слева) ис­пользует непредска­зуемые данные и преобразует их в слу­чайные числа Гене­ратор псевдослучай­ных чисел (справа) берет информацию из начального мно­жества и преобразует ее в числа, которые выдерживают стати­стические тесты на случайность, но мо­гут повторяться

Зачем применять генератор псевдослучайных чисел и почему бы просто не использовать начальное множество чисел? На это есть две основные причины. Первая связана с производительностью. Получение начального множества требует сравнительно больших за­трат времени. Предположим, что нужно получить несколько тысяч битов случайных данных. Программе для получения начального множества мо­жет потребоваться несколько минут, чтобы получить необходимые числа. Чтобы сэкономить время, можно получить 160 или около этого битов начального множества (что займет совсем немного времени), передать их генератору псевдослучайных чисел и получить требуемые тысячи битов за несколько миллисекунд.

Второй причиной, по которой следует использовать генератор псевдо­случайных чисел, является энтропия — термин, который описывает меру хаоса. Чем выше энтропия, тем больше хаос. Иначе говоря, чем выше эн­тропия, тем более случайным является результат. Предположим, вьх хоти­те получить 128 битов данных с высокой энтропией. Начальное множество может это обеспечить, но для этого потребуется более 2400 битов. Напри­мер, время дня в миллисекундах представляется 64 битами. Но год, месяц, день и даже час и минуту можно легко угадать. Миллисекунды — несколь­ко битов в значении являются случайными. Аналогичная проблема имеет место и для других способов задания начального множества. Генератор псевдослучайных чисел принимает 2400.битов начального множества и сжимает их до 128 битов.

Почему бы тогда не взять начальное множество и не отбро­сить биты с низкой энтропией? В известном смысле именно это и делает ге­нератор псевдослучайных чисел. Вы можете сделать это сами, либо пору­чить генератору псевдослучайных чисел, что избавляет вас от лишней ра­боты.

Между прочим, большинство генераторов псевдослучайных чисел ис­пользуют вычисление дайджестов сообщений, чтобы сделать эту работу. Дайджесты сообщений (см. также параграф, посвященный электронной подписи) в криптографии являются своеобразными “смеси­телями”. Подобно тому, как смеситель принимает вполне распознаваемую пищу и превращает ее в случайным образом перемешанную массу, про­грамма, формирующая дайджест сообщения, принимает биты и байты и смешивает их в случайную “кашу”. Именно это нам и нужно от генератора псевдослучайных чисел.