Как предсказать случайные числа

В этой статье маг Ольга Васильева отвечает на вопрос «Как предсказать случайные числа?».

Интересует взаимосвязь генератора случайных чисел и теории вероятностей. Что можно сказать по этому поводу?
В моем понятии генератор случайных чисел — это что-то, что построено только потому, что существует сама теория вероятностей. ГСЧ является применением ТВ на практике. Т.е. в принципе ГСЧ подчиняется законам ТВ, а соответственно в какой-то степени можно предсказывать тот или иной результат.

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

Представим, что имеется шанс выпадения орла равный 10%. С ГСЧ было проведено 9 опытов и выпадала решка. С одной стороны алгоритму без разницы на исход следующего опыта. С другой стороны вроде бы следующим должен(не знаю, уместно ли слово «должен») упасть орел. Можно ли утверждать, что с большой долей вероятности выпадет орел или же все просто как палка и шанс выпадения орла останется 10%? Скорее всего, что все просто как палка и шанс орла на 10м опыте останется 10%. Но, если я возьму 100 абсолютно одинаковых ГСЧ, на каждом из них соберу по 9 опытов подряд с результатом «решка» и начну спорить с кем-либо, что последующий 10ый опыт на каждом из 100 ГСЧ даст более чем 10 «орлов» в итоге, окажусь ли я правым или проиграю спор?

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

ГСЧ при неизменности исходных данных и запуске с исходной позиции будет вырабатывать одну и ту же последовательность. Стандартизованные ХЭШ- и ЭЦП-функции (есть стандарт РФ) — это классы ГСЧ. Новая случ. последовательность формируется, если изменились начальные условия. Для ХЭШ — это обрабатываемый текст. Для ЭЦП — текст, закрытый ключ и др. данные.

Редактировалось 1 раз(а). Последний 23.07.2013 10:50.

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

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

Форекс и казино- это не хаос,это другое.

Есть три известных:
1- порядковый номер генерации
2- хэш генерации
3- сгенерированое число

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

играл в jellyfish backgammon windows 98 se в 2000-2003 году, в конце уже в матче из 3-9 партий набирал больше чем самый сильный уровень программы, тупо интуицией «взломал» гсч машинки 🙂 человек сильнее любой машины, нужно только желание и ресурсы. с тех пор играю только в игры с полной информацией с машиной и то неохотно. всегда можно или посмотреть исходник или дизассемиблировать программу и «положить на лопатки»

Редактировалось 1 раз(а). Последний 19.06.2019 10:54.

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

В 2017 году специалисты Positive Technologies реализовали проекты по анализу безопасности и защите от киберпреступников как процедуры ICO, так и внедрения блокчейн-технологий. Результаты исследования оказались безрадостными: уязвимости в смарт-контрактах были выявлены в 71% проектов, в 23% проектов были выявлены недостатки, позволяющие атаковать инвесторов. В каждом проекте ICO в среднем содержалось пять уязвимостей. Однако злоумышленникам достаточно всего одной, чтобы присвоить деньги инвесторов.

Наше исследование включает следующие стадии:

1. Собрали 3649 умных контрактов с etherscan.io и GitHub.
2. Импортировали контракты в Elasticsearch, поисковик с открытым кодом.
3. С помощью веб-интерфейса Kibana с богатыми возможностями по поиску и фильтрации данных обнаружили 72 уникальные реализации ГПСЧ.
4. Проанализировав вручную каждый контракт, мы обнаружили, что 43 контракта были уязвимы.

Анализ выявил четыре категории уязвимых ГПСЧ:

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

Рассмотрим каждую категорию с примерами уязвимого кода.

Существует ряд переменных блока, которые могут быть по ошибке использованы как источники энтропии:

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

У каждого блока в блокчейне Ethereum есть хеш для верификации транзакций. Так называемая виртуальная машина Ethereum (EVM) позволяет получить хеш блока с помощью функции block.blockhash() . Функция ожидает числовой аргумент, который обозначает номер блока. Во время исследования мы обнаружили, что результат функции block.blockhash() часто некорректно используется при генерации случайных значений.

Существуют три основные уязвимые вариации генераторов, использующих хеш блока:

• block.blockhash(block.number) — хеш текущего блока;
• block.blockhash(block.number-1) — хеш последнего блока;
• block.blockhash() — хеш блока, который как минимум на 256 блоков старше.

Рассмотрим каждую из перечисленных вариаций.

Переменная состояния block.number позволяет узнать высоту данного блока. Когда майнер добавляет в блок транзакцию, которая выполняет код контракта, известен block.number будущего блока этой транзакции и контракту доступно его значение. Однако в момент выполнения транзакции в EVM хеш создаваемого блока еще неизвестен по очевидным причинам, и EVM всегда выдает ноль.

Некоторые контракты ошибочно интерпретируют значение выражения block.blockhash(block.number) . В таких контрактах хеш блока считается известным во время выполнения транзакции и используется как источник энтропии.

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

1. Игрок делает ставку, казино запоминает block.number транзакции.
2. При втором вызове контракта игрок запрашивает у казино выигрышный номер.
3. Казино извлекает сохраненный block.number, получает хеш блока по его номеру и затем использует хеш при генерации псевдослучайного числа.

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

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

