Схемы генераторов случайных чисел

Лекция 9. Генераторы случайных чисел

В основе метода Монте-Карло (см. Лекцию 8. Статистическое моделирование) лежит генерация случайных чисел, которые должны быть равномерно распределены в интервале (0; 1).

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

Математическое ожидание и дисперсия такой последовательности, состоящей из случайных чисел , должны быть следующими (если это действительно равномерно распределенные случайные числа в интервале от 0 до 1):

Если пользователю потребуется, чтобы случайное число x находилось в интервале (a; b), отличном от (0; 1), нужно воспользоваться формулой x = a + (ba) · r, где r — случайное число из интервала (0; 1). Законность данного преобразования демонстрируется на рис. 9.1.

Рис. 9.1. Схема перевода числа из интервала (0; 1) в интервал (a; b)

Теперь x — случайное число, равномерно распределенное в диапазоне от a до b.

За эталон генератора случайных чисел (ГСЧ) принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0; 1). За одно обращение данный генератор возвращает одно случайное число. Если наблюдать такой ГСЧ достаточно длительное время, то окажется, что, например, в каждый из десяти интервалов (0; 0.1), (0.1; 0.2), (0.2; 0.3), …, (0.9; 1) попадет практически одинаковое количество случайных чисел — то есть они будут распределены равномерно по всему интервалу (0; 1). Если изобразить на графике k = 10 интервалов и частоты Ni попаданий в них, то получится экспериментальная кривая плотности распределения случайных чисел (см. рис. 9.2).

Рис. 9.2. Частотная диаграмма выпадения случайных чисел,
порождаемых реальным генератором

Заметим, что в идеале кривая плотности распределения случайных чисел выглядела бы так, как показано на рис. 9.3. То есть в идеальном случае в каждый интервал попадает одинаковое число точек: Ni = N/k, где N — общее число точек, k — количество интервалов, i = 1, …, k.

Рис. 9.3. Частотная диаграмма выпадения случайных чисел,
порождаемых идеальным генератором теоретически

Следует помнить, что генерация произвольного случайного числа состоит из двух этапов:

  • генерация нормализованного случайного числа (то есть равномерно распределенного от 0 до 1);
  • преобразование нормализованных случайных чисел ri в случайные числа xi, которые распределены по необходимому пользователю (произвольному) закону распределения или в необходимом интервале.

Генераторы случайных чисел по способу получения чисел делятся на:

  • физические;
  • табличные;
  • алгоритмические.

Физические ГСЧ

Примером физических ГСЧ могут служить: монета («орел» — 1, «решка» — 0); игральные кости; поделенный на секторы с цифрами барабан со стрелкой; аппаратурный генератор шума (ГШ), в качестве которого используют шумящее тепловое устройство, например, транзистор (рис. 9.4–9.5).

Рис. 9.4. Схема аппаратного метода генерации случайных чисел

Рис. 9.5. Диаграмма получения случайных чисел аппаратным методом

Задача «Генерация случайных чисел при помощи монеты»

Сгенерируйте случайное трехразрядное число, распределенное по равномерному закону в интервале от 0 до 1, с помощью монеты. Точность — три знака после запятой.

Первый способ решения задачи
Подбросьте монету 9 раз, и если монета упала решкой, то запишите «0», если орлом, то «1». Итак, допустим, что в результате эксперимента получили случайную последовательность 100110100.

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

Итак, 1: интервал [0; 1] делится пополам — [0; 0.5] и [0.5; 1], — выбирается правая половина, интервал сужается: [0.5; 1]. Следующее число, : интервал [0.5; 1] делится пополам — [0.5; 0.75] и [0.75; 1], — выбирается левая половина [0.5; 0.75], интервал сужается: [0.5; 0.75]. Следующее число, : интервал [0.5; 0.75] делится пополам — [0.5; 0.625] и [0.625; 0.75], — выбирается левая половина [0.5; 0.625], интервал сужается: [0.5; 0.625]. Следующее число, 1: интервал [0.5; 0.625] делится пополам — [0.5; 0.5625] и [0.5625; 0.625], — выбирается правая половина [0.5625; 0.6250], интервал сужается: [0.5625; 0.6250].

По условию точности задачи решение найдено: им является любое число из интервала [0.5625; 0.6250], например, 0.625.

В принципе, если подходить строго, то деление интервалов нужно продолжить до тех пор, пока левая и правая границы найденного интервала не СОВПАДУТ между собой с точностью до третьего знака после запятой. То есть с позиций точности сгенерированное число уже не будет отличимо от любого числа из интервала, в котором оно находится.

