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

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

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

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

Основными блоками этого устройства являются генератор импульсов, собранный на трех элементах 3И — НЕ (D4.1—D4.3) микросхемы D4, и счетная декада на микросхемах D1 — D3 и транзисторах V1—V10 с цифровым газоразрядным индикатором H1 на выходе. Частота следования импульсов, формируемых генератором, определяется постоянной времени цепи R5C2 и равна приблизительно 30 кГц.

При нажатии кнопки S1 импульсы генератора поступают на вход десятичного счетчика, собранного на четырех D-триггерах микросхем D2, D3. За время удержания этой кнопки пальцем (1. 3 с) счетчик многократно переполняется» поэтому число, записанное в нем после отпускания кнопки, практически случай» ное. В нем все четыре D-триггера соединены между собой последовательно и работают в счетном режиме, т. е. положительный перепад напряжения на входе каждого триггера меняет его состояние на противоположное предыдущему. Для обеспечения такого режима работы триггера его информационный вход D соединен с инверсным выходом этого же триггера. Коэффициент пересчета 10 получен благодаря использованию обратной связи с инверсного выхода счетчика через цепочку C1R3R4.

Работа счетчика поясняется таблицей истинности:

В этой таблице Q1 Q2, Q3 и Q4 — прямые выходы триггеров D2.1, D2.2, D3.1 и D3.2 соответственно. Цифры в строках обозначают состояния триггеров после прихода импульсов: 1 — напряжение высокого уровня; 0 — напряжение низкого уровня.

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

Допустим, все триггеры находятся в нулевом состоянии. При подаче первых семи импульсов декада работает подобно обычному двоичному счетчику. С приходом восьмого импульса вначале устанавливается состояние триггеров 0001. Но это состояние кратковременное (оно длится несколько десятков наносекунд), так как отрицательный перепад напряжения на выходе D-триггера почти мгновенно через дифференцирующую цепь C1R3R4 переключает триггеры D2.2, D3.1 в единичные состояния (в таблице показано стрелками). Дальнейшая работа декады иллюстрируется таблицей.

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

Максимальная частота работы декады определяется в основном номиналами конденсатора С1 и резистора R3 и может быть вычислена по приближенной формуле (здесь емкость конденсатора — в фарадах, сопротивление резистора — в омах). Емкость конденсатора должна быть не менее 100 пФ, а сопротивление резистора — не более 10 кОм.

Для расшифровки состояний триггеров использован дешифратор, собранный на элементах D1.1 — D1.4 микросхемы D1 и транзисторах V1 — V10, являющихся одновременно и высоковольтными электронными ключами. Работает дешифратор следующим образом. Низкий потенциал на выводе 3 элемента D1.1, открывающий со стороны эмиттера транзистор V1 или V6, формируется при наличии на обоих входах этого логического элемента и выводе 14 (питание) высокого потенциала. Если хотя бы на одном из входов элемента D1.1 будет напряжение низкого уровня, то на его выходе (вывод 3) будет напряжение высокого уровня и транзисторы V1, V6 будут закрыты. Если на вывод 14 будет подано напряжение низкого уровня, то все транзисторы микросхемы D1 и транзисторы V1—V4, V6—V9 будут закрыты. Открыт будет только один из транзисторов V5 или V10, в зависимости от состояния первого триггера счетчика (элемент D2.1).

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

Микросхемы питаются от двухполупериодного выпрямителя.на диодах V13 — V16 со стабилизатором выпрямленного напряжения, в котором работают стабилитрон V12 и транзистор V11. Цифровой индикатор H1 для повышения срока службы питается напряжением однопрлупериодного выпрямителя на диоде V17. На время подачи импульсов генератора к счетчику контакты S1.2 кнопки S1 размыкают цепь анодного напряжения, что устраняет мерцание цифр индикатора.

Конструкция генератора случайных чисел произвольная. Вместо микросхем серии К155 можно использовать аналогичные им микросхемы серии К133. Транзисторы V1—V10 могут быть серий П307, П308, П309, КТ605 или микросборка 1НТ661А; транзистор V11 — КТ801, КТ807 или КТ602 с любым буквенным индексом. Конденсаторы и резисторы — любых типов. Цифровой индикатор H1 — ИН-1, ИН-4, ИН-8, ИН-12 или ИН-14. Сопротивление резистора R7 указано для индикатора ИН-14.

Читайте также:  Стиральная машина без нагрева воды

