Генерация случайных чисел - Random number generation

Игральные кости являются примером механического аппаратного генератора случайных чисел. Когда бросается кубический кубик, получается случайное число от 1 до 6.

Генерация случайных чисел - это процесс, с помощью которого, часто с помощью генератора случайных чисел ( ГСЧ ), генерируется последовательность чисел или символов , которую невозможно разумно предсказать лучше, чем на основе случайной случайности. Это означает, что конкретная последовательность результатов будет содержать некоторые закономерности, обнаруживаемые задним числом, но непредсказуемые для предвидения. Истинные генераторы случайных чисел могут быть аппаратными генераторами случайных чисел (HRNGS), которые генерируют случайные числа, при этом каждое поколение является функцией текущего значения атрибута физической среды, который постоянно меняется, что практически невозможно моделировать. Это будет контрастировать с так называемой «генерацией случайных чисел», выполняемой генераторами псевдослучайных чисел (ГПСЧ), которые генерируют числа, которые только выглядят случайными, но на самом деле предопределены - эти генерации можно воспроизвести, просто зная состояние ГПСЧ. .

Различные применения случайности привели к развитию нескольких различных методов генерации случайных данных. Некоторые из них существовали с древних времен, в том числе в рядах которой хорошо известны «классические» примеры, в том числе при прокатке кости , монеты листать , то перетасовки из игральных карт , использование тысячелистника стеблями (для гаданий ) в I Ching , а также бесчисленное множество других техник. Из-за механического характера этих методов генерация большого количества достаточно случайных чисел (что важно в статистике) требовала много работы и времени. Таким образом, результаты иногда собирались и распределялись в виде таблиц случайных чисел .

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

Практическое применение и использование

Генераторы случайных чисел применяются в азартных играх , статистической выборке , компьютерном моделировании , криптографии , полностью рандомизированном дизайне и других областях, где желательно получение непредсказуемого результата. Как правило, в приложениях, в которых непредсказуемость является главной особенностью, например, в приложениях безопасности, аппаратные генераторы обычно предпочтительнее псевдослучайных алгоритмов, где это возможно.

Генераторы псевдослучайных чисел очень полезны при разработке моделирования методом Монте-Карло , поскольку отладке способствует возможность снова запустить ту же последовательность случайных чисел, начиная с того же случайного начального числа . Они также используются в криптографии - пока семя является секретным. Отправитель и получатель могут автоматически сгенерировать один и тот же набор чисел для использования в качестве ключей.

Генерация псевдослучайных чисел - важная и распространенная задача в компьютерном программировании. В то время как криптография и определенные числовые алгоритмы требуют очень высокой степени очевидной случайности, многие другие операции требуют лишь умеренной непредсказуемости. Некоторые простые примеры могут представлять пользователю «случайную цитату дня» или определять, каким образом компьютерный злоумышленник может двигаться в компьютерной игре. Более слабые формы случайности используются в хеш-алгоритмах и при создании амортизированных алгоритмов поиска и сортировки .

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

«Истинные» против псевдослучайных чисел

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

Скорость, с которой энтропия может быть извлечена из естественных источников, зависит от измеряемых физических явлений. Таким образом, источники естественной «истинной» энтропии называются блокирующими  - они ограничены по скорости до тех пор, пока не будет собрано достаточно энтропии для удовлетворения спроса. В некоторых Unix-подобных системах, включая большинство дистрибутивов Linux , файл псевдоустройства / dev / random будет блокироваться до тех пор, пока из среды не будет собрана достаточная энтропия. Из-за такого поведения блокировки большие объемные операции чтения из / dev / random , такие как заполнение жесткого диска случайными битами, часто могут быть медленными в системах, использующих этот тип источника энтропии.

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

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

Хотя генератор псевдослучайных чисел, основанный исключительно на детерминированной логике, никогда не может рассматриваться как «истинный» источник случайных чисел в самом чистом смысле этого слова, на практике их обычно достаточно даже для требовательных приложений, критичных к безопасности. Действительно, тщательно разработанные и реализованные генераторы псевдослучайных чисел могут быть сертифицированы для критических с точки зрения безопасности криптографических целей, как в случае с алгоритмом тысячелистника и fortuna . Первый является основой / dev / random источника энтропии во FreeBSD , AIX , OS X , NetBSD и других. OpenBSD использует алгоритм псевдослучайных чисел, известный как arc4random .

