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

Обзор аппаратных генераторов случайных чисел

Подорожный, И. В. Обзор аппаратных генераторов случайных чисел / И. В. Подорожный. — Текст : непосредственный // Молодой ученый. — 2016. — № 1 (105). — С. 190-194. — URL: https://moluch.ru/archive/105/24688/ (дата обращения: 27.10.2021).

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

Ключевые слова: генератор случайных чисел, квантовый генератор, тепловой шум.

Генераторы, использующие физические квантовые случайные процессы

Фазовый квантовый шум в лазерном луче

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

На полупрозрачное зеркало направляются фотоны, генерируемые источником одиночных фотонов. Фотон может отразиться, а может пройти через полупрозрачное зеркало с одинаковыми долями вероятности. Выбор, который «делает» фотон, абсолютно случаен. На выходе системы стоят два счетчика фотонов, регистрирующих прошедшие и отраженные фотоны и формирующих выходные электрические сигналы. [1]

2015-12-10_145029.png

Рис. 1. Схема ГСЧ, построенного на базе фазового квантового шума в лазерном луче

Подобные квантовые генераторы имеют высокую скорость выходного потока — до 10–16 Мбит/с, — при которой не наблюдается никаких корреляций и выполняются все статистические тесты. [2]

Матрица фотокамеры

Большинство источников света выпускают фотоны в совершенно случайные моменты времени и количество фотонов, выпущенных за единицу времени будет различаться на величину, которая является полностью случайной. Этот факт лег в основу ГСЧ, построенного на базе светочувствительной КМОП-матрицы обычной фотокамеры группой ученых из Женевского университета во главе с Бруно Сангинетти.

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

https://cdn-images-1.medium.com/max/720/1*u7E66i3rdO_fVDGucpoFJw.png

Рис. 2. Схема ГСЧ, построенного на базе фотоматрицы

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

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

Генераторы, использующие другие физические случайные процессы

Тепловой шум

Тепловой шум, также называемый шумом Джонсона, генерируется всеми пассивными резистивными элементами электрических цепей. Причина его появления — случайное броуновское движение электронов в резистивной среде. Тепловой шум увеличивается с ростом температуры и сопротивления и часто оказывается самой существенной составляющей шума в прецизионных полупроводниковых преобразователях данных. [4]

Одним из успешных примеров построения ГСЧ на базе теплового шума является генератор, разработанный компанией Intel в 1999 году и используемый в чипсетах Intel 800 серии.

ГСЧ Intel использует последовательности случайных чисел, получаемые с двух тактовых генераторов, частота работы одного из которых превышает частоту другого в 100 раз. Тепловой шум с источника (полупроводникового резистора) усиливается и используется для управления частотой колебаний медленного генератора.

2015-12-10_152549.png

Рис. 3. Временная диаграмма ГСЧ Intel

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

Среди недостатков данного генератора случайных чисел можно выделить большое энергопотребление (из-за кольцевого генератора, используемого для усиления теплового шума) и относительно небольшую для современных потребностей скорость генерации (порядка 75 Кбит/с после пост-обработки). [5]

Цифровая схема с неопределенным состоянием

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

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

1911489.jpg

Рис. 4. Современный генератор Intel

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

Данная разработка позволила избавиться от неудобств аналоговых компонентов предыдущего варианта ГСЧ, значительно уменьшить энергопотребление и увеличить скорость генерации более чем в 30 тысяч раз. [6]

Лавинный шум (шум лавинного умножения)

Источниками лавинного шума являются PN-переходы, работающие в режиме обратного пробоя, как это происходит в стабилитронах (зенеровских диодах). Ток, генерируемый во время лавинного пробоя, состоит из случайно распределённых шумовых выбросов, проходящих через обратно смещённый переход. Подобно дробовому шуму, для генерации лавинного шума требуется наличие тока, но обычно он гораздо интенсивнее. [4]

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

Случайные числа с подобных ГСЧ проходят все статистические тесты, однако скорость их генерации крайне мала — менее 10 Кбит/с. [7]

Фазовое дрожание в кольцевых генераторах

Фазовое дрожание цифрового сигнала данных (джиттер от англ. jitter) — нежелательные фазовые и/или частотные случайные отклонения передаваемого сигнала. Возникают вследствие нестабильности задающего генератора, изменений параметров линии передачи во времени и различной скорости распространения частотных составляющих одного и того же сигнала. Поскольку фазовое дрожание зависит от различных факторов, некоторые из которых полностью случайны, оно может быть использовано как источник случайных чисел. [8]

2015-12-10_152549.png

