Войти
Игральные кости являются примером механического аппаратного генератора случайных чисел. Когда бросается кубическая игральная кость, получается случайное число от 1 до 6. Генерация случайных чисел (RNG ) - это процесс, который с помощью устройства генерирует последовательность числа или символы, которые нельзя разумно предсказать лучше, чем с помощью случайной вероятности. Генераторы случайных чисел могут быть истинными аппаратными генераторами случайных чисел (HRNGS), которые генерируют случайные числа в зависимости от текущего значения некоторого атрибута физической среды, который постоянно изменяется таким образом, что практически невозможно моделировать, или генераторы псевдослучайных чисел (PRNGS), которые генерируют числа, которые выглядят случайными, но на самом деле являются детерминированными, и могут быть воспроизведены, если состояние PRNG известно.
Различные приложения случайности привели к развитию нескольких различных методов генерации случайных данных, некоторые из которых существуют с древних времен, среди которых хорошо развиты -известные "классические" примеры, в том числе бросание кубиков, подбрасывание монеты, перетасовка из игральных карт, использование стебли тысячелистника (для гадания ) в И Цзин, а также бесчисленное множество других техник. Из-за механической природы этих методов генерация большого количества достаточно случайных чисел (что важно в статистике) требовала много работы и времени. Таким образом, результаты иногда собираются и распределяются в виде таблиц случайных чисел.
Существует несколько вычислительных методов для генерации псевдослучайных чисел. Все они не достигают цели истинной случайности, хотя они могут с переменным успехом соответствовать некоторым из статистических тестов на случайность, предназначенных для измерения того, насколько непредсказуемы их результаты (то есть, в какой степени их шаблоны различимо). Обычно это делает их непригодными для таких приложений, как криптография. Однако также существуют тщательно разработанные криптографически безопасные генераторы псевдослучайных чисел (CSPRNGS) со специальными функциями, специально разработанными для использования в криптографии.
Генераторы случайных чисел применяются в азартных играх, статистическая выборка, компьютерное моделирование, криптография, полностью рандомизированный дизайн и другие области, в которых желательно получение непредсказуемых результатов. Как правило, в приложениях, в которых непредсказуемость является важнейшей особенностью, например, в приложениях безопасности, аппаратные генераторы обычно предпочтительнее псевдослучайных алгоритмов, где это возможно.
Генераторы случайных чисел очень полезны при разработке моделирования методом Монте-Карло, поскольку отладка облегчается возможностью снова запустить ту же последовательность случайных чисел, запустив из того же случайного числа. Они также используются в криптографии - пока семя является секретным. Отправитель и получатель могут автоматически сгенерировать один и тот же набор чисел для использования в качестве ключей.
Генерация псевдослучайных чисел - важная и распространенная задача в компьютерном программировании. В то время как криптография и некоторые численные алгоритмы требуют очень высокой степени очевидной случайности, многие другие операции требуют лишь умеренной непредсказуемости. Некоторые простые примеры могут представлять пользователю «случайную цитату дня» или определять, каким образом компьютерный противник может двигаться в компьютерной игре. Более слабые формы случайности используются в алгоритмах хеширования и при создании амортизированных поисковых и алгоритмов сортировки.
Некоторые приложения, которые на первый взгляд кажутся подходящие для рандомизации на самом деле не так уж и просты. Например, система, которая «случайным образом» выбирает музыкальные треки для системы фоновой музыки, должна отображаться только случайным образом и может даже иметь способы управления выбором музыки: истинная случайная система не будет иметь ограничений на то, чтобы один и тот же элемент появлялся двумя или тремя раз подряд.
Для генерации случайных чисел используются два основных метода. Первый метод измеряет некоторые физические явления, которые, как ожидается, будут случайными, а затем компенсирует возможные смещения в процессе измерения. Примеры источников включают измерение атмосферного шума, теплового шума и других внешних электромагнитных и квантовых явлений. Например, космическое фоновое излучение или радиоактивный распад, измеренные в коротких временных масштабах, представляют источники естественной энтропии.
. Скорость, с которой энтропия может быть извлечена из естественных источников, зависит от лежащих в основе измеряемых физических явлений. Таким образом, источники естественной «истинной» энтропии называются блокирующими - они ограничены по скорости до тех пор, пока не будет собрано достаточно энтропии для удовлетворения спроса. В некоторых Unix-подобных системах, включая большинство дистрибутивов Linux, файл псевдоустройства / dev / random будет блокироваться до тех пор, пока из среды не будет собрана достаточная энтропия. Из-за такого поведения блокировки большие объемные операции чтения из / dev / random, такие как заполнение жесткого диска случайными битами, часто могут быть медленными в системах, которые используют это тип источника энтропии.
Второй метод использует вычислительные алгоритмы , которые могут создавать длинные последовательности явно случайных результатов, которые на самом деле полностью определяются более коротким начальным значением, известным как начальное значение или ключ .. В результате вся кажущаяся случайной последовательность может быть воспроизведена, если известно начальное значение. Этот тип генератора случайных чисел часто называют генератором псевдослучайных чисел . Этот тип генератора обычно не полагается на источники естественной энтропии, хотя он может периодически пополняться естественными источниками. Этот тип генератора является неблокирующим, поэтому скорость его работы не ограничивается внешним событием, что делает возможными большие объемные чтения.
Некоторые системы используют гибридный подход, предоставляя случайность, полученную из естественных источников, когда она доступна, и возвращаясь к периодически обновляемым программным криптографически безопасным генераторам псевдослучайных чисел (CSPRNG). Откат происходит, когда желаемая частота случайности чтения превышает способность естественного подхода к сбору данных, чтобы не отставать от спроса. Этот подход позволяет избежать ограниченного по скорости блокирования генераторов случайных чисел, основанного на более медленных и чисто экологических методах.
Хотя генератор псевдослучайных чисел, основанный исключительно на детерминированной логике, никогда не может рассматриваться как «истинный» источник случайных чисел в самом чистом смысле этого слова, на практике их обычно достаточно даже для требовательных приложений, критичных к безопасности. Действительно, тщательно разработанные и реализованные генераторы псевдослучайных чисел могут быть сертифицированы для критических с точки зрения безопасности криптографических целей, как в случае с алгоритмом тысячелистника и fortuna. Первый является основой / dev / random источника энтропии в FreeBSD, AIX, OS X, NetBSD, и другие. OpenBSD использует алгоритм псевдослучайных чисел, известный как arc4random.
. В октябре 2019 года было отмечено, что введение квантовых генераторов случайных чисел (QRNG) в модели машинного обучения, включая нейронные сети и сверточные нейронные сети для случайного начального распределения весов и случайные леса для процессов разделения оказали глубокое влияние на их возможности по сравнению с классическим методом генераторов псевдослучайных чисел (ГПСЧ).
Самые ранние методы генерации случайных чисел, такие как игра в кости, подбрасывание монет и колесо рулетки, все еще используются сегодня, в основном в играх и азартных играх, поскольку они, как правило, слишком медленны для большинства приложений в статистике и криптографии.
Физический генератор случайных чисел может быть основан на существенно случайном атомном или субатомном физическом явлении, непредсказуемость которого можно отнести к законам квантовой механики. Источники энтропии включают радиоактивный распад, тепловой шум, дробовой шум, лавинный шум в стабилитронах, смещение часов, синхронизация фактических перемещений жесткого диска головки чтения-записи и радиошум. Однако физические явления и инструменты, используемые для их измерения, обычно имеют асимметрии и систематические ошибки, которые делают их результаты не всегда случайными. Средство извлечения случайности , такое как криптографическая хеш-функция , может использоваться для достижения равномерного распределения битов из неравномерно случайного источника, хотя и с более низкой скоростью передачи битов.
Появление широкополосных источников фотонной энтропии, таких как оптический хаос и шум усиленного спонтанного излучения, в значительной степени способствует развитию физического генератора случайных чисел. Среди них оптический хаос имеет высокий потенциал физического создания высокоскоростных случайных чисел из-за его высокой пропускной способности и большой амплитуды. В 2013 году был построен прототип высокоскоростного физического генератора случайных битов в реальном времени на основе хаотического лазера.
Были разработаны различные творческие способы сбора этой энтропийной информации. Один из способов - запустить хеш-функцию для кадра видеопотока из непредсказуемого источника. Лаваран использовал эту технику с изображениями ряда лавовых ламп. HotBits измеряет радиоактивный распад с помощью трубок Гейгера – Мюллера, а Random.org использует вариации амплитуды атмосферного шума, зарегистрированные с помощью обычного радио.
Демонстрация простого генератора случайных чисел на основе того, где и когда нажимается кнопка Другой распространенный источник энтропии - это поведение людей, пользующихся системой. Хотя люди не считаются хорошими генераторами случайности по запросу, они довольно хорошо генерируют случайное поведение в контексте игры со смешанной стратегией. Некоторое компьютерное программное обеспечение, связанное с безопасностью, требует от пользователя выполнения длительной серии движений мыши или ввода с клавиатуры для создания достаточной энтропии, необходимой для генерации случайных клавиш или для инициализации генераторов псевдослучайных чисел.
Большинство случайных чисел, генерируемых компьютером, используют ГПСЧ, которые представляют собой алгоритмы, которые могут автоматически создавать длинные серии чисел с хорошими случайными свойствами, но в конечном итоге последовательность повторяется (или использование памяти неограниченно растет). Эти случайные числа подходят во многих ситуациях, но не так случайны, как числа, генерируемые из электромагнитного атмосферного шума, используемого в качестве источника энтропии. Последовательность значений, генерируемых такими алгоритмами, обычно определяется фиксированным числом, называемым начальным значением. Одним из наиболее распространенных ГПСЧ является линейный конгруэнтный генератор, который использует повторение
для создания числа, где a, b и m - большие целые числа, а 
Простым методом генерации случайных чисел с помощью ручки и бумаги является так называемый метод среднего квадрата, предложенный Джоном фон Нейманом. Несмотря на то, что он прост в реализации, его продукция низкого качества. У него очень короткий период и серьезные недостатки, например, выходная последовательность почти всегда стремится к нулю. Недавнее нововведение - объединить средний квадрат с последовательностью Вейля. Этот метод обеспечивает получение высококачественной продукции в течение длительного периода времени. См. Последовательность Вейля в среднем квадрате ГПСЧ.
Большинство языков программирования включают функции или библиотечные процедуры, которые предоставляют генераторы случайных чисел. Они часто предназначены для предоставления случайного байта или слова или числа с плавающей запятой , равномерно распределенного между 0 и 1.
Качество, т.е. случайность таких библиотечных функций широко варьируется от полностью предсказуемого вывода до криптографически безопасного. Генератор случайных чисел по умолчанию на многих языках, включая Python, Ruby, R, IDL и PHP, основан на алгоритме Mersenne Twister и недостаточен для целей криптографии, как это явно указано в документации по языку. Такие библиотечные функции часто имеют плохие статистические свойства, и некоторые из них будут повторять шаблоны только после десятков тысяч испытаний. Они часто инициализируются с использованием компьютерных часов реального времени в качестве начального числа, поскольку такие часы обычно измеряют в миллисекундах, что намного превышает точность человека. Эти функции могут обеспечить достаточную случайность для определенных задач (например, видеоигр), но не подходят там, где требуется высококачественная случайность, например, в приложениях криптографии, статистике или численном анализе.
Источники случайных чисел гораздо более высокого качества являются доступно в большинстве операционных систем; например, / dev / random в различных вариантах BSD, Linux, Mac OS X, IRIX и Solaris или CryptGenRandom для Microsoft Windows. Большинство языков программирования, включая упомянутые выше, предоставляют средства доступа к этим источникам более высокого качества.
Существует несколько методов генерации случайного числа на основе функции плотности вероятности. Эти методы включают в себя какое-либо преобразование однородного случайного числа. По этой причине эти методы одинаково хорошо работают при генерации как псевдослучайных, так и истинных случайных чисел. Один метод, называемый методом инверсии, включает в себя интегрирование до области, большей или равной случайному числу (которое должно быть сгенерировано между 0 и 1 для правильного распределения). Второй метод, называемый методом принятия-отклонения, включает выбор значений x и y и проверку того, больше ли функция x, чем значение y. Если это так, значение x принимается. В противном случае значение x отклоняется, и алгоритм пытается снова.
Генерация случайных чисел также может выполняться людьми в форме сбора различных входных данных от конечных пользователей и используя их как источник рандомизации. Однако в большинстве исследований обнаруживается, что люди-субъекты имеют некоторую степень неслучайности при попытке создать случайную последовательность, например, цифры или буквы. Они могут слишком часто чередовать варианты выбора по сравнению с хорошим генератором случайных чисел; таким образом, этот подход не получил широкого распространения.
Даже при наличии источника правдоподобных случайных чисел (возможно, из аппаратного генератора на основе квантовой механики) получение абсолютно несмещенных чисел позаботится. Кроме того, поведение этих генераторов часто меняется в зависимости от температуры, напряжения источника питания, возраста устройства или других внешних помех. И программную ошибку в подпрограмме псевдослучайных чисел или аппаратную ошибку в оборудовании, на котором она работает, также может быть трудно обнаружить.
Сгенерированные случайные числа иногда перед использованием подвергаются статистическим тестам, чтобы убедиться, что основной источник все еще работает, а затем подвергаются последующей обработке для улучшения их статистических свойств. Примером может служить аппаратный генератор случайных чисел TRNG9803, который использует измерение энтропии в качестве аппаратного теста, а затем обрабатывает случайную последовательность с помощью потокового шифра регистра сдвига. Обычно сложно использовать статистические тесты для проверки сгенерированных случайных чисел. Ван и Николь предложили методику статистического тестирования, основанную на расстоянии, которая используется для выявления слабых сторон нескольких случайных генераторов. Ли и Ван предложили метод проверки случайных чисел на основе источников лазерной хаотической энтропии с использованием свойств броуновского движения.
Случайные числа, равномерно распределенные между 0 и 1, можно использовать для генерации случайных чисел любого желаемого распределения, передав их через обратную кумулятивную функцию распределения (CDF) желаемого распределения (см. Выборка с обратным преобразованием ). Обратные функции CDF также называются функциями квантилей. Чтобы сгенерировать пару статистически независимых стандартных нормально распределенных случайных чисел (x, y), можно сначала сгенерировать полярные координаты (r, θ), где r ~ χ2 и θ ~ UNIFORM (0,2π) (см. преобразование Бокса – Мюллера ).
Некоторые ГСЧ от 0 до 1 включают 0, но исключают 1, в то время как другие включают или исключают оба.
Выходы нескольких независимых RNG могут быть объединены (например, с использованием побитовой операции XOR ), чтобы обеспечить объединенный RNG, по крайней мере, такой же хороший, как и лучший используемый RNG. Это называется программным отбеливанием..
Вычислительные и аппаратные генераторы случайных чисел иногда объединяются, чтобы отразить преимущества обоих типов. Вычислительные генераторы случайных чисел обычно могут генерировать псевдослучайные числа намного быстрее, чем физические генераторы, в то время как физические генераторы могут генерировать «истинную случайность».
Некоторые вычисления с использованием генератора случайных чисел можно резюмировать как вычисление общего или среднего значения, например, вычисление интегралов с помощью Метод Монте-Карло. Для таких проблем можно найти более точное решение, используя так называемые последовательности с низким расхождением, также называемые квазислучайными числами. Такие последовательности имеют определенный узор, который качественно равномерно заполняет пробелы; действительно случайная последовательность может оставлять и обычно оставляет большие промежутки.
Следующие сайты предоставляют образцы случайных чисел:
Поскольку большая часть криптографии зависит от криптографически безопасного генератора случайных чисел для ключа и генерации криптографического одноразового номера, если Генератор случайных чисел можно сделать предсказуемым, он может использоваться злоумышленником как бэкдор для взлома шифрования.
Сообщается, что АНБ вставило бэкдор в сертифицированный NIST криптографически безопасный генератор псевдослучайных чисел Dual EC DRBG. Если, например, с помощью этого генератора случайных чисел создается SSL-соединение, то, согласно Мэтью Грин, это позволит NSA определять состояние генератора случайных чисел и, таким образом, в конечном итоге иметь возможность читать все передаваемые данные. SSL-соединение. Несмотря на то, что было очевидно, что Dual_EC_DRBG был очень плохим генератором псевдослучайных чисел, возможно, задолго до того, как бэкдор АНБ был подтвержден в 2013 году, он широко использовался на практике до 2013 года, например, известной охранной компанией RSA Security. Впоследствии были обвинения в том, что RSA Security сознательно вставила бэкдор АНБ в свои продукты, возможно, как часть программы Bullrun. RSA отрицает намеренное внедрение бэкдора в свои продукты.
Также было высказано предположение, что аппаратные ГСЧ могут быть тайно модифицированы, чтобы иметь меньшую энтропию, чем заявлено, что сделало бы шифрование с использованием аппаратного ГСЧ уязвимым для атак. Один такой метод, который был опубликован, работает путем изменения легирующей маски микросхемы, которую невозможно обнаружить при оптическом реверс-инжиниринге. Например, для генерации случайных чисел в Linux считается неприемлемым использование аппаратного ГСЧ Intel RDRAND без смешивания вывода RDRAND с другими источниками энтропии, чтобы противодействовать любым бэкдорам в аппаратном ГСЧ, особенно после разоблачение программы АНБ Bullrun.
В 2010 году розыгрыш лотереи в США был сфальсифицирован директором по информационной безопасности Межгосударственной лотерейной ассоциации (MUSL), кто тайно установил бэкдор вредоносное ПО на защищенный ГСЧ-компьютер MUSL во время планового обслуживания. Во время взломов мужчина выиграл общую сумму в 16 500 000 долларов, правильно угадав числа несколько раз в год.
Рандомизация разметки адресного пространства (ASLR), средство защиты от атак Rowhammer и связанных с ними атак на физическое оборудование микросхем памяти было признано VUSec неадекватным на начало 2017 года. Алгоритм случайных чисел, если он основан на сдвиговом регистре, реализованном на аппаратном уровне, предсказуем при достаточно больших значениях p и может быть реконструирован с достаточной вычислительной мощностью (Brute Force Hack ). Это также косвенно означает, что вредоносные программы, использующие этот метод, могут работать как на графических процессорах, так и на процессорах, если они закодированы для этого, даже используя графический процессор для нарушения ASLR на самом процессоре.