Второй способ решения задачи
Разобьем полученную двоичную последовательность 100110100 на триады: 100, 110, 100. После перевода этих двоичных чисел в десятичные получаем: 4, 6, 4. Подставив спереди «0.», получим: 0.464. Таким методом могут получаться только числа от 0.000 до 0.777 (так как максимум, что можно «выжать» из трех двоичных разрядов — это 1112 = 78) — то есть, по сути, эти числа представлены в восьмеричной системе счисления. Для перевода восьмеричного числа в десятичное представление выполним:
0.4648 = 4 · 8 –1 + 6 · 8 –2 + 4 · 8 –3 = 0.601562510 = 0.60210.
Итак, искомое число равно: 0.602.

Табличные ГСЧ

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

Таблица 9.1. Случайные цифры. Равномерно распределенные от 0 до 1 случайные числа
Случайные цифры Равномерно распределенные от 0 до 1 случайные числа
0.929
0.204
0.269

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

Ниже находится таблица, содержащая 500 абсолютно случайных проверенных чисел (взято из книги И. Г. Венецкого, В. И. Венецкой «Основные математико-статистические понятия и формулы в экономическом анализе»).

5489 5583 3156 0835 1988 3912 0938 7460 0869 4420
3522 0935 7877 5665 7020 9555 7379 7124 7878 5544
7555 7579 2550 2487 9477 0864 2349 1012 8250 2633
5759 3554 5080 9074 7001 6249 3224 6368 9102 2672
6303 6895 3371 3196 7231 2918 7380 0438 7547 2644
7351 5634 5323 2623 7803 8374 2191 0464 0696 9529
7068 7803 8832 5119 6350 0120 5026 3684 5657 0304
3613 1428 1796 8447 0503 5654 3254 7336 9536 1944
5143 4534 2105 0368 7890 2473 4240 8652 9435 1422
9815 5144 7649 8638 6137 8070 5345 4865 2456 5708
5780 1277 6316 1013 2867 9938 3930 3203 5696 1769
1187 0951 5991 5245 5700 5564 7352 0891 6249 6568
4184 2179 4554 9083 2254 2435 2965 5154 1209 7069
2916 2972 9885 0275 0144 8034 8122 3213 7666 0230
5524 1341 9860 6565 6981 9842 0171 2284 2707 3008
0146 5291 2354 5694 0377 5336 6460 9585 3415 2358
4920 2825 5238 5402 7937 1993 4332 2327 6875 5230
7978 1947 6380 3425 7267 7285 1130 7722 0164 8573
7453 0653 3645 7497 5969 8682 4191 2976 0361 9334
1473 6938 4899 5348 1641 3652 0852 5296 4538 4456
8162 8797 8000 4707 1880 9660 8446 1883 9768 0881
5645 4219 0807 3301 4279 4168 4305 9937 3120 5547
2042 1192 1175 8851 6432 4635 5757 6656 1660 5389
5470 7702 6958 9080 5925 8519 0127 9233 2452 7341
4045 1730 6005 1704 0345 3275 4738 4862 2556 8333
5880 1257 6163 4439 7276 6353 6912 0731 9033 5294
9083 4260 5277 4998 4298 5204 3965 4028 8936 5148
1762 8713 1189 1090 8989 7273 3213 1935 9321 4820
2023 2589 1740 0424 8924 0005 1969 1636 7237 1227
7965 3855 4765 0703 1678 0841 7543 0308 9732 1289
7690 0480 8098 9629 4819 7219 7241 5128 3853 1921
9292 0426 9573 4903 5916 6576 8368 3270 6641 0033
0867 1656 7016 4220 2533 6345 8227 1904 5138 2537
0505 2127 8255 5276 2233 3956 4118 8199 6380 6340
6295 9795 1112 5761 2575 6837 3336 9322 7403 8345
6323 2615 3410 3365 1117 2417 3176 2434 5240 5455
8672 8536 2966 5773 5412 8114 0930 4697 6919 4569
1422 5507 7596 0670 3013 1351 3886 3268 9469 2584
2653 1472 5113 5735 1469 9545 9331 5303 9914 6394
0438 4376 3328 8649 8327 0110 4549 7955 5275 2890
2851 2157 0047 7085 1129 0460 6821 8323 2572 8962
7962 2753 3077 8718 7418 8004 1425 3706 8822 1494
3837 4098 0220 1217 4732 0150 1637 1097 1040 7372
8542 4126 9274 2251 0607 4301 8730 7690 6235 3477
0139 0765 8039 9484 2577 7859 1976 0623 1418 6685
6687 1943 4307 0579 8171 8224 8641 7034 3595 3875
6242 5582 5872 3197 4919 2792 5991 4058 9769 1918
6859 9606 0522 4993 0345 8958 1289 8825 6941 7685
6590 1932 6043 3623 1973 4112 1795 8465 2110 8045
3482 0478 0221 6738 7323 5643 4767 0106 2272 9862