Рис. 5. ГСЧ, построенный на кольцевых генераторах

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

Среди минусов такого ГСЧ можно выделить относительно небольшую скорость генерации и большое энергопотребление.

Заключение

В статье были рассмотрены основные способы построения аппаратных генераторов случайных чисел. Среди них можно выделить один из самых современных и прогрессивных способов — генератор случайных чисел на базе неопределенных состояний, разработанный инженерами компании Intel и обладающий одной из самых высоких скоростей выходного потока (до 3 Гбит/с) и низким энергопотреблением.

Виды генераторов случайных чисел (ГСЧ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Где целые числа xn, xn+1 — n-й иn+1-й элементы ПСП; m>0 – модуль; 0<a, b<m, — начальное заполнение. Максимальный период ПСП равен 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 ; просмотров: 3465 ; Мы поможем в написании вашей работы!

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

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

Очень простой генератор случайных чисел. Такой простой, что я его даже и не придумывал, а просто взял описание в википедии: Регистр сдвига с линейной обратной связью. В англоязычной литературе такой метод генерации псевдослучайных чисел называется linear feedback shift register, LFSR.

Берется сдвиговый регистр и по каждому такту сдвигается вправо, а новый, вычисленный бит задвигается в регистр слева. Вычисление нового бита ведется операцией исключающего ИЛИ (XOR).

Написать такое на языке описания аппаратуры Verilog HDL — очень просто:

input wire rst,
input wire clk,
input wire enable,
output wire [31:0]out,
output wire [7:0]out_lb
);

reg [31:0]shift_reg;
assign out = shift_reg;
assign out_lb = shift_reg[7:0];
wire next_bit;
assign next_bit =
shift_reg[31] ^
shift_reg[30] ^
shift_reg[29] ^
shift_reg[27] ^
shift_reg[25] ^
shift_reg[ 0];

always @( posedge clk or posedge rst)
if (rst)
shift_reg <= 32’h00000001;
else
if (enable)
shift_reg <= < next_bit, shift_reg[31:1] >;

Вычисление нового значения сдвигового регистра происходит в строке shift_reg <= < next_bit, shift_reg[31:1] >;
Следующий задвигаемый бит next_bit вычисляется выше: assign next_bit =.

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

Предположим, модуль генерации псевдослучайных чисел готов. Что дальше? Я думаю пусть плата Марсоход3 с ПЛИС MAX10 генерирует случайные байты и я буду отправлять их через последовательный порт в компьютер. А на компьютере напишу программу, которая будет принимать поток байт и строить гистограмму распределения случайных чисел в интервале времени.

Читайте также  Автоматический блок управления для генератора

Значит теперь мне нужен модуль передачи в последовательный порт:

module serial(
input wire clk12,
input wire [7:0]sbyte,
input wire sbyte_rdy,
output wire tx,
output wire end_of_send,
output wire ack
);

reg [9:0]sreg;
assign tx = sreg[0];
reg [3:0]cnt = 0;
wire busy; assign busy = (cnt<11);
assign ack = sbyte_rdy &

always @( posedge clk12)
begin
if (sbyte_rdy &

busy)
cnt <= 0;
else
if (busy)
cnt <= cnt + 1’b1;
end

reg prev_busy;
always @( posedge clk12)
prev_busy <= busy;

assign end_of_send = busy==1’b0 && prev_busy==1’b1;

По сигналу sbyte_rdy входной байт sbyte фиксируется в сдвиговом регистре sreg. Как-то я писал про передачу в последовательный порт. При этом, в младший бит регистра записывается ноль — это будет старт-бит, а 9й и 10й биты — записываются единицы — это будут стоп биты. Далее по каждому такту данные сдвигается влево, младшими вперед.

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

Как мне все это проверить? В принципе проект простой, можно сразу в плате пытаться смотреть как работает, например, с помощью Altera SignalTap.

Но я думаю было бы интересно, например, сделать функциональную симуляцию этих двух модулей: lfsr и serial.
Для симуляции нужен тестбенч. Это такая же программа на Verilog, но только ее цель — это исключительно отладка проекта. В тестбенче я соединю модули lfsr и serial и подам на них тактовую частоту. Вот тестбенч:

reg clk;
reg rst;

initial
begin
clk <= 1’b0;
while (1)
begin
#5 clk <=

wire w_tx,w_ack;
wire [31:0]w_random;

lfsr u_lfsr(
.rst( rst ),
.clk( clk ),
.enable( w_eos ),
.out( w_random )
);

serial u_serial(
.clk12( clk ),
.sbyte( w_random[7:0] ),
.sbyte_rdy( w_eos ),
.tx( w_tx ),
.end_of_send( w_eos ),
.ack( w_ack )
);

