Генератор случайных чисел. Разбираемся с принципом работы генератора случайных чисел

• Перевод

Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com - новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.

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

Проблема в том, что секретные ключи, которые использовал Netscape , были недостаточно случайными. Их длина составляла всего 40 бит, что означает около триллиона возможных комбинаций. Это кажется большим числом, но хакерам удалось взломать эти коды, даже на компьютерах 1990-х годов, примерно за 30 часов. Якобы случайное число, которое Netscape использовал для генерации секретного ключа, базировалось всего на трёх значениях: времени суток, идентификационном номере процесса и идентификационном номере материнского процесса - все они являются предсказуемыми. Из-за этого злоумышленник имел возможность сократить количество вариантов для перебора и найти нужный ключ гораздо раньше, чем предполагали в Netscape.

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

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

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

В течение последних лет в онлайне работает источник случайных чисел под названием Lavarand . Он был создан в 1996 году для автоматической генерации случайных значений путём обработки фотографий декоративного светильника - лавовой лампы, которая непредсказуемым образом меняет облик каждую секунду. С тех пор случайными значениями из этого источника воспользовались более миллиона раз.

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

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

Первая попытка Intel сделать лучший генератор случайных чисел на обычных ПК датируется 1999-м годом, когда компания Intel представила компонент Firmware Hub для чипсетов. Генератор случайных чисел в этом чипе (PDF) представляет собой аналоговый дизайн на базе кольцевого осциллятора, который регистрирует тепловой шум с резисторов, усиливает его и использует результирующий сигнал для изменения периода относительно медленного генератора тактовых импульсов. На каждый непредсказуемый «тик» этого медленного генератора микросхема накладывала частоту колебаний второго, быстрого генератора, который регулярно меняет своё значение между двумя бинарными состояниями: 0 и 1. В результате получается непредсказуемая последовательность нулей и единиц.

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

Вот почему в 2008 году Intel принялась за разработку генератора случайных чисел, который работает исключительно на цифровой основе. Исследователи компании в Хиллсборо (Орегон, США), совместно с инженерами Design Lab в Бангалоре (Индия) начали изучать ключевую проблему - как получить случайный поток битов без использования аналоговых схем.

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

Наш предыдущий аналоговый генератор был способен выдавать только пару сотен килобит случайных чисел в секунду, в то время как новый генерирует их потоком около 3 Гб/с. Он начинает работу, собирая практически случайные значения двух инвертеров блоками по 512 бит. В дальнейшем эти блоки разбиваются на пары 256-битных чисел. Конечно, если оригинальные 512 бит не полностью случайны, эти 256-битные числа тоже не будут полностью случайными. Но их можно математически скомбинировать таким образом, чтобы получить 256-битное число, близкое к идеальному.

ТРИ УРОВНЯ ЧИСЕЛ: Генератор случайных чисел Intel Bull Mountain предотвращает любые варианты предсказуемости с помощью трёхступенчатого процесса. Сначала цифровой контур генерирует поток случайных битов. Потом «нормализатор» (conditioner) генерирует на основе этого потока хорошие случайные начальные значения (random seeds). На третьем этапе генератор псевдослучайных чисел выдаёт поток цифр для использования в программном обеспечении.

Всё это лучше показано на простой иллюстрации. Предположите на секунду, что генератор случайных битов выдаёт 8-битные комбинации, то есть как бы числа в диапазоне от 0 до 255. Предположите также, что эти 8-битные числа не полностью случайны. Теперь представьте, что, к примеру, какой-то неуловимый изъян в цепи смещает выдаваемые значения в нижнюю часть диапазона. На первый взгляд, поток случайных чисел кажется хорошим, но если вы обработаете миллионы значений, то заметите, что числа из верхней части диапазона встречаются немножко реже, чем числа из нижней части.

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

