Что такое рандомные числа
Что значит «рандомно» в интернет-сленге?
Современный интернет-сленг ежедневно пополняется новыми словами и выражениями. Они заимствуются из других языков и профессиональных жаргонизмов, подстраиваются под нужды пользователей сети и прочно закрепляются в их речи. Одним из таких терминов является слово «рандомно». Что оно обозначает? Откуда появилось и как используется сейчас?
Значение и происхождение
Термин «рандомно» произошел от английского random (случайный, произвольный, хаотичный). Внедрился в русское интернет-сообщество благодаря геймерскому комьюнити.
Еще в «древних» пиксельных RPG присутствовал элемент случайности в выпадении лута после поединков. В современных РПГ и ММОРПГ этот принцип сохраняется.
Инди RPG Job Hunt Heroes. Момент выпадения лута
Кейсы Counter-Strike:Global Offensive
В некоторых играх можно выбрать рандомный мир для выживания или персонажа для сражения со случайным набором характеристик. Это позволяет игроку прокачивать свои умения в любых условиях.
Также считается, что слово «рандомно» пришло из языка программирования, а точнее, произошло от функции random (случайная последовательность чисел).
Современное использования термина
Выражение давно используется за пределами гейм-комьюнити и среды программирования. Сейчас его употребляют повсеместно. Например, термин «рандомно» применяется во время розыгрыша каких-либо предметов в соцсетях (от стикеров Вконтакте до автомобилей). Так, во время раздачи призов выбирается рандомный победитель с помощью генератора чисел. Таких сервисов в интернете много, их называют рандомайзерами. Принцип пользования очень прост. Каждому участнику конкурса присваивается индивидуальный номер. В рандомайзер вводится общее число участников, после чего программа выдает рандомное число. Победителем считается человек, чей конкурсный номер совпал с числом, выданным рандомайзером.
Рандомайзер
Это не исключительный вариант использования термина. Слово настолько прижилось, что стало полноправным синонимом слова «случайно». Оно используется и за пределами сети.
Несмотря на давность появления, «рандомно» используется и по сей день. Употребление термина популярно как среди молодежи, так и среди взрослых.
С происхождением и использованием сленговых выражений, таких как: рофлю, страйк, коннект, – можно ознакомиться в других статьях.
Краткая история случайных чисел
«Когда я задался целью получить действительно случайное число, то не нашел для этого ничего лучшего, чем обычная игральная кость» — писал в 1890 году Фрэнсис Гальтон в журнале Nature. «После того, как кости встряхивают и бросают в корзинку, они ударяются друг о друга и о стенки корзинки столь непредсказуемым образом, что даже после легкого броска становится совершенно невозможным предопределить его результат».
(Игральные кости времён Римской Империи)
Как мы можем сгенерировать равномерную последовательность случайных чисел? Случайность, столь прекрасная в своём многообразии, часто встречается в живой природе, но её не всегда легко было извлечь искусственным путём. Самые древние из игральных костей были найдены на Среднем Востоке, и они датируются примерно 24 столетием до нашей эры. Другим примером может быть Китай, где ещё в 11 столетии до нашей эры применялось разбивание ударом черепашьего панциря, с дальнейшей интерпретацией размера полученных случайных частей. Столетиями позже люди разрубали несколько раз стебли растений и сравнивали размеры полученных частей.
Но к середине 40-ых годов ХХ столетия человечеству понадобилось значительно больше случайных чисел, чем можно было получить от бросков костей или разрезания стеблей. Американский аналитический центр RAND создал машину, которая была способна генерировать случайные числа с помощью использования случайного генератора импульсов (что-то вроде электронной рулетки). Они запустили её и через какое-то время получили достаточное количество случайных чисел, которые опубликовали в виде книги «Один миллион случайных чисел и сто тысяч нормальных отклонений».
Книгу можно почитать онлайн или купить бумажное переиздание 2001 года на Amazon. То, что сегодня может показаться абсурдным арт-проектом, в то время было серьёзным прорывом. Впервые учёным стала доступна действительно большая последовательность действительно случайных чисел.
Другая похожая машина, ERNIE, построенная в знаменитом сегодня Блетчли-парке в 40-ых годах ХХ века, использовалась для генерации случайных чисел в британской лотерее Premium Bond. Для того, чтобы развеять страхи по поводу случайности и честности результатов, была даже снята документальная лента «The Importance of Being E.R.N.I.E.». Сегодня её можно посмотреть на Youtube:
В 1951 году случайность наконец была формализована и воплощена в реальном компьютере Ferranti Mark 1, который поставлялся со встроенным генератором случайных данных на основе дробовых шумов и инструкцией, позволяющей получить 20 случайных бит. Этот функционал был разработан Аланом Тьюрингом. Его коллега Кристофер Стрэчи применил его для создания «генератора любовных писем». Вот пример текста, который был сгенерирован данной программой:
Но генератор случайных чисел Тьюринга не делал программистов тех лет счастливыми, поскольку привносил в и так новые и нестабильные компьютерные системы фактор ещё большей нестабильности. Желая добиться стабильной работы некоторой программы — без отладчиков и со случайными данными — никогда нельзя было достичь повторяемости результатов. Тогда возникла следующая мысль: «А что, если генератор случайных чисел может быть представлен в виде некоторой детерминированной функции?» Тогда получилось бы, что, с одной стороны, генерируемые числа имели бы признаки случайных, но с другой стороны, при одинаковой инициализации генератора данные последовательности были бы каждый раз одни и те же. Так появились генераторы псевдослучайных чисел (ГПСЧ).
Джон фон Нейман разработал ГПСЧ в 1946 году. Его идеей было начать с некоторого числа, взять его квадрат, отбросить цифры из середины результата, снова взять квадрат и отбросить середину, и т.д. Полученная последовательность, по его мнению, обладала теми же свойствами, что и случайные числа. Теория фон Неймана не выдержала испытания временем, поскольку какое бы начальное число вы не выбрали, сгенерированная таким образом последовательность вырождалась в короткий цикл повторяющихся значений, вроде 8100, 6100, 4100, 8100, 6100, 4100,…
Полностью избежать циклов невозможно, когда мы работаем с детерминированной функцией, чьи последующие значения основаны на предыдущих. Но что, если период цикла будет столь большим, что на практике это уже не будет иметь значения?
Математик Деррик Генри Лемер развил эту идею в 1949 году с изобретением линейного конгруэнтного метода. Вот генератор псевдослучайных чисел, основанный на подходе Лемера и написанный на Javascript:
Вы можете заметить в коде ряд «магических констант». Эти числа (как правило, простые) выбирались таким образом, чтобы максимизировать период цикла до повторения последовательности результатов. Данный генератор использует в качестве начального значения текущее время и имеет период около 2^31. Он стал популярным с выходом JavaScript 1.0, поскольку он тогда ещё не имел встроенной функции Math.random(), а все ведь хотели, чтобы их рекламные баннеры сменялись случайным образом. «Я не использовал бы этот алгоритм для чего-то связанного с безопасностью, но для многих применений его достаточно», — писал автор вышеуказанного кода Paul Houle.
Но Интернет как раз требовал чего-то, связанного с безопасностью. SSL появился в 1995 году и его реализация требовала высококачественного генератора псевдослучайных чисел. Это привело к серии достаточно диких экспериментов в данной области. Если вы посмотрите на патенты, связанные с генерацией случайных чисел, выданные в те времена, то получите ощущение, будто смотрите на осовремененные попытки построения первого самолёта.
Большинство популярных процессоров в 90-ых годах не имели специальной инструкции для генерации случайных чисел, так что выбор хорошего начального значения для генератора псевдослучайных чисел имел очень важное значение. Это вылилось в проблемы с безопасностью, когда Phillip Hallam-Baker обнаружил, что в браузере Netscape (доминирующем в то время) реализация SSL использовала для инициализации ГПСЧ комбинацию текущего времени и ID своего процесса. Он показал, как хакер может легко подобрать это значение и расшифровать SSL-трафик. Угадывание начального значения алгоритма генерации псевдослучайных чисел — до сих пор популярная атака, хотя с годами она стала слегка сложнее. Вот пример удачной атаки, опубликованный на Hacker News в 2009 году.
В 1997 году программисты были ограничены в способах получения по-настоящему случайных чисел, так что команда SGI создала LavaRand, который состоял из вебкамеры, направленной на пару лава-ламп, стоявших рядом на столе. Картинка с этой камеры была отличным источником энтропии — Настоящим Генератором Случайных Чисел, таким же, как у Тьюринга. Но в этот раз получалось генерировать 165 Кб случайных чисел в секунду. Изобретение было тут же запатентовано.
Большинство экспериментов в этой области не выдержали испытания временем, но один ГПСЧ, названный Вихрем Мерсенна и разработанный в 1997 году Макото Мацумото и Такудзи Нисимура, смог удержать пальму первенства. В нём сочетались производительность и качество результатов, что позволило ему быстро распространиться на многие языки и фреймворки. Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей и генерирует детерминированную последовательность с огромным периодом цикла. В текущей реализации период равен 2¹⁹⁹³⁷− 1 и именно эта реализация входит сегодня в большинство языков программирования.
В 1999 году Intel добавил аппаратный генератор случайных чисел в чипсет i810. Это было хорошо, поскольку данная реализация давала по-настоящему случайные числа (на основе температурных шумов), но работало не настолько же быстро, как программные ГПСЧ, так что большинство криптоприложений всё ещё используют ГПСЧ, которые теперь, по крайней мере, можно инициализировать начальным значением от аппаратного генератора случайных чисел.
Это приводит нас к понятию криптографически-безопасного генератора псевдослучайных чисел (КБГПСЧ). (Ох уж эти аббревиатуры! Не удивительно, что компьютерные науки кажутся некоторым людям скучными.) КБГПСЧ стали очень популярными в эпоху SSL. Каким требованиям должен удовлетворять КБГПСЧ? Ну вот вам 131-страничный документ с этими требованиями, развлекайтесь. Как вы уже понимаете, требований не мало. Например, тот же Вихрь Мерсенна им не удовлетворяет, поскольку, имея достаточно большую последовательность сгенерированных им чисел, можно угадать следующее число.
В 2012 году INTEL добавил в свои чипы инструкции RDRAND и RDSEED, позволяющие получить настоящие случайные числа на основе тех же колебаний температуры, но теперь уже на скорости до 500 Мб/с, что должно бы сделать применение программных ГПСЧ ненужным. Но в обществе бродят слухи и сомнения в честности этих инструкций. Нет ли в них специально сделанной закладки для NSA? Никто не может сказать этого точно. Вернее, кто-то, наверное, может, но он точно не напишет об этом в Твиттере.
(Случайные данные полученные от аппаратного генератора случайных чисел Redoubler)
В последние годы начали появляться также аппаратные генераторы случайных чисел от сторонних производителей и даже полностью открытые (как в плане софта, так и аппаратной части). Сила этих продуктов именно в открытости: можно изучить их самостоятельно и даже построить дома самому из общедоступных компонентов. Примерами могут быть REDOUBLER и Infinite Noise TRNG.
Сегодня люди всё ещё ведут дискуссии о том, какой именно генератор случайных чисел стоит использовать в той или иной системе, ядре ОС, языке программирования, криптографической библиотеке и т.д. Есть много вариантов алгоритмов, заточенных на скорость, экономию памяти, безопасность. И каждый из них постоянно подвергается атакам хакеров и специалистов по безопасности. Но для ежедневных задач, не связанных с безопасностью, вы вполне можете положиться на данные из /dev/random или функции rand(), доступных на большинстве платформ. Это даст вам достаточно большую и случайную последовательность данных, которая бы сделала в своё время счастливым Алана Тьюринга.
Что такое генератор случайных чисел.
На макроскопических случайных процессах с использованием таких простых предметов, как игральная кость, колесо рулетки или монетка, могут быть основаны генераторы случайных чисел. Теорией хаоса и теорией неустойчивых динамических систем можно объяснить наличие непредсказуемости в данных и даже макроскопические системы, полностью определенные уравнениями Ньютона, на практике часто имеют непредсказуемый выход, так как зависит он от микроскопических деталей начальных условий.
Кстати, на нашем сайте вы можете cгенерировать случайное число, воспользовавшись Генератором случайных чисел онлайн.
Что такое генератор случайных чисел и как он использует случайные физические процессы?
Скорость получения случайных чисел, достаточную для прикладных задач, не могут обеспечить устройства, которые основаны на макроскопических случайных процессах. Источник шума, из которого происходит извлечение случайных битов, поэтому лежит в основе современных АГСЧ. Источники шума бывают двух видов: те, которые имеют квантовую природу и квантовые явления не использующие.
Сложный генератор случайных чисел.
Для АГСЧ «золотым стандартом» являются некоторые из квантово-механических процессов, поскольку они абсолютно случайны. Использующие в генераторах случайных чисел явления включают:
Детектировать гораздо проще неквантовые явления, но основанные на них генераторы случайных чисел, тогда будут иметь сильную зависимость от температуры (например, величина теплового шума будет пропорциональна температуре окружающей среды). Можно отметить такие процессы, среди использующихся в АГСЧ:
Чтобы из физического случайного процесса получить последовательность случайных битов, то для этого существует несколько подходов. Заключается один из них в том, что усиливается полученный сигнал-шум, затем фильтруется и подается на вход быстродействующего компаратора напряжений, для получения логического сигнала. Будет случайной длительность состояний компаратора и это позволяет создавать последовательность случайных чисел, проводя измерения этих состояний.
Второй подход состоит в том, что подается случайный сигнал на вход аналого-цифрового преобразователя (могут применяться как специальные устройства, так и аудиовход компьютера), представлять собой последовательность из случайных чисел, в результате которой будет оцифрованный сигнал и при этом она может быть программно обработана.
Что такое генератор случайных чисел и какие другие явления он использует?
Использующие физические случайные процессы генераторы случайных чисел, дают возможность для получения хороших случайных чисел, но производство их дорого и относительно сложно (особенно это касается тех АГСЧ, которые основаны на радиоактивном распаде), однако существуют и другие более доступные источники случайности:
Простая генерация случайных чисел.
Работы цифровых видеокамер, которые используют съемку макроскопических явлений, следует отнести к наиболее необычным генераторам. Так например, для генерации случайных чисел, командой из Silicon Graphics была использована видеозапись лавовой лампы потому, что воск хаотически меняет свои формы в лампе. Ленты от вентилятора в потоке воздуха или пузыри в аквариуме, могут быть также использованы в качестве объекта для съемки.
Подробно о генераторах случайных и псевдослучайных чисел
Введение
Как отличить случайную последовательность чисел от неслучайной?
Чуть более сложный пример или число Пи
Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.
Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)
Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел. ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.
Энтропия – это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.
Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.
Уязвимости ГПСЧ
Линейный конгруэнтный ГПСЧ (LCPRNG)
Распространённый метод для генерации псевдослучайных чисел, не обладающий криптографической стойкостью. Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:
где a (multiplier), c (addend), m (mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа (seed) X0 и при разных его значениях получаются различные последовательности случайных чисел.
Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].
Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений
Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия [8], эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.
Предсказание результатов линейно-конгруэнтного метода
Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь [4](есть онлайн запуск) и здесь [5]. Описание алгоритма можно найти в [9].
Простая реализация конгруэнтного метода на Java.
Отправив 20 чисел на сайт [4], можно с большой вероятностью получить следующие. Чем больше чисел, тем больше вероятность.
Взлом встроенного генератора случайных чисел в Java
Многие языки программирования, например C(rand), C++(rand) и Java используют LСPRNG. Рассмотрим, как можно провести взлом на примере java.utils.Random. Зайдя в исходный код (jdk1.7) данного класса можно увидеть используемые константы
Метод java.utils.Randon.nextInt() выглядит следующим образом (здесь bits == 32)
Результатом является nextseed сдвинутый вправо на 48-32=16 бит. Данный метод называется truncated-bits, особенно неприятен при black-box, приходится добавлять ещё один цикл в brute-force. Взлом будет происходить методом грубой силы(brute-force).
Пусть мы знаем два подряд сгенерированных числа x1 и x2. Тогда необходимо перебрать 2^16 = 65536 вариантов oldseed и применять к x1 формулу:
до тех пор, пока она не станет равной x2. Код для brute-force может выглядеть так
Вывод данной программы будет примерно таким:
Несложно понять, что мы нашли не самый первый seed, а seed, используемый при генерации второго числа. Для нахождения первоначального seed необходимо провести несколько операций, которые Java использовала для преобразования seed, в обратном порядке.
И теперь в исходном коде заменим
crackingSeed.set(seed);
на
crackingSeed.set(getPreviousSeed(seed));
И всё, мы успешно взломали ГПСЧ в Java.
Взлом ГПСЧ Mersenne twister в PHP
Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. Основные преимущества алгоритма — это скорость генерации и огромный период 2^19937 − 1, На этот раз будем анализировать реализацию алгоритма mt_srand() и mt_rand() в исходном коде php версии 5.4.6.
Можно заметить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)). В бинарном представление операция выглядит так:
10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Видно, что первые 18 бит (выделены жирным) остались без изменений.
Напишем две функции для инвертирования битового сдвига и xor
Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так
Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister, то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister, и сможем легко определить каждое последующее значение, запустив php_mt_reload для известного набора значений.
Область для взлома
Если вы думаете, что уже нечего ломать, то Вы глубоко заблуждаетесь. Одним из интересных направлений является генератор случайных чисел Adobe Flash(Action Script 3.0). Его особенностью является закрытость исходного кода и отсутствие задания seed’а. Основной интерес к нему, это использование во многих онлайн-казино и онлайн-покере.
Есть много последовательностей чисел, начиная от курса доллара и заканчивая количеством времени проведенным в пробке каждый день. И найти закономерность в таких данных очень не простая задача.
Задание распределения для генератора псевдослучайных чисел
Для любой случайной величины можно задать распределение. Перенося на пример с картами, можно сделать так, чтобы тузы выпадали чаще, чем девятки. Далее представлены несколько примеров для треугольного распределения и экспоненциального распределения.
Треугольное распределение
Приведем пример генерации случайной величины с треугольным распределением [7] на языке C99.
Экспоненциальное распределение
Тесты ГПСЧ
Некоторые разработчики считают, что если они скроют используемый ими метод генерации или придумают свой, то этого достаточно для защиты. Это очень распространённое заблуждение. Следует помнить, что есть специальные методы и приемы для поиска зависимостей в последовательности чисел.
Одним из известных тестов является тест на следующий бит — тест, служащий для проверки генераторов псевдослучайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.
В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило, для этой цели используются различные статистические тесты, такие как DIEHARD или NIST. Эндрю Яо в 1982 году доказал, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
В интернете [10] можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.