Как сгенерировать нужное число
Подробно о генераторах случайных и псевдослучайных чисел
Введение
Как отличить случайную последовательность чисел от неслучайной?
Чуть более сложный пример или число Пи
Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.
Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)
Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел. ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.
Энтропия – это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.
Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.
Уязвимости ГПСЧ
Линейный конгруэнтный ГПСЧ (LCPRNG)
Распространённый метод для генерации псевдослучайных чисел, не обладающий криптографической стойкостью. Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:
где a (multiplier), c (addend), m (mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа (seed) X0 и при разных его значениях получаются различные последовательности случайных чисел.
Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].
Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений
Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия [8], эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.
Предсказание результатов линейно-конгруэнтного метода
Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь [4](есть онлайн запуск) и здесь [5]. Описание алгоритма можно найти в [9].
Простая реализация конгруэнтного метода на Java.
Отправив 20 чисел на сайт [4], можно с большой вероятностью получить следующие. Чем больше чисел, тем больше вероятность.
Взлом встроенного генератора случайных чисел в Java
Многие языки программирования, например C(rand), C++(rand) и Java используют LСPRNG. Рассмотрим, как можно провести взлом на примере java.utils.Random. Зайдя в исходный код (jdk1.7) данного класса можно увидеть используемые константы
Метод java.utils.Randon.nextInt() выглядит следующим образом (здесь bits == 32)
Результатом является nextseed сдвинутый вправо на 48-32=16 бит. Данный метод называется truncated-bits, особенно неприятен при black-box, приходится добавлять ещё один цикл в brute-force. Взлом будет происходить методом грубой силы(brute-force).
Пусть мы знаем два подряд сгенерированных числа x1 и x2. Тогда необходимо перебрать 2^16 = 65536 вариантов oldseed и применять к x1 формулу:
до тех пор, пока она не станет равной x2. Код для brute-force может выглядеть так
Вывод данной программы будет примерно таким:
Несложно понять, что мы нашли не самый первый seed, а seed, используемый при генерации второго числа. Для нахождения первоначального seed необходимо провести несколько операций, которые Java использовала для преобразования seed, в обратном порядке.
И теперь в исходном коде заменим
crackingSeed.set(seed);
на
crackingSeed.set(getPreviousSeed(seed));
И всё, мы успешно взломали ГПСЧ в Java.
Взлом ГПСЧ Mersenne twister в PHP
Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. Основные преимущества алгоритма — это скорость генерации и огромный период 2^19937 − 1, На этот раз будем анализировать реализацию алгоритма mt_srand() и mt_rand() в исходном коде php версии 5.4.6.
Можно заметить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)). В бинарном представление операция выглядит так:
10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Видно, что первые 18 бит (выделены жирным) остались без изменений.
Напишем две функции для инвертирования битового сдвига и xor
Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так
Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister, то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister, и сможем легко определить каждое последующее значение, запустив php_mt_reload для известного набора значений.
Область для взлома
Если вы думаете, что уже нечего ломать, то Вы глубоко заблуждаетесь. Одним из интересных направлений является генератор случайных чисел Adobe Flash(Action Script 3.0). Его особенностью является закрытость исходного кода и отсутствие задания seed’а. Основной интерес к нему, это использование во многих онлайн-казино и онлайн-покере.
Есть много последовательностей чисел, начиная от курса доллара и заканчивая количеством времени проведенным в пробке каждый день. И найти закономерность в таких данных очень не простая задача.
Задание распределения для генератора псевдослучайных чисел
Для любой случайной величины можно задать распределение. Перенося на пример с картами, можно сделать так, чтобы тузы выпадали чаще, чем девятки. Далее представлены несколько примеров для треугольного распределения и экспоненциального распределения.
Треугольное распределение
Приведем пример генерации случайной величины с треугольным распределением [7] на языке C99.
Экспоненциальное распределение
Тесты ГПСЧ
Некоторые разработчики считают, что если они скроют используемый ими метод генерации или придумают свой, то этого достаточно для защиты. Это очень распространённое заблуждение. Следует помнить, что есть специальные методы и приемы для поиска зависимостей в последовательности чисел.
Одним из известных тестов является тест на следующий бит — тест, служащий для проверки генераторов псевдослучайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.
В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило, для этой цели используются различные статистические тесты, такие как DIEHARD или NIST. Эндрю Яо в 1982 году доказал, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
В интернете [10] можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.
Разбор алгоритмов генерации псевдослучайных чисел
Я работаю программистом в игровой студии IT Territory, а с недавних пор перешел на направление экспериментальных проектов, где мы проверяем на прототипах различные геймплейные гипотезы. И работая над одним из прототипов мы столкнулись с задачей генерации случайных чисел. Я хотел бы поделиться с вами полученным опытом: расскажу о псевдогенераторах случайных чисел, об альтернативе в виде хеш-функции, покажу, как её можно оптимизировать, и опишу комбинированные подходы, которые мы применяли в проекте.
Случайными числами пользовались с самого зарождения математики. Сегодня их применяют во всевозможных научных изысканиях, при проверке математических теорем, в статистике и т.д. Также случайные числа широко используются в игровой индустрии для генерирования 3D-моделей, текстур и целых миров. Их применяют для создания вариативности поведения в играх и приложениях.
Есть разные способы получения случайных чисел. Самый простой и понятный — это словари: мы предварительно собираем и сохраняем набор чисел и по мере надобности берём их по очереди.
К первым техническим способам получения случайных чисел можно отнести различные генераторы с использованием энтропии. Это устройства, основанные на физических свойствах, например, емкости конденсатора, шуме радиоволн, длительности нажатия на кнопку и так далее. Хоть такие числа действительно будут случайными, у таких способов отсутствует важный критерий — повторяемость.
ERNIE 1 — аппаратный генератор случайных чисел, созданный в 1957 году
Сегодня мы с вами поговорим о генераторах псевдослучайных чисел — вычисляемых функциях. К ним предъявляются следующие требования:
Длинный период. Любой генератор рано или поздно начинает повторяться, и чем позже это случится, тем лучше, тем непредсказуемее будет результат.
Портируемость алгоритма на различные системы.
Скорость получения последовательности. Чем быстрее, тем лучше.
Повторяемость результата. Это очень важный показатель. От него зависят все компьютерные игры, которые используют генераторы миров и различные системы с аналогичной функциональностью. Воспроизводимость даёт нам общий контент для всех, то есть мы можем генерировать на отдельных клиентах одинаковое содержимое. Также мы можем генерировать контент на лету в зависимости от входных данных, например, от местоположения игрока в мире. Ещё повторяемость случайных чисел используется для сохранения конкретного контента в виде зерна. То есть мы можем держать у себя только какое-то число или массив чисел, на основе которых будут генерироваться нужные нам параметры для заранее отобранного контента.
Зерно
Зерно — это основа генерирования. Оно представляет собой число или вектор чисел, который мы отправляем при инициализации генератора.
Решить эту проблему можно будет с помощью разделения одного генератора на несколько отдельных.
То есть берём несколько генераторов и задаём им разные зёрна. Но тут мы можем столкнуться со второй проблемой: нельзя гарантировать случайность i-тых элементов разных последовательностей с разными зёрнами.
На иллюстрации изображён результат генерирования нулевого элемента последовательности с помощью стандартной библиотекой C#. Мы постепенно меняли зерно от 0 до N.
Качество генератора
Предлагаю оценивать качество генератора с помощью изображений разного типа. Первый тип — это просто сгенерированная последовательность, который мы визуализируем с помощью первых трёх байтов полученного числа, конвертированных в RGB-представление.
Второй тип изображений — это пространственная интерпретация сгенерированной последовательности. Мы берём первые два бита числа (Х и Y), затем считаем количество попаданий в заданные точки и при визуализации вычитаем из 1 отношение количества попаданий в конкретный пиксель к максимальному количеству попаданий в какой-то другой пиксель. Черные пиксели — это точка, куда мы попадаем чаще всего, а белые — куда мы либо почти, либо совсем не попали.
Сравнение генераторов
Стандартные средства C#
Ниже я сравнил стандартный генератор из библиотеки С# и линейную последовательность. Первый столбец слева — это случайная последовательность от 0 до N в рамках одного зерна. В центре вверху показаны нулевые элементы случайных последовательностей при разных зёрнах от 0 до N. Вторая линейная последовательность — это числа от 0 до N, которые я визуализировал нашим алгоритмом.
В рамках одного зерна генератор действительно создаёт случайное число. Но при этом для i-тых элементов последовательностей с разным зерном прослеживается паттерн, который схож с паттерном линейной последовательности.
Линейный конгруэнтный генератор (LCG)
Давайте рассмотрим другие алгоритмы. Деррик Генри в 1949 году создал линейный конгруэнтный генератор, который подбирает некие коэффициенты и с их помощью выполняет возведения в степень со сдвигом.
При генерировании с одним зерном паттерн нигде не образуется. Но при использовании i-тых элементов в последовательностях с различными зёрнами паттерн начинает прослеживаться. Причём его вид будет зависеть исключительно от коэффициентов, которые мы подобрали для генератора. Например, есть частный случай линейного конгруэнтного генератора — Randu.
XorShift
Давайте теперь посмотрим на более свежую разработку — XorShift. Этот алгоритм просто выполняет операцию Xor и сдвигает байт в несколько раз. У него тоже будет прослеживаться паттерн для i-тых элементов последовательностей.
Вихрь Мерсенна
Неужели не существует генераторов без паттерна? Такой генератор есть — это вихрь Мерсенна. У этого алгоритма очень большой период, из-за чего появление паттерна на некотором количестве чисел физически невозможно. Однако и сложность этого алгоритма достаточно велика, в двух словах его не объяснить.
Unity — Random
Из других разработок стоит упомянуть генератор от компании Unity — Random, который используется в наборе стандартных библиотек для работы с Unity. При использовании первых элементов последовательности для разных зёрен у него будет прослеживаться паттерн, но при увеличении индекса паттерн исчезает и получается действительно случайная последовательность.
Перемешанный конгруэнтный генератор (PCG)
Противоположностью юнитёвского Random’a является перемешанный конгруэнтный генератор. Его особенность в том, что для первых элементов с различными зёрнами отсутствует ярко выраженный паттерн. Но при увеличении индекса он всё же возникает.
Длительность последовательного генерирования
Это важная характеристика генераторов. В таблице приведена длительность для алгоритмов в миллисекундах. Замеры проводились на моём MacBook Pro 2019 года.
0 seed 0..n
100 seed 0..n
Вихрь Мерсенна работает дольше всего, но даёт качественный результат. Стандартный генератор Random из библиотеки C# подходит для задач, в которых случайность вторична и не имеет какой-то значимой роли, то есть его можно использовать в рамках одного зерна. LCG (линейный конгруэнтный генератор) — это уже более серьёзный алгоритм, но требуется время на подбор нужных коэффициентов, чтобы получить адекватный паттерн. XorShift — самый быстрый алгоритм из всех рассмотренных. Его можно использовать там, где нужно быстро получить случайное значение, но помните про ярко выраженный паттерн с повторяющимся значением. Unity Random и PCG (перемешанный конгруэнтный генератор) сопоставимы по длительности работы, поэтому в разных ситуациях мы можем менять их местами: для длительных последовательностей использовать Unity, а для коротких — PCG.
Альтернатива генераторам — хеш-функции
Хеш-функции (функции свёртки) по определённому алгоритму преобразуют массив входных данных произвольной длины в строку заданной длины. Они позволяют быстрее искать данные, это свойство используется в хеш-таблицах. Также для хеш-функций характерна равномерность распределения, так называемый лавинный эффект. Это означает, что изменение малого количества битов во входном тексте приведёт к лавинообразному и сильному изменению значений выходного массива битов. То есть все выходные биты зависят от каждого входного бита.
Требования к генераторам на основе хеш-функций предъявляются те же самые, что и к простым генераторам, кроме длительности получения последовательности. Дело в том, что такому генератору можно отправить на вход одновременно зерно и требуемое состояние, потому что хеш-функции принимают на вход массивы данных.
Вот пример использования хеш-функции: можно либо создать конкретный класс, отправить туда зерно и постепенно запрашивать только конкретные состояния, либо написать статичную функцию, и отправить туда сразу и зерно, и конкретное состояние. Слева показан алгоритм работы MD5 из стандартной библиотеки C#.
Сделать генератор на основе хеш-функции можно так. Непосредственно при инициализации генератора задаём зерно, увеличиваем счётчик на 1 при запросе следующего значения и выводим результат хеша по зерну и счётчику.
Одни из самых популярных хеш-функций — это MurMur3 и WangHash.
MurMur3 не создаёт паттернов при использованиии i-тых элементов разных последовательностей при разных зёрнах. У WangHash статистические показатели образуют заметный паттерн. Но любую функцию можно прогнать через себя два раза и получить улучшенные показатели, как это показано в правом крайнем столбце WangDoubleHash.
Также сегодня активно развивается и набирает популярность алгоритм xxHash.
Забегая вперёд, скажу, что мы выбрали этот генератор для наших проектов и активно его используем.
Длительность последовательного генерирования у всех хеш-функций примерно одинакова. Однако у MD5 эта характеристика заметно отличается, но не потому, что алгоритм плохой, а потому что в стандартной реализации MD5 много разных состояний, которые влияют на быстродействие алгоритма.
Генераторы случайных чисел в разных ОС
Как-то поздним летним вечером мне пришлось разобраться, как устроены генераторы случайных чисел в Windows и Linux. Собственно, в этой статье я попробую привести саккумулированную информацию, и преподнести ее максимально простыми словами, без необходимости лезть в исходники, туториалы и статьи.
Генераторы псевдослучайных чисел
С развитием технологий и безопасности мы все больше и больше нуждаемся в действительно случайных числах, которые нельзя было бы предсказать извне. Почему? В первую очередь из-за шифрования, ведь с каждым годом растет количество пересылаемого трафика, и при этом хочется иметь достаточную степень безопасности наших данных. И вот в тот момент, когда нужно сгенерировать случайное число, у наших компьютеров возникают проблемы, поскольку они созданы быть максимально послушными, предсказуемыми и детерминированными для того, чтобы все результаты при одинаковых входных данных воспроизводились, иначе бы весь мир развалился.
Немного про энтропию
Код перемешивания в ChaCha
Создание ключа K и начального вектора V при помощи алгоритма обновления и дополнительных входных данных;
Создание необходимых псевдослучайных чисел, происходит шифрованием счетчика, при этом счетчик инкрементируется после каждого шага. Само шифрование происходит при помощи алгоритма AES с сгенерированным ключом. Таким образом этот алгоритм лишен необходимости дополнительного перемешивания начального состояния после каждого обращения, как это было в ChaCha.
Алгоритм обновления Создание выходных данных
Случайные события
Linux
Основные правила выбора событий, которые расцениваются как случайные. Во-первых, эти события должны быть недетерминированные. Во-вторых, их должно быть тяжело пронаблюдать извне. Эти случайные события добавляются в пул энтропии (просто массив чисел), перемешиваясь с его содержимым с помощью специальной CRC-подобной хэш-функции. Она выполняется быстро, чтобы ее можно было применять после каждого интересующего события в системе, и достаточно хороша, если предполагать, что случайные события заполняют пул не вредоносным образом. При этом при добавлении события в пул, происходит учет прибывшего количества энтропии.
В данный момент используется 4 типа источников случайных событий:
Информация от устройств, которая должна быть разной на физически разных машинах, например MAC адрес сетевой карты. Фактически, это не добавляет энтропии системе, но позволяет в очень плохих случаях (запуск с одного образа) на разных устройствах получать разные состояния;
Информация от таймера, прерывания, типа прерывания, значения;
Информация о времени поиска блока на диске. Однако на современных SSD это достаточно плохой источник случайности, так как у них время поиска сравнительно маленькое и примерно одинаковое всегда.
Чтобы инициализировать или переинициализировать ГПСЧ, необходимо из пула энтропии достать несколько случайных байт. Для этого, весь пул хэшируется алгоритмом SHA-1, а хэш-сумма выдается как случайный набор бит. При этом предпринимаются меры для обеспечения безопасности генератора в будущем. Во-первых, результат хэширования перемешивается с пулом, чтобы по выходному значению нельзя было восстановить текущее состояние. Во-вторых, происходит постоянная оценка оставшегося количества энтропии в пуле.
Windows
В качестве источников энтропии в Windows используются:
Как правило, не только Hyper-V при работе с Windows предоставляет такие улучшения. Многие гипервизоры «прикидываются» Hyper-V, чтобы обеспечивать такой же функционал и использовать встроенные возможности по повышению производительности при работе с Windows.
Во время старта системы данные с 7 источников (Seed файл, внешняя энтропия, TPM, RDRAND, ACPI-OEM0, UEFI и время старта) хэшируются SHA-512 и используются для инициализации SP800-90 AES-CTR-DRBG. Уже во время работы системы, данные предоставленные источником, помещаются в пул (за исключением первого раза, когда они идут сразу на переинициализацию корневого ГПСЧ).
Заключение
Как можно было заметить, многие источники случайных событий связаны с текущим состоянием машины, следовательно при виртуализации могут начаться проблемы. В Linux в комментариях к коду иногда открыто признается эта проблема. В Windows с Hyper-V (или другим гипервизором, «прикидывающимся» им) пытаются с этим бороться, но сама проблема все же иногда проявляется. Ситуация несколько облегчается, тем фактом, что в современных процессорах есть «железные» генераторы случайных чисел, а так же существуют виртуализированные генераторы, которые подсовывают случайные числа хостовой ОС гостевой. Ведь нельзя оставлять это на волю случая.
Генератор случайных чисел без программирования и даже компьютера: чем удивить юного программиста?
Сейчас, когда Arduino продолжает триумфальное шествие по планете, вряд ли кого-то удивишь схемами на макетной плате. Белые беспаечные макетные платы уже стали обязательным элементом наборов для гиков. И всё-таки я решила попробовать заинтересовать юных программистов из летней школы GoToCamp: провести для них мастер-класс по основам цифровой схемотехники, оканчивающийся сборкой интересного устройства – генератора случайных чисел.
При нажатии на кнопку, на индикаторе высвечивается случайное число. В чем же тут случайность, откуда она берется? Сразу раскрою секрет. Цифры генерируются по порядку: 0, потом 1, 2, и так далее. Хитрость вот в чем: очень высокая частота импульсов. Они выдаются так быстро, что цифры сливаются в одну на индикаторе. И совершенно невозможно угадать цифру!
Далее вы прочтете о том, как устроен такой генератор, и как собрать его самостоятельно.
Предыстория
Я работаю методистом в Центре инновационных образовательных технологий (ЦИОТ) МФТИ, а более конкретно — представляю направление поддержки развития технического творчества. А также участвую в разработке продуктов компании «Киберфизика».
В настоящий момент у нас активно развиваются два курса: основы электроники и программирование на Arduino. По каждому курсу мы делаем видеоматериалы, пишем методические рекомендации, собираем готовые наборы.
Курс по Arduino уже достаточно хорошо проработан: по нему готов замечательный онлайн-курс, получивший недавно награду EdCrunch OOC Award в номинации «Естественные и технические науки».
Но направление по основам электроники имеет большие перспективы: оно не настолько известно и популярно, как Arduino, а значит, есть большой простор для методической работы. В дружественной нам школе GoToCamp, например, Arduino есть уже давно, а вот «чистой» электроникой никто не занимался. Меня пригласили провести у ребят-старшеклассников небольшой мастер-класс. Стоит отметить, что ребята уже к тому моменту занимались Arduino, а значит, рассчитывать на вау-эффект от мигающего светодиода не стоило. Поэтому я как следует продумала программу мастер-класса, о результате напишу далее.
Как устроен «железный» генератор случайных чисел
Вот схема генератора случайных чисел, которую я предложила собрать (кликабельно): 
Выглядит сложно? На самом деле, она близка сердцу любого программиста. Ведь она сделана из четырех отдельных элементов – как программа из четырех функций. Далее компоненты просто стыкуются между собой: выход одного элемента перенаправляется на вход следующего.
Кто любит программировать в Linux, наверняка вспомнит концепцию pipe – таких «труб», которые обозначаются черточкой «|» и позволяют из многих маленьких программ (даже написанных на разных языках программирования) быстро составить работающий скрипт. Лично я эти «трубы» просто обожаю и часто использую. Чувствуешь себя водопроводчиком Марио
Теперь рассмотрим подробнее элементы этой схемы
Генератор импульсов
Режим работы таймера задается тремя элементами: резисторами R1 и R2 и конденсатором C1.
Просто подставив в эту формулу значения (или воспользовавшись онлайн-калькулятором, если лень считать), получаем частоту 40 Гц – то есть 40 колебаний в секунду. Соответственно, период будет 25 миллисекунд, и такую частую смену цифры на индикаторе человеческий глаз никогда не заметит.
Четвертый вывод отвечает за сброс и работает в инверсном режиме: чтобы произошел сброс, нужно замкнуть его на «минус». Поэтому через подтягивающий резистор он соединен с «плюсом» питания, а через кнопку с «минусом». Пока удерживаем кнопку «сброс», таймер стоит на месте и не выдает ничего – в это время можно полюбоваться на цифру на индикаторе.
Счётчик
Дешифратор
Если проводить опять аналогию с программированием, то дешифратор – это как библиотечная функция, которая двоичному числу ставит в соответствие набор светящихся сегментов на объекте типа «стандартный семисегментный индикатор». Бывают некоторые гики, которые сами это всё прописывают через микроконтроллер – я видела примеры и на Arduino, и на «чистых» ATMega. Не делайте так! Есть же специальная удобная микросхема для этого!
Здесь самое важное – это входы для двоичного числа (A, B, C, D) и выходы («a» … «f»), которые напрямую подключаются к соответствующим сегментам, которые точно так же промаркированы буквами.
Семисегментный индикатор
Слева – «подключение здорового человека». Каждый светодиод – через свой резистор. Справа – «подключение курильщика», только один резистор на всех. Несоблюдение этого правила приводит к тому, что некоторые светодиоды забирают себе больше тока, чем другие, и из-за этого сегменты светятся неравномерно.
Монтажная схема генератора случайных чисел
Вот и всё! Теперь, для тех, кто хочет сам собрать такую схему:
И список компонентов к ней:
Зачем это нужно?
Многие могут спросить: а зачем вообще нужен «железный» генератор случайных чисел? Не проще ли взять микроконтроллер, запрограммировать его… Ведь генератор случайных чисел — это уже давно известное всем готовое решение!
Тут мне вспомнилась история о том, как я в группе товарищей участвовала в техническом оснащении полевой ролевой игры «Чужие под землёй» (естественно, по мотивам известного фильма). Важным элементом игры был фонарики, которые должны были спустя некоторое время после включения «барахлить» и выключаться на время — чтобы создавать страшную и безысходную атмосферу. Для маленьких фонариков была разведена крошечная плата с микроконтроллером, настолько мелким, что стандартная библиотека генератора случайных чисел вместе с программой в него не влезала! Времени оптимизировать не было, заменять микроконтроллер тоже ни в коем случае было нельзя.
В итоге, я стала всерьез смотреть в сторону альтернативного варианта — брать значение со свободно «висящего» входа микроконтроллера, из АЦП. Даже протестировала его, и помню, что результат оказался не вполне случайным (некоторые значения систематически встречались чаще других), но для нужд игры вполне подходил. Забавно, что создавать псевдослучайное число из недр микроконтроллера чисто математическим способом оказалось сложнее, чем брать неопределенность напрямую, из окружающего мира…
Про аппаратные генераторы случайных чисел есть хорошая статья в Википедии.
Итоги
Мастер-класс, проведенный мной в GoToCamp, показал, что такую схему подростки-старшеклассники вполне могут собрать и понять, если им подробно объяснить все шаги и дать предварительный «загруз» в виде 10 более простых схем начального уровня.
Ребята получили важный опыт объединения нескольких простых схем в одну сложную. Мы объединили генератор импульсов, счётчик, дешифратор и семисегментный индикатор в схему — генератор случайных чисел. Обратите внимание, как легко это произошло благодаря понятным интерфейсам между маленькими схемами. Первая схема — генератор импульсов — на выходе имеет меандр, то есть прямоугольный сигнал. Частота этого меандра задает скорость работы счётчика. Счётчик, в свою очередь, «разговаривает» с дешифратором на языке двоичного кода. А тот, в свою очередь, передает данные в уже удобном для семисегментного индикатора виде.
На фото — тестирование генераторов на случайность при помощи секундомера в телефоне 🙂
Простота и логичность этой схемы обусловлена тем, что микросхемы в ней подобраны так, чтобы они наиболее легко стыковались между собой. Отсюда вывод на будущее как для инженеров, так и для программистов: старайтесь хорошо представлять себе взаимодействие компонентов между собой и подбирайте их так, чтобы они «общались» на максимально простом и понятном друг другу языке.
А главное – изучайте готовые решения и успешные практики! Многое уже придумано до нас. Изучайте «азбуку» цифровой электроники, даже если вы уже уверенный «ардуинщик» или хардкорный микроконтроллерщик. Никогда не знаешь, для чего могут пригодиться те или иные кейсы.
Схема позаимствована из Tronix Book 2 замечательного американского популяризатора схемотехники Гэри Гибсона. А рассказал нам об этой книжке не менее замечательный выпускник МФТИ, инженер, разработчик микропроцессоров Юрий Панчул, за что ему большое спасибо!
Автор – Татьяна Волкова, специалист по учебно-методической работе ЦИОТ МФТИ (направление поддержки развития технического творчества), разработчик продуктов «Киберфизики»