Способы генерации

Физические методы

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

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

Появление широкополосных источников фотонной энтропии, таких как оптический хаос и усиленный шум спонтанного излучения , в значительной степени способствует развитию физического генератора случайных чисел. Среди них оптический хаос имеет высокий потенциал физического создания высокоскоростных случайных чисел из-за его высокой пропускной способности и большой амплитуды. В 2013 году был построен прототип высокоскоростного физического генератора случайных битов в реальном времени на основе хаотического лазера.

Были изобретены различные творческие способы сбора этой энтропийной информации. Один из способов - запустить хеш-функцию для кадра видеопотока из непредсказуемого источника. Лаваранд использовал эту технику с изображениями ряда лавовых ламп . HotBits измеряет радиоактивный распад с помощью трубок Гейгера – Мюллера , а Random.org использует вариации амплитуды атмосферного шума, записанные с помощью обычного радио.

Демонстрация простого генератора случайных чисел в зависимости от того, где и когда нажимается кнопка

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

Вычислительные методы

Большинство случайных чисел, генерируемых компьютером, используют ГПСЧ, которые представляют собой алгоритмы, которые могут автоматически создавать длинные серии чисел с хорошими случайными свойствами, но в конечном итоге последовательность повторяется (или использование памяти неограниченно растет). Эти случайные числа хороши во многих ситуациях, но не так случайны, как числа, генерируемые из электромагнитного атмосферного шума, используемого в качестве источника энтропии. Ряд значений, генерируемых такими алгоритмами, обычно определяется фиксированным числом, называемым начальным числом . Одним из наиболее распространенных ГПСЧ является линейный конгруэнтный генератор , который использует рекуррентность

для генерации чисел, где a , b и m - большие целые числа, и следующее в X в виде серии псевдослучайных чисел. Максимальное количество чисел, которое может дать формула, на единицу меньше модуля , m -1. Соотношение рекуррентности можно распространить на матрицы, чтобы иметь гораздо более длительные периоды и лучшие статистические свойства. Чтобы избежать определенных неслучайных свойств одного линейного конгруэнтного генератора, несколько таких генераторов случайных чисел с немного разными значениями коэффициента множителя a могут использоваться параллельно с «главным» генератором случайных чисел, который выбирает из нескольких разные генераторы.

Простой способ генерации случайных чисел с помощью ручки и бумаги - это так называемый метод среднего квадрата, предложенный Джоном фон Нейманом . Несмотря на то, что он прост в реализации, его продукция низкого качества. У него очень короткий период и серьезные недостатки, например, выходная последовательность почти всегда стремится к нулю. Недавнее нововведение - объединить средний квадрат с последовательностью Вейля . Этот метод обеспечивает получение высококачественной продукции в течение длительного периода времени.

Большинство языков программирования включают функции или библиотечные процедуры, которые предоставляют генераторы случайных чисел. Они часто предназначены для обеспечения случайный байт или слово, или с плавающей запятой число равномерно распределенных между 0 и 1.

Качество, т.е. случайность таких библиотечных функций, широко варьируется от полностью предсказуемого вывода до криптографически безопасного. Генератор случайных чисел по умолчанию во многих языках, в том числе Python, Ruby, R, IDL и PHP на основе Twister Mersenne алгоритма и не достаточно для целей криптографии, как это явно указано в документации языка. Такие библиотечные функции часто имеют плохие статистические свойства, и некоторые из них будут повторять шаблоны только после десятков тысяч испытаний. Они часто инициализируются с использованием часов реального времени компьютера в качестве начального числа, поскольку такие часы обычно измеряют в миллисекундах, что намного превышает точность человека . Эти функции могут обеспечить достаточную случайность для определенных задач (например, видеоигр), но не подходят там, где требуется высококачественная случайность, например, в приложениях криптографии, статистике или численном анализе.