Поэтому, если второй вызов не был сделан в пределах 256 блоков и не было проверки номера блока, псевдослучайное число будет известно заранее — это 0.

Самый нашумевший случай эксплуатации этой уязвимости — взлом лотереи SmartBillions. Контракт неверно проверял возраст block.number, и это привело к тому, что игрок выиграл 400 ETH: после создания 256 блоков он запросил предсказуемый выигрышный номер, который отправил в первой транзакции.

Подписка позволит тебе в течение указанного срока читать ВСЕ платные материалы сайта. Мы принимаем оплату банковскими картами, электронными деньгами и переводами со счетов мобильных операторов. Подробнее о подписке

Заинтересовала информация, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для материалов, опубликованных более двух месяцев назад.

Вы когда-нибудь задумывались, как работает Math.random()? Что такое случайное число и как оно получается? А представьте вопрос на собеседовании — напишите свой генератор случайных чисел в пару строк кода. И так, что же это такое, случайность и возможно ли ее предсказать?

Меня очень увлекают различные IT головоломки и задачки и генератор случайных чисел — одна из таких задачек. Обычно в своем телеграм канале я разбираю всякие головоломки и разные задачи с собеседований. Задача про генератор случайных чисел набрала большую популярность и мне захотелось увековечить ее в недрах одного из авторитетных источников информации — то бишь здесь, на Хабре.

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

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

Этот источник используется для накопления энтропии с последующим получением из неё начального значения (initial value, seed), которое необходимо генераторам случайных чисел (ГСЧ) для формирования случайных чисел.

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

Энтропия — это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.

Выходит, что чтобы создать псевдослучайную последовательность нам нужен алгоритм, который будет генерить некоторую последовательность на основании определенной формулы. Но такую последовательность можно будет предсказать. Тем не менее, давайте пофантазируем, как бы могли написать свой генератор случайных чисел, если бы у нас не было Math.random()

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

Генератор псевдослучайных чисел (ГПСЧ, англ. pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

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

Эта функция генерит нам последовательность 01010101010101… и назвать ее даже псевдослучайной никак нельзя. Чтобы генератор был случайным, он должен проходить тест на следующий бит. Но у нас не стоит такой задачи. Тем не менее даже без всяких тестов мы можем предсказать следующую последовательность, значит такой алгоритм в лоб не подходит, но мы в нужном направлении.

А что если взять какую-то известную, но нелинейную последовательность, например число PI. А в качестве значения для модуля будем брать не 2, а что-то другое. Можно даже подумать на тему меняющегося значения модуля. Последовательность цифр в числе Pi считается случайной. Генератор может работать, используя числа Пи, начиная с какой-то неизвестной точки. Пример такого алгоритма, с последовательностью на базе PI и с изменяемым модулем:

Но в JS число PI можно вывести только до 48 знака и не более. Поэтому предсказать такую последовательность все так же легко и каждый запуск такого генератора будет выдавать всегда одни и те же числа. Но наш генератор уже стал показывать числа от 0 до 9.

Мы получили генератор чисел от 0 до 9, но распределение очень неравномерное и каждый раз он будет генерировать одну и ту же последовательность.

Мы можем взять не число Pi, а время в числовом представлении и это число рассматривать как последовательность цифр, причем для того, чтобы каждый раз последовательность не повторялась, мы будем считывать ее с конца. Итого наш алгоритм нашего ГПСЧ будет выглядеть так:

Вот это уже похоже на генератор псевдослучайных чисел. И тот же Math.random() — это ГПСЧ, про него мы поговорим чуть позже. При этом у нас каждый раз первое число получается разным.

Собственно на этих простых примерах можно понять как работают более сложные генераторы случайных числе. И есть даже готовые алгоритмы. Для примера разберем один из них — это Линейный конгруэнтный ГПСЧ(LCPRNG).

Линейный конгруэнтный ГПСЧ(LCPRNG) — это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой формулой. Получаемая последовательность зависит от выбора стартового числа — т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ — это проблема. Если говорить про другие задачи, то эти свойства — могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

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

Метод Math.random() возвращает псевдослучайное число с плавающей запятой из диапазона [0, 1), то есть, от 0 (включительно) до 1 (но не включая 1), которое затем можно отмасштабировать до нужного диапазона. Реализация сама выбирает начальное зерно для алгоритма генерации случайных чисел; оно не может быть выбрано или сброшено пользователем.

Как устроен алгоритм Math.random() — интересный вопрос. До недавнего времени, а именно до 49 Chrome использовался алгоритм MWC1616:

Именно этот алгоритм генерит нам последовательность псевдослучайных чисел в промежутке между 0 и 1.

Чем это было чревато? Есть такой квест: alf.nu/ReturnTrue

В нем есть задача:

Что нужно вписать вместо вопросов, чтобы функция вернула true? Кажется что это невозможно. Но, это возможно, если вы заглядывали в спеку и видели алгоритм ГПСЧ V8. Решение этой задачи в свое время мне показал Роман Дворнов:

Этот код работал в 70% случаев для Chrome +21