Bull Mountain не работает с 8-битными числами: он работает, как уже было сказано, с 256-битными числами. И он их не перемножает, а производит более сложные криптографические операции. Но основная идея та же самая. Вы можете представить этот этап как «нормализацию» по устранению тех отклонений от случайного распределения чисел, которое может возникнуть в схеме с двумя инвертерами.

Нам действительно хочется хорошо спать по ночам, так что спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам. Таким образом, операции производятся только с качественными парами чисел.

Гарантированной случайности недостаточно, если случайные значения не выдаются достаточно быстро, чтобы соответствовать стандартам. Хотя аппаратный контур генерирует поток значительно быстрее, чем его предшественники, этого всё ещё недостаточно для некоторых современных задач. Чтобы Bull Mountain мог выдавать случайные числа так же быстро, как выдают поток программные генераторы псевдослучайных чисел, но при этом сохранять высокое качество случайных чисел, мы добавили ещё один уровень в схему. Здесь 256-битные случайные числа используются как криптографически надёжные начальные значения (random seeds) для генерации большого количества псевдослучайных 128-битных чисел. Поскольку 256-битные числа поступают с частотой 3 ГГц, то гарантируется достаточное количество материала для быстрой генерации криптографических ключей.

Новая инструкция под названием RdRand даёт возможность программе, которой нужны случайные числа, обратиться с запросом к аппаратному обеспечению, которое их производит. Созданная для 64-битных процессоров Intel, инструкция RdRand - это ключ к генератору Bull Mountain. Она извлекает 16-, 32- или 64-битные случайные значения и помещает их в регистр, доступный для программы. Инструкция RdRand была открыта для публики около года назад, и первым процессором Intel, который будет поддерживать её, станет Ivy Bridge. Новый чипсет работает на 37% быстрее, чем его предшественник, а размер его минимальных элементов уменьшен с 32 до 22 нанометров. Общее увеличение производительности хорошо сочетается с потребностями нашего генератора случайных чисел.

Хотя лавовые лампы выглядят круто , они впишутся не в каждый интерьер. Мы думаем, что наш подход к генерации случайных чисел, напротив, найдёт самое универсальное применение.

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

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

В зависимости от того, с кем вы разговариваете, генерация случайных чисел выглядит или тривиальной, или невозможной. Теоретически это невозможно. Джон фон Нейман, отец вычислительной техники, сказал: «Любой, кто считает, что существуют арифметические методы получения случайных цифр, безусловно, грешит». Он имел в виду, что невозможно получить что-то случайное в полном смысле слова на выходе такого детерминированного зверя, как компьютер. Это правда, но, к счастью, кое-что сделать мы можем. От генератора случайных чисел нам необходимо не то, чтобы числа были действительно случайными, а чтобы их невозможно было предсказать и воспроизвести. Если у нас будут выполнены эти два условия, мы сможем достичь безопасности.

С другой стороны, если мы нарушаем эти два условия, безопасности нет. В 1994 году в казино Монреаля установили компьютерный генератор случайных чисел для лотерей. Один наблюдательный игрок, проводивший в казино очень много времени, заметил, что выигрышные номера были каждый день одни и те же. Он успешно сорвал три Джек-Пота подряд и получил 600 000 долларов. (Как следует позаламывав руки, поскрежетав зубами и расследовав все, казино заплатило выигрыш.)

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

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

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

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

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

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

Понятие генератора чисел

Генератор случайных чисел для лотереи - некое устройство или заданная программа, которая выдает номера, находящиеся на выделенном интервале, в случайном (правильнее сказать, псевдослучайном) порядке. Для определенного вида лотерей, к примеру, "Спортлото", генерируются номера, находящиеся на интервале от 1 до 49.

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

Почему утверждается, что выданные результаты псевдослучайны и что генератор чисел для лотереи работает именно по такому принципу?

Функция RAND: понятие и способ использования

Функция RAND() - это программа или, к примеру, аппарат с детерминированным алгоритмом, который при одинаковых заданных условиях будет показывать постоянно одни и те же результаты. Но для того чтобы соблюдались условия истинной случайной последовательности, не должно быть никакой зависимости от начальных условий или параметров. Поэтому, чтобы избежать подобных случаев, дополнительно используется специальная процедура RANDOMIZE, которая убирает предсказуемость начальных условий, делая их случайными.

