1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Как работает генератор случайных чисел как выиграть

Содержание

Подробно о генераторах случайных и псевдослучайных чисел

Введение

Генераторы случайных чисел — ключевая часть веб-безопасности. Небольшой список применений:

  • Генераторы сессий (PHPSESSID)
  • Генерация текста для капчи
  • Шифрование
  • Генерация соли для хранения паролей в необратимом виде
  • Генератор паролей
  • Порядок раздачи карт в интернет казино

Как отличить случайную последовательность чисел от неслучайной?

Пусть есть последовательность чисел: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 . Является ли она случайной? Есть строгое определение для случайной величины. Случайная величина — это величина, которая принимает в результате опыта одно из множества значений, причём появление того или иного значения этой величины до её измерения нельзя точно предсказать. Но оно не помогает ответить на наш вопрос, так как нам не хватает информации для ответа. Теперь скажем, что данные числа получились набором одной из верхних строк клавиатуры. «Конечно не случайная» — воскликните Вы и тут же назовете следующие число и будете абсолютно правы. Последовательность будет случайной только если между символами, нету зависимости. Например, если бы данные символы появились в результате вытягивания бочонков в лото, то последовательность была бы случайной.

Чуть более сложный пример или число Пи


Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.

Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)

Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (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.

В данном случае мы берем случайную величину rand() и задаем ей распределение, исходя из функции треугольного распределения. Для параметров a = -40, b = 100, c = 50 график 10000000 измерений будет выглядеть так

Экспоненциальное распределение

Пусть требуется получить датчик экспоненциально распределенных случайных величин. В этом случае F(x) = 1 – exp(-lambda * x). Тогда из решения уравнения y = 1 – exp(-lambda * x) получаем x = -log(1-y)/lambda.
Можно заметить, что выражение под знаком логарифма в последней формуле имеет равномерное распределение на отрезке [0,1), что позволяет получать другую, но так же распределённую последовательность по формуле: x = -log(y)/lambda, где y есть случайная величина(rand()).

Тесты ГПСЧ

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

Одним из известных тестов является тест на следующий бит — тест, служащий для проверки генераторов псевдослучайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.

В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило, для этой цели используются различные статистические тесты, такие как DIEHARD или NIST. Эндрю Яо в 1982 году доказал, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
В интернете [10] можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.

Выбор случайного числа лотереи: это сложнее, чем вы думаете

Казалось бы – ну что может быть легче, чем взять и выбрать несколько случайных чисел. Например, берем 6 цифр, первых которые “пришли к нам в голову”. А вот как раз такая стратегия и считается провальной. И делать так можно только в одном случае: если вы участвуете в розыгрыше просто так, ради интереса. А если ваша цель – выиграть джекпот, такая система вряд ли вам поможет. Итак, выбор случайного числа лотереи: что не так с классическим вариантом выбора и как выбирать числа правильно.

Наш мозг ужасно предсказуем!

Почему именно “ужасно”? Давайте проведем небольшой эксперимент. Выберите, не задумываясь, число от 1 до 10. Если это цифры от 3 до 7 – то вы входите в 90%, то есть большинство людей выбирают именно эти числа. Почему так происходит? Все дело в нашем мозге. Он предсказуем. И в большинстве случаев не “хочет” выбирать первые и последние цифры. Вот и получается, что наш выбор – это цифры от трех до семи. Но не все так плохо. Люди действительно плохие “генераторы случайных чисел”, поэтому вам нужно выбрать другой метод, если вы хотите быть действительно победителями.

Выбор чисел в лотерею: случайность или правильная тактика?

Представьте, что вы стоите на вершине Эйфелевой башни с мешком листьев, а ниже вы расстелили сетку чисел. Теперь попытайтесь предсказать, на каком числе приземлится один лист, если вы уроните его в определенный день. Это кажется невозможным, и что число “попаданий” листьев будет случайным.

Однако, если бы вы могли написать программу, которая идеально анализирует важные факторы, такие как размер и форма листа, а также сила и направление ветра при его падении, было бы без проблем предсказать, на какое число приземлится лист.

Как выбрать числе в лотерее правильно?

Вот несколько важных советов:

  1. Всегда просматривайте архивы розыгрышей (если, конечно, такая функция вам доступна). Смотреть нужно розыгрыши за последние 6-8 месяцев. Только так можно собрать достаточное количество данных.
  2. Просматривая архивы выигрышей, отметьте для себя цифры, которые в розыгрышах вообще не участвовали. Эти цифры вам вообще не нужны.
  3. Также выделите цифры, которые выпадали всего пару раз. Берем их на “заметку”. То есть со счетов не списываем, но и не особо на них надеемся.
  4. Далее выбираем те числа, которые участвовали в розыгрышах чаще остальных. Вот они нам и нужны. Выбираем из них нужное количество цифр и “делаем ставку” именно на них.
  5. + как я уже не раз говорил, чем больше билетов вы покупаете – тем выше ваши шансы на выигрыш. Да, может быть вы и не выиграете миллион, но пару тысяч выиграть очень даже реально.

Случайности не случайны, Или как компьютеры генерируют случайные числа

Генератор случайных чисел — это намного сложнее, чем кажется.

Как думаете, что общего в компьютерных гонках, азартных играх и криптографии? На первый взгляд кажется, что ничего. Но на самом деле все они зависят от случайных чисел. От прослушивания музыки до шифрования всего Интернета — случайные числа являются важной частью жизни современного человека. И чаще всего мы полагаемся на компьютеры, которые генерируют их для нас.

Это заставляет задуматься: а как именно компьютеры генерируют случайные числа?

Если вы занимались программированием, то наверняка использовали в своем коде генератор случайных чисел. Для этого в Ruby достаточно вызвать «rand», а в Python — «random ()». Создание ряда случайных чисел может показаться простым. В конце концов числа на компьютере — это набор единиц и нулей. Машине просто нужно случайным образом выбрать 1 или 0 и повторить это столько раз, сколько нужно. Даже мы, люди, можем сделать это легко и просто на листе бумаги.

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

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

Первый и самый распространенный тип называется «генератор псевдослучайных чисел (ГПСЧ)». Как следует из названия, он не создает «истинных» случайных чисел. Чтобы сгенерировать с помощью него число, понадобится единственное начальное значение, откуда последует псевдослучайность. Алгоритмы генерации, используемые для ГПСЧ, включают в себя «метод извлечения квадратов», «линейный конгруэнтный метод», «регистр сдвига с линейной обратной связью» и «вихрь Мерсенна».

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

Нельзя не сказать о том, что слабым местом ГПСЧ все-таки пользуются: например, любители гонок, которые манипулируют ГСЧ и заставляют игру работать предсказуемо, чтобы пройти ее как можно скорее. Есть случаи, когда предсказание случайных чисел имеет более серьезные последствия. Зная начальное значение, злоумышленник может угадать сгенерированный пароль и получить доступ к личным данным пользователя.

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

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

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

Однако на самом деле спектр использования ГИСЧ тоже ограничен, ведь у него есть свои недостатки. Во-первых, для генерации чисел требуется много времени. А еще ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для создания истинных случайных чисел, но случайность заключается в том, что она возникает… случайно! Неактивный или новый сервер не сможет создавать номера такого же высокого качества, как активный.

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

КСГПЧ — это генератор, использующий высококачественный источник энтропии для создания начального числа. Затем оно вводится в алгоритм, который производит случайные и безопасные числа. Проще говоря, он использует ГИСЧ для создания начального числа для ГПСЧ. Если все сделано правильно, КСГПЧ гарантирует, что начальное число действительно случайно, а полученный результат нельзя взломать или реконструировать. Обычно его используют в операционных системах вроде Unix и Linux.

Тем не менее, даже несмотря на преимущества КСГПЧ, как и всего остального в технологической индустрии, абсолютная безопасность недостижима.

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

Что такое ГСЧ – как работает генератор случайных чисел

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

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

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

Истинный ГСЧ против псевдо ГСЧ

Есть два типа генераторов случайных чисел: истинные и псевдо.

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

Какие приложения используют ГСЧ

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

  • Азартные игры: бинго, карточные игры, лотереи и подобные игры.
  • Игры со сбором добычи: все игры, требующие от игроков сбора добычи для использования в игровом процессе, например, PubG, Diablo и Borderlands используют ГСЧ. Возможность получать лучшую добычу каждый раз – вот причина, по которой люди становятся зависимыми от них.
  • Приключенческие игры: такие игры, как Марио и Покемон Го используйте алгоритм генератора случайных чисел, чтобы определить, какие предметы будут добавлены, и каждый раз вы встречайтесь с новым претендентом на покемона.
  • Процедурно-сгенерированные игры: все игры, в которых нет предварительно разработанных карт и уровней, но которые были разработаны в игре с использованием процедурного программирования, таких как Minecraft и Civilization. Это помогает создать всю игру с использованием алгоритма.
  • Соревновательные игры: некоторые соревновательные игры, например, Counter-Strike используйте алгоритм генератора случайных чисел, чтобы регулировать, как пули поражают цели.

Помимо игровых приложений, есть код случайных чисел в JavaScript, используемый разработчиками и кодировщиками во всём мире для включения генератора случайных чисел в их программы. У Google есть свой очень интересный инструмент, который также основан на теории случайных чисел JavaScript и может генерировать случайные числа. Этот инструмент может пригодиться, когда вы играете в игры с друзьями и семьей. Чтобы посмотреть ГСЧ Google, нажмите здесь.

Манипуляции с ГСЧ

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

ГСЧ на основе алгоритма использует начальное число, которое представляет собой комбинацию определенных факторов и генерирует результат в игре. Это применяемые законы математики, и поскольку 1+1 всегда равно 2, аналогично, если известны факторы в игре, которые приносят желаемый результат, то вы всегда можете достичь того же результата.

Например, если игра требует от игрока выбрать определенного персонажа с определенными усилениями, и результатом будет легкая битва с боссом, то этот шаблон будет постоянным, и все, кто выберет одни и те же варианты, будут иметь одинаковые результаты. Но, для обычного игрока это было бы невозможно, и псевдо-ГСЧ всегда казался бы истинным ГСЧ.

Почему геймеры ненавидят ГСЧ

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

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

Кто такой RNGesus?

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

Игроки, которые проигрывают, часто винят в своих поражениях злой ГСЧ, который выгоден их противникам. Там где зло, должен быть Бог – RNGesus.

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

Окончательный вердикт по ГСЧ – хорошо или плохо?

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

Алгоритм генератора случайных чисел действительно сохраняет непредсказуемость и интересность каждый раз, когда вы играете на одном уровне. Он стал важной частью многих игр, предлагая разнообразие, например, головоломки, карточные игры, ролевые игры и многие другие. Но, для геймеров, которые верят в навыки как в единственный способ пройти игру, ГСЧ подрывает их потенциал, когда вытаскивает что-то случайное из коробки.

Игры предназначены для развлечения и удовольствия. Если у вас хороший ГСЧ, вы сможете получить лучшие варианты, несмотря на низкие шансы. В случае плохого ГСЧ, вы получите худший результат, даже если вы играли в игру именно так, как должно. Правда в том, что это не то, что можно воспринимать так серьёзно, особенно если оно основано на алгоритме генератора случайных чисел.

«Случайности не случайны, всё это большой обман.» или как работают элементы рандома в играх.

ПРЕДИСЛОВИЕ

Доброго времени суток 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». Не могу точно уверять, что всё рабоатет именно так, как я говорю, поскольку доступа к исходному коду «движка» у простых пользователей нет, но всё намекает именно на такой метод.Торговцы появляются в случайное время (которое определяется через ГСПЧ) со случайным товаром в случайном месте. Но и тут к сожалению никакого по настоящему случайного элемента нет. Торговцы появляются в специально заготовленных местах, которые выбрали для них разработчики, и продают товар, который тоже не случайно генерируется (товар создают из специально заготовленных наборов предметов, который разработчики тоже успели ранее сделать). Также и цены на товар могут меняться в большую или меньшую сторону всего одной формулой (убавления процентов к изначальной цене товара), тем самым привлекая игрока «временной скидкой и ограниченным предложением», но всё это лишь иллюзия обмана.

Можно ли взломать генератор случайных чисел?

Что такое генератор случайных чисел?

Генератор случайных чисел (ГСЧ) – это современный эквивалент бросания кубиков или тасования карт.

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

Когда дело доходит до игр казино, лотерей, розыгрышей и подобных игр, ГСЧ принимают форму блоков кода, скрытых в программном обеспечении, которое обеспечивает «шанс» в азартных играх.

Рандомные ГСЧ и псевдо ГСЧ

ГСЧ в играх казино и игровых автоматах на самом деле не рандомные, а скорее «псевдо».

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

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

П севдо ГСЧ, с другой стороны, используют математический алгоритм или иным образом генерируются компьютером.

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

Как и во всем, что связано с математикой, если есть уравнение, то оно вовсе не случайное.

Все н е так уж и случайно

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

Правда лишь в том, что большинство ГСЧ не случайны.

Используя уравнение для создания случайных результатов, человек, знакомый с формулой, может фактически предсказать результаты.

Именно эта полуслучайность фактически делает компьютерные ГСЧ уязвимыми для хакеров.

На самом деле есть еще одна причина, по которой ГСЧ может быть только полуслучайным.

Е сли бы ГСЧ действительно работал случайным образом, казино не было довольно шансами игроков.

Поскольку казино – это бизнес, которому необходимо получать прибыль, чтобы быть на плаву, ГСЧ должны быть запрограммированы соответствующим образом.

Однако этот процесс незначительного уравновешивания шансов в пользу казино открывает слабое место для потенциальной атаки.

Итак, можно ли взломать ГСЧ?

Генераторы случайных чисел довольно сложны.

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

Вы должны быть полным идиотом, если думаете, что можете взломать Генератор случайных чисел.

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

Поскольку ГСЧ – это в основном повторные вызовы функций для генерации «случайных» чисел, все, что вам нужно, это ключ к функции.

Подобно шифру, используемому для декодирования секретного сообщения, знание критического «ключа» – это то, что может позволить вам взломать код.

Это число, также известное как «начальное число», представляет собой начальное целое число, которое вставляется в ГСЧ, с которого начинается вся операция.

Как только вы нашли семя, весь алгоритм можно легко расшифровать.

Если хакер может заменить псевдослучайный бит предсказуемым способом, краткий ответ заключается в том, что безопасность ГСЧ полностью скомпрометирована (и обычно не обнаруживается).

Но, легче сказать, чем сделать.

Есть несколько ярких примеров успешного взлома ГСЧ различными способами.

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

Заключение

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

Однако нельзя сказать, что это легко.

Эти компании тратят немалые деньги, чтобы убедиться, что их игры безопасны!

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

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

Ссылка на основную публикацию
Статьи c упоминанием слов:
Adblock
detector