Алгоритмические ГСЧ

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

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

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

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

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

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

Содержание

Источники случайных чисел

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

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

Генератор псевдослучайных чисел включён в состав многих современных процессоров (напр., семейства x86)

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

Детерминированные ГПСЧ

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

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и составляет около 2 n/2 , где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2 n . Если порождаемая ГПСЧ последовательность сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.

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

  • Слишком короткий период/периоды.
  • Последовательные значения не являются независимыми.
  • Некоторые биты «менее случайны», чем другие.
  • Неравномерное одномерное распределение.
  • Обратимость.

В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим [1] [2] , что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (2 19937 −1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако, существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.

ГПСЧ с источником энтропии или ГСЧ

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

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

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

В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. Сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в PGP и Yarrow [4] , или взаимодействия между потоками, как, например, в Java SecureRandom.

Пример простейшего ГСЧ с источником энтропии

Если в качестве источника энтропии использовать текущее время, то для получения натурального числа от 0 до N достаточно вычислить остаток от деления текущего времени в миллисекундах на число N+1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.

Примеры ГСЧ и источников энтропии

Источник энтропии ГПСЧ Достоинства Недостатки
/dev/random в UNIX/Linux Счётчик тактов процессора, однако собирается только во время аппаратных прерываний LFSR, с хешированием выхода через SHA-1 Есть во всех Unix, надёжный источник энтропии Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
Yarrow от Брюса Шнайера [4] Традиционные методы AES-256 и SHA-1 маленького внутреннего состояния Гибкий криптостойкий дизайн Медленный
Microsoft CryptoAPI Текущее время, размер жёсткого диска, размер свободной памяти, номер процесса и NETBIOS-имя компьютера MD5-хеш внутреннего состояния размером в 128 бит Встроен в Windows, не «застревает» Сильно зависит от используемого криптопровайдера (CSP).
Java SecureRandom Взаимодействие между потоками SHA-1-хеш внутреннего состояния (1024 бит) Большое внутреннее состояние Медленный сбор энтропии
Chaos от Ruptor [5] Счётчик тактов процессора, собирается непрерывно Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора Пока самый быстрый из всех, большое внутреннее состояние, не «застревает» Оригинальная разработка, свойства приведены только по утверждению автора
RRAND от Ruptor [6] Счётчик тактов процессора Зашифровывание внутреннего состояния поточным шифром EnRUPT в authenticated encryption режиме (aeRUPT) Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает» Оригинальная разработка, свойства приведены только по утверждению автора. Шифр EnRUPT не является криптостойким.

ГПСЧ в криптографии

Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ.  seed ), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

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

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Примеры криптостойких ГПСЧ

Циклическое шифрование

В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.

ANSI X9.17

ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:

  1. Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
  2. Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
  3. Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.
  • DTi — значение даты и времени на начало i-ой стадии генерации.
  • Vi — начальное значение для i-ой стадии генерации.
  • Ri — псевдослучайное число, созданное на i-ой стадии генерации.
  • K1, K2 — ключи, используемые на каждой стадии.

Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.

Аппаратные ГПСЧ

Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы и также держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA- или ASIC-ячеек). Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, поэтому до сих пор все известные аппаратные ГПСЧ были взломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR-генераторами, и оба были взломаны с помощью алгебраических атак.

Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры (DES, AES) и хеш-функции (SHA-1) в поточных режимах.

Генератор случайных чисел на микросхемах

Генератор случайных чисел, также разработанный горьковчанами (Радио, 1984, № 1, с. 54), очень прост в изготовлении и наглядно демонстрирует работу триггерных счетчиков (рис. 4.10). Он очень надежен в работе. За две лагерные смены кружковцы в пионерлагере Иссары успели сделать четыре таких автомата, поступивших затем на игровую площадку лагеря.

На элементах D1.1 и D1.2 выполнен генератор прямоугольных импульсов, следующих с частотой 500. 900 кГц. Когда нажата кнопка S1, импульсы генератора поступают на счетчик, состоящий из трех триггеров, каждый из которых собран на двух логических элементах 2И-НЕ (D1.3 и D1.4, D2.1 и D2.2, D2.3 и D2.4). Через ограничительные резисторы (R4, R7, R10) к каждому триггеру подключен светодиод (VI—V3). Поскольку частота поступающих на триггеры импульсов высока, светятся все светодиоды.