initial
begin
$dumpfile («out.vcd»);
$dumpvars (0,tb);
rst <= 1’b1;
#50 rst <= 1’b0;
#100;
#10000;
$finish ;
end

Выход генератора псевдослучайных чисел u_lfsr проводами w_random подключен к модулю u_serial. Сигнал окончания передачи u_serial.end_of_send проводом w_oes передается на u_lfsr.enable для генерации следующего числа и начинает новую передачу u_serial.sbyte_rdy( w_eos ).

Для симуляции использую Icarus Verilog.
Компилирую: iverilog -o outfile tb.v serial.v lfsr.v
Симулирую: vvp outfile
В результате получаю временные диаграммы out.vcd, которые можно посмотреть программой GtkWave:

waveform icarus verilog, gtkwave

Теперь, убедившись с помощью симуляции, что все должно работать, перехожу к проекту в среде Quartus Prime.
Эта среда проектирования используется для разработки проектов для микросхем ПЛИС серии Altera MAX10.
За основу своего проекта я беру проект leds с нашего сайта и вставляю туда мои модули.
Получается вот такой топ модуль:

prj top

Для тех, кто впервые использует квартус: сделать графический компонент из текста verilog просто: из главного меню пункты File => Create / Update => Create Symbol Files for Current File. Потом получившиеся модули можно вставить в графический дизайн через правый клик мыши и Insert => Synbol.

В топ модуле кроме lfsr и serial еще есть модуль display — это совсем простая штука, случайные числа генерируются слишком часто. Если их просто вывести на светодиоды, то они просто будут равномерно светиться. Поэтому тут в модуле display я буду показывать только случайный байт из последовательности один раз примерно в 200 миллисекунд.

Ну и обратите внимание на вход кнопочки KEY0 — это сброс генератора.
В настройках проекта (в меню Assignments => Assignment Editor) на кнопочке KEY0 прямо в ПЛИС назначен подтягивающий резистор Weak Pull Up Resistor. Эта фишка есть только в микросхемах серии MAX II и MAX10. В Cyclone III или Cyclone IV такого нет. Если кнопочку на плате Марсоход3 не нажимать, то подтягивающий резистор делает единицу на входе KEY0. Когда кнопочка нажата — то ноль.

Выход модуля передатчика serial идет на вывод ftdi_bd1, который, в свою очередь идет на микросхему FTDI на плате Марсоход3. Она позволяет организовать связь платы Марсоход3 с компьютером через последовательный порт FTDI USB-to-COM.

Чтобы дополнительно проиллюстрировать работу генератора я встроил в систему модуль SignalTap. Он позволит смотреть в реальном времени некоторые сигналы проекта прямо из чипа ПЛИС, а именно вот эти три сигнала: serial:inst7|tx, serial:inst7|end_of_send, и serial:inst7|sbyte[7..0].

Ну или вот другой масштаб, чтобы увидеть «шум» случайных чисел:

Теперь следующая задача.
Нужно для компьютера написать программу, которая будет читать из последовательного порта и рисовать гистограмму плотности вероятности случайных чисел за какой-то промежуток времени. Я написал эту программу для Windows в среде Visual Studio 2012. Программа, как диалоговое окно MFC.

гистограмма распределения случайных чисел из генератора LFSR

Программа открывает последовательный порт (тот который в выпадающем списке в дропбоксе), программирует его на скорость передачи 12МБит/Сек — такая скорость передачи из платы и периодически выполняет чтение и порта всех имеющихся там данных. По этим принятым байтам строится гистограмма значений и рисуется на экране.

Весь проект для среды Quartus Prime и Visual Studio можно скачать вот здесь:

Ну и видео демонстрация как это все работает:

В принципе, распределение похоже на равномерное. Значит мой генератор работает!

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

Пожалуй нужно еще добавить, что современные процессоры Интел (теперь — подразделение компании Альтера, ой, шучу.. наоборот) имеют встроенные аппаратные генераторы случайных последовательностей. Причем они используют для создания случайных последовательностей несколько асинхронных «источников энтропии» (Entropy Source) от теплового шума кристалла (The ES runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz). Такой генератор повторить или хотя бы сделать подобный в «гаражных» условиях весьма трудно. Еще труднее доказать, что созданный генератор случайных чисел имеет действительно равномерное распределение и действительно весьма случаен. Кому интересно, про генераторы случайных чисел в процессорах Интел написано вот здесь.

ПРОГРАММИРОВАНИЕ БАЗОВЫХ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

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

