Случайные числа и методы их генерации играют важную роль во многих областях науки и техники, в том числе в методах Монте-Карло и криптографии. Из-за разных сценариев применения “случайных” чисел к ним и их генераторам возникают различные требования. Для чисел это могут быть: качество многомерного равнораспределения, непредсказуемость, независимость и равнораспределение (IID) и отсутствие смещения (bias). Для генераторов случайных чисел (ГСЧ) такие требования могут включать скорость генерации, период повторения, физические размеры устройств и совместимость с технологическими процессами. Эти разные, часто конфликтующие, требования делают процесс разработки и тестирования генераторов, а также производимых ими чисел, нетривиальным. Особенно в автоматических режимах и на физических реализациях, находящихся под воздействием внешних пассивных и активных факторов.
Цель данного обзора - представить основные понятия и знания, которые требуются для начала работы со “случайными” числами и их генераторами, ввести нужную систематику области и предоставить ссылки на полезные теоретические и практические ресурсы, без погружения в глубокую теорию.
Случайность и неопределенность – понятия, тесно связанные с теорией вероятностей. В разных контекстах “случайность” может означать либо реально случайные события, либо определять нашу степень неосведомленности. Тем самым случайность может быть как объективным, так и субъективным феноменом. Оба сценария важны в процессе генерации случайных чисел.
Частый пример первого – подбрасывание монетки. С точки зрения классической механики процесс абсолютно детерминированный, описанный уравнениями Ньютона, но зависящий от неизвестных параметров, например формы и массы. Случайностью здесь мы описываем уровень незнания о параметрах и, соответственно, результате эксперимента. Такая неопределенность называется эпистемической. Эпистемическую неопределенность возможно уменьшить при проведении дополнительных измерений и вычислений, например, при применении высокоскоростных камер для снимка динамики броска, позволяющего более точно предсказать результат эксперимента из-за предсказуемости самого процесса.
Второй тип – так называемая алеаторическая неопределенность. Это неопределенность, связанная со случайностью самого процесса, к примеру путь одного фотона при прохождении через оптический делитель пучка. Здесь случайность свойственна самому физическому процессу, который в рамках квантовой механики ограничивает наши возможности по улучшению прогнозирования эксперимента, даже при увеличении точности измерений и увеличении вычислительных мощностей.
Для построения ГСЧ можно использовать оба типа неопределенности или комбинировать их. Часто при классификации ГСЧ (рис. 1) используются другие признаки и свойства ГСЧ, а тип неопределенности становится важным только при сравнении физических ГСЧ основанных на классических и квантовых принципах.
Рис. 1 Типы генераторов случайных чисел
Первый тип генераторов – “детерминированные” ГСЧ (ДГЧС), работающие по заданному алгоритму по принципу эпистемической неопределенности. Сам по себе генератор не имеет случайности и неопределенности – она закладывается через “инициализирующее значение” (seed) при запуске. Такие генераторы часто используются для методов Mонте-Kарло, где важна равномерность распределения и скорость генерации. В криптографических версиях ДГСЧ добавляются требования к непредсказуемости вывода генератора при наблюдении последовательности на выходе. Это ограничивает максимальное количество информации о состоянии генератора и его начальном значении, содержащейся в его выводе. Здесь случайность приравнивается к непредсказуемости. A непредсказуемость в свою очередь разбивается на два типа: прямая секретность (forward secrecy) - невозможность предсказать будущие выводы, и обратная секретность (backward secrecy) – невозможность предсказать прошлые значения, и тем самым, инициализирующее значение.
Второй тип – это “недетерминированный” генератор случайных чисел (НГСЧ) или генератор “истинно” случайных чисел, который включает в себя два подкласса: «физические» и «нефизические» генераторы.
Физические ГСЧ (ФГСЧ) получают случайность, измеряя физический процесс, и могут использоваться как трудно предсказуемые эпистемические, так и алеаторические физические системы. Ключевое свойство ФГСЧ состоит в том, что они предоставляют возможность контролировать параметры физического процесса и делать оценку качества генерируемой «случайности» ФГЧС.
Первый подтип ФГЧС часто называют «шумовики». В их основе стоят классические стохастические процессы из окружающей среды, такие как шумы в диодах Зенера [1], или фазовое дрожание в работе кольцевых генераторов [2, 3, 4]. Такие источники случайности могут иметь преимущество в малых габаритах и возможности их реализации на интегральных микросхемах, процессорах [5] или ПЛИС [6]. Однако из-за использования ими эпистемической неопределенности, характеристики таких ФГСЧ могут зависеть от внешних факторов, не находящихся под контролем разработчика, таких как дисперсия параметров физических реализаций и внешнее воздействие на них [7].
Второй подтип ФГЧС основан на алеаторической неопределенности, что часто приравнивается к использованию квантовых процессов, тем самым получая название «квантовые» ГСЧ [8]. Это играет важнейшую роль, так как позволяет в большей мере разделить реализацию и вариацию в параметрах измеряемой системы от свойств генерируемых последовательностей [3,9], подавляя неидеальные эффекты в процессе генерации случайных чисел. Часто такие ФГСЧ основаны на оптических системах [10,11,12] из-за удобства оптических технологий с точки зрения подавления внешних эффектов, детектирования и масштабируемости.
Компоненты случайного генератора
Оба типа недетерминированных генераторов имеют общую структуру (рис. 2). Различие этих двух типов состоит в “источнике энтропии”, который оцифровывается и обрабатывается генератором, тем самым получая случайную последовательность на выводе. От качества энтропии источника зависит качество получаемых “случайных чисел”, а характеризация энтропии источника - одна из важнейших частей валидации и тестирования датчика. В противном случае, при выходе источника энтропии из строя, «случайный генератор» начинает генерировать предсказуемую последовательность.
Рис 2. Компоненты ГЧС
Энтропия – это мера неопределенности случайной величины. Если ГСЧ создает последовательности символов из конечного алфавита (при оцифровке аналогового сигнала или с использованием НФГСЧ), то к нему применимо определение энтропии для дискретных величин:
Энтропия Шеннона (Shannon Entropy)
Для дискретной случайной переменной $X$ с вероятностью $P(X=x_i)=p_i$ энтропия Шеннона $H(X)$ определяется как:
$$ H(X) = \sum_i p_i \cdot \log_2 \frac{1}{p_i} = - \sum_i p_i \cdot \log_2 p_i \tag{1} $$
Энтропия Шеннона оценивает среднюю непредсказуемость случайной величины. Минимальная энтропия дает более консервативную оценку, учитывая только самое вероятное значение.
Минимальная энтропия (мин-энтропия, min-entropy)
Для дискретной случайной переменной $X$ с вероятностью $P(X=x_i)=p_i$ и максимальным значением вероятности $p_{\max}=\max(p_1,p_2,p_3,\ldots)$ минимальная энтропия $H_{\min}$ определена через логарифм максимальной вероятности:
$$ H_{\min}(X) = \log_2 \frac{1}{p_{\max}} = \log_2 p_{\max} \tag{2} $$
Мин-энтропия — это нижняя граница для энтропии Шеннона, а значит, она даёт более строгую оценку информации в случайной величине. Из-за этого свойства её чаще применяют при анализе ГСЧ.
$$ H_{\min}(X) \le H(X) \tag{3} $$
При работе генератора мы рассматриваем выходные биты как реализацию случайной величины. При использовании идеального источника, $n$ сгенерированных бит (независимых и равновероятных, с $p=0.5$) дают $n$ бит энтропии. Однако реальные источники энтропии неидеальны: у них есть смещения $(p \ne 0.5)$ и корреляции между битами. Из-за этого распределение $n$-битной последовательности отклоняется от равномерного (каждый вариант имеет вероятность $2^{-n}$), и фактическая энтропия становится меньше $n$. Определение характеристик источника, количества генерируемой энтропии и влияния параметров источника на производимую энтропию происходит в процессе валидации и тестирования, примеры которого описаны в NIST SP800-90B [13] и AIS 20/31 [14, 15]. Основной целью в таком процессе является определение наименьшего значения энтропии, производимой источником на один бит генерируемой последовательности в нормальных условиях работы генератора.
Оцифровка и пост-обработка
Для получения потока дискретных символов из физического датчика нужно сначала провести оцифровку сигнала, переводя непрерывную случайную величину в дискретную. Для разных типов физических систем существуют разные методы оцифровки, размер и сложность которых тесно связаны с типом измерения и его параметрами, включая скорость, точность и объем генерируемых данных. Математически, процесс представляет собой создание из непрерывного случайного процесса - дискретного, где процесс измерения определяет используемые трансформации. Тем самым для правильной оценки свойств источника энтропии важно учитывать не только саму физическую систему, но и процесс ее измерения. Вывод такого процесса, назовем – «сырыми» случайными числами (raw random numbers), которые могут, из-за корреляций и смещений, содержать низкое количество энтропии на один бит последовательности. Такой источник называется «слабым».
Для создания высококачественных случайных чисел из слабого источника, нужно повысить количество энтропии на один бит. Это достигается с использованием процедуры постобработки, часто называемой «экстрактом» [7, 16, 17]. Цель сконцентрировать энтропию из большого количества низко энтропийных битов в более малое количество высокоэнтропийных, минимизируя потери энтропии в процессе.
Примеры практических реализаций экстракторов даны в стандартах NIST SP800-90B [13], где приведен список рекомендаций по так называемым “vetted conditioning components” – экстракторам, использующим криптографические хэш функции и алгоритмы. Такие преобразования делают сложным обратную задачу получение оценки состояния источника энтропии, дают равномерное распределение в пространстве вывода, а также позволяют предотвратить манипуляцию вывода экстрактора через влияние на сам источник энтропии [2], используя лавинный эффект хэш функции. Экстракторы на основе resilient functions [18, 19] также могут обладать стойкостью к внешнему воздействию на источник
Также существует подход к созданию экстракторов на основе ДГСЧ и конструкции Тревисана [20, 21], где малое количество высококачественных битов используется для инициализации ДГСЧ, которая далее извлекает энтропию из низкоэнтропийного источника. Обобщение этой идеи позволяет создавать экстракторы, способные комбинировать несколько независимых низко-энтропийных источников в один высокоэнтропийный [13, 14]. Это имеет применения как в классических, так и в квантовых [22, 23] системах, а также для процесса “privacy amplification” [24] квантовых ключей при доступности некой информации о них внешнему наблюдателю.
Внутренние и внешние случайные числа
После пост-обработки биты с повышенной энтропией, в зависимости от типа генератора и его категории, могут стать внутренними случайными числами (рис. 2). Это финальные сгенерированные значения, подготовленные для вывода, но остающиеся в пределах ГСЧ. После вывода чисел за предел ГЧС (с возможной промежуточной трансформацией), получаем внешние случайные числа, внутренние случайные числа, или их трансформацию, выведенные за пределы защищенного периметра ГСЧ.
Если генератор не физический или смешивает несколько источников энтропии, то возможен вариант добавления обработанных битов в промежуточную структуру данных - пул энтропии (entropy pool), из которой уже создаются внутренние биты через процесс хэширования, либо через инициализацию ДГСЧ [25, 26]. Одна из систематик по возможным структурам ГЧС, их компонентам и категориям дана в немецком стандарте AIS 20/31 [27,15].
Верификация и тестирование генераторов
Учитывая ключевую роль генератора в конечных системах, проверка его корректности, тестирование в реальных условиях, надежность и непредсказуемость формируемой последовательности являются важнейшими факторами при создании и внедрении генераторов.
Одним из самых известных, но не достаточным, из подходов к тестированию генераторов являются батареи тестов на случайность. Наиболее известный набор тестов - NIST STS [28]. Эти тесты проверяют случайность чисел с помощью статистических критериев: они вычисляют pvalue, которое показывает вероятность получить столь же или более крайнее значение тестовой статистики при условии, что числа действительно случайны и равномерно распределены. Другие часто используемые тесты это Diehard [29], TestU01 [30], Dieharder [31] последний из которых доступен на системах Linux через стандартные системы управления пакетами, к примеру apt. Важно учесть, что статистические тесты не гарантируют случайность. Они могут быть пройдены уязвимым генератором [32] и, с определенной вероятностью, могут отбраковать идеальный генератор. Поэтому тестирование необходимо, но недостаточно для проверки и валидации ГСЧ.
Для физических генераторов частым требованием является обоснование принципа действия источника энтропии - самой физической системы, как до оцифровки, так и после. Такой процесс часто формализуется через определения “стохастической модели” для случайных чисел [27] с целью вычисления теоретического нижнего лимита на энтропию/минэнтропию. Часто из-за сложности физической системы генерирующей энтропию, создание полного описания статистической модели процесса невозможно, и допускается, что стохастическая модель описывает ключевые свойства системы с учетом возможной вариации в параметрах. Тем самым цель - определить класс вероятностных распределений, в которые будут входить истинное распределение случайных чисел в течение работы генератора, с учетом вариации в параметрах компонентов и при их старении. В лучшем случае, стохастическая модель должна описать “внутренние” случайные числа, но такое требование может быть слишком трудным к реализации, если процесс пост-обработки имеет сложные трансформации, например, функцию хэширования. Из-за этого, например в AIS 20/31 [27], требование для стохастической модели применяется только для сырых чисел, из которых формируется первичная оценка содержания энтропии.
В [13] оценка производимой энтропии в сырых числах зависит от типа источника с разделением на один из двух треков: iid track и non-iid track. А дальнейшее вычисление энтропии внутренних чисел зависит от типа постобработки и ее параметров - ширины вывода и минимальной внутренней ширины обрабатывающего блока
Тестирование в процессе работы
Важную роль также играет тестирование генератора в процессе его работы, так как здесь могут происходить ошибки приводящие к частичной деградации или полному выходу из строя источника. Такие тесты можно разбить на три основных класса – стартовые, непрерывные и самотестирование. Стартовые тесты запускаются при начале работы или перезапуске генератора, их цель – детектировать «период разогрева»
Важную роль также играет тестирование генератора в процессе его работы, так как здесь могут происходить ошибки, приводящие к частичной деградации или полному выходу из строя источника. Такие тесты можно разбить на три основных класса — стартовые, непрерывные и самотестирование. Стартовые тесты запускаются при начале работы или перезапуске генератора, их цель — детектировать «период разогрева» источника энтропии, не допуская выдачи случайных чисел перед тем, как источник будет готов к работе. Непрерывные тесты работают параллельно с процессом генерации. Их цель состоит в детектировании ошибок в производимых последовательностях чисел с малой вероятностью ложноположительных случаев (оценивается как $1$ на $2^{20}$ в [13]) и детектировании деградации качества производимой энтропии. Одним из таких тестов является тест на полный отказ (total failure test/TOT), определяющий критические отказы в источнике энтропии. Тесты самотестирования запускаются по внешнему запросу. Они также могут быть интегрированы в процесс запуска как часть стартовых тестов либо вызываться отдельно, возможно с другими параметрами.
В статье рассмотрены основные типы генераторов случайных чисел и их ключевые компоненты. Особое внимание уделено важности верификации генераторов на основе стохастических моделей и использования оценки минэнтропии производимых чисел