dxdt.ru: занимательный интернет-журнал

Всё-таки довольно забавно начинает звучать текст, если автор называет псевдослучайные числа – случайными. Вот в “Компьютерре” статья, где как раз речь о псевдослучайных числах, но автор предпочитает уверенно называть их “случайные”. В статье пишут, например:

”
Скажем, генератор случайных чисел, встроенный в ОС Windows, автоматически используется во всех приложениях системы, связанных с защитой информации. И при этом конкретные алгоритмы генерации, используемые в Microsoft для данной цели, никогда открыто не публиковались[…]

…аналитики нашли уязвимость, позволяющую организовать атаку, эффективно отыскивающую предыдущие состояния генератора, а значит, и вычислять будущие числа на выходе.”

Вот такие случайные числа, генерируемые, тем не менее, “алгоритмом” и, тем не менее, вычисляемые на будущее аналитиками. По-моему, кошмар.

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

Но при этом псевдослучайные числа очевидно не являются случайными, так как они зависят друг от друга, а впечатление случайности (ложное) возникает лишь от того, что аналитику не “виден” механизм генерации. Тем не менее, криптоанализ псевдослучайных последовательностей может принести полезные результаты, а в самих алгоритмах генерации известны уязвимости.

Таким образом, если криптосистема существенным образом использует тот или иной алгоритм генерации псевдослучайных чисел, то стойкость этой криптосистемы оказывается завязана на стойкость “псевдослучайного” алгоритма. Например, сам шифр может быть очень стойким, но если для генерации ключей шифра использован нестойкий алгоритм, то стойкость самого шифра, понятно, уже не имеет значения.

Эта особенность, конечно, давно известна, поэтому для получения более стойких “случайных” последовательностей используются другие методы. На практике они привязаны к некоторым физическим процессам, происходящим в окружающем мире. Например, в качестве источника для получения последовательности чисел используется тепловой шум в электронных устройствах. Этот тепловой шум, несомненно, более близок к случайному процессу. Тем не менее, только близок, а в строгом смысле этот процесс тоже не является случайным.

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

С генерацией же действительно случайных чисел, совершенно непредсказуемых (по современным представлениям), имеются большие проблемы. Однако и такие генераторы сейчас существуют, они основаны на квантовых физических процессах. Например, генератор действительно случайных чисел может быть построен на основе регистрации радиоактивного распада – этот процесс совершенно непредсказуем.

Ссылка по теме: моя колонка про случайные числа на “Информационном буме”.

Адрес записки: https://dxdt.ru/2007/12/09/891/