Базовым генератором для получения последовательностей случайных величин с любым заданным распределением является генератор равномерно распределенной случайной величины на интервале [0; 1). Такая непрерывная случайная величина А» имеет функцию распределения

и функцию плотности распределения вероятности

Математическое ожидание такой равномерно распределенной случайной величины Нравно М(Х) = 1/2, дисперсия D(X) = 1/12. Графики плотности//*) и функции распределения Fx(x) изображены на рис. 2.1.

Функция плотности вероятности и функция распределения для равномерного распределения на интервале [0; 1)

Рис. 2.1. Функция плотности вероятности и функция распределения для равномерного распределения на интервале [0; 1)

В дальнейшем равномерно распределенные на интервале [0; 1) случайные величины будем называть случайными числами.

Равномерное распределение на интервале [0; 1) очень важно, поскольку случайные величины из всех других распределений могут быть получены путем преобразования независимых случайных чисел некоторым способом, определяемым нужным распределением. Некоторые из таких преобразований будут рассмотрены в четвертой главе.

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

  • 1. Аппаратный. В основе работы аппаратного генератора лежит какой-либо физический эффект (например, шумы в электронных устройствах или другие явления). Достоинством такого генератора является то, что случайные числа, получаемые с его помощью, являются абсолютно случайными. Также запас чисел аппаратного генератора неограничен. В качестве недостатка аппаратного генератора можно отметить, что данный способ не гарантирует качество получаемой последовательности случайных чисел непосредственно во время моделирования. Кроме того, с помощью аппаратного генератора нельзя получать одинаковые последовательности случайных чисел, которые желательно использовать при отладке моделирующих программ и сравнении альтернативных вариантов организации системы. Поэтому при моделировании аппаратные генераторы практически не используются.
  • 2. Табличный. При использовании табличного генератора заранее полученные и проверенные случайные числа оформлены в виде таблицы в памяти ЭВМ. Данный способ свободен от отмеченных недостатков аппаратного генератора. Однако при использовании табличного генератора запас случайных чисел ограничен размером таблицы. Кроме этого, неэффективно используются ресурсы ЭВМ. Поэтому данный способ при моделировании используется сравнительно редко.
  • 3. Арифметический (численный). При использовании арифметического генератора каждое новое число определяется одним или несколькими предшествующими числами в соответствии с заданной математической формулой. Данный способ свободен от описанных недостатков ранее рассмотренных генераторов. Поэтому при моделировании чаще всего используются именно арифметические генераторы.
Читайте также  Съемник подшипников генератора ваз 2107

Отметим, что при получении последовательности случайных чисел на ЭВМ с помощью арифметических генераторов используются алгоритмы. Поэтому такие последовательности, являющиеся по сути детерминированными, но для стороннего наблюдателя выглядящие как случайные, называются псевдослучайными. Также заметим, что любая ЭВМ оперирует только «-разрядными числами. Поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел из интервала [0; 1) может получиться лишь дискретная последовательность не более чем 2″ случайных чисел из того же интервала. Поэтому закон распределения такой дискретной последовательности называется квазиравномерным.

Далее перечислим основные требования, предъявляемые к идеальному генератору случайных чисел [4]:

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

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

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

Алгоритм работы генератор случайных чисел «Generator-Chisel.ru» основан на базе Вихря Мерсенна. Сам же, Вихрь Мерсенна основывается на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных по критерию случайности псевдослучайных чисел.

Вихрь Мерсенна лишён многих недостатков, присущих другим ГПСЧ (генератор псевдослучайных чисел), таких как малый период, предсказуемость, легко выявляемые статистические закономерности. Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (TGFSR) (англ. twisted generalised feedback shift register). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5 измерениями). Поэтому функция корреляции между двумя последовательностями выборок в выходной последовательности вихря Мерсенна пренебрежимо мала. Псевдослучайная последовательность, порождаемая вихрем Мерсенна, имеет очень большой период, равный числу Мерсенна, что более чем достаточно для многих практических приложений. Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2—3 раза быстрее линейных конгруэнтных генераторов). Алгоритм вихря Мерсенна реализован в программной библиотеке Boost, Glib и стандартных библиотеках для C++, Python, Ruby, R, PHP, MATLAB, Autoit. Выдаваемые вихрем Мерсенна последовательности псевдослучайных чисел успешно проходят статистические тесты DIEHARD, что подтверждает их хорошие статистические свойства.

