На практике для выбора равномерно случайного $x\in\mathbb{Z}^*_q$, мы сводим эту задачу к проблеме выбора равномерно случайных и независимых битов. В современной компьютерной системе будет некоторая служба операционной системы, предоставляющая такие биты, например. /dev/urandom во многих производных Unix (мы вернемся к проблеме получения таких битов во втором разделе).
Самый простой способ выбрать равномерно случайное $x\in\mathbb{Z}^*_q$, то есть целое число в $[0,q)$, иногда называемая выборкой отбраковки, выглядит следующим образом:
- Предварительно выполняется однократно независимо от того, сколько $х$ мы хотим сгенерировать: как (детерминированную) функцию $q$, выберите несколько $к$ с $2^k\geq$, например $к$ немного больше количества битов в двоичном выражении $q$.
- Рисовать $к$ равномерно случайные и независимые биты $b_i$, за $0\le i<k$
- Соберите $к$ биты в целое число $y=\сумма b_i\,2^i$
- Если $y<(2^k\bmod q)$, продолжайте в 2.
- Вычислить и вывести $х=у\bmod q$.
Вероятность того, что $х$ любое конкретное целое число в $[0,q)$ точно $1/к$ по гипотезе биты $b_i$ равномерно случайны и независимы.
Распространенные вариации:
- Производство бит $b_i$ сгруппированы в компьютерное слово и/или $к$ вынужден быть кратным размеру некоторых слов.
- Большой порядок байтов в 2: $y=\сумма b_i\,2^{k-i-1}$; это также позволяет $у$ строиться по мере того, как мы рисуем $b_i$ как $y_0=0$, $y_{i+1}=y_i+y_i+b_i$ за $0\le i<k$, $у=у_к$.
- Различные условия испытаний на 4, например. $y\ge2^k-(2^k\bmod q)$.
Мы также можем удалить шаг 4 (в этом случае метод больше не является выборкой отбраковки). Пока не $q$ является степенью двойки, это оставляет целые числа в $[0,2^k\bmod q)$ более вероятно, чем в $[(2^k\bmod q), q)$, с вероятностью $\lceil 2^k/q\rceil/2^k$ скорее, чем $\lэтаж 2^k/q\rэтаж/2^k$. Но если $к$ соответственно больше, чем количество битов в $q$ (сказать, $k\>\lceil\log_2 q\rceil+64$ ), или/и если $\мин(2^k\bmod q,-2^k\bmod q)/q$ меньше некоторого подходящего предела (например, $2^{-128}$ ), то это смещение экспериментально не обнаруживается.
(Есть лучшие характеристики того, когда мы можем удалить шаг 4, и более сложные методы, чтобы минимизировать количество $b_i$ генерируется при создании многих $х$, но их использование редко).
Мы вернулись к проблеме выбора равномерно случайных и независимых битов или, возможно, компьютерных слов, состоящих из таких битов.
Все рекомендуемые методы используют один и тот же общий принцип: источник (и) несовершенной случайности подвергается постобработке в биты, которые, как мы надеемся, неотличимы (в действительности, в том числе для произвольно сильных противников; или в качестве запасного варианта, вычислимо) от желаемых равномерно случайных и независимых битов.
Примеры источников:
- Входы, включая нажатия клавиш, положение мыши, микрофон, вход камеры.
- Время, когда происходят нажатия клавиш, изменяется положение мыши, блоки диска или пакеты Ethernet/Wifi/Bluetooth/USB достигают материнской платы, измеряется, например. в тактах с момента запуска компьютера
- Специальное устройство. Один метод сравнивает мгновенное напряжение на Стабилитрон к его среднему значению и сэмплирует результат через равные промежутки времени. Другой сэмплирует предположительно хаотический осциллятор, используя другой, надеюсь, независимый.
Много усилий должно быть направлено на наблюдение за источником(ами), чтобы убедиться, что он/они работают должным образом (или, если мы объединим несколько, для оценки минимального энтропия мы можем быть уверены, что они коллективно добьются результата).
Одним из наиболее простых эффективных средств постобработки является хеширование: некоторое количество битов из источника(ов) хешируется, а результат (или его часть) формирует условный вывод. Это безопасно для хэша, вычислительно неотличимого от случайного оракула (для используемой входной длины), и достаточно большого (мин-) энтропия хеш-ввода.
Если нам нужно много случайных битов, мы можем сделать их по низкой цене, задав Криптографически безопасный генератор псевдослучайных чисел со случайностью, полученной как в последнем пункте. Однако, если состояние CSPRNG скомпрометировано (например, сторонними каналами), весь его вывод скомпрометирован. По этой причине существуют более сложные методы получения высоконадежных случайных битов с высокой скоростью таким образом, чтобы они хорошо восстанавливались после компрометации их внутреннего состояния.
Дополнение: на современных процессорах часто есть источник на кристалле (который когда-то был в чипсете). Часто его вывод недоступен в хорошо документированном виде. Оправдания для этого заключаются в том, что люди будут использовать его напрямую или / и хвастаться обнаружением в нем некоторой предвзятости, даже если это ожидается. Предполагается, что программист использует загадочно обусловленный вывод с помощью некоторой инструкции (например, РДРАНД). То, как отслеживается работоспособность источника, часто остается плохо документированным и/или не поддерживается программным обеспечением/ОС. Другие возможные проблемы с ГСЧ на базе ЦП включают плохую защиту конфиденциальности их вывода, см., например. это. Сделайте (каламбур) свои собственные выводы о том, следует ли им доверять как единственному источнику или случайности в криптографии.