Источники случайных чисел гораздо более высокого качества доступны в большинстве операционных систем; например, / dev / random в различных вариантах BSD, Linux, Mac OS X, IRIX и Solaris или CryptGenRandom для Microsoft Windows. Большинство языков программирования, включая упомянутые выше, предоставляют средства для доступа к этим источникам более высокого качества.

Людьми

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

Постобработка и статистические проверки

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

Сгенерированные случайные числа иногда подвергаются статистическим тестам перед использованием, чтобы убедиться, что основной источник все еще работает, а затем подвергаются последующей обработке для улучшения их статистических свойств. Примером может служить аппаратный генератор случайных чисел TRNG9803, который использует измерение энтропии в качестве аппаратного теста, а затем обрабатывает случайную последовательность с помощью потокового шифра сдвигового регистра. Как правило, сложно использовать статистические тесты для проверки сгенерированных случайных чисел. Ван и Никол предложили методику статистического тестирования, основанную на расстоянии, которая используется для выявления слабых сторон нескольких случайных генераторов. Ли и Ван предложили метод проверки случайных чисел на основе источников лазерной хаотической энтропии с использованием свойств броуновского движения.

Прочие соображения

Изменение распределения

Равномерные распределения

Большинство генераторов случайных чисел изначально работают с целыми числами или отдельными битами, поэтому требуется дополнительный шаг для достижения «канонического» равномерного распределения между 0 и 1. Реализация не так тривиальна, как деление целого числа на его максимально возможное значение. Конкретно:

  1. Целое число, используемое в преобразовании, должно обеспечивать достаточное количество бит для намеченной точности.
  2. Сама природа математики с плавающей запятой означает, что чем ближе число к нулю, тем выше точность. Эта дополнительная точность обычно не используется из-за большого количества требуемых битов.
  3. Ошибка округления при делении может исказить результат. В худшем случае предположительно исключенная граница может быть проведена с учетом ожиданий, основанных на математике с действительными числами.

Основной алгоритм, используемый OpenJDK, Rust и Numpy, описан в предложении для C ++ STL. Он не использует дополнительную точность и страдает смещением только в последнем бите из-за округления до четности. При переносе этого "канонического" равномерного распределения в другой диапазон возникают другие числовые соображения. Предлагаемый метод для языка программирования Swift утверждает, что везде используется полная точность.

Равномерно распределенные целые числа обычно используются в таких алгоритмах, как тасование Фишера-Йейтса . Опять же, простая реализация может вызвать смещение результата по модулю, поэтому необходимо использовать более сложные алгоритмы. Метод, который почти никогда не выполняет деление, был описан в 2018 году Дэниелом Лемиром, при этом текущее состояние дел - вдохновленный арифметическим кодированием «оптимальный алгоритм» 2021 года Стивеном Каноном из Apple Inc.

Большинство ГСЧ от 0 до 1 включают 0, но исключают 1, в то время как другие включают или исключают оба.

Другие дистрибутивы

Учитывая источник однородных случайных чисел, существует несколько методов для создания нового случайного источника, который соответствует функции плотности вероятности . Один метод, называемый методом инверсии , включает интегрирование до области, большей или равной случайному числу (которое должно быть сгенерировано между 0 и 1 для правильного распределения). Второй метод, называемый методом принятия-отклонения , включает выбор значений x и y и проверку того, больше ли функция x значения y. Если это так, значение x принимается. В противном случае значение x отклоняется, и алгоритм пытается снова.

В качестве примера для отбраковочной выборки, чтобы сгенерировать пару статистически независимых стандартных нормально распределенных случайных чисел ( x , y ), можно сначала сгенерировать полярные координаты ( r , θ ), где r 2 ~ χ 2 2 и θ ~ UNIFORM ( 0,2π) (см. Преобразование Бокса – Маллера ).

Отбеливание

Выходы нескольких независимых RNG могут быть объединены (например, с помощью операции побитового XOR ), чтобы обеспечить объединенный RNG, по крайней мере, такой же хороший, как и лучший используемый RNG. Это называется программным отбеливанием .

Вычислительные и аппаратные генераторы случайных чисел иногда объединяют, чтобы отразить преимущества обоих типов. Вычислительные генераторы случайных чисел обычно могут генерировать псевдослучайные числа намного быстрее, чем физические генераторы, в то время как физические генераторы могут генерировать «истинную случайность».