Алгоритм работы Вихря Мерсенна алгоритмически реализуется двумя основными частями: рекурсивной и закалки. Рекурсивная часть представляет собой регистр сдвига с линейной обратной связью, в котором все биты в его слове определяются рекурсивно; поток выходных битов определяются также рекурсивно функцией битов состояния. Регистр сдвига состоит из 624 элементов, и, в общей сложности, из 19937 клеток. Каждый элемент имеет длину 32 бита за исключением первого элемента, который имеет только 1 бит за счет отбрасывания бита. Процесс генерации начинается с логического умножения на битовую маску, отбрасывающей 31 бита (кроме наиболее значащих). Следующим шагом выполняется инициализация (x0, x1,…, x623) любыми беззнаковыми 32-разрядными целыми числами. Следующие шаги включают в себя объединение и переходные состояния. Пространство состояний имеет 19937 бит (624·32 — 31). Следующее состояние генерируется сдвигом одного слова вертикально вверх и вставкой нового слова в конец. Новое слово вычисляется гаммированием средней части с исключённой[13]. Выходная последовательность начинается с x624, x625,…

Алгоритм производится в шесть этапов(шагов):

Шаг 0. Предварительно инициализируется значение констант u, h, a
u ← 10…0   битовая маска старших w-r бит,
h ← 01…1   битовая маска младших r бит,
a ← aw-1aw-2…a  последняя строка матрицы A.

Шаг 1. x[0], x[1],…,x[n-1] ←  начальное заполнение

Шаг 2. Вычисление (xi u | xi+1 l )

y ← (x[i] AND u1) OR (x[(i + 1) mod n] AND h1)

Шаг 3. Вычисляется значение следующего элемента последовательности по рекуррентному выражению (1)
x[i] ← x[(i + m) mod n] XOR (y>>1) XOR a   если младший бит y = 1

Или x[i] ← x[(i + m) mod n] XOR (y>>1) XOR 0   если младший бит y = 0

Шаг 4. Вычисление x[i]T
y ← x[i]
y ← y XOR (y>>u)
y ← y XOR ((y<<s) AND b)
y ← y XOR ((y<<t) AND c)
z ← y XOR (y>>l)
вывод z

Генератор псевдослучайных чисел с равномерным, нормальным и логнормальным распределением своими руками

Проблема случайных чисел начинается с того, что пока не существует ни одного генератора случайных чисел. Быть может, некоторые читатели возразят, и будут настаивать на том, что непосредственно человек является генератором случайных чисел. Но, к сожалению, это не так. Если попросить респондента загадать случайное число, то с высокой долей вероятности это будет число из промежутка от 0 до 20. Из этого интервала, скорее всего, будет загадано число «3», «7», «10», «12». Если же «случайное» число не будет принадлежать данному отрезку, то оно будет либо из повторяющихся цифр, например «111», «666» и так далее, либо будет кратно 10 («100», «1000»). Еще респонденты называют какие-то культовые числа, как то «42», «23», «13».

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

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

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

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

Способы решения

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

Встроенный в Pascal генератор случайных чисел является эталоном для наших последующих экспериментов. Данное изображение было создано при использовании графических средств. Были созданы 5000 случайных чисел для x , 5000 – для y , а после по полученным значениям были построены точки с координатами ( x , y ).

Это похоже на равномерное распределение.

Возникла идея проанализировать распределение у цифр десятичной записи деления единицы на большое простое число.

Была создана простая программа в Pascal :

program pseudorandomnumbersgeneratorthree;

writeln( 1 / 9941 );

В результате: 0.000100593501659793

Очевидно, что для нашего эксперимента такой точности недостаточно. Самый большой тип данных в Pascal – real (действительные числа) – ограничен 1.7*10^38, поэтому возникла идея обратиться к Java .

«Я же просил 400 капель , а тут 402!»

Будем запрашивать текущее время в миллисекундах, проверять, является ли оно простым числом (если нет, то будем увеличивать его на 1 до тех пор, пока оно не станет простым), а дальше – находить величину, обратную ему и брать значения с 1 цифры, не равной 0, по 1001 цифру после запятой.

import java.math.BigDecimal;

import java.math.BigInteger;

public class testing <

public static void main(String[] args ) <

BigDecimal input = BigDecimal.valueOf(1.0);

BigInteger helper = BigInteger.valueOf(1);

BigInteger input1 = BigInteger.valueOf(( int )System.currentTimeMillis());

boolean primenumber = input1 .isProbablePrime(100);

while ( primenumber != true ) <

input1 = input1 .add( helper );

primenumber = input1 .isProbablePrime(100);

if ( primenumber ) <

BigDecimal input3 = new BigDecimal( input1 .toString());

BigDecimal input4 = input .divide( input3 , 1001, BigDecimal. ROUND_DOWN );

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

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