Как только кнопку отпускают, триггеры устанавливаются в произвольном состоянии, отображаемом свето-диодами — каждый из них обозначен соответствующей цифрой (1, 2 и 4). Сумма чисел у горящих светодиодов и есть количество набранных очков в данной попытке.

Рис. 4.10. Принципиальная схема генератора случайных чисел

Рис. 4.11. Радиомина

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

Соревнования юных саперов

На территории лагеря в различных местах закладываются радиомины, смонтированные старшими ребятами по схеме, приведенной на рис. 4.11. Это немного измененная схема сигнализатора обрыва проводника, подключенного к контактам X1.

Этот сигнализатор состоит из двух, мультивибраторов. Один из них (на транзисторах V1 и V2) служит нагрузкой другого (на транзисторах V4 и V5). Второй мультивибратор отличается от первого большей емкостью конденсатора обратной связи С 4 . Поэтому его частота сравнительно низка—около 1 Гц. Первый мультивибратор подключается к источнику питания на короткий промежуток времени (0,2. 0,3 с), в течение которого звучит, акустическая головка В 1 .

Несложное преобразование сигнализатора обрыва проводника позволит использовать его как мину в соревнованиях юных саперов или при проведении военной игры Зарница. Для этого нужно включить вместо динамической головки катушку (например, от электромагнитного реле) сопротивлением 4. 10 Ом. Ее можно изготовить самим, намотав на швейную катушку из-под ниток провод ПЭВ-1 диаметром 0,25. 0,4 мм до заполнения. Катушку зарывают в землю на небольшую глубину, а электронное устройство маскируют поблизости от нее. При включении питания вокруг катушки образуется переменное магнитное поле звуковой частоты.

Чтобы обнаружить катушку-мину, потребуется миноискатель. Чувствительным миноискателем может быть карманный радиоприемник, настроенный на свободный от радиостанций участок диапазона длинных волн. Звук в приемнике начнет прослушиваться при приближении его к катушке мины на расстояние 0,5.. .1 м. Он появляется из-за того, что колебания мультивибратора, как известно, помимо основной частоты содержат множество гармоник, то есть сигналов, частота которых кратна основной. Их и улавливает приемник.

Еще лучших результатов можно достигнуть, если катушку мины заменить несколькими витками провода диаметром 0,4. 0,5 мм в эмалевой изоляции, уложенного непосредственно в землю. Диаметр витков 1. 3 м, общее сопротивление такой катушки должно быть 4. 10 Ом. Теперь сигнал мины будет хорошо прослушиваться радиоприемником и внутри катушки, и в нескольких метрах от нее.

Соревнования юных радиолюбителей в пионерлагере

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

Рис. 4.12. Детекторный приемник, смонтированный на картонной панели

В ходе таких соревнований особенно проявляются все достоинства радиокубиков , из которых соревнующиеся буквально в считанные минуты собирают генераторы сигналов азбуки Морзе, различные мультивибраторы, мигалки со световой и звуковой индикацией, радиоприемники, генераторы различных звуковых сигналов и другие самоделки. Соревнования на радиокубиках наглядно демонстрируют степень овладения теоретическими основами электроники; После сборки схем из радиокубиков проводятся состязания на звание лучшего радиомонтажника-конструктора. В этом случае продолжительность каждого состязания не должна превышать 15. 20 мин; ведь зрители — народ нетерпеливый. При этом нужно учитывать, что главное — не сложность поставленных задач, а доступность их выполнения. В то же время ребята должны продемонстрировать здесь свои знания, смекалку и сноровку. В спокойной обстановке на выполнение монтажа, ремонта и испытания готовой конструкции уходит не более 10. 15 мин.

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

Каркас катушки склеивают из бумаги на отрезке круглого ферритового стержня марки 400НН или 600НН длиной 40. 45 мм, который будет выполнять роль подстроеч-ного сердечника контурной катушки. Для настройки приемника на радиостанцию длинноволнового диапазона контурная катушка L1 может содержать 250. 300 витков провода ПЭВ-1 или ПЭЛ 0,15. 0,18, намотанных пятью секциями (для уменьшения собственной емкости) по равному числу витков в каждой секции, а для приема радиостанции средневолнового диапазона — около 80 витков такого же провода, уложенных на каркас виток к витку.