Сетевой трансформатор Т1 блока питания — мощностью 5. 10 Вт, понижающий напряжение сети до 7. 10 В. Данные самодельного трансформатора: магнитопровод Ш20Х20, обмотка I — 2640 витков провода ПЭВ-2 0,12, обмотка II — 100 витков провода ПЭВ-2 0,22.

Прибор, собранный правильно и из исправных деталей, не нуждается в налаживании. Проверить же, что индицируемые им цифры действительно случайны, можно, записав последовательность определенного числа цифр, «выданных» прибором, например 500 цифр. В этом случае, в соответствии с теорией вероятностей, каждая из цифр 0. 9 должна повторяться в этой последовательности примерно 50 раз, т. е. 1/10 часть от общего числа цифр последовательности. Чем длиннее последовательность, тем точнее будет результат.

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

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

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

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

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

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

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

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

Источ-ник шума
Усилитель
Двух-сторонний ограничитель
Кла-пан
Счетчик
Буфер
Тактовые импульсы
Случайные числа

Рассмотрим примераппаратного генератора на основе физического генератора шума. Структурная схема генератора показана на рис. 1

Рисунок 1. Структурная схема аппаратного ГСЧ

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

Биометрические ГСЧ

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

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

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

Программные ГСЧ

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

Читайте также:  Яндекс музыка в каком формате

Линейный конгруэнтный генератор. Псевдослучайная последователь-
ность (ПСП) формируется согласно уравнению.

Где целые числа xn, xn+1 – n-й иn+1-й элементы ПСП; m>0 – модуль; 0 – начальное заполнение. Максимальный период ПСП равен m при выборе параметров генератора согласно следующей теореме.

Теорема 1.1 Линейная конгруэнтная последовательность, определяемая числами a, b, mимеет период равный mтогда и только тогда, когда

m и b взаимно простые числа;

a– 1 кратноpдля каждого простого p, являющегося делителем m;

a– 1 кратно 4, если mкратно 4.

Аддитивный генераторФибоначчи.Псевдослучайная последовательность (ПСП) формируется согласно уравнению

Теорема 1.2 Если многочлен x q +x p +1является примитивным над полем GF,То последовательность, формируется фддитивным генератором Фибоначчи, имеет максимальный период равный .

Генераторы ПСП на основе криптографических преобразований Структурная схема такого генератора включает счетчик и блочный шифратор (рис. 2). Начальное состояние счетчика и ключ для блочного шифра задаются

ПСП
Ключ
Случайное число
Счетчик
Блочный шифратор

чисто случайными числами.

Рис. 2. Схема генератора ПСП на основе блочного шифра

В дальнейшем с каждым тактом счетчик увеличивает свое состояние на 1. Числа с выхода счетчика шифруются блочным шифром. Выходные блоки шифратора образуют псевдослучайную последовательность чисел.

Применение ГСЧ

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

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

Для того чтобы гарантировать конфиденциальность передаваемого сообщения, отправитель создает зашифрованный текст путем сочетания текста, который необходимо передать, с ключом с помощью алгоритма шифрования. Затем этот зашифрованный текст передается по незащищенному каналу связи получателю, который использует алгоритм расшифровки и ключ для расшифровки, чтобы восстановить исходный текст. В идеале злоумышленник не может расшифровать зашифрованный текст без ключа. Таким образом, сила системы шифрования в конечном итоге зависит от силы ключа или, что эквивалентно, от сложности для перехватчика угадать его. Эта трудность заметно увеличивается с длиной ключа – типичные размеры ключа, используемые в настоящее время, составляют 56 бит (DES), 168 бит (3-DES) и 256 бит (IDEA и AES). Как известно, ключ – одна из важнейших частей криптографии, ни один процесс шифрования или дешифрования не обходится без ключа. Некоторые ключи присылаются от доверенного источника, например, сервера криптографических ключей, большинство – создаются с помощью генератора случайных чисел. При этом генерация качественной случайной последовательности является неотъемлемой и самой важной частью многих криптографических операций. Для создания криптостойкого ключа с помощью генератора необходимо учитывать множество факторов, таких как длина ключа, его энтропия, использование истинно случайных и псевдослучайных чисел, а также предусматривать возможные атаки на генератор.

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

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

Вывод по главе

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

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

Дата добавления: 2018-06-01 ; просмотров: 1108 ; ЗАКАЗАТЬ РАБОТУ

Генератор случайных чисел, также разработанный горьковчанами (Радио, 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 очков. У кого меньше очков, тот победитель.

Оцените статью
Добавить комментарий

Adblock
detector