Кроме уже известного нам принципа генерации, используется еще один вид генератора лотереи. Рассмотрим его ниже.

Генератор цифр 6 из 45

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

Можно указать критерии отбора, например:

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

Генератор номеров: инструкция к пользованию

• По умолчанию установлен вывод пяти номеров. Поменяв настройки, можно получить до 250 случайных выигрышных комбинаций.
• Задаем диапазон, стандартно указывается от 0 до 36, вы же можете указать максимально до 9 999 999 999.
• Выбираем необходимую к нашему виду лотереи сортировку: по возрастанию, по убыванию или расположение цифр в случайном порядке.
• Следующим шагом указываем, как будут отделяться цифры друг от друга - запятой, точкой, пробелом, точкой с запятой.
• Избавляемся от случайных повторений, возникших в процессе выборки.

Таким образом, мы получаем качественно отобранные числа, которые могут быть самыми счастливыми и выигрышными.

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

Функция rand

В программировании на си, для получения случайных значений изобрели встроенные операторы, которые выдают нам требуемые результаты. И так, для создания случайного числа применяется функция rand , которая Оператор rand применяется для получения случайных чисел, которые возвращают диапазон от 0, и до определенной константы. Причем данная константа объявляется в системной директиве “stdlib.h”, там и базируется эта функция rand. Синтаксис этой функции прост: int m= rand(); т.е. выдается целое число. Опробовав оператор на практике, вы увидите, что появляющиеся числа при старте приложения идентичные. Оплошность заключается в том, что оператор rand работает с одним и тем же системным временем, которое сохранилось при компиляции. Данный генератор случайных чисел завязан на алгоритме изменения программного времени, то все работает неверно.

Теперь о srand и random

Для данной проблемы, незаменима была функция, которая б обнуляла встроенное время при каждом обращении к оператору rand, и разработчики ПО сделали функцию srand . Действие позволяет функции rand каждый раз обращаться не к установленному, а к текущему встроенному таймеру, что открывает возможность работать генератору верно – выдавать случайные значения. Недавно в программирования си ++ усовершенствовался механизм выдачи случайных чисел, из-за появления микросекунд. К тому же расширился диапазон значений, и все текущие новшества трансформировались в функцию random.

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

Устройство игрового Автомата

Современные игровые автоматы http://igrat-avtomati-wulcan.com отличаются достаточно сложным алгоритмом, который выдаёт выигрышные комбинации. Его можно разделить на части: Датчики в виде генераторов, счётчик который принимает оплату и выдаёт выигрыш, накопительная система для крупных призов в виде джек-пота, алгоритм в виде ядра для выдачи выигрышных средств. Данные Алгоритмы формируются в механическую конструкцию в виде слотов или рулетки.

Датчик случайных комбинаций и чисел. (ГСЧ)

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

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

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

Если рассматривать генератор случайных чисел с математической точки зрения-то, вычислить его работу различными формулами невозможно. Однако, если брать в расчёт уже выигрышную ситуацию, и вести расчёты с начало одной игры и до конца, то формулу написать всё-таки можно. Печально, что после выдачи джек-пота, генераций чисел продолжится по новой формуле, которая будет известна только по исходу игры.

Также существует мнение, что владелец автомата может выстроить настройки датчиков таким образом, что каждый выигрышный слот, будет выпадать, условно, через каждые 300 или 500 игр, однако, сам владелец не может точно знать через какое количество выведенных алгоритмов будет точный выигрыш. Но, то что датчики настраиваются это факт. Для того чтобы избежать конфликта интересов устанавливают не один датчик, а несколько, иначе хозяин игорного дома оставался всегда в плюсе, а в противном случае датчик мог бы вычислить какой ни будь умелец и очистить кассу казино почти легальным путём.

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