Последовательности с низким расхождением в качестве альтернативы

Некоторые вычисления с использованием генератора случайных чисел можно резюмировать как вычисление общего или среднего значения, например, вычисление интегралов методом Монте-Карло . Для таких проблем можно найти более точное решение, используя так называемые последовательности с низким расхождением , также называемые квазислучайными числами. Такие последовательности имеют определенный узор, который качественно равномерно заполняет пробелы; действительно случайная последовательность может оставлять и обычно оставляет большие промежутки.

Мероприятия и демонстрации

Следующие сайты предоставляют образцы случайных чисел:

  • В SoCR страница ресурса содержит ряд практических на интерактивных мероприятиях и демонстрациях генерации случайных чисел с использованием Java - апплетов.
  • Группа квантовой оптики в ANU генерирует случайные числа, полученные из квантового вакуума. Примеры случайных чисел доступны на их странице исследования генератора квантовых случайных чисел.
  • Random.org предоставляет случайные числа, которые получены из случайности атмосферного шума.
  • Служба квантового генератора случайных битов в Институте Руджера Бошковича извлекает случайность из квантового процесса фотонной эмиссии в полупроводниках. Они предоставляют множество способов получения данных, включая библиотеки для нескольких языков программирования.
  • Группа Технологического университета Тайюань генерирует случайные числа, полученные с помощью хаотического лазера. Образцы случайных чисел доступны в их службе генератора физических случайных чисел.

Бэкдоры

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

Сообщается, что АНБ вставило бэкдор в сертифицированный NIST криптографически безопасный генератор псевдослучайных чисел Dual EC DRBG . Если, например, с помощью этого генератора случайных чисел создается SSL-соединение, то, по словам Мэтью Грина, это позволит NSA определять состояние генератора случайных чисел и, таким образом, в конечном итоге иметь возможность читать все данные, отправленные через SSL-соединение. Несмотря на то, что было очевидно, что Dual_EC_DRBG был очень плохим генератором псевдослучайных чисел, возможно, задолго до того, как бэкдор АНБ был подтвержден в 2013 году, он широко использовался на практике до 2013 года, например, известной компанией по обеспечению безопасности RSA Security . Впоследствии были обвинения в том, что RSA Security сознательно вставила бэкдор АНБ в свои продукты, возможно, в рамках программы Bullrun . RSA отрицает намеренное использование бэкдора в своих продуктах.

Также было высказано предположение, что аппаратные ГСЧ могут быть тайно модифицированы, чтобы иметь меньшую энтропию, чем заявлено, что сделает шифрование с использованием аппаратного ГСЧ уязвимым для атак. Один такой метод, который был опубликован, работает путем изменения легирующей маски микросхемы, которую невозможно обнаружить с помощью оптического обратного проектирования. Например, для генерации случайных чисел в Linux считается неприемлемым использовать аппаратный ГСЧ Intel RDRAND без смешивания вывода RDRAND с другими источниками энтропии, чтобы противодействовать любым бэкдорам в аппаратном ГСЧ, особенно после раскрытия программы NSA Bullrun. .

В 2010 году розыгрыш лотереи в США был сфальсифицирован директором по информационной безопасности Межгосударственной лотерейной ассоциации (MUSL), который тайно установил вредоносную программу- бэкдор на защищенный ГСЧ-компьютер MUSL во время планового обслуживания. Во время хакерских атак этот человек выиграл общую сумму в 16 500 000 долларов, правильно угадав числа несколько раз в год.

В начале 2017 года VUSec признала, что рандомизация адресного пространства (ASLR), защита от rowhammer и связанных атак на физическое оборудование микросхем памяти неадекватна. Алгоритм случайных чисел, если он основан на сдвиговом регистре, реализованном на оборудовании, предсказуем при достаточно больших значениях p и может быть реконструирован с достаточной вычислительной мощностью ( взлом грубой силы ). Это также косвенно означает, что вредоносные программы, использующие этот метод, могут работать как на графических процессорах, так и на процессорах, если они закодированы для этого, даже используя графический процессор для нарушения ASLR на самом процессоре.

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки