Рандомная система что это
Подробно о генераторах случайных и псевдослучайных чисел
Введение
Как отличить случайную последовательность чисел от неслучайной?
Чуть более сложный пример или число Пи
Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.
Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)
Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (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 и множество других, чтобы определить критостойкость алгоритма.
«Случайности не случайны, всё это большой обман.» или как работают элементы рандома в играх.
ПРЕДИСЛОВИЕ
Доброго времени суток StopGame! Сегодня я расскажу вам, как работают элементы рандома (случайных событий) и как на самом деле разработчики создают те или иные ситуации, где эти элементы требуются. Сразу уточню для большего понимания: случайность — рандом. Постараюсь рассказать как можно более сжато и понятно для восприятия. Ну что же, поехали!
О ВИДАХ СЛУЧАЙНЫХ ЭЛЕМЕНТОВ
Немногие знают, но компьютер не может создать полностью случайное число, какие алгоритмы бы не применялись. Всегда созданное число будет от чего-нибудь зависеть и не будет полностью случайным. Компьютер — это машина и она подчиняется математическим алгоритмам и формулам, а случайность в принципе прямая противоположность каким-либо математическим правилам. Разработчики всегда идут на ухищрения, чтобы максимально правдоподобно создать иллюзию случайности, но это всё равно нельзя назвать полным рандомом.
На самом деле существует несколько ситуаций, где требуется применение элементов рандома:
1.Процедурная генерация (создание ландшафта и миров).
2.«Честная» генерация предметов (Выпадение предметов из противников, сундуков и тд.).
3.«Не честная» генерация предметов (Кейсы в играх, покупаемые за реальные деньги).
4.Ситуации, где на элементах рандома завязана вся игра. (Игральные карты, игры с шестигранным кубиком)
5.Различные ситуации, которые должны возникать в рандомное время (Например смена погоды с солнечной на дождливую).
Остановимся на каждом выделенном элементе более подробно. (если что-то забыл добавить в список, милости прошу в комментарии. Если будет действительно интересный и конструктивный коммент, я дополню блог).
Процедурная генерация
Конечно под этим словом подразумевается не только создание ландшафта и окружения, сюда входит местонахождение предметов на локации, персонажей и много чего ещё, но всё же самым популярным методом использования всё равно остаётся генерация случайных миров. Ярким примером может являться создание мира в «Minecraft», где работает именно процедурная генерация, она создаёт абсолютно всё окружение вокруг игрока (все блоки, сундуки, враги, объекты, персонажи и др.) и давайте разберём, как же он создаётся. На самом деле алгоритм не раз менялся, но на сегодняшний день он работает так:
Знаете ли вы, что мир в «Minecraft» не бесконечен? Он составляет 30 на 30 миллионов блоков. При генерации (не только в «Minecraft», во многих играх также) используется так называемый «seed» — начальное значение.
Чтобы создать уникальный мир, это начальное значение создать из случайных цифр и символов. Без него не работает практически никакой метод ГПСЧ (Генератор псевдослучайных чисел). Но так как, компьютер не может создать ничего случайного, игра берёт за случайные цифры дату и время на компьютере. Если вы попытаетесь создать два мира в игре с одной и той же датой и временем (например 20.10.2020, 18:34), то получите два абсолютно одинаковых мира. Но созданием «seed» всё не кончается, далее это начальное значение преобразуется в 32-х битное число путём нескольких формул. После получается число, которое применяется ещё к одному методу — Шуму Перлина.
Шум Перлина на самом деле к звуку никакого отношения не имеет, это по сути картинка (пример на изображении ниже) с множеством оттенков серых, белых и чёрных цветов. Если говорить совсем простым языком, чем темнее пиксель на изображении шума Перлина, тем выше (либо ниже) создаётся ландшафт.
Допустим такой пример (очень упрощённо, на деле всё сложнее, есть куча «фильтров» последующей «полировки» мира). На картинке шума есть пиксели только трёх цветов (без оттенков): белый, серый и чёрный, тогда мир «Minecraft» может сгенерироваться с ландшафтом высотой максимум в 3 блока. Белым будет блок воздуха (по сути отсутствие блока), серым толщина ландшафта в 1 блок, а чёрным толщина в 2 блока. Но такой шум Перлина принято называть двумерным.
В игре используется в основном трёхмерный шум(3D) (но и двумерный тоже работает для «полировки»), так как при использовании только двумерного (2D) невозможно было бы создать например пещеры и различные постройки. Ниже вы можете увидеть 2D шум. На первой картинке вы видите слева сам шум, а справа результат создания (неудачный я нашёл пример, справа создаётся какая-то 2D игра). На второй картинке вы сразу видите результат работы шума Перлина уже в игровом движке. На третей и четвёртой картинке показано всё более понятно.
Вот примерно так и создаются все процедурно-генерируемые миры, шум Перлина совместно с алгоритмами псевдослучаных чисел остаются пожалуй самыми популярными и простыми. Я старался описать как можно более понятно, но допускаю, что всё равно слишком сложно для восприятия. Напишите в комментариях, если не понятно, буду дорабатывать блог. Ну а мы перейдём к следующему элементу случайности. Более подробно и в разы более интересно про процедурную генерацию можно узнать из видео ниже:
«Честная» и «нечестная» генерация предметов.
Что я вообще подразумеваю под словом «честная»? Честной я называю генерацию предметов, которая не зависит от серверных данных и вероятность выпадения таких предметов генерируется движком, а не разработчиками или издателями.
Давайте приведу условный пример: у вас есть игра в которой имеется 4 вида редкости какой-либо вещи: Обычный, редкий, эпический и легендарный. Вы подходите например к сундуку, откуда эти вещи вам выпадут и честной будет та система, где алгоритм случайности не изменяется разработчиками после релиза по желанию. То есть если вам выпал например легендарный предмет, то вам «повезло», так как в алгоритме выпало нужное число, если же нет, то вероятность на выпадение этого предмета не изменится исходя из прошлого полученного предмета.
Упрощённо эта система работает так: пусть вероятность выпадения предметов такая — обычный (70%), редкий (20%), эпический (9%), легендарный (1%). Всё это суммарно даёт 100% вероятность, и тогда алгоритм будет выглядеть так условно так: если случайно введённое число находится в промежутке от 0 до 70, выпадет обычный предмет, если от 71 до 90, выпадет редкий предмет, если от 91 до 99 то выпадет эпический предмет, а если введённое число 100 выпадет легендарный. Элементом рандома здесь и является это самое ввёденное число. Где же взять это рандомное число? Способов на самом деле масса: от ранее упомянутого seeda (просто брать последние два его числа), до прослушивания атмосферного шума и шума микрофона для его последующего преобразования в цифровой вид (так работает популярный сайт: Random.org).
Однако же StopGame — это игровой портал, поэтому давайте узнаем, как генерируются такие числа в двух, самых популярных игровых движках: Unity и Unreal Engine.
-В этих движках одним из методов используется «XorShift», который берёт за seed дату и время на ПК, потом преобразует полученное число в двоичную систему счисления, потом суммирует это число несколько раз со сдвигом вправо и влево, после полученное число обрезается по длине исходного и получается псевдослучайное число. Более понятно и подробно об этом способе рассказано в видео ниже.
Давайте теперь поговорим о «нечестной» генерации предметов.
Самое широкое распространение такой способ имеет в онлайн играх по типу: «Warface», «Overwatch» и «CS:GO». В них тоже используется принцип, основанный на вероятностях, как и в «честном» способе, только в отличие от него нечестный способ изменяет свою вероятность в зависимости от ранее полученных данных. Теперь языком попроще: если вам выпала «легендарная» вещь с шансом в 1%, то следующая «легендарная» вещь уже будет иметь шанс выпадения например 0.5% или менее, а вещи «обычной» с шансом в 70% наоборот поднимут свой шанс выпадения например до 80%, так после нескольких попыток открытия условных «кейсов в CS:GO» шанс будет повышаться, пока опять не достигнет своего максимума в 1%, а вероятность на выпадение «обычной» вещи не опустится до 70%.
Естественно нечестный способ, как правило, нужен для того, чтобы получить прибыль с игроков, ведь азарт и призрачная надежда на то, что «скоро уже выпадет легендарка, я чувствую» и заставляет игроков тратить деньги на подобного рода кейсы, рулетки, ставки и казино. Весь процесс контролируется разработчиками и они могут изменить параметры вероятностей в любой момент, так как все алгоритмы находятся на удалённом сервере. Давайте теперь поговорим о следующем элементе рандома.
Ситуации, где на элементах рандома завязана вся игра:
Я говорю про те игры, где ваша победа напрямую зависит от изначально (или в процессе) полученной случайной комбинации элементов. Самый яркий пример тому в реальной жизни — это игральные карты. Человек перемешивает карты руками, после раздаёт их на всех игроков. Но как карты может перемешать компьютер? На самом деле можно воспользоваться весьма странным, но рабочим методом: отслеживания перемещений стрелки мыши. (Не знаю, используется ли конкретно в конкретно карточных играх такой способ, но во многих проектах он присутствует). Компьютер отслеживает координаты X и Y, на которых сейчас находится мышь и берёт только по последней цифре от каждой координаты. Допустим стрелка мыши находится на координатах X=54 и Y=27. Алгоритм возьмёт для создания случайного числа только 4 (из числа 54) и 7 (из числа 27), далее функций может быть много, числа можно сложить, вычесть, умножить, разделить и получить любое другое новое псевдослучайное число. Далее карты нумеруются допустим от 0 до 36, сложим ранее полученные 4 и 7, получим 11, значит игроку достанется карта под номером 11 из колоды и так, пока игроки не получат нужное количество карт. Естественно отслеживаются все перемещения мыши допустим за минуту времени, так как если каждый раз смотреть на текущую координату мыши, псевдослучайное число всегда будет одним и тем же если мышь не двигается.
Очень надеюсь, что вы поняли то, что я хотел сказать, старался обьяснять понятно, но моя манера речи и повествования конечно «оставляет желать лучшего».
Давайте перейдём к последнему элементу рандома, который я смог сформулировать.
Различные ситуации, которые должны возникать в рандомное время.
В пример можно привести дождь и грозу из того же «Minecraft». На самом деле там нет никакой случайности, периодичность дождей зависит от всё того же «злополучного» seedа, который создан при генерации мира. При определённых seedах период дождей изменяется, благодаря вычислениям по определённым формулам (которые «Mojang» не показывает). Грубо говоря в одном мире, с одним seed дожди происходят раз в игровых 5 дней, в другом же мире, с другим seed периодичность уже будет например раз в игровых 7 дней. Тут вообще нет никаких элементов рандома, всё происходит закономерно и по формулам.
Действительно случайные ситуации в играх используются очень редко, но всё же присутствуют. Давайте разберём и их работу.
Возьмём в пример странствующих торговцев в «Dying Light». Не могу точно уверять, что всё рабоатет именно так, как я говорю, поскольку доступа к исходному коду «движка» у простых пользователей нет, но всё намекает именно на такой метод.Торговцы появляются в случайное время (которое определяется через ГСПЧ) со случайным товаром в случайном месте. Но и тут к сожалению никакого по настоящему случайного элемента нет. Торговцы появляются в специально заготовленных местах, которые выбрали для них разработчики, и продают товар, который тоже не случайно генерируется (товар создают из специально заготовленных наборов предметов, который разработчики тоже успели ранее сделать). Также и цены на товар могут меняться в большую или меньшую сторону всего одной формулой (убавления процентов к изначальной цене товара), тем самым привлекая игрока «временной скидкой и ограниченным предложением», но всё это лишь иллюзия обмана.
Что значит «рандомно» в интернет-сленге?
Современный интернет-сленг ежедневно пополняется новыми словами и выражениями. Они заимствуются из других языков и профессиональных жаргонизмов, подстраиваются под нужды пользователей сети и прочно закрепляются в их речи. Одним из таких терминов является слово «рандомно». Что оно обозначает? Откуда появилось и как используется сейчас?
Значение и происхождение
Термин «рандомно» произошел от английского random (случайный, произвольный, хаотичный). Внедрился в русское интернет-сообщество благодаря геймерскому комьюнити.
Еще в «древних» пиксельных RPG присутствовал элемент случайности в выпадении лута после поединков. В современных РПГ и ММОРПГ этот принцип сохраняется.
Инди RPG Job Hunt Heroes. Момент выпадения лута
Кейсы Counter-Strike:Global Offensive
В некоторых играх можно выбрать рандомный мир для выживания или персонажа для сражения со случайным набором характеристик. Это позволяет игроку прокачивать свои умения в любых условиях.
Также считается, что слово «рандомно» пришло из языка программирования, а точнее, произошло от функции random (случайная последовательность чисел).
Современное использования термина
Выражение давно используется за пределами гейм-комьюнити и среды программирования. Сейчас его употребляют повсеместно. Например, термин «рандомно» применяется во время розыгрыша каких-либо предметов в соцсетях (от стикеров Вконтакте до автомобилей). Так, во время раздачи призов выбирается рандомный победитель с помощью генератора чисел. Таких сервисов в интернете много, их называют рандомайзерами. Принцип пользования очень прост. Каждому участнику конкурса присваивается индивидуальный номер. В рандомайзер вводится общее число участников, после чего программа выдает рандомное число. Победителем считается человек, чей конкурсный номер совпал с числом, выданным рандомайзером.
Рандомайзер
Это не исключительный вариант использования термина. Слово настолько прижилось, что стало полноправным синонимом слова «случайно». Оно используется и за пределами сети.
Несмотря на давность появления, «рандомно» используется и по сей день. Употребление термина популярно как среди молодежи, так и среди взрослых.
С происхождением и использованием сленговых выражений, таких как: рофлю, страйк, коннект, – можно ознакомиться в других статьях.