Детектором (VI) может быть любой точечный диод. Головные телефоны В 1 — высокоомные , например ТОН-2, ТА-4. Емкость конденсатора С 1 может быть до 470. 510 пФ, конденсатора С2 — от 1000 пФ до 0,01 мкФ.

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

Определяя призеров соревнования, судейская коллегия учитывает не только время, затраченное участниками на выполнение задания, но и коэффициент качества монтажа. Можно предложить такие значения этого коэффициента: за хороший монтаж — 0,1, за посредственный — 0,5, за плохой— 1,0. Например, приемник сдан судейской коллегии через 380 с после команды начала монтажа. Коэффициент качества монтажа — 0,5. Участнику, следовательно, начисляется 380 х 0,5 = 190 очков. У кого меньше очков, тот победитель.

Откуда берутся результаты игр? Генератор случайных чисел казино

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

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

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

Можно ли взломать ГПСЧ?

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

Есть как минимум одно подтвержденное свидетельство того, что именно определение работы алгоритма давало игрокам преимущество. Алекс из России купил игровой аппарат Mark VI от Aristocrat и определил как он генерирует случайные числа.

Затем в реальных казино он мог определять, в какой точно момент система сгенерирует числа, привязанные к крупным выплатам. Это относительно недавний случай, который был предан гласности в 2011 году. Подробнее о нем мы рассказывали в этой статье.

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

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

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

Для того, чтобы иметь более четкое представление о чем идет речь, разберем ранний метод формирования псевдослучайных чисел. Это самый простой и понятный метод, придуманный Джоном фон Нейманом в 40-х годах. Берется базовое четырехзначное число, возводится в квадрат. Затем из получившегося числа берутся четыре цифры находящиеся в середине. Затем дальше и дальше.

Например, 7839 в квадрате дает 61449921. Это был бы результат одного раунда игры. Затем берем четыре числа из середины 61449921 и снова возводим в квадрат, получаем 20241001 — это результат другого раунда игры. И так продолжается дальше, после 20241001 получаем 5764801. Если цифр получается семь, то для следующего числа берутся со второй по пятую цифры.

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

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

Сейчас используются намного более продвинутые математические формулы. Например, ниже представлена лишь часть описания метода «Вихрь Мерсена» из Wikipedia. Это уже далеко не возведение в квадрат.

Реальный ГСЧ

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

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

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

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

Какие алгоритмы используют разработчики?

По данным двух отчетов iTechLabs за 2012 и 2015 года, разработчик NetEnt использует алгоритм Fortuna, который основывается на постоянной смене исходного числа. Эти исходные числа он получает из многочисленных источников энтропии. В качестве этих источников могут быть движение компьютерной мыши, шум кулера и т.д. Они дают непредсказуемые числа, которые никто не должен определить.

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

Методы генерации случайных чисел

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

Многие вещи можно сделать и без генератора случайных чисел. Вот например, такая последовательность чисел не может считаться случайной: <0, 1, 2, 3, 4, 5, 6, 7>. Здесь, зная предыдущее число, очень легко угадать следующее. Существуют другие последовательности. Например: <0, 1, 3, 2, 6, 7, 5, 4>. Здесь, угадать следующее число значительно сложнее. Подобные последовательности иногда удобно использовать в программах.

Генераторы случайных чисел по способу получения чисел делятся на:

Существует 3 способа генерации случайных чисел:

1. Аппаратный. (простой пример это монетка)

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

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

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

2. Табличный. Случайные числа оформлены в виде таблицы, которая хранится в оперативной памяти или на внешнем носителе. Плюс: можно воспроизводить неоднократно одну и ту же последовательность псевдослучайных чисел. Минус: запас чисел ограничен, неэффективное использование вычислительных ресурсов компьютера (таблица больших размеров хранится в памяти, к которой постоянно обращаются). Используется редко.

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

Требования к идеальному генератору случайных чисел:

1. Генерируемые числа имеют квазиравномерную распределимость (квази=почти).

2. Числа в последовательности статически независимы

3. Последовательность воспроизводима

4. Алгоритм функционирует при минимальных затратах вычислительных ресурсов

5. Эксперимент с использованием имитационной модели системы, интерпретация и реализация результатов.

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

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

Экспериментирование – процесс осуществления имитации с целью получения желаемых данных и анализа чувствительности.

Интерпретация – построение выводов по данным, полученным путем имитации.

Реализация – практическое использование модели и результатов моделирования.

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

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

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

Чтобы иметь максимальные шансы успешного применения результатов имитационного исследования, имитационная модель должна быть:

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: