Схема генератор случайных чисел: чем удивить юного программиста? / Хабр

чем удивить юного программиста? / Хабр

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

При нажатии на кнопку, на индикаторе высвечивается случайное число. В чем же тут случайность, откуда она берется? Сразу раскрою секрет. Цифры генерируются по порядку: 0, потом 1, 2, и так далее. Хитрость вот в чем: очень высокая частота импульсов. Они выдаются так быстро, что цифры сливаются в одну на индикаторе. И совершенно невозможно угадать цифру!

Далее вы прочтете о том, как устроен такой генератор, и как собрать его самостоятельно.

Я работаю методистом в

Центре инновационных образовательных технологий

(ЦИОТ) МФТИ, а более конкретно

—

представляю направление поддержки развития технического творчества. А также участвую в разработке продуктов компании

«Киберфизика»

.

В настоящий момент у нас активно развиваются два курса: основы электроники и программирование на Arduino. По каждому курсу мы делаем видеоматериалы, пишем методические рекомендации, собираем готовые наборы.

Курс по Arduino уже достаточно хорошо проработан: по нему готов замечательный онлайн-курс, получивший недавно награду EdCrunch OOC Award в номинации «Естественные и технические науки».

Но направление по основам электроники имеет большие перспективы: оно не настолько известно и популярно, как Arduino, а значит, есть большой простор для методической работы. В дружественной нам школе GoToCamp, например, Arduino есть уже давно, а вот «чистой» электроникой никто не занимался. Меня пригласили провести у ребят-старшеклассников небольшой мастер-класс. Стоит отметить, что ребята уже к тому моменту занимались Arduino, а значит, рассчитывать на вау-эффект от мигающего светодиода не стоило. Поэтому я как следует продумала программу мастер-класса, о результате напишу далее.

Фотоотчет

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

Собирали схемы из привезенных мною с собой наборов «Киберфизики»:

Вот схема генератора случайных чисел, которую я предложила собрать (кликабельно):

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

Кто любит программировать в Linux, наверняка вспомнит концепцию pipe – таких «труб», которые обозначаются черточкой «|» и позволяют из многих маленьких программ (даже написанных на разных языках программирования) быстро составить работающий скрипт. Лично я эти «трубы» просто обожаю и часто использую. Чувствуешь себя водопроводчиком Марио

Теперь рассмотрим подробнее элементы этой схемы

Генератор импульсов

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

Внутреннее устройство микросхемы таймера не очень просто объяснить новичку. Но зато эту микросхему очень удобно использовать так, как любят программисты – в режиме «чёрного ящика». Выводы таймера 555:

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

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

Режим работы таймера задается тремя элементами: резисторами R1 и R2 и конденсатором C1.

Просто подставив в эту формулу значения (или воспользовавшись

онлайн-калькулятором

, если лень считать), получаем частоту 40 Гц – то есть 40 колебаний в секунду. Соответственно, период будет 25 миллисекунд, и такую частую смену цифры на индикаторе человеческий глаз никогда не заметит.

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

Счётчик

Счётчик – это очень простая штука, практически как переменная i в программировании. Счётчик накапливает в себе число, вот и всё. А инкремент счётчика происходит по внешнему импульсу. Можно сделать по нажатию кнопки, а можно, как в нашем случае, от таймера.

Микросхема счётчика устроена так:

• Цифра выводится как двоичное число на выходах Q1…Q4
  
• По сигналу на 15-м выводе («Тактовый сигнал») счётчик прибавляет единицу
  
• В десятичном режиме после цифры 9 счётчик сбрасывается и начинает опять с 0
  

В нашей схеме счётчик тоже подключается достаточно просто:

• Вход U/D (направление счёта) подключен к «плюсу» питания, чтобы счёт шел по возрастающей.
  
• Выводы PE (разрешение предустановки), J1…J4 (входы данных для предустановки счётчика), B/D (двоичный режим счёта), CI и CO (вход и выход переноса) все подключены к «земле», так как их функционал в данной схеме нам не нужен
  

Дешифратор

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

Здесь самое важное – это входы для двоичного числа (A, B, C, D) и выходы («a» … «f»), которые напрямую подключаются к соответствующим сегментам, которые точно так же промаркированы буквами.

Служебные входы:

• вход для тестирования индикатора (LT) и для его гашения (Bl) заведены на «плюс»
  
• вход для «замораживания» цифры (LE) – на «минус».
  

Семисегментный индикатор

Здесь всё совсем просто. Используется семисегментный индикатор с общим катодом.

Каждый из светодиодов подключается через токоограничивающий резистор. Бывает, что некоторые стараются сэкономить на резисторах и подключить семисегментник через только один резистор – на этот случай в документации на индикатор есть специальная картинка:

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

Вот и всё! Теперь, для тех, кто хочет сам собрать такую схему:

И список компонентов к ней:

1. Микросхема таймера NE555
   
2. Микросхема счётчика CD 4029
   
3. Микросхема дешифратора CD 4511
   
4. Тактовая кнопка
   
5. Семисегментный индикатор с общим катодом (например, Kingbright SC56-11SRWA)          
   
6. Электролитический конденсатор 10 мкФ, рабочим напряжением не менее 25 В         
   
7. Резистор 1,2 кОм: 3 шт.
   
8. Резистор 560 Ом: 7 шт
   
9. Перемычки
   
10. Беспаечная макетная плата
    
11. Батарейка (в нашем случае, 9 вольт, но схема работает и в более широком диапазоне — от 5 до 12 вольт, нужно лишь подкорректировать номиналы резисторов)
    
12. Разъём для подключения батареи
    

Схема в собранном виде (фото кликабельно):

Многие могут спросить: а зачем вообще нужен «железный» генератор случайных чисел? Не проще ли взять микроконтроллер, запрограммировать его… Ведь генератор случайных чисел — это уже давно известное всем готовое решение!

Тут мне вспомнилась история о том, как я в группе товарищей участвовала в техническом оснащении полевой ролевой игры «Чужие под землёй» (естественно, по мотивам известного фильма). Важным элементом игры был фонарики, которые должны были спустя некоторое время после включения «барахлить» и выключаться на время — чтобы создавать страшную и безысходную атмосферу. Для маленьких фонариков была разведена крошечная плата с микроконтроллером, настолько мелким, что стандартная библиотека генератора случайных чисел вместе с программой в него не влезала! Времени оптимизировать не было, заменять микроконтроллер тоже ни в коем случае было нельзя.

В итоге, я стала всерьез смотреть в сторону альтернативного варианта — брать значение со свободно «висящего» входа микроконтроллера, из АЦП. Даже протестировала его, и помню, что результат оказался не вполне случайным (некоторые значения систематически встречались чаще других), но для нужд игры вполне подходил. Забавно, что создавать псевдослучайное число из недр микроконтроллера чисто математическим способом оказалось сложнее, чем брать неопределенность напрямую, из окружающего мира…

Про аппаратные генераторы случайных чисел есть хорошая статья в Википедии.

Мастер-класс, проведенный мной в GoToCamp, показал, что такую схему подростки-старшеклассники вполне могут собрать и понять, если им подробно объяснить все шаги и дать предварительный «загруз» в виде 10 более простых схем начального уровня.

Ребята получили важный опыт объединения нескольких простых схем в одну сложную. Мы объединили генератор импульсов, счётчик, дешифратор и семисегментный индикатор в схему — генератор случайных чисел. Обратите внимание, как легко это произошло благодаря понятным интерфейсам между маленькими схемами. Первая схема — генератор импульсов — на выходе имеет меандр, то есть прямоугольный сигнал. Частота этого меандра задает скорость работы счётчика. Счётчик, в свою очередь, «разговаривает» с дешифратором на языке двоичного кода. А тот, в свою очередь, передает данные в уже удобном для семисегментного индикатора виде.

На фото — тестирование генераторов на случайность при помощи секундомера в телефоне 🙂

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

А главное – изучайте готовые решения и успешные практики! Многое уже придумано до нас. Изучайте «азбуку» цифровой электроники, даже если вы уже уверенный «ардуинщик» или хардкорный микроконтроллерщик. Никогда не знаешь, для чего могут пригодиться те или иные кейсы.

Схема позаимствована из Tronix Book 2 замечательного американского популяризатора схемотехники Гэри Гибсона. А рассказал нам об этой книжке не менее замечательный выпускник МФТИ, инженер, разработчик микропроцессоров Юрий Панчул, за что ему большое спасибо!
Автор – Татьяна Волкова, специалист по учебно-методической работе ЦИОТ МФТИ (направление поддержки развития технического творчества), разработчик продуктов «Киберфизики»

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

    Данное устройство выдаёт случайные числа в виде цифр, высвечиваемых цифровым индикатором. Принципиальная схема генератора случайных чисел приведена на Рис. Устройство выполнено на двух микросхемах серии К176.
  Данная серия выполнена на полевых транзисторах, поэтому микросхемы этих серий потребляют очень малую мощность. Так, для используемых в описанном генераторе микросхем К176ЛА7 и К176ИЕ8 ток потребления ( в статическом режиме ) не превышает 0,1 и 100 мкА соответственно. Кроме того логические элементы, входящие в состав микросхем, имеют высокое входное сопротивление ( несколько мегаом ), что также является их достоинством.

На микросхеме DD1 собран генератор, а на микросхеме DD2 – счётчик с дешифратором. Микросхема К176ИЕ8 представляет собой десятичный счётчик, совмещённый с дешифратором. Вход R служит для установки исходного состояния ( для этого на него нужно кратковременно подать напряжение высокого уровня ), а вход СР – для подачи счётных импульсов положительной полярности ( в данном на него подано напряжение высокого логического уровня ). Микросхема имеет также вход CN для подачи импульсов отрицательной полярности. В процессе счёта на выходах микросхемы последовательно появляется напряжение высокого уровня, которое через резисторы R3 – R12 подаётся на базы высоковольтных транзисторов VT1 – VT10. Последние управляют цифровым газоразрядным индикатором HG1. Поскольку за время удержания кнопки SB1 счётчик многократно переполнялся, высвечиваемое индикатором число будет практически случайным.

  Контакты кнопки SB1 отключают питание индикатора на время нажатия кнопки, чтобы исключить мерцание цифр.
  Питание генератора чисел осуществляется от простейшего однополупериодного выпрямителя с параметрическим стабилизатором и фильтром VD1VD2C2. Резистор R2 необходим для подачи напряжения высокого уровня на вход 12 микросхемы DD1.
  Генератор случайных чисел собирается на печатной плате из фольгированного стеклотекстолита.
  В налаживании устройство не нуждается.
  При работе с генератором случайных чисел необходимо соблюдать меры безопасности, поскольку все элементы устройства имеют гальваническую связь с сетью.
  Прибор можно использовать для иллюстрации некоторых вопросов теории вероятностей и математической статистики, при проведении различного рода экспериментов, а также в ряде игр.

МРБ, А. Н. Евсеев “ЭЛЕКТРОННЫЕ УСТРОЙСТВА ДЛЯ ДОМА”, Москва “Радио и связь” 1994 стр. 24 – 26

Похожее

Российские ученые сообщили о самом быстром методе квантовой генерации случайных чисел

Ученые НИТУ «МИСиС» и Российского квантового центра вместе со своими зарубежными коллегами спроектировали и создали самый быстрый и доступный квантовый генератор случайных чисел. Технология может лечь в основу производства коммерческих генераторов случайных чисел, применяемых в криптографии и для моделирования сложных систем.

Источник изображения: НИТУ «МИСиС»

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

Лабораторная установка. Источник изображения: НИТУ «МИСиС»

Новый метод генерации истинно случайных чисел предложили ученые НИТУ «МИСиС», РКЦ, Окфордского университета, Голдсмитского колледжа и Свободного университета Берлина. Он основан на использовании квантовых свойств фотонов, подделать или предсказать которые нельзя. Более того, учёные также предложили метод сертификации в реальном времени полученных оптическим генератором случайных чисел и достигли в этом рекордных показателей — 8,05 Гбайт/с.

Блок-схема установки. Источник изображения: публикация в Physics Review X

Предложенная установка выглядит следующим образом. Недоверенный источник фотонов (лазер) подаёт излучение на один из двух входных портов светоделителя. На второй порт не подаётся ничего. На выходах светоделителя расположены фотодетекторы. Поскольку светоделитель симметричный, фотон с одинаковой и непредсказуемой вероятностью попадёт либо на один детектор, либо на другой. Данные с датчиков проходят АЦП и подаются на схему, которая подсчитывает фотоны и генерирует истинное случайное число. Истинность его подтверждается входным несимметричным светоделителем и фотодетектором, которые ведут подсчёт фотонов, прошедших в систему.

Блок-схема электронной части генератора случайных чисел. Источник изображения: публикация в Physics Review X

«Технология может лечь в основу производства коммерческих генераторов случайных чисел, применяемых в криптографии и для моделирования сложных систем. Результаты исследования опубликованы в журнале Physics Review X», — сообщается в пресс-релизе НИТУ «МИСиС».

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

Если вы заметили ошибку — выделите ее мышью и нажмите CTRL+ENTER.

Генератор случайных чисел (Лабораторная работа)

Кафедра: Автоматика и Вычислительная Техника

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

Содержание

1. Способы получения случайных чисел 3

2. Характеристики ГСЧ 5

3. Применение ГСЧ 6

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

5. Генерирование чисел с произвольным распределением 12

6. Тестирование ГСЧ 17

7. Генератор случайных чисел в Borland C++ 21

8. Практические задания 23

8.1 Случайные числа в заданном диапазоне 23

8.2 Двумерные случайные величины 23

8.3 Генерация одномерной случайной величины 23

8.4 Оценить вероятность. 23

8.5. Медианы треугольника. 24

9. Лабораторные задания 25

9.1 ГСЧ фон Неймана 25

9.2 Случайная матрица 25

9.3 Площадь фигуры 26

9.4 Случайная величина с заданными свойствами 26

10. Дополнительные задания 27

10.1 Многомерные случайные величины 27

10.2 Быки и коровы 27

Библиографический список 28

1. Способы получения случайных чисел

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

• тестирование алгоритмов;

• имитационное моделирование;

• некоторые задачи численного анализа;

• имитация пользовательского ввода.

Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на аппаратные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел.

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

К программным ГСЧ относятся различные алгоритмы генерирования последовательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов, предложенный в 1946 г. Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10-значное число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю. Кроме того, существуют и другие сравнительно короткие циклы.

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

В дальнейшем мы будем рассматривать лишь программные генераторы псевдослучайных чисел.

2. Характеристики ГСЧ

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

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

3.4 Генератор случайных чисел. | Техническая библиотека lib.qrz.ru

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

По принципу действия это устройство аналогично описанному выше, но оно выдает случайные числа в виде цифр, высвечиваемых цифровым индикатором. Принципиальная схема генератора случайных чисел приведена на рис. 22. Устройство выполнено на двух микросхемах серии К176.

Названная серия отличается от уже знакомой нам серии К155 тем, что выполнена на полевых транзисторах. Поэтому микросхемы этой серии потребляют очень малую мощность. Так, для используемых в описываемом ниже генераторе случайных чисел микросхем К176ЛА7 и К176ИЕ8 ток потребления (в статическом режиме) не превышает 0,1 и 100 мкА соответственно. Кроме того, логические элементы, входящие в состав микросхем, имеют высокое входное сопротивле

ние (несколько мегаом), что также является их достоинством (в этом вы убедитесь ниже).

На микросхеме DD1 собран генератор, а на микросхеме DD2 -счетчик с дешифратором. Микросхема Е176ЕА8 представляет собой десятичный счетчик, совмещенный с дешифратором. Напомним, как работает микросхема. Вход R служит для установки исходного состояния (для этого на него необходимо кратковременно подать напряжение высокого уровня), а вход СР — для подачи счетных импульсов положительной полярности (в данном случае на него в процессе работы подается напряжение высокого логического уровня). Микросхема имеет также вход CN для подачи импульсов отрицательной полярности. В процессе счета на выходах микросхемы последовательно появляется напряжения высокого уровня, которое через резисторы R3-R12 подается на базы высоковольтных транзисторов VT1-VT10. Последние управляют цифровым газоразрядным индикатором HG1. Поскольку за время удержания кнопки SB1 счетчик многократно переполнялся, высвечиваемое индикатором число будет практически случайным.

Контакты кнопки SB1 отключают питание индикатора на время нажатия кнопки, чтобы исключить мерцание цифр.

Питание генератора чисел осуществляется от простейшего однополупериодного выпрямителя с параметрическим стабилизатором и

фильтром VD1VD2C2 Резистор R2 необходим для подачи напряжения высокого уровня на вывод 12 микросхемы DD1

Генератор случайных чисел собран на печатной плате из фольгированного стеклотекстолита (рис 23). В налаживании устройство не нуждается.

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

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

 

Прогнозирование производительности при реализации алгоритмов генерации случайных последовательностей больших размерностей на реконфигурируемых архитектурах с сопроцессорами Текст научной статьи по специальности «Компьютерные и информационные науки»

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

Д.В. Быков, А.Д. Неретин

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

1. Малой размерности: для генерации малого количества ключей.

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

2. Большой размерности: для генерации большого количества ключей и для безопасной очистки диска.

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

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

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

Для решения подобных проблем повышения производительности в настоящее время используются параллельные и/или конвейерные системы на базе сопроцессоров, в качестве которых могут использоваться графические процессоры (Graphics Processing Unit, GPU), либо программируемые логические интегральные схемы (ПЛИС или FPGA, Field Programmable Gateway Array).

До недавнего времени разработка под архитектуру ПЛИС была довольно трудоемкой задачей (даже по сравнению с разработкой под GPU), которая требовала дополнительных знаний, как в программировании, так и в схемотехнике, даже не смотря на текущие возможные средства разработки [2]. Однако, с выходом стандарта Open Computing Language 2.0 (OpenCL) в июле 2013 года, а так же добавлением его поддержки Altera Corporation (USA, San Jose) для работы с их платами, разработка приложений под ПЛИС становится крайне актуальной задачей. К тому же, как показано в [3, 4], использование OpenCL позволяет достичь значительного прироста производительности.

Генераторы случайных последовательностей большой размерности в основном используют довольно простые алгоритмы, получающие какое-либо начальное состояние (seed), из которого генерируется вся последовательность. Данные алгоритмы довольно просто распараллелить (достаточно с максимальной энтропией получать значения начального состояния для каждого потока), однако, из-за простоты алгоритма не всегда есть возможность создать полноценный конвейер, а поскольку разработка под ПЛИС по большей части предполагает именно конвейерную обработку данных, а не параллельную, необходимо получить предварительную оценку прироста производительности, чтобы удостоверится в целесообразности разработки [5].

Естественно, подобные методы предварительной оценки обладают теми или иными недостатками, такими как сложность и длительность расчетов,

низкая точность оценки, отсутствие учета особенностей архитектуры ПЛИС. Одной из методик, позволяющих быстро, просто и эффективно рассчитать оценку прироста производительности реализации алгоритмов на ПЛИС является Reconfigurable Amenability Test (RAT), предложенная в 2009 году B. Holland, K. Nagarajan и A. D. George в [6].

В RAT используются следующие критерии для определения целесообразности реализации алгоритма на ПЛИС: пропускную способность, числовую точность и необходимые ресурсы. Данные факторы являются доминирующими при оценке эффективности реализации алгоритмов на ПЛИС. Методология RAT предполагает, что первоначально определяется необходимая точность приложения с учётом типа и количества доступных ресурсов, затем проводится тест пропускной способности для получения прогнозируемой производительности алгоритма. operations/element

comp fclock*throughputprocess ‘

где tcomp — время непосредственных вычислений на ПЛИС; Neiements -количество обрабатываемых элементов; Noperations/element — количество операций над элементов данных, необходимое для достижения конечного результата; fciock — тактовая частота; troughputprocess — количество операций за такт.

Рассмотрим аппаратные реализации алгоритмов генерации случайных последовательностей, предложенных Altera Corporation (USA, San Jose):

1. Linear Feedback Shift Register.

2. C Library Random Number Generator.

3. Race Condition-Based True Random Numbers.

4. Word Stream Scrambling.

Linear Feedback Shift Register (LFSR, Регистр сдвига с линейной обратной связью) — один из самых простых генераторов случайных чисел. Состоит всего из двух частей: функции битового сдвига (которая обеспечивает сдвиг регистров в ту или иную сторону) и обратной связи. Выходная последовательность зависит только он начального состояния и ассоциированного многочлена [8]. Ассоциированные многочлен изначально выбирается для генератора определенной размерности (списки рекомендованных значений можно найти в интернете). Достаточно просто реализуется аппаратно, и подобная реализация имеет высокую производительность. Однако сам по себе алгоритм плохо поддается конвейеризации.

C Library Random Number Generator (CLRNG, Генератор случайных чисел библиотеки C) — генератор случайных чисел, основанный на линейном конгруэнтном методе [9]. Так же довольно простой метод, в котором каждое следующее значение рассчитывается следующим образом:

Хп+1 = (а * Хп + с) mod т,

где a, c и m — некоторые константы, к которым предъявлены определенные требования (список рекомендованных значений так же можно найти в интернете).

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

Для повышения производительности m обычно берут равной 232, 264 и т.д. в зависимости от разрядности чисел, чтобы избежать операции деления.

Race Condition-Based True Random Numbers (RCBTRN, Генератор истинных случайных чисел на базе состояния гонки) — в отличии от большинства генераторов истинно случайных чисел для ПЛИС, использующих в своей основе несколько независимых сигналов кольцевого генератора, данный генератор, предложенный компанией Altera Corporation (USA, San Jose), построен на основе создания состояния гонки на нескольких несущих цепях.

Данный генератор состоит из трех основных модулей:

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

2. Конечный автомат регулировки: производит настройку one-hot дешифраторов. Для того чтобы в схеме гонки на выходе были именно случайные числа, необходимо подбирать нестабильные параметры для one-hot дешифратора.

3. Выходной фильтр фон Неймана: необходим для того, чтобы убрать наиболее вероятные результаты.

Подобный алгоритм куда более сложен и менее быстро действен, чем предыдущие два, однако, в отличие от них, он хорошо поддается

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

Word Stream Scrambling (WSS, Скремблинг потока слов) — может быть использован как для генерации случайной последовательности из определенного потока данных, так и для шифрования этого потока. Поток данных поступает на сдвиговый регистр, а затем мультиплексируется в псевдослучайном порядке, чтобы получить искаженный поток данных, в котором каждое значение находится в пределах определенного смещения [10].

Изначально создается случайный шаблон перетасовки, который гарантирует, что данные не будут потеряны и/или дублированы. Для обеспечения периода в 64 цикла, данный шаблон записывается в 6-разрядную таблицу поиска. Это позволяет ускорить время выполнения за счет замены операций длительный вычислений на более быструю операцию поиска, при этом сохраняя достаточную энтропию.

Данный алгоритм довольно прост в реализации, однако, в таком виде использовать его для шифрования данных не рекомендуется. Несмотря на то, что в отличие от остальных алгоритмов, в данном алгоритме на ПЛИС записывается большой объем данных (чтобы получить определенное количество случайных чисел, необходимо передать такое же количество на ПЛИС), за счет того, что алгоритм очень хорошо конвейеризуется, достигается значительный прирост производительности. Так же стоит отметить, что запас стойкости данного алгоритма выше, чем у первых двух.elements/process 32 511 2176 1674

tcomm> c 0,73 1,46

tcomp, c 0,18 0,36 5,81 0,60

Время выполнения на CPU, с 2,78 4,17 75,61 10,68

Прогнозируемое ускорение(одиночная буферизация) 3,05 3,83 11,56 5,18

Прогнозируемое ускорение(двойная буферизация) 3,81 5,71 13,01 7,32

Из полученных результатов видно, что даже при реализации Linear Feedback Shift Register можно получить прирост производительности. Стоит учитывать, что во всех случаях кроме Race Condition-Based True Random Numbers, время записи с ПЛИС на CPU превышает время вычислений. Это связано с тем, что платы серии Cyclone V не поддерживают PCI Express третьего поколения. Соответственно, увеличение скорости передачи данных в 2 раза за счет использования PCI Express третьего поколения для этих трех алгоритмов при двойной буферизации повысит прирост производительности так же в 2 раза. WSS

Время выполнения, с 0,48 6,15 0,59

Ускорение 3,45 11,00 5,21

Разница с оценкой, % 11,00 5,10 0,60

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

Литература:

1. Иванов, М.А. Теория, применение и оценка качества генераторов псевдослучайных последовательностей [Текст] / М.А. Иванов, И. В. Чугунков. — М.: КУДИЦ-ОБРАЗ, 2003. — 240 с.

2. Андреев, А.А. Методика выбора базовой архитектуры реконфигурируемой вычислительной системы на основе методов теоретико-игровой оптимизации [Электронный ресурс] / А.А. Андреев // «Инженерный вестник Дона», 2013, № 1. — Режим доступа: http://www.ivdon.ru/magazine/archive/n1y2013/1569 (доступ свободный) — Загл. с экрана. — Яз. рус.

3. Берилло, А.Б. Тестирование производительности в ОрепСЬ [Электронный ресурс] / А.Б. Берилло, — Режим доступа: http://www.ixbt.com/video3/opencl_bench.shtml (доступ свободный) — Загл. с экрана. — Яз. рус.

4. Блохин, О.Д. Исследование высокопроизводительного решения задачи N тел на базе платформы OpenCL [Электронный ресурс] / О. Д. Блохин, Д.К. Боголепов, М.М. Захаров, Д.П. Сопин. — 2010. — С. 34-37. — Режим доступа: http://www.itlab.unn.ru/archive/MSConf10/msconf-2010_book.pdf (доступ свободный) — Загл. с экрана. — Яз. рус.

5. Димаки, А.В. Аппаратно-программный генератор случайных чисел, сопрягаемый с компьютером типа IBM PC [Текст] / А.В. Димаки, А.А. Светлаков // «Известия томского политехнического университета», 2004, № 1. — 144-148 с.

6. Holland B. RAT: RC Amenability Test for Rapid Performance Prediction / Brian Holland, Karthik Nagarajan, Alan D. George. — URL: http://www.cse .sc.edu/~jbakos/reading_list/trets_rat_final.pdf.

7. Андреев, А. Е. Прогнозирование производительности при реализации алгоритмов на гибридных архитектурах с сопроцессорами [Электронный ресурс] / А. Е. Андреев, И. М. Силкин, Ю. В. Шафран // Журнал «Современные проблемы науки и образования», 2012, №3. — Режим доступа: http://www.science-education.ru/103-6389 (доступ свободный) — Загл. с экрана. -Яз. рус.

8. Кузьмин, Е.В. Параметризованная модель генератора псевдослучайных последовательностей в OrCAD [Электронный ресурс] / Е.В. Кузьмин, Ф.Г. Зограф // «Инженерный вестник Дона», 2013, № 3. — Режим доступа: http://www.ivdon.ru/magazine/archive/n3y2013/1766 (доступ свободный) — Загл. с экрана. — Яз. рус.

9. Chung-Chih Li Using Linear Congruential Generators for Cryptographic Purposes / Chung-Chih Li. — URL:

http://pdf.aminer.org/000/077/798/using_linear_congruential_generators_for_crypto graphic_purposes.pdf

10. Каляев, И. А. Реконфигурируемые мультиконвейерные вычислительные структуры [Текст] / И.А. Каляев, И.И. Левин, Е.А. Семерников, В .И. Шмойлов. — М.:ЮНЦ РАН, 2008. — 320 с.

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

Библиотека:	Память
Введён в:	2.3.0
Внешний вид:

Поведение

Этот компонент перебирает псевдослучайную последовательность чисел, переходя к следующему числу в последовательности каждый раз, когда срабатывает тактовый вход, если компонент включен. С технической точки зрения, алгоритм, используемый для вычисления псевдослучайных последовательностей — это линейный конгруэнтный генератор: начиная с семени r₀, следующий номер r₁ — это число

r₁ = (25,214,903,917 r₀ + 11) mod 2⁴⁸

Следующее значение r₂ вычисляется из r₁, используя те же вычисления, и так далее. Эта последовательность состоит из 48-битных чисел; значение на выходе компонента — это младшие биты, количество которых выбрано в атрибуте Биты данных, но после отбрасывания младших 12 битов текущего семени.

Кроме тактового входа, компонент имеет вход включение, который заставляет компонент игнорировать тактовый вход, если на входе включение 0; и вход сброс, который асинхронно сбрасывает значение компонента на начальное семя r₀.

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

Контакты

Восточный край, отмечен Q (выход, разрядность соответствует атрибуту Биты данных)

Выдаёт значение, хранящееся в данный момент в компоненте.

Западный край, верхний контакт, отмечен треугольником (вход, разрядность равна 1)

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

Западный край, нижний контакт (вход, разрядность равна 1)

Включение: компонент включен, когда этот вход не подключен, или на нём 1; но когда на нём 0, тактовый вход игнорируется.

Южный край (вход, разрядность равна 1)

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

Атрибуты

Когда компонент выбран, или уже добавлен, комбинации от Alt-0 до Alt-9 меняют его атрибут Биты данных.

Биты данных

Разрядность значения, выдаваемого компонентом.

Семя

Начальное значение, используемое для псевдослучайной последовательности. Когда равно 0 (по умолчанию), стартовое значение основано на времени старта текущего моделирования.

Срабатывание

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

Метка

Текст внутри метки, привязанной к компоненту.

Шрифт метки

Шрифт, которым отрисовывается метка.

Поведение Инструмента Нажатие

Нет.

Поведение Инструмента Текст

Позволяет редактировать привязанную к компоненту метку.

Назад к Справке по библиотеке

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

Решение на основе MCU

Люди впервые ступили на Луну 50 лет назад. На той же неделе, что и это историческое событие, Дев разделил свое время между просмотром события по телевизору и созданием уникальной настольной схемы новинки — генератора случайных цифр. В этой схеме использовалась лампа Никси для отображения и несколько интегральных схем TTL для реализации сдвигового регистра с линейной обратной связью. В этой статье Дев обновляет свой оригинальный дизайн, используя доступные сегодня цифровые КМОП-схемы и 7-сегментный светодиодный дисплей.Он также представляет улучшенную версию, в которой используется микроконтроллер Microchip PIC.

Я интересовался случайными числами со школы, когда наткнулся на знаменитую книгу о миллионе случайных чисел корпорации RAND в публичной библиотеке. Этот набор случайных чисел был основан на исследовании, проведенном для ВВС США, и случайные числа были сгенерированы с использованием физического источника шума. Эта книга не была первой книгой случайных чисел. Этой вехой стали «Числа случайной выборки», созданные в 1927 году английским статистиком Л.H.C. Типпетт, взявший случайные цифры из записей британской переписи населения, чтобы создать 10400 четырехзначных случайных чисел.

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

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

Регистры сдвига работают, перемещая логические биты «1» или «0» на их входе через серию этапов, точно так же, как ученики передают заметки от стола к столу в классе. В регистре сдвига с линейной обратной связью Фибоначчи, названном в честь известного математика 13 века Фибоначчи, этот входной бит берется из комбинации битов из каскадов регистра сдвига. Логические элементы исключающего ИЛИ (XOR) объединяют биты таким образом, чтобы максимизировать случайность. Для максимальной длины 24-битного регистра сдвига с линейной обратной связью обратная связь может быть получена от каскадных логических вентилей XOR, которые отводят выходы каскадов 7, 16, 22 и 24, как показано на рис. 1 .Есть и другие отводы, которые также работают, и отводы как для более длинных, так и для более коротких регистров сдвига.

РИСУНОК 1 — 24-битный регистр сдвига с линейной обратной связью максимальной длины. Биты данных могут быть извлечены на любом из 24 этапов, но случайность гарантируется только тогда, когда регистр циклически перебирает эти биты. Длина последовательности превышает 16 миллионов, поэтому можно извлечь 4 миллиона случайных десятичных или шестнадцатеричных цифр.

СХЕМА
Схема для реализации генератора случайных цифр с использованием этого подхода, как показано на рис. 2 , использует семь недорогих интегральных схем.Его преимущество в том, что не требуется прошивка. Три из этих микросхем — это 4015 8-битных регистров сдвига, которые каскадно соединены для создания 24-битного регистра сдвига. Есть микросхема с четырьмя XOR 4070, два таймера 555 для циклической смены битов и обновления дисплея и драйвер декодера 4511 для 7-сегментного светодиодного дисплея. В схеме, показанной на рисунке 2, IC1-IC3 представляют собой каскадные 8-битные регистры сдвига, которые составляют 24-битный регистр сдвига с линейной обратной связью. Этот сдвиговый регистр задействуется на этапах 7, 16, 22 и 24 и имеет вход на вывод IC1-pin7.Микросхема XOR на IC4 обрабатывает функцию обратной связи, а цифра BCD (двоично-десятичная дробь) берется из IC1.

РИСУНОК 2 — Схема генератора случайных чисел из сдвигового регистра с линейной обратной связью. Регистр сдвига выводит шестнадцатеричные цифры, но драйвер дисплея 4511 показывает только 0–9 и пропускает шестнадцатеричные цифры A-F. В оригинальной схеме TTL автора использовался драйвер дисплея 7447, который выводит произвольные символы для входов, превышающих 9. В этом случае использовались некоторые дополнительные логические микросхемы для обнаружения этих состояний и гашения дисплея.

IC6 и IC7 — это таймеры 555, которые циклируют регистр сдвига четыре раза в секунду. Циклические импульсы генерируются IC7, и они приходят в виде коротких пакетов, которые запускаются IC6. IC6 генерирует импульс длительностью 50 мс каждую секунду, и этот сигнал отправляется на разрешающий вывод IC7 для создания последовательности импульсов, показанной на , рис. 3, . Важно, чтобы за цикл генерировалось как минимум четыре импульса. Если их меньше четырех, последовательные цифры будут коррелированы, и случайность будет потеряна.Их может быть больше четырех, поэтому вы можете уменьшить значение конденсатора синхронизации на IC7, чтобы быть осторожными, если у вас нет осциллографа для подсчета импульсов.

РИСУНОК 3 — Тактовые импульсы, генерируемые двумя таймерами 555. IC6 затвор IC7 генерирует четыре импульса для опережения сдвигового регистра с линейной обратной связью на одну двоично-десятичную цифру. Эта последовательность импульсов происходит с интервалом в одну секунду, поэтому каждую секунду появляется новое случайное число.

IC5 — это комбинированный драйвер-декодер, который представляет данные BCD на 7-сегментный светодиодный дисплей.Этот чип слеп к числам, выходящим за пределы диапазона 0–9, поэтому шестнадцатеричные цифры A-F не ​​отображаются, когда они встречаются. Это означает, что случайные цифры иногда могут быть разделены более чем на секунду. Некоторые дополнительные микросхемы решат эту проблему, но я подумал, что это излишне усложнит схему.

В этой конструкции довольно много микросхем, поэтому я спроектировал печатную плату так, чтобы ее можно было разрезать пополам и сложить под прямым углом, как показано на Рис. 4 . Я протравливаю свои собственные печатные платы, поэтому они всегда конструируются с медными проводниками на одной стороне с несколькими необходимыми перемычками.Логической схеме обычно требуются более длинные перемычки для сигнальных соединений, в данном случае от ответвлений сдвиговых регистров до микросхемы XOR.

РИСУНОК 4 — Печатную плату генератора случайных чисел можно разрезать пополам и сложить, чтобы получить более компактную конструкцию. Разъем питания USB можно увидеть справа, а разъем для 7-сегментного дисплея — слева.

ЗАВЕРШЕННОЕ УСТРОЙСТВО
Хотя эту схему можно использовать для генерации случайных ПИН-кодов для различных учетных записей, по сути, это новинка настольного компьютера — кукла с качающейся головой компьютерного человека.В довершение к новинке я встроил свою в полупрозрачный пластиковый корпус и добавил два синих светодиода для освещения салона. Светодиоды нуждались в рассеивателях света, чтобы лучше рассеивать свет внутри, и я сделал их из пластиковых трубок и капли полупрозрачного силиконового клея. Готовое устройство можно увидеть на Рисунок 5 .

РИСУНОК 5 — Генератор случайных чисел на основе 24-битного сдвигового регистра с линейной обратной связью. Устройство встроено в полупрозрачный пластиковый корпус, внутренняя схема которого подсвечивается двумя синими светодиодами.Разъем питания USB находится справа, а подключение ленточного кабеля к 7-сегментному светодиодному дисплею можно увидеть слева.

Устройство было разработано для питания от небольшого сетевого трансформатора USB, так как его ток в 135 мА при 5 В предположительно выходит за пределы 100 мА для компьютерного разъема USB-2.0. Поскольку я предполагал, что в компьютерах есть внутренняя схема ограничения тока для предотвращения повреждений, я рискнул и подключил к старому настольному компьютеру, и он работал нормально.Схема также работала с подключением USB-2.0 на другом домашнем компьютере. Спецификация USB-3.0 требует максимального потребления тока 150 мА на разъем, так что это считается безопасным.

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

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

РИСУНОК 6 — Отклонение от единообразия цифр при моделировании 24-битного регистра сдвига с линейной обратной связью. Было проанализировано 32 000 цифр, поэтому ожидаемая частота каждой цифры составляет около 2 000. Статистически эти отклонения — то, что можно было бы ожидать от размера выборки.

С MCUS ПРОЩЕ ЖИЗНЬ
Несмотря на то, что вышеупомянутая схема имеет то преимущество, что не требуется прошивка, я запрограммировал тот же регистр сдвига с линейной обратной связью в микроконтроллер Microchip Technology PIC (MCU) и дал устройству несколько вариантов.Поскольку можно запрограммировать PIC в спящий режим, который потребляет очень мало тока, этот второй генератор случайных чисел питается от батареи и управляется кнопочным переключателем. Устройство не только отображает случайные цифры, но также имитирует бросок игральных костей и отвечает на вопрос «да / нет».

Простота схемы показана на Рисунок 7 . Микроконтроллер PIC 16F630 имеет достаточное количество контактов ввода-вывода для управления 7-сегментным светодиодным дисплеем, обнаружения кнопок и переключателей режимов и обеспечения последовательного программирования внутри схемы.Смещенный по центру тумблер выбирает один из трех режимов: режим, который дает последовательность из шести случайных чисел, другой, который дает два случайных числа от 1 до 6, и третий, который случайным образом дает «Y» вместо «да» или «N». за нет. Последний режим идеален для принятия сложных управленческих решений.

РИСУНОК 7 — Схема генератора случайных чисел сдвигового регистра с линейной обратной связью, моделируемая микроконтроллером PIC. Использование MCU позволяет использовать несколько режимов работы. Резисторы переключателя режимов питаются от разъема RC5, поэтому они не потребляют питание, когда PIC находится в спящем режиме.

Я построил всю схему — включая держатель батареи, печатную плату, переключатели и 7-сегментный дисплей — в контейнер, который я построил из куска трубы ПВХ, купленного в магазине товаров для дома. Я использовал заглушку из ПВХ в качестве съемного основания, чтобы обеспечить доступ для замены батареи. Потребляемый в устройстве ток настолько мал, что при периодическом использовании батарей хватит почти на весь срок их хранения. Фотография устройства представлена ​​как Рисунок 8 .

РИСУНОК 8 — Генератор случайных чисел с питанием от батареи на основе PIC MCU.Нажатие кнопки дает либо шесть случайных цифр, либо два броска шестигранных кубиков, либо ответ да / нет, в зависимости от выбранного режима. Для этой версии смоделированный 24-битный регистр сдвига с линейной обратной связью используется с отводами на этапах 1, 3, 4 и 24, а данные BCD берутся с этапов 21-24. Компилятор имеет встроенный генератор случайных чисел, который можно использовать вместо имитируемого сдвигового регистра с линейной обратной связью.

В отличие от первого генератора случайных чисел, для версии MCU требуется программа микропрограммы, которую я написал с помощью компилятора PICBasic Professional (ME Labs, melabs.com). Поскольку я использую исключительно Linux, я запускаю старую версию этого компилятора и связанный с ним программатор в очень старой операционной системе Windows, установленной как виртуальная машина. На веб-странице загрузки кода и файлов Circuit Cellar вы можете найти скомпилированный шестнадцатеричный файл для программирования PIC MCU без использования компилятора. Было бы достаточно просто переписать исходный код на C, чтобы можно было использовать другие компиляторы, включая бесплатный компилятор MPLAB C18 от Microchip, производителя микроконтроллеров PIC.

РЕСУРСЫ
Миллион случайных цифр со 100 000 нормальных отклонений, RAND Corporation, The Free Press (1955), доступно по адресу https://www.rand.org/pubs/monograph_reports/MR1418.html

Джордж У. Браун , «История случайных цифр RAND — Сводка», в AS Хаусхолдер, Г. Форсайт и Х.Х. Жермонд, ред., Метод Монте-Карло, Национальное бюро стандартов, серия по прикладной математике, т. 12 (Вашингтон, округ Колумбия: типография правительства США, 1951 г.), стр. 31 и далее, доступно по адресу https: // www.rand.org/content/dam/rand/pubs/papers/2008/P113.pdf

ME Labs | www.melabs.com
Технология микрочипов | www.microchip.com

ОПУБЛИКОВАНО В ЖУРНАЛЕ CIRCUIT CELLAR • ОКТЯБРЬ 2019 № 351 — Получить номер в формате PDF

Дев Гуалтьери получил степень доктора философии. Он получил степень доктора наук и технологий твердого тела в Сиракузском университете в 1974 году. Он проработал 30 лет в области исследований и технологий в крупной аэрокосмической компании и сейчас на пенсии. Доктор Гуалтьери ведет научно-технический блог на сайте www.tikalon.com/blog/blog.php. Он является автором трех научно-фантастических романов и книг по естествознанию и математике. Подробности см. На сайте www.tikalonpress.com.

Спонсируйте эту статью

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

Энтропия (Базель). 2021 Март; 23 (3): 371.

Иржи Петрзела, научный редактор

Департамент электротехники и вычислительной техники, Государственный университет Бойсе, Бойсе, ID 83725, США; мок[email protected]

Поступила в редакцию 10 февраля 2021 г .; Принято 17 марта 2021 г.

Лицензиат MDPI, Базель, Швейцария. Эта статья представляет собой статью в открытом доступе, распространяемую в соответствии с условиями лицензии Creative Commons Attribution (CC BY) (http://creativecommons.org/licenses/by/4.0/).

Abstract

В этой работе мы строим и тестируем три схемы генератора истинных случайных чисел (TRNG) на основе мемристоров: две ранее представленные в литературе, а одна является нашей собственной разработкой. Функциональность каждой цепи оценивается с помощью набора статистических тестов (STS) Национального института стандартов и технологий (NIST).Цепи TRNG были построены с использованием имеющихся в продаже готовых деталей, включая мемристор. Результаты этой работы подтверждают полезность мемристоров для успешной реализации схем TRNG, а также легкость, с которой TRNG может быть построен с использованием простых схем и готовых компонентов макетных схем.

Ключевые слова: генератор истинных случайных чисел, мемристор, энтропия, мультивибратор, осциллятор

1. Введение

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

ГСЧ делятся на два основных типа: генераторы псевдослучайных чисел (ГПСЧ) и генераторы истинных случайных чисел (ГСЧ) [7]. PRNG часто реализуются как регистр сдвига с линейной обратной связью (LFSR) или линейный конгруэнтный генератор (LCG) [8] среди других.Одна вещь, которая отличает ГПСЧ от ГПСЧ, — это то, что все ГПСЧ детерминированы. То есть, если текущее состояние ГПСЧ известно, то будущий вывод ГПСЧ может быть предсказан. Основное использование ГПСЧ часто — это научные исследования и моделирование (например, Монте-Карло) [6,9].

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

TRNG могут быть реализованы разными способами. Примеры TRNG включают измерение времени между щелчками на счетчике Гейгера [10], измерение частот или задержек асинхронных событий на ПК [11,12] и схемы, состоящие из осцилляторов, в которых энтропия фиксируется как джиттер [3,4,5, 7,13,14,15,16]. Даже современные процессоры могут иметь специальное оборудование на специализированной интегральной схеме (ASIC) для захвата энтропии [17].

Недавний подход в схемах TRNG заключался в использовании мемристорного устройства [18,19,20] для захвата энтропии для схем TRNG [1,2,5,6,15,21,22,23]. Многие из этих конструкций используют мемристоры в цепи, которая колеблется (например, кольцевой генератор) или приводится в действие генератором импульсов. Во многих случаях мемристор просто используется вместо резистора в более традиционной схеме генератора. Мемристоры предлагают отличную платформу для моделирования случайных событий из-за природы нитевидного мемристора, состоящего из постоянно перестраивающихся атомов [20].

В этой работе мы реализуем две схемы TRNG, недавно представленные в литературе [1,2], с использованием имеющихся в продаже мемристоров [24] и деталей [25]. Затем мы подвергли эти схемы тестам, установленным набором статистических тестов (STS) Национального института стандартов и технологий (NIST), который используется для оценки случайности TRNG [26]. Наконец, мы создаем схему TRNG на основе мемристора собственной разработки и проводим ее через те же тесты, чтобы продемонстрировать простоту реализации TRNG на основе мемристора и их доступность для всех, кто использует коммерчески доступные компоненты.В то время как существуют другие наборы статистических тестов для проверки случайности ГСЧ, NIST STS наиболее широко использовался в нашем обзоре литературы, который использовался для оценки ГСЧ в [1,2,5,6,7,8,14, 15,16]. Краткое описание каждого теста в NIST STS можно найти в Приложении A.

2. Материалы и методы

2.1. Электрические компоненты и измерения

Для реализации каждой схемы и электрических испытаний использовались коммерчески доступные готовые детали.Использованный мемристор представлял собой 16-контактный двухрядный корпус (DIP) с дискретным вольфрамовым самонаправленным каналом (W-SDC), состоящий из 8 мемристорных устройств на корпус [24]. Остальные компоненты схемы были приобретены в DigiKey [25], а часть номера указаны на принципиальных схемах. Все схемы реализованы на макетных платах; однако TRNG, разработанный для этой работы, также был реализован на печатной плате (PCB). Мемристор W-SDC работает с использованием механизма самонаправленного канала, как описано для базового мемристора SDC [18], за исключением того, что конструкция устройства предназначена для обеспечения более непрерывного изменения сопротивления и работы с использованием сочетания механизмов изменения фазы и SDC. путем включения тонкого слоя совместно нанесенного W-Ge ₂ Se ₃ между слоями Ge ₂ Se ₃ .

Электрические измерения были выполнены с использованием Digilent Analog Discovery 2 [27] с монтажной платой, которая соединяла AD2 с макетной платой. AD2 использовался для подачи питания на схему, генерации входной последовательности импульсов и тактовых сигналов и сбора данных с помощью программного обеспечения Digilent Waveforms, поставляемого с AD2. Поток отдельных битов был дискретизирован по нарастающему или спадающему фронту тактовой частоты входных данных. Один бит (или выборка) генерируется последовательно за такт. Каждый бит представляет собой выходной сигнал TRNG за один такт.Биты были последовательно объединены в файл CSV и подвергнуты последующей обработке с помощью сценария Perl для преобразования их в двоичный формат. Используемый сценарий Perl приведен в дополнительном материале. Любые дополнительные сведения об электрических измерениях, относящихся к каждой цепи, описаны в разделах описания цепей в разделе 2.2 Проверенные цепи. В общей сложности 100 битовых потоков длиной 1 миллион бит каждый были проверены на случайность для каждой схемы. Конечные двоичные потоки битов представляют собой серию единиц и нулей, которые последовательно записываются в файл сценарием Perl, обрабатывающим файлы CSV.Используемый сценарий Perl включен в файл дополнительных материалов.

Устранение смещения фон Неймана [9] использовалось при постобработке данных из цепей ГСЧ и включено в сценарий Perl, генерирующий файлы CSV. Отбеливание (также известное как сглаживание) — это метод устранения смещения в выходном потоке битов, например, если нулей больше, чем единиц. Фон Неймана или другие типы алгоритмов устранения смещения часто используются для устранения смещения выходных данных генераторов истинных случайных чисел [5,7,10,16,17].Было обнаружено, что необходимо применить сглаживание к выходу всех трех проверенных цепей ГСЧ из-за смещения в выходных данных ГСЧ. Схема устранения смещения фон Неймана проста в реализации как аппаратно, так и программно. Он обеспечивает простой метод удаления смещения из потока битов, не влияя на энтропию потока битов. Смещение смещения — это метод, который обычно используется в ГПСЧ. Чтобы описать этот процесс, мы используем который показывает смещенный входной битовый поток, который устраняется отбеливанием по фон Нейману.Биты во входном потоке битов сгруппированы в пары. Если два бита одинаковы, то оба бита отбрасываются. Если два бита различны, то сохраняется только первый бит. Результирующий битовый поток — это вывод с устранением смещения. Ниже первая пара двоичных битов равна единице. Биты совпадают, поэтому отсчет отбрасывается. Следующая пара битов, ноль и единица, различны. Первый бит (ноль) сохраняется и добавляется к окончательному потоку битов. Этот процесс повторяется до тех пор, пока все пары во входном потоке битов не будут обработаны.

Пример отбеливания по фон Нейману.

2.2. Проверенные схемы

Два ранее описанных ГПСЧ, использующих мемристоры, были реализованы аппаратно с мемристорным устройством W-SDC: Цзян [1] и Рай [2]. Третья испытанная цепь ГПСЧ была нашей собственной разработкой и получила название ГПСЧ студента (S-TRNG). Эти схемы показаны на.

Проверенные цепи. ( a ) Схема Цзяна модифицирована для тестирования [1]; ( b ) Схема Рая адаптирована для тестирования [2]; ( c ) Наша разработка, генератор случайных чисел по-студенческому (S-TRNG).

2.3. Цзян TRNG

Схема Цзяна, a, была физически реализована в их опубликованной работе [1] с использованием диффузионного мемристорного устройства на основе Ag: SiO ₂ . В конструкции Цзяна последовательность импульсов проходит через мемристор, включенный последовательно с резистором. Энтропия фиксируется мемристорным устройством как изменчивость времени, которое требуется устройству для перехода из состояния с высоким сопротивлением в состояние с низким сопротивлением.

2.3.1. Работа цепи Цзяна

Работа ГПСЧ Цзяна описана на временной диаграмме в.Когда на выходе схемы мемристор-резистор (Mem Out) низкий уровень (мемристор имеет высокое сопротивление), ниже V _ref , на выходе компаратора (Clk_en_) высокий уровень. Когда сигнал Clk_en_ высокий, счетчик отключен. В противоположном случае, когда мемристор находится в состоянии низкого сопротивления, выходной сигнал схемы выше, чем V _ref , и сигнал Clk_en_ имеет низкий уровень, что включает счетчик. Это небольшая модификация исходной схемы Цзяна, в которой на входе счетчика использовался логический элемент И для включения или отключения синхросигнала вместо вывода включения счетчика.Эти две схемы функционально эквивалентны, потому что логический элемент И действует как разрешающий сигнал тактового сигнала. Если вход разрешения равен 0, то выход логического элемента И подавляет синхронизацию и всегда равен 0. Если вход разрешения равен 1, то выход логического элемента И совпадает с входом вывода синхронизации.

Пояснение временной диаграммы схемы истинного генератора случайных чисел Цзяна.

Область временного окна, обозначенная буквой A in, показывает время, в течение которого Digilent AD2 производит выборку случайного бита из предыдущих часов.Линия B обозначает нарастающий фронт последовательности импульсов. В это время счетчик очищается коротким импульсом на входе сброса. Это время, когда мемристор будет запрограммирован на состояние с более низким сопротивлением. В момент времени, обозначенный линией C, мемристор переходит с высокого сопротивления на низкое. Когда напряжение Mem Out поднимается выше V _ref , выходной сигнал компаратора становится низким. Это включает Clk_en_ на счетчике, позволяя ему считать. В точке D напряжение последовательности импульсов становится низким, в результате чего напряжение Mem Out упадет ниже V _ref и отключит счетчик, сохранив выходное значение MSB.Случайный бит, сгенерированный в этом случае, сохраняется в «1». В это время мемристор также будет сброшен из высокого состояния в низкое. В точке E цикл возобновляется. В точке F переход мемристора с высокого сопротивления на низкое происходит раньше, чем в предыдущем цикле. Сигнал Clk_en_ переходит в высокий уровень на G, и счетчик отключается, на этот раз сохраняя свой выход равным «0», потому что было подсчитано другое количество тактов, чем в предыдущем окне последовательности импульсов.

2.3.2. Реализация макетной платы и измерения схемы Цзяна

Мы реализовали схему Цзяна на макетной плате, используя мемристор W-SDC, который отличается от мемристорной технологии, используемой Цзяном.Во время тестирования использовались частота последовательности импульсов 4 кГц и тактовая частота 50 МГц (обе генерируются Digilent AD2 Wavegen и функциями шаблона). V _ref был сгенерирован с помощью потенциометра между источником питания Digilent AD2 V + и источником питания V-. Это позволило легко регулировать напряжение V _ref для изменения амплитуд входного импульсного напряжения. Наименьший значащий бит (LSB) с выхода счетчика был дискретизирован цифровым входом AD2. Данные были сохранены с использованием частоты дискретизации 20 кГц.Резистор 22 кОм использовался последовательно с мемристорным устройством W-SDC, как показано на рисунке. Окончательный двоичный результат был подвергнут постобработке с использованием устранения смещения фон Неймана [9] и проанализирован с помощью приложения NIST STS [28]. Было протестировано 100 выборок по 1 миллиону бит. Время, затраченное на сбор этих образцов, составило примерно 40 часов. показывает изображение макета схемы ГПСЧ Цзяна.

Реализация дизайна Цзяна на макете. Схема подключена к Digilent AD2 справа.

2.4. Rai’s TRNG

Второй TRNG, реализованный в этой статье, предложенный Райом и др., Является конструкцией, вдохновленной конструкцией обычного двойного инверторного генератора TRNG [2]. Дизайн Раи ранее физически не реализовывался до того, как мы здесь приступили к работе. Вместо этого дизайн был смоделирован Раем с использованием мемристорной модели TiO ₂ , описанной в [29]. Энтропия определяется как время, которое требуется для образования проводящего канала в мемристорном устройстве, или как время, которое требуется устройству для перехода от высокого сопротивления к низкому сопротивлению.

2.4.1. Работа схемы Рая

Схема ГПСЧ Рая состоит из двух трактов задержки инвертора, с мемристором, включенным последовательно с инверторными устройствами в каждом тракте задержки [2]. Выходы двух инверторных цепочек дискретизируются, а выход TRNG зависит от того, какой выход переключается первым. Если первый выход D _{переключается первым, выход равен 0. Если первым переключается выход D второй , то выход равен 1.}

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

2.4.2. Макетная реализация и измерения схемы Раи

Макетная схема для конструкции TRNG Раи показана на рис. Инверторные микросхемы TI CD40106BE использовались вместе с мемристорами SDC на основе W для создания цепочек путей задержки инвертор-мемристор. Вход схемы управлялся часами прямоугольной формы, генерируемыми Digilent AD2 Wavegen. Для входа тактовой частоты последовательности импульсов использовалась частота 2 кГц. Компаратор Analog Devices AD8561 использовался для определения того, какое устройство переключилось первым, с помощью входа защелки на компараторе.V _ref был сгенерирован аналоговым выходом Digilent AD2. Было протестировано 100 выборок по 1 миллиону бит. Прошедшее время для сбора этих данных составило примерно 80 часов.

Макетная реализация схемы истинного генератора случайных чисел Раи. Схема подключена к Digilent AD2 справа.

2,5. S-TRNG

Новая схема TNRG на основе мемристора, называемая студенческим TRNG или S-TRNG, была создана, реализована и охарактеризована для сравнения с двумя предыдущими схемами.Принципиальная схема этой конструкции показана на c. Основная концепция схемы S-TRNG аналогична многим другим TRNG [3,4,5,7,13,14,15,16]. Схема состоит из двух генераторов. Один осциллятор работает с высокой скоростью, а другой осциллятор работает с медленной. Медленный осциллятор действует как часы для выборки данных из быстрого осциллятора. Энтропия фиксируется в медленном осцилляторе как джиттер или изменчивость периода осциллятора. В случае S-TRNG используются два медленных генератора, а выходы объединяются с помощью операции XOR, чтобы увеличить частоту получаемого медленного тактового сигнала.Это позволило нам быстрее собирать данные.

2.5.1. Работа схемы S-TRNG

Схема S-TRNG состоит из двух мемристорных генераторов мультивибратора, которые подаются на вентиль XOR. Выход логического элемента XOR подается на вход защелки компаратора. Он действует как медленный генератор, который выбирает выходной сигнал гораздо более быстрого генератора. Третья схема мультивибратора с резистором (не мемристором) используется для генерации быстрых колебаний. Выход этой схемы подается на вход компаратора.Таким образом, быстрый осциллятор опрашивается часами, генерируемыми медленными осцилляторами.

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

Период колебаний схемы мультивибратора — это общее время, необходимое для зарядки конденсатора с -1/2 В _CC до 1/2 В _CC , а затем разряда обратно до -1/2 В _CC . Период колебаний схемы мультивибратора может быть получен для типичного мемристорного устройства с высоким сопротивлением R _H , низким сопротивлением R _L и временем переключения R _LH путем изучения двух временных окон работы. .Первое временное окно — это зарядка конденсатора, когда мемристор находится в состоянии низкого сопротивления, пока он не переключится в состояние высокого сопротивления. Это моделируется уравнением (1) для вычисления V _LH , напряжения, при котором мемристор переключается из состояния с высоким сопротивлением в состояние с низким сопротивлением.

VLH = VCC − 1.5VCCe − TLHRLC

(1)

Второе временное окно, показанное в уравнении (2), вычисляет T _HLC как время с момента, когда устройство переключает низкое сопротивление в состояние высокого сопротивления до конденсатора. полностью заряжен.

TLHC = −RHCln (12VCCVCC − VLH)

(2)

Уравнение (3) представляет собой сумму времени переключения с высокого сопротивления на низкое сопротивление и оставшегося времени для зарядки конденсатора.

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

Уравнение (5) представляет собой просто сумму уравнений (3) и (4) и дает период одного колебания мультивибратора.Уравнение (5) показывает время одиночного периода колебаний мультивибратора с мемристором.

TOSC = TC + TD = TLH + TLHC + THL + THLD

(5)

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

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

Гистограммы энтропии, захваченные как медленные тактовые импульсы, дискретизирующие быстрые тактовые импульсы в генераторе случайных чисел с двумя осцилляторами, используемом в схеме S-TRNG. Верхний график: с мемристором. Нижний график: только с резистором. Всего было отобрано 6000 тактовых периодов для каждого типа осциллятора.

Пример тактовых периодов для генераторов на основе мемристоров и резисторов (в этом примере подчеркивается изменчивость).

2.5.2. Реализация макетной платы и измерения схемы S-TRNG

Схема изначально была создана на макете (а), а затем спроектирована и протестирована на печатной плате (b).Подобные ответы были измерены с помощью тестов NIST STS для двух разных реализаций. Поэтому окончательное тестирование проводилось на печатной плате. Как и в случае схем Цзян и Рай, 100 битовых потоков длиной 1 миллион бит каждый были протестированы с помощью схемы S-TRNG на печатной плате. Один бит данных собирается для каждого тактового цикла медленного генератора TRNG. В отличие от Jiang и Rai TRNG, S-TRNG самосинхронизируется медленным генератором в цепи. В этом случае необходимо выполнить асинхронную выборку выходного сигнала S-TRNG с помощью Digilent AD2.Также было необходимо более чем в 2 раза увеличить дискретизацию из-за изменчивости тактового периода медленного осциллятора на основе мемристора. Цепи Цзяна и Рая синхронизировались Digilent AD2, что позволяло использовать тактовые импульсы с последовательностью импульсов в качестве тактовых импульсов для сбора данных для этих ГПСЧ.

( a ) Макетная реализация; ( b ) Реализация схемы S-TRNG на печатной плате.

Конденсатор емкостью 1 нФ использовался для медленных генераторов с устройствами W-SDC, в результате чего частота колебаний могла составлять от 500 Гц до 5 кГц, в зависимости от состояния мемристорного устройства.Для схемы быстрого генератора использовались резистор и конденсатор 2,2 кОм и 100 пФ, что дало частоту колебаний 600 кГц. Из-за значительной вариабельности выходной тактовой частоты медленного генератора возникла необходимость передискретизации более чем в 2 раза. Тактовая частота 40 кГц использовалась для дискретизации выходного сигнала схемы. С каждым медленным генератором, работающим на частоте приблизительно 4 кГц, для завершения сбора данных потребовалось около 25 часов.

3.Результаты

Набор статистических тестов NIST [26], кратко описанный в Приложении A, был использован для оценки случайности всех трех реализованных TRNG. Все тесты NIST были запущены с настройками по умолчанию и параметрами, перечисленными в Приложении A. Данные для всех TRNG были подвергнуты последующей обработке с помощью отбеливания по фон Нейману. Результаты этих тестов суммированы в том месте, где перечислены все тесты NIST вместе с показателями прохождения этого теста для каждой цепи. В таблице приведены два дополнительных столбца, чтобы показать сравнение ранее опубликованных результатов испытаний схемы Цзян с использованием мемристора другого типа и опубликованных результатов моделирования для Rai с измерениями, выполненными в этой работе.Чтобы считаться пройденным, должно пройти не менее 96% из 100 битовых потоков для каждого теста.

Таблица 1

Сравнение всех результатов измерений TRNG для 15 тестов STS и сравнение дополнительных последовательностей, сглаживания и реализации для каждого набора данных. Показатели успешности показаны для каждого теста STS. Выделенные жирным шрифтом показатели успешности считаются неудовлетворительными (менее 96%).

3 Накопленная 903 99% % Шаблон с перекрытием Linear mplexity 903 Аппаратное обеспечение 17 903 сообщил о прохождении тестов STS (первая колонка данных) с использованием диффузионного мемристора на основе Ag: SiO ₂ . лед с содержанием> 96%.Аппаратная реализация (второй столбец данных) с использованием мемристора W-SDC также показывает прохождение всех тестов. Чтобы пройти частотный тест во время реализации схемы W-SDC в нашей работе, необходимо было применить дебиазинг к выходу TRNG. Без устранения смещения схемы ГПСЧ Цзяна процент успешных испытаний составил 0% для частотного теста STS. Схема Цзяна в нашей реализации работала немного хуже, чем в [1]. Это могло быть связано с множеством факторов, скорее всего с тем, что в нашем тестировании использовался мемристор другого типа.

Результаты моделирования Раи с использованием модели TiO ₂ [29] приведены в третьем столбце результатов в. В отчете Рай было смоделировано только пять тестов NIST. Однако аппаратная реализация Rai TRNG с использованием мемристора W-SDC (четвертый столбец данных) показывает, что Rai TRNG проходит все тесты NIST с превосходной производительностью по сравнению с любыми другими TRNG, протестированными в нашем исследовании. Тем не менее, без устранения дефектов наша аппаратная реализация TRNG Рая имеет показатель успешности 0% для теста частоты STS, аналогично результату, полученному для схемы Цзян.

В последнем столбце данных показаны результаты 13 тестов S-TRNG из 15 тестов NIST STS, которые проходят для этой цепи. Тест Runs завершился неудачно со скоростью прохождения 82%, а приблизительный тест энтропии не прошел с прохождением 94%. Тест запусков — это мера количества запусков в последовательности. Прогон определяется как повторение одного и того же значения в последовательности. Например, серия нулей длиной 4 будет «0000». Если количество запусков каждой длины не соответствует ожидаемому распределению запусков в случайной последовательности, то тест запусков не выполняется.Приблизительный энтропийный тест анализирует шаблоны в данных, в частности, рассматривая последовательности длиной m и m + 1 бит. Если распределение шаблонов в случайной последовательности не соответствует ожидаемому значению, то приблизительный тест энтропии не проходит. Тщательное исследование схемы на предмет источников потенциального шума может устранить определенное детерминированное поведение и улучшить скорость прохождения схемы для этих двух тестов.

Пропускная способность тестируемых ГПСЧ различалась в зависимости от конструкции. Пропускная способность — это мера того, насколько быстро каждый TRNG может генерировать случайные данные.Все TRNG работали до тех пор, пока не было собрано 100 миллионов бит после отбеливания по фон Нейману. S-TRNG был самым быстрым — 25 часов (1111 бит в секунду). Jiang был следующим по производительности при 40 часах (694 бит в секунду). Rai потребовалось 80 часов для сбора данных (347 бит в секунду). Следует отметить, что пропускная способность TRNG сильно зависит от устройств и значений компонентов схемы, используемых в случае S-TRNG. На частоту колебаний S-TRNG может влиять как изменчивость устройства W-SDC, так и выбранная емкость конденсатора в цепи.Точно так же на пропускную способность как Jiang, так и Rai TRNG влияет частота, с которой работает последовательность импульсов. Это ограничено временем, которое требуется мемристорным устройствам для переключения состояний.

4. Обсуждение

Три схемы TRNG были физически реализованы и протестированы с использованием мемристоров W-SDC. Цепи TRNG на основе мемристоров Цзян и Рай прошли все тесты NIST STS на истинную случайность. Студент TRNG (S-TRNG) сдал 13 из 15 тестов NIST STS. В данной работе анализируются несколько плюсов и минусов каждого ГПСЧ.Схема S-TRNG сложнее, чем у Рай и Цзян, и не генерирует случайные числа так же хорошо, как Рай или Цзян. Однако конструкция S-TRNG самосинхронизируется; то есть не требуется подавать на схему внешний тактовый сигнал. В некоторых случаях это может быть преимуществом. Кроме того, во время тестирования TRNG от Rai было обнаружено, что требуется некоторая тонкая настройка, чтобы получить близкие друг к другу временные задержки цепочки задержки для получения значимого вывода. Этого можно было достичь несколькими способами: либо заменой мемристорных устройств до тех пор, пока не будут найдены два устройства, дающие аналогичные задержки, либо добавлением сопротивления последовательно с мемристором, либо добавлением небольшого количества емкости на выходе мемристора.Кроме того, было обнаружено, что тонкий баланс путей задержки может меняться в процессе тестирования. Это одна из областей, в которой одного моделирования недостаточно, чтобы доказать случайность ГПСЧ. S-TRNG не требовал такой настройки. Все ГПСЧ требовали отбеливания вывода для прохождения частотного теста. Во время первоначальной разработки схемы S-TRNG было обнаружено, что мемристор W-SDC вместо резистора в схеме мультивибратора привел к значительному увеличению джиттера, создаваемого схемой.Это свойство было использовано для значительного увеличения количества энтропии, захваченной схемой. Также было обнаружено, что может быть полезно реализовать счетчик после логического элемента XOR и перед входом в защелку, чтобы существенно разделить медленные часы на еще более низкую частоту. Этот эффект позволяет захватывать больше энтропии, потому что джиттер от нескольких медленных тактовых циклов теперь вносит шум в выборку быстрых тактовых импульсов. Кроме того, частоту медленных тактовых импульсов можно более легко отрегулировать, выбрав другой выход из двоичного счетчика IC.

В ходе обширной разработки и тестирования схемы S-TRNG было обнаружено, что одним из основных факторов, которые могут привести к неслучайному выходу из TRNG, является шум питания. Пульсации источника питания могут наблюдаться из-за мгновенного высокого тока, наблюдаемого при переключении схемы мультивибратора из одного моностабильного состояния в другое. Эта пульсация питания от переключения одного генератора может привести к тому, что другие генераторы будут использовать одно и то же переключение питания в одно и то же время. Чтобы улучшить изоляцию источника питания между медленными генераторами и быстрым генератором, выходы генератора напряжения на Digilent AD2 использовались для питания быстрого генератора, в то время как обычные выходы источника питания использовались для питания медленных генераторов.Это помогает гарантировать отсутствие корреляции между быстрым и медленным генераторами из-за шума источника питания, вносимого одним или другим генератором.

5. Выводы

Мемристоры были физически реализованы в схемах для генерации истинных случайных чисел посредством захвата энтропии. Были реализованы две схемы, описанные в литературе (Jiang [1] и Rai [2]), и одна дополнительная схема была разработана и реализована в этой работе. Цель этой работы состояла в том, чтобы продемонстрировать, что схемы истинного генератора случайных чисел легко достижимы с помощью готовых компонентов и схем на многих уровнях сложности.

Приложение A

NIST (Национальный институт стандартов и технологий) предоставил программное обеспечение для проверки случайности генераторов случайных чисел [26]. Пакет статистических тестов (STS) версии 2.1.2 использовался для анализа двоичных битовых потоков чисел, генерируемых ГСЧ. STS содержит серию из 15 статистических тестов на случайность серии сгенерированных чисел. Некоторые тесты так же просты, как проверка того, что количество единиц и нулей равно 50/50 (частотный тест).Другие тесты ищут повторяющиеся шаблоны или непрерывные прогоны одного и того же бита в последовательности. В следующих параграфах приводится полный список и краткое описание каждого теста.

Приложение A.1. Проверка частоты (монобиты)

Истинно случайное число должно иметь распределение единиц и нулей 50/50. Частотный тест анализирует количество единиц и нулей в тестовой последовательности. Тест не пройден, если единиц значительно больше, чем нулей, или нулей значительно больше, чем единиц.Количество нулей и единиц должно быть примерно одинаковым. Ни один из других тестов случайности NIST не действителен, если этот тест не прошел. Случай всех нулей или всех единиц в последовательности не является случайным и не пройдет проверку частоты.

Приложение A.2. Проверка частоты в блоке

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

Приложение A.3. Тест запусков

Цель теста запусков — оценить общее количество запусков в последовательности случайных чисел. Прогон состоит из последовательности повторяющихся битов, ограниченных на каждом конце противоположным битом. Длина серии — это количество идентичных битов в серии. Например, последовательность «100001» представляет собой серию нулей длиной 4.Этот тест проверяет, соответствует ли количество прогонов различной длины ожидаемому для случайной последовательности. В частности, этот тест может находить колебания в случайной последовательности. Последовательность из четырех нулей, за которыми следуют четыре повторяющихся снова и снова, может пройти оба теста частоты, описанные выше, но не пройти тест запусков, потому что нет прогонов длины один, два или три.

Приложение A.4. Тест на самые длинные прогоны

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

Приложение A.5. Тест ранжирования двоичной матрицы

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

Приложение A.6. Тест дискретного преобразования Фурье (спектральный)

Спектральный тест дискретного преобразования Фурье (ДПФ) анализирует случайную последовательность и ищет в ней периодические шаблоны.Этот тест определит, находятся ли повторяющиеся узоры рядом друг с другом. Совершенно случайная последовательность должна иметь ровный спектральный анализ (должен выглядеть как шум). Тест завершится неудачно, если в спектре будут пики, превышающие 95% -ный порог. Двоичное представление синусоидальной волны не пройдет тесты DFT из-за единственного большого спектрального пика.

Приложение A.7. Тест совпадения неперекрывающихся шаблонов

Цель этого теста — проанализировать частоту появления заранее заданных целевых списков чисел.Этот тест ищет совпадения между предоставленными двоичными шаблонами (расположенными в папке «templates») и случайной входной последовательностью. Если совпадение не найдено, последовательность сдвигается на 1 бит, и поиск следующей последовательности начинается с этой последовательности. Если последовательность найдена, то поиск следующей последовательности начинается с конца текущей последовательности. Тест не пройден, если в последовательности обнаружено слишком много вхождений одного и того же шаблона. Например, упомянутая выше тестовая последовательность в тесте частотного блока из четырех нулей, за которыми следуют четыре повторяющихся единицы, не сможет пройти тест на соответствие неперекрывающемуся шаблону.

Приложение A.8. Тест сопоставления с перекрывающимся шаблоном

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

Приложение A.9. «Универсальный статистический» тест Маурера

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

Приложение A.10. Тест линейной сложности

Цель этого теста — вычислить длину LFSR, необходимую для генерации входного шаблона. Алгоритм Берлекампа-Месси используется для определения минимальной длины LFSR, необходимой для генерации шаблона для каждого блока в последовательности. Шаблон с LFSR небольшой длины или шаблон, в котором отсутствует линейная сложность, считается неслучайным. Во многих случаях ГПСЧ не могут быть обнаружены с помощью этого теста, потому что большинство современных ГПСЧ имеют чрезвычайно длительный период.Известный Mersenne Twister имеет период 2 ¹⁹⁹³⁷ -1.

Приложение A.11. Последовательный тест

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

Приложение A.12. Приблизительный тест энтропии

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

Приложение A.13. Тест совокупных сумм

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

Приложение A.14. Тест на случайные экскурсии

Тест на случайные экскурсии — это другой подход к тесту совокупных сумм. Как и в случае теста совокупных сумм, единица добавляет единицу к совокупной сумме, а ноль убирает единицу из совокупной суммы. Последовательности выбираются таким образом, чтобы они начинались и заканчивались на нуле. Выполняется анализ количества посещений определенного состояния (т.е. -4, -3, -2, -1, +1, +2, +3 или +4) в последовательностях. Если количество посещений определенного состояния не соответствует ожидаемому от случайной последовательности, последовательность не является случайной.Из предыдущего примера, в котором повторяются четыре единицы с последующими четырьмя нулями, тест совокупных сумм будет последовательно достигать совокупной суммы +4 и 0 с той же частотой появления. Для действительно случайной последовательности кумулятивная сумма +4 должна встречаться реже, чем кумулятивная сумма 0.

Приложение A.15. Тест варианта случайных экскурсий

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

Вклад авторов

Концептуализация, S.S. and K.A.C .; Формальный анализ, S.S. and K.A.C .; Расследование, С.С .; Программное обеспечение, S.S .; Надзор, K.A.C .; Письмо — черновик, С.С .; Написание — просмотр и редактирование, K.A.C. Все авторы прочитали и согласились с опубликованной версией рукописи.

Финансирование

Это исследование не получало внешнего финансирования.

Конфликты интересов

Патенты на мемристор (патенты США 9,583,703 и 9,583,699), используемые в этой работе, лицензированы Knowm, Inc. Государственным университетом Бойсе. KC является изобретателем патента и потенциально может получать гонорары от Государственного университета Бойсе за счет продажи мемристоров компанией Knowm, Inc.

Footnotes

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

Ссылки

1.Цзян Х., Белкин Д., Савельев С.Е., Лин С., Ван З., Ли Ю., Джоши С., Мидья Р., Ли К., Рао М. и др. Новый генератор истинных случайных чисел на основе стохастического диффузионного мемристора. Nat. Commun. 2017; 8: 882. DOI: 10.1038 / s41467-017-00869-х. [Бесплатная статья PMC] [PubMed] [CrossRef] [Google Scholar] 2. Рай В.К., Трипат С., Мэтью Дж. Генератор случайных чисел на основе мемристора: Архитектура и оценка. Процедуры Comput. Sci. 2017; 125: 577–583. DOI: 10.1016 / j.procs.2017.12.074. [CrossRef] [Google Scholar] 3.Буччи М., Джермани Л., Луцци Р., Трифилетти А., Варанонуово М. Источник истинно случайных чисел на основе высокоскоростного осциллятора для криптографических приложений на ИС смарт-карты. IEEE Trans. Comput. 2003. 52: 403–409. DOI: 10.1109 / TC.2003.11. [CrossRef] [Google Scholar] 4. Ян К., Блаау Д., Сильвестр Д. Проекты оборудования для обеспечения безопасности в системах Интернета вещей сверхнизкого энергопотребления: обзор и обзор. IEEE Micron. 2017; 37: 72–89. DOI: 10.1109 / MM.2017.4241357. [CrossRef] [Google Scholar] 5. Хашим Н.А.Н., Лунг Дж.Т.Х., Газали А., Хамид Ф.А. Мемристорные кольцевые осцилляторы, генератор истинных случайных чисел с различными оконными функциями для приложений в криптографии. Индонезийский. J. Electr. Англ. Comput. Sci. 2019; 14: 201–209. DOI: 10.11591 / ijeecs.v14.i1.pp201-209. [CrossRef] [Google Scholar] 6. Таскиран З.Г.К., Таскиран М., Киллиоглу М., Кахраман Н., Седеф Х. Новый мемристический дизайн истинного генератора случайных чисел. Compel Int. J. Comput. Математика. Электр. Электрон. Англ. 2019; 39: 1931–1947. DOI: 10.1108 / COMPEL-11-2018-0463. [CrossRef] [Google Scholar] 7.Сунар Б., Мартин В. Дж., Стинсон Д. Р. Генератор случайных чисел Provably Secure True со встроенной устойчивостью к активным атакам. IEEE Trans. Comput. 2007. 56: 109–119. DOI: 10.1109 / TC.2007.250627. [CrossRef] [Google Scholar] 8. Каттис Р.С., Кавассери Р.Г., Сай В. Генерация псевдослучайных битов с использованием связанных конгруэнтных генераторов. IEEE Trans. Circuits Syst. II Экспресс-трусы. 2010; 57: 203–207. DOI: 10.1109 / TCSII.2010.2041813. [CrossRef] [Google Scholar] 9. Фон Нейман Дж. Различные техники, используемые в связи со случайными цифрами.В: Householder A.S., Forsythe G.E., Germond H.H., редакторы. Метод Монте-Карло. Том 12. Типография правительства США; Вашингтон, округ Колумбия, США: 1951. С. 36–38. [Google Scholar] 13. Ракитин В.В., Русаков С.Г. Генератор последовательности импульсов на основе мемристора. Русь. Микроэлектрон. 2019; 48: 255–261. DOI: 10,1134 / S106373971

Тест NIST STS	Jiang TRNG (с [1])	Jiang TRNG	Rai TRNG (с [2])	Rai TRNG	S-TRNG
Частота 97%	99%	100%	100%	98%
Частота блоков	99%	99%	—	100%	98%
97%	99%	100%	100%	97%
циклов	99%	98%	100%	100%	82%	82%	82%		100%	99%	—	100%	100%
Рейтинг	100%	96%	—	100%	983	99%	100%	100%	97%
Шаблон без перекрытия	98%	99%	—	99%	99%
98%	—	100%	98%
Универсальный	100%	99%	—	100%	100%
Приблизительно	99%	100%	100%	94%
Случайные экскурсии	98%	98%	—	96%	98%	Случайные изменения			Случайные варианты		%	99%	—	98%	99%
Серийный	100%	99%	—	96%	98%
100%	99%	—	100%	100%
Длина последовательности	1,000,000	1,000,000	5000	1,000,000		100	100	100	100
Снятие смещения применяется	Нет	Да	Нет	Да	Да
903 Реализация схемы 903ICE Аппаратные средства	Аппаратные средства
Мемристорное устройство	Ag: SiO 2	W-SDC	Модель для TiO 2 [28]	W-SDC	W- 0
73. [CrossRef] [Google Scholar] 14. Робсон С. Магистерская диссертация. Университет Ватерлоо; Ватерлоо, Онтарио, Канада: 2013. Генератор действительно случайных чисел на основе кольцевого осциллятора. [Google Scholar] 15.Сингх Дж. П., Колей Дж., Акгул А., Гурвин Б., Рой Б. К. Новый хаотический генератор, содержащий обобщенный мемристор, одиночный операционный усилитель и RLC с подавлением хаоса и приложение для генерации случайных чисел. Евро. Phys. J. 2019; 228: 2233–2245. [Google Scholar] 16. Ядав А. Магистерская диссертация. Университет Содружества Вирджинии; Ричмонд, Вирджиния, США: 2013. Разработка и анализ цифрового генератора истинных случайных чисел. [Google Scholar] 18. Кэмпбелл К.А. Самонаправленный канальный мемристор для работы при высоких температурах.Микроэлектрон. J. 2017; 59: 10–14. DOI: 10.1016 / j.mejo.2016.11.006. [CrossRef] [Google Scholar] 19. Чуа Л.О. Четвертый элемент. Proc. IEEE. 2012; 100: 1920–1927. DOI: 10.1109 / JPROC.2012.21 . [CrossRef] [Google Scholar] 20. Ян Ю., Гао П., Ли Л., Пан Х., Таппертцхофен С., Чой С., Вазер Р., Валов И., Лу В.Д. Электрохимическая динамика наноразмерных металлических включений в диэлектриках. Nat. Commun. 2014; 5: 4232. DOI: 10,1038 / ncomms5232. [PubMed] [CrossRef] [Google Scholar] 21. Раджендран Дж., Карри Р., Вендт Дж.Б., Потконяк М., Макдональд Н., Роуз Г.С., Высоцкий Б. Нано встречает безопасность: исследование наноэлектронных устройств для приложений безопасности. Proc. IEEE. 2015; 103: 829–849. DOI: 10.1109 / JPROC.2014.2387353. [CrossRef] [Google Scholar] 22. Чакраборти С., Гарг А., Сури М. Генерация истинных случайных чисел из обычных чипов NVM. IEEE Trans. Избрать. Dev. 2020; 67: 888–894. DOI: 10.1109 / TED.2019.2963203. [CrossRef] [Google Scholar] 23. Kuka C.S., Hu Y., Xu Q., Alkahtani M. Инновационная безопасность связи ближнего поля, основанная на хаосе, создаваемом мемристическими цепями, принятыми в качестве симметричного ключа.Доступ IEEE. 2020; 8: 167975–167984. DOI: 10.1109 / ACCESS.2020.3023049. [CrossRef] [Google Scholar] 26. Бэшем Л.Е., Рухин А.Л., Сото Дж., Нечватал Дж. Р., Смид М.Э., Баркер Э. Б., Ли С. Д., Левенсон М., Вангель М., Бэнкс Д. Л. и др. Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений. Национальный институт стандартов и технологий; Гейтерсбург, М.Л., США: 2010. [Google Scholar] 29. Струков Д.Б., Снайдер Г.С., Стюард Д.Р., Вильямс Р.С. Обнаружен пропавший мемристор.Природа. 2008. 453: 80–83. DOI: 10,1038 / природа06932. [PubMed] [CrossRef] [Google Scholar] Разработка и анализ цифрового генератора истинных случайных чисел % PDF-1.7 % 1 0 объект > эндобдж 6 0 obj > эндобдж 2 0 obj > транслировать 2016-10-21T13: 42: 03-07: 002016-10-21T13: 42: 03-07: 002016-10-21T13: 42: 03-07: 00Appligent pdfHarmony 2.0uuid: 156ac890-a429-11b2-0a00-782dad000000uuid : 156b2aec-a429-11b2-0a00-00a07121fc7fapplication / pdf Разработка и анализ цифрового генератора истинных случайных чисел Авантика Ядав Цифровой генератор истинных случайных чисел Князь 9.0 rev 5 (www.princexml.com) Цифровой генератор истинных случайных чиселpdf Harmony 2.0 Linux Kernel 2.6 64bit 13 марта 2012 Библиотека 9.0.1 конечный поток эндобдж 3 0 obj > эндобдж 4 0 obj > эндобдж 5 0 obj > эндобдж 7 0 объект > эндобдж 8 0 объект >> эндобдж 9 0 объект > эндобдж 10 0 obj > эндобдж 11 0 объект > / MediaBox [0 0 612 792] / Родитель 15 0 R / Ресурсы> / ProcSet [/ PDF / Text / ImageC] / XObject> >> / Повернуть 0 / Тип / Страница >> эндобдж 12 0 объект > эндобдж 13 0 объект > эндобдж 14 0 объект > эндобдж 15 0 объект > эндобдж 16 0 объект > эндобдж 17 0 объект > эндобдж 18 0 объект > эндобдж 19 0 объект > эндобдж 20 0 объект > эндобдж 21 0 объект > эндобдж 22 0 объект > эндобдж 23 0 объект > эндобдж 24 0 объект > эндобдж 25 0 объект > эндобдж 26 0 объект > эндобдж 27 0 объект > эндобдж 28 0 объект > эндобдж 29 0 объект > эндобдж 30 0 объект > / Граница [0 0 0] / Rect [81.0 649,194 243,75 661,206] / Подтип / Ссылка / Тип / Аннотация >> эндобдж 31 0 объект > / Граница [0 0 0] / Rect [81,0 653,07 243,75 707,07] / Подтип / Ссылка / Тип / Аннотация >> эндобдж 32 0 объект > / Граница [0 0 0] / Rect [369,468 646,991 540,0 665,009] / Подтип / Ссылка / Тип / Аннотация >> эндобдж 33 0 объект > / Граница [0 0 0] / Rect [81.0 617.094 192.168 629.106] / Подтип / Ссылка / Тип / Аннотация >> эндобдж 34 0 объект > / Граница [0 0 0] / Rect [473.736 617.094 549.0 629.106] / Подтип / Ссылка / Тип / Аннотация >> эндобдж 35 0 объект > / Граница [0 0 0] / Rect [243.(& ǂSA6bxy @ ΐ𒖧N q Генератор случайных чисел Генератор случайных чисел Мы можем объединить функцию сдвига вправо с логическим элементом XOR, чтобы создать схему пути поезда, способную генерировать последовательность псевдослучайных чисел. Вот типичная принципиальная схема 5-ступенчатого регистра сдвига с линейной обратной связью. Условно этапы помечаются слева направо. 5-битный регистр сдвига с линейной обратной связью Логический вентиль XOR использует ответвления от стадий 1 и 4, что дает максимум 31 цикл состояния.Нам нужен шестиступенчатый сдвиговый регистр, потому что выходной сигнал логического элемента XOR должен храниться в «дополнительной» позиции, пока его нельзя будет сдвинуть вправо. Схема никогда не должна вводить 00000, чтобы избежать состояния блокировки. Схема включает логический вентиль XOR над функцией сдвига вправо внизу. Не нужно очищать точки, просто беги! Щелкните макет, чтобы приостановить / запустить поезд Щелкните по точкам для переключения 0/1 Щелкните начальный круг, чтобы сбросить поезд / точки Ленивые точки переключаются между верхней 0 или нижней 1 ветвями Поезда, прибывающие на ветку, переключают точку на эту линию Подпружиненные точки позволяют поездам ответвления присоединяться к основной линии Все поезда главной линии едут прямо и никогда не «разветвляются» Эксплуатация Пуск поезда от станции. Регистр n циклически перебирает последовательность псевдослучайных чисел. Его можно прочитать каждый раз, когда поезд проезжает через станцию. Каждое число следует за этой максимальной последовательностью из 31 шага: Шаг x16 x8 x4 x2 x1 Значение 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 16 8 20 10 21 26 29 14 23 27 13 6 3 9 24 28 30 31 15 7 19 25 12 22 11 5 18 9 4 2 1 В столбце x1 показана платформа, на которую подъезжает поезд.Если бы вы ждали на станции и не знали, на каком этапе вышеуказанного цикла находится схема, вы не смогли бы предсказать, на какой платформе прибудет следующий поезд. Это было бы псевдослучайно. Положение установки поезда гарантирует, что либо ленивая точка x8 , либо XOR установлена ​​на 1 , и, таким образом, сдвиговый регистр избегает состояния полной блокировки нуля. Другие регистры сдвига с линейной обратной связью с 2 отводами максимальной длины: Кол-во бит Длина петли Положения РПН 5 6 7 9 10 11 15 17 18 20 21 22 23 25 31 63 127 511 1,023 2,047 32,767 131,071 262,143 1,048,575 2,097,151 4,194,303 8,388,607 16,777,215 1 и 4 0 и 5 0 и 6 3 и 8 2 и 9 1 и 10 0 и 14 2 и 16 6 и 17 2 и 19 1 и 20 0 и 21 2 И 22 0 и 23 Расширение с 5 до 25 бит увеличивает время для каждого шага на 5, но увеличивает полный цикл в полмиллиона раз.Если поезд будет двигаться с той же скоростью, то он будет проезжать станцию ​​каждые 2,5 минуты, а не каждые полминуты, но время повторения цикла увеличится с 15,5 минут до 80 лет. (PDF) Реализация недорогого облегченного генератора случайных чисел Время (с) 0.00 50.00u 100.00u 150.00u 200.00u Vout -2.00 2.00 ClockN -3.00 0.00 Часы 0,00 3.00 -Vdiff -200.00n 200.00n Рисунок 3. Моделирование 2 для LM741 5. Заключение Настоящий генератор случайных чисел реализован с помощью операционного усилителя с двойным питанием. Это также было реализовано в операционных усилителях с однополярным питанием микроконтроллера MSP430 , широко используемых для меток RFID. Напряжение случайного теплового шума резисторов на входе операционного усилителя с положительной обратной связью в режиме триггера Шмитта было использовано для генерации случайных чисел .Данные прошли тест NIST, тест непредсказуемости . Из-за умеренного потребления мощности и низкой скорости передачи данных данные подходят в качестве начального значения для генератора псевдослучайных чисел . 6. Ссылки [1] Цзян-Юань Хуанг, В.К. Шен, Юань-Хэн Цзэн, Я-Чин Кинг и Чронг-Юнг Линь, «Контактное лицо — на основе резистивной оперативной памяти. Генератор истинных случайных чисел ”, IEEE Electron Device Letters, vol. 33, стр. 1108 — 1110, август 2012 г. [2] М. Гамбург, П. Кохер и М. Э. Марсон, «Анализ генератора цифровых случайных чисел Intel Ivy Bridge », Cryptography Research Inc. ., Март 2012 г. Доступно: http://www.cryptography.com/public/pdf/Intel_TRNG_R eport_20120312.pdf. На 4 октября 2012 г. IEEE Trans.VLSI Syst., Том 20, стр. 385 — 389, февраль 2012. [4] М. Мери, Дж. К. Эрнандес-Кастро, П. Перис- Лопес, «Изучение генератора псевдослучайных чисел. недорогой RFID-метки », в Proc. IEEE International Conferences RFID TA, сентябрь 2011 г., стр. 381-385. [5] Х. Мартин, Э.С. Миллан, Л. Энтрена, П. Перис-Лопес, и Дж. К. Эрнандес-Кастро, «AKARI-X: псевдо- Генератор случайных чисел для безопасных облегченных систем » , в Proc.2011 IEEE 17-й Международный симпозиум по тестированию линий IOLTS, июль 2011 г., стр. 228– 233. [6] Т. Сугиура, Я. Яманаси и Н. Йошикава, «Демонстрация 30 Гбит / s Создание сверхпроводящего генератора истинных случайных чисел ”, IEEE Trans. Прил. Supercond., Т. 21, pp. 843-846, June 2011. [7] JM Segui, JG Alfaro и JH Joancomarti, «Практическая реализация атаки на слабые псевдослучайные Конструкции генераторов номеров для тегов EPC Gen2», в Proc.Беспроводная персональная связь, июль 2011 г., стр. 1-17. [8] П. Перис-Лопес, Э. С. Миллан, Дж. С. А. В. Люббе и Л. А. Энтрена, «Криптографически безопасный псевдо Генератор случайных битов для RFID-меток», in Proc. ICITST’10, ноябрь 2010 г., стр. 490-495. [9] С. А. Уилбер, «Генератор случайных чисел и метод генерации », Патент США № 7752247 B2, 2010 г. [10] Х. Дебяо, К. Цзяньхуа и Х.Джин, «Генератор случайных чисел на основе криптосистемы NTRU», Международный научно-технический журнал Maejo, т. 4, № 3, стр. 428 — 434, 2010. [11] SS Saab, JG Hobeika и IE Ouaiss, «Новый псевдослучайный шум и глушитель полосы с использованием составной синусоидальной функции », IEEE Trans . Сигнал Процесс., Т. 58, pp. 535–543, февраль 2010 г. [12] Я. Яманаши и Н.Йошикава, «Сверхпроводящий генератор случайных чисел , использующий тепловые шумы в схемах SFQ», IEEE Trans. Прил. Supercond., Т. 19, pp. 630–633, июнь 2009 г. [13] О. Кац, Д.А. Рамон и И.А. Вагнер, «Надежный генератор случайных чисел на основе дифференциального Current Mode Chaos», IEEE Trans . СБИС. 16, pp. 1677 — 1686, Dec. 2008. [14] C. Tokunaga, D. Blaauw, and T.Мадж, «Истинный генератор случайных чисел с контролем качества на основе метастабильности», IEEE J. Solid-State Circuits, vol. 43, pp. 78–85, январь 2008 г. [15] Л. Вестлунд, «Генератор случайных чисел с использованием MSP430», Отчет по применению, Texas Instruments, 2006. Доступно: http: // focus.ti.com/lit/an/slaa338/slaa338.pdf По состоянию на 15 декабря 2011 г. [16] С. Ясуда, Х. Сатаке, Т. Танамото, Р.Обха, К. , Учида и С. Фуджита, «Генератор физических случайных чисел на основе МОП-структуры после сбоя программного обеспечения », IEEE J. Solid-State Circuits, vol. 39, pp. 1375 — 1377, август 2004 г. [17] М. Буччи, Л. Германи, Р. Луцци, П. Томмазино, А. Трифилетти и М. Варанонуово, «Высокий- Speed ​​IC Источник случайных чисел для микроконтроллеров SmartCard », IEEE Trans. Circuits Syst. Я: Фундамент. Теория Appl., Т. 50, pp. 1373-1380, Nov. 2003. [18] К. С. Петри и Дж. А. Коннелли, «Генератор случайных чисел IC на основе шума для приложений в криптографии », IEEE Trans. Circuits Syst. Я: Фундамент. Теория Прил. (до 2003 г.), т. 47, pp. 615-621, May 2000. [19] М. Бланд и Г. М. Мегсон, «Генерация случайных систолических чисел для генетических алгоритмов», Electronics Letters, vol.32, нет. 12, pp. 1069-1070, июнь 1996. [20] П. Дж. Пачини и Б. Коско, «Адаптивная нечеткая скачкообразная перестройка частоты», IEEE Trans. Commun., Т. 43, pp. 2111 — 2117, июнь 1995. [21] MJ Bellido, AJ Acosta, M. Valencia, A. Barriga, и JL Huertas, «Simple Binary Random Number Generator», Electronics Letters . т. 28, вып. 7, pp. 617 — 618, March 1992. [22] Г. М. Бернштейн и М.А. Либерман, «Безопасная генерация случайных чисел с использованием хаотических схем», Международный журнал инженерных исследований и технологий (IJERT) Vol. 1 Выпуск 10, декабрь 2012 г. ISSN: 2278-0181 5www.ijert.org Истинные генераторы случайных чисел для повышенной безопасности в любой SoC Подключенные устройства и их связь должны быть защищены от развивающихся угроз и атак для защиты экосистем и ценной личной и деловой информации.Высококачественные TRNG — это фундаментальная технология, необходимая для построения цепочки доверия в системах, поскольку многие криптографические алгоритмы для протоколов шифрования / аутентификации и безопасности зависят от истинных случайных чисел для генерации ключей, вызовов, начальных значений и одноразовых значений. Общая сила безопасности в системах и приложениях зависит от качества источника энтропии, обеспечиваемого ГПСЧ. Недостатки в генераторах случайных чисел могут использоваться злоумышленниками для взлома устройств, которые в остальном алгоритмически безопасны.Synopsys разработала эффективные ГПСЧ, которые соответствуют стандартам NIST и AIS и могут быть сертифицированы в конечных продуктах для таких сертификатов, как FIPS 140-2 / 140-3, Common Criteria (CC) и OSCCA Китая. В дополнение к TRNG, Synopsys предоставляет широкий портфель высокоинтегрированных IP-решений для обеспечения безопасности, которые используют общий набор основанных на стандартах строительных блоков и концепций безопасности, чтобы обеспечить наиболее эффективную конструкцию микросхем и высочайшие уровни безопасности для ряда продуктов в рынки мобильных устройств, автомобилей, цифрового дома, Интернета вещей и облачных вычислений. IP-решения Synopsys с широкими возможностями настройки включают в себя аппаратные модули безопасности с Root of Trust, защиту контента, криптографию и ускорители протоколов безопасности для интеграции в SoC. Эти интегрированные решения обеспечивают основу для многих стандартов безопасности, поддерживая конфиденциальность, целостность данных, аутентификацию пользователя / системы, неотказуемость и положительную авторизацию. В совокупности IP-решения Synopsys для обеспечения безопасности помогают предотвратить широкий спектр развивающихся угроз для подключенных устройств, таких как кража, взлом, атаки по побочным каналам, вредоносное ПО и утечки данных. Дополнительные сведения: Генераторы случайных чисел DesignWare True ASIC-реализация генераторов случайных чисел с использованием SR-защелок и ее оценка | Журнал EURASIP по информационной безопасности В этом разделе мы оцениваем, генерируют ли наши ГПСЧ, созданные на ASIC, случайные числа высокого качества независимо от изменений окружающей среды. Как упоминалось в разделе 3, на ГПСЧ могут влиять колебания как температуры, так и напряжения. Система оценки Наша экспериментальная система для получения случайных чисел показана на рис. 5. На этом рисунке показаны основные функциональные блоки. Система состоит из двух плат: изготовленной на заказ платы для ASIC ГПСЧ и платы стартового комплекта Spartan-3E с ПЛИС Xilinx для управления ГПСЧ [25] (далее именуемой «платой ПЛИС»). Напряжение сердечника на ГПСЧ подавалось с помощью стабилизирующего источника питания, который мог регулировать напряжение питания с интервалами 0.01 В. Тактовые сигналы были введены в TRNG через плату FPGA. Тактовая частота генератора 50 МГц была разделена на 2,5 МГц цифровым менеджером синхронизации (DCM) на плате FPGA и введена в микросхему TRNG. Случайные числа, сгенерированные TRNG, были записаны на карту micro SD через блочное ОЗУ и модуль записи SD на плате FPGA. Мы получили не только случайные числа, но и выход каждой защелки для дальнейшей оценки. ПК устанавливает команды в регистр команд в микросхеме TRNG через интерфейс ПК на плате FPGA.Установив регистр команд, два мультиплексора, мультиплексор 256-1 (256-1 MUL на рисунке 5) и мультиплексор 2-1 (2-1 MUL на рисунке 5), управлялись для вывода либо случайных чисел, либо каждой защелки. . Случайные числа или выходы каждой защелки на SD-карте были вручную перенесены на жесткий диск ПК. Рис. 5 Экспериментальная система для получения случайных чисел. Наша экспериментальная система состоит из двух плат: изготовленной на заказ платы для ASIC для TRNG и платы стартового набора Spartan-3E с ПЛИС Xilinx для управления TRNG.Случайные числа, сгенерированные TRNG, были записаны на карту micro SD через блочное ОЗУ и модуль записи SD на плате FPGA. Мы получили не только случайные числа, но и выход каждой защелки . В этой среде мы оценили случайные числа, генерируемые всеми 39 TRNG, при изменении температуры и напряжения. Напряжение ядра было изменено на 1,65 В (1,80–0,15 В), 1,80 В (стандартное) и 1,95 В (1,80 + 0,15 В) с помощью стабилизирующего источника питания.Температуру поддерживали на уровне -20 и 60 ° C с использованием печи с постоянной температурой. Мы также собирали данные при комнатной температуре (≈ 27 ° C). В термостат с постоянной температурой помещалась только изготовленная по индивидуальному заказу плата для ГПСГ. Плата FPGA всегда работала при номинальном напряжении и комнатной температуре. Эти две платы были соединены кабелем, устойчивым к низким / высоким температурам. Оценка случайности Предварительно: проверка работоспособности по SP800-90B В качестве предварительного теста мы оценили случайные числа с нашими TRNG с помощью теста работоспособности, определенного в SP800-90B [4].Этот тест постоянно проверяет наличие сбоев источника энтропии. Поэтому в наши микросхемы TRNG должна быть встроена схема проверки работоспособности. Однако мы не реализовали эту схему на наших изготовленных микросхемах, потому что цель реализации заключалась в оценке энтропии генератора случайных чисел на основе защелки. Вместо этого мы выполнили тест работоспособности в автономном режиме на ПК, используя случайные числа, полученные системой оценки в разделе 5.1, потому что TRNG не будут подходить для практического использования, если случайные числа не пройдут проверку работоспособности.Мы получили примерно 5,5 Мбит случайных чисел от каждого TRNG при изменении температуры и напряжения. Тест работоспособности состоит из двух тестов: теста количества повторений и теста адаптивной пропорции. Частота ложных срабатываний , которая представляет собой вероятность того, что идеальные истинные случайные числа не пройдут эти тесты, установлена ​​на 2 −30 , как рекомендовано в SP800-90B. [ Проверка счетчика повторений ] Целью проверки счетчика повторений является «быстрое обнаружение катастрофического отказа, из-за которого источник шума« застревает »на одном выходном значении на длительное время» [4]. Процедура проверки следующая. Если одно и то же значение (0 или 1) появляется последовательно c раз или более в последовательности случайных чисел, случайные числа являются ошибкой, где c = потолок (1 + 30 / мин-энтропия). В этой статье c равно 32, а мин-энтропия будет упомянута в разделе 5.2.3. [ Тест адаптивной пропорции ] Целью теста адаптивной пропорции является «обнаружение большой потери энтропии, которая может произойти в результате некоторого физического сбоя или изменения окружающей среды, влияющего на источник шума» [4] . Процедура проверки следующая. Сначала мы получаем 1-битное значение из начала случайных чисел в качестве опорного значения. Во-вторых, мы получаем один блок из последующих случайных чисел. Битовая длина блока представлена ​​размером окна , и если опорное значение оказывается больше, чем отсечка в раз в блоке, случайные числа являются ошибкой. Размер отсечки определяется частотой ложных срабатываний , мин-энтропией и размером окна .Эта процедура повторяется до конца случайных чисел. В наших оценках размер окна и отсечка составляли 64 и 55 для тестовых настроек I и 4096 и 2240 для тестовых настроек II. То есть около 84700 блоков были оценены для параметров теста I, и около 1350 блоков были оценены для параметров теста II, в каждом случае случайных чисел. В этом тесте значение отсечки отличается от значения в SP800-90B, когда размер окна равен 64, поскольку ожидается, что значение будет неправильным на основе расчета, приведенного в сноске на странице 35 в SP800-90B [4 ]. Случайные числа из MN-TRNG и ML-TRNG прошли все тесты на работоспособность в девяти случаях температуры и напряжения. В [6] ML-TRNG не прошли некоторые тесты в некоторых условиях. Однако после корректировки порогового значения ML-TRNG прошли все тесты на работоспособность в девяти случаях. Благодаря этому тесту наши TRNG будут постоянно проходить проверку работоспособности, если схема проверки работоспособности будет встроена в наш чип TRNG. Мы не оценивали тест на полный отказ в AIS20 / 31 с той же целью, потому что «тест должен быть выбран с учетом стохастической модели источника шума» [3], а стохастическая модель нашего ГПСЧ является дальнейшей работой. быть рассмотренным. Статистические тесты AIS20 / 31 Мы оценили случайные числа при различных температурах и напряжениях с помощью статистических тестов AIS20 / 31 [3]. Набор данных для этого теста был таким же, как и в разделе 5.2.1. AIS20 / 31 включает критерий оценки истинных генераторов случайных чисел, определенный BSI, то есть Федеральным ведомством Германии по информационной безопасности. AIS20 / 31 включает восемь стандартных статистических тестов, таких как покерный тест, длительный тест и тест равномерного распределения.Мы оценили наши TRNG с помощью статистических тестов для процедуры тестирования A в AIS20 / 31. В этой процедуре используются пять статистических тестов из восьми. Для идеального случайного числа вероятность прохождения тестов составляет ≈0,9987, а вероятность провала более двух тестов составляет ≈0. Если один тест не удался, выполняется второй запуск. Если второй тест не пройден, процедура тестирования A не выполняется [3]. AIS20 / 31 классифицирует TRNG на два класса: класс PTG.1 и класс PTG.2. TRNG в классе PTG.1 могут использоваться для генерации случайных чисел для аутентификации запроса и ответа.TRNG в классе PTG.2 могут использоваться для генерации ключей и начального числа для генераторов псевдослучайных чисел, поэтому эти TRNG обеспечивают более высокий уровень безопасности, чем в классе PTG.1. На рис. 6 показано количество ГПСЧ, прошедших тесты AIS20 / 31. Горизонтальная ось показывает окружающую среду при различных температурах и напряжениях. Вертикальная ось показывает количество ГПСЧ, прошедших тесты. MN-TRNG прошли испытания во всех случаях, поэтому наши MN-TRNG обладают устойчивостью к колебаниям температуры и напряжения.Однако ML-TRNG не прошли испытания только в двух случаях из 171. Две из 19 микросхем ML-TRNG не прошли испытания, и каждая микросхема ML-TRNG провалила один случай из девяти. Другими словами, 17 чипов из 19 прошли все статистические тесты AIS20 / 31. Для справки, мы повторно протестировали случайные числа двух вышедших из строя чипов, получив числа из файлов случайных чисел, удалив первые 10 000 бит и добавив биты в конце исходных случайных чисел. Оба случайных числа прошли статистические тесты AIS20 / 31.Мы считаем, что ML-TRNG также обладают устойчивостью к колебаниям температуры и напряжения независимо от отказов первых испытаний. В разделе 6.1 мы обсуждаем ML-TRNG с точки зрения количества защелок SR. Рис.6 Скорость прохождения AIS20 / 31. MN-TRNG прошли испытания AIS20 / 31 во всех 180 случаях. Однако ML-TRNG не прошли испытания в двух случаях из 171 . На основании этих оценок наши TRNG прошли стандартный статистический тест для PTG.1 и PTG.2 с точки зрения AIS20 / 31. Дополнительные тесты, включая тест на полный отказ и онлайн-тест, необходимы для того, чтобы рассматривать наши TRNG как PTG.1, и, кроме того, для PTG.2 требуется стохастическая модель источника энтропии; тем не менее, эту дальнейшую работу следует рассмотреть. SP800-90B IID-тест и мин-энтропия Мы используем мин-энтропию в качестве объективного критерия случайности. Мин-энтропия определяется как нижняя граница количества информации случайной величины [4].Минимальная энтропия на бит идеальных истинных случайных чисел равна 1, потому что соотношение нулей и единиц в идеале составляет 0,5. Метод оценки минимальной энтропии различается в зависимости от того, является ли TRNG независимым и одинаково распределенным (IID). Случайная последовательность оценивается как IID, когда «каждый элемент последовательности имеет то же распределение вероятностей, что и другие значения, и все значения взаимно независимы» [4]. Оценка состоит из шести тестов перетасовки и статистического теста. Поэтому сначала мы внедрили программное обеспечение для проверочных тестов IID в соответствии с SP800-90B и оценили наши TRNG с помощью этого теста.Набор данных для этого теста был таким же, как и в разделе 5.2.1. На рисунке 7 показана скорость прохождения теста IID для девяти случаев температуры и напряжения. По результатам, MN-TRNG прошли все 180 случаев, поэтому мы выполнили оценку минимальной энтропии для источников IID (см. Раздел 9.2 в [4]). Напротив, ML-TRNG прошли 166 случаев из 171. Мы, однако, рассматривали ML-TRNG как источники IID, потому что все 19 микросхем прошли испытания в нормальных условиях, то есть при 27 ° C и 1,80 В, а 14 микросхем из 19 прошли все испытания в девяти случаях температуры и напряжения.Мы считаем, что для прохождения всех тестов необходим ML-TRNG для подключения соответствующего компонента кондиционирования или увеличения количества защелок, как описано в разделе 6. Рис. 7 Скорость прохождения оценочного теста IID. MN-TRNG прошли оценочный тест IID во всех 180 случаях. Напротив, ML-TRNG прошли 166 случаев из 171. Мы, однако, рассматривали ML-TRNG как источники IID, потому что они прошли испытания в нормальных условиях, то есть при 27 ° C и 1,80 В На рисунках 8 и 9 показаны результаты оценки минимальной энтропии в MN-TRNG и ML-TRNG, соответственно.Индикация x, верхняя и нижняя строки показывают среднее, максимальное и минимальное значение минимальной энтропии на бит во всех тестовых случаях соответственно. Мин-энтропия очень близка к «1» (т. Е. Идеальной мин-энтропии) в обоих типах ГПСЧ. Следовательно, наши ГПСЧ имеют очень высокую минимальную энтропию независимо от температуры или напряжения. Рис. 8 Оценка минимальной энтропии (MN). Мин-энтропия очень близка к «1» (то есть идеальной мин-энтропии) в девяти случаях температур и напряжений.Индикация x , верхняя строка и нижняя строка строки показывают среднее, максимальное и минимальное значение минимальной энтропии в тестовых примерах соответственно . Рис. 9 Оценка минимальной энтропии (ML). Мин-энтропия была очень близка к «1» (идеальная мин-энтропия) в девяти случаях температур и напряжений. Индикация x , верхняя строка и нижняя строка показывают среднее, максимальное и минимальное значение минимальной энтропии в тестовых примерах соответственно . Статистические тесты SP800-22 Мы оценили случайные числа с помощью статистических тестов SP800-22 [1] для справки, поскольку эти тесты считаются полезными для анализа источников случайных чисел в AIS20 / 31 [3].Мы использовали набор статистических тестов NIST под названием «sts-2.1.2» [26] и рекомендуемые настройки параметров AIS 20/31. Мы выбрали микросхему MN-TRNG и получили случайные числа при комнатной температуре (25 ° C) и номинальном напряжении (1,8 В). Были оценены два набора данных (набор данных 1 и 2), и размер каждого набора данных составлял около 2 30 бит. Результаты тестов показаны в таблице 1. Звездочка означает, что тест состоял из нескольких подтестов и что показано минимальное значение p .Набор данных 1 прошел все тесты, а набор данных 2 прошел тесты, за исключением теста на совпадение неперекрывающихся шаблонов. Значения неудавшегося теста показаны жирным шрифтом . Мы считаем, что количество чипов должно увеличиться, чтобы правильно оценить последовательность MN-TRNG. Если значительное количество микросхем не проходит статистические тесты SP800-22, MN-TRNG потребуется соответствующий компонент кондиционирования или увеличение количества защелок в MN-TRNG, чтобы пройти все статистические тесты в SP800-22. Таблица 1 Результат статистического теста NIST 800-22. Мы оценили случайные числа с помощью статистических тестов SP800-22 [1] для справки. Мы использовали набор статистических тестов NIST под названием «sts-2.1.2» [26] и рекомендуемые настройки параметров AIS 20/31. Мы выбрали MN-TRNG и получили случайные числа при комнатной температуре (25 ° C) и номинальном напряжении (1,8 В) Оценка случайных защелок В этом разделе мы оценили поведение каждой защелки SR, чтобы прояснить причины устойчивости наших TRNG к колебаниям температуры и напряжения. Мы определили качество случайных защелок на основе доли единиц в выходной последовательности. Если последовательность случайной защелки имеет равное распределение 0 и 1, это считается хорошим случайным числом. Следовательно, 50 % является наивысшим качеством, а 0% (все 0) или 100% (все 1) — наихудшим. В [2] сообщается, что выходной сигнал TRNG прошел статистические тесты SP800-22, когда имелась одна высококачественная случайная защелка и 17 низкокачественных. Поэтому наш TRNG генерирует хорошие случайные числа, если есть несколько высококачественных случайных защелок от колебаний температуры и напряжения. Мы сосредоточились на двух осях оценки: количество случайных защелок и качество случайных чисел из каждой случайной защелки в нашем TRNG. Мы получили выходную последовательность размером около 21 Кбит от каждой защелки SR в девяти случаях температуры и напряжения на чип. Количество случайных защелок Мы оценили количество случайных защелок в 256 защелках. На рисунках 10 и 11 показано количество случайных защелок в MN-TRNG и ML-TRNG соответственно. Гистограммы, а также верхняя и нижняя линии показывают среднее, максимальное и минимальное количество случайных защелок в тестовых случаях. Рис.10 Количество произвольных защелок (MN). Гистограммы и верхняя и нижняя строки показывают среднее, максимальное и минимальное количество случайных защелок в девяти случаях температуры и напряжения, соответственно Рис. 11 Количество произвольных защелок (ML). Гистограммы и верхняя и нижняя строки показывают среднее, максимальное и минимальное количество случайных защелок в девяти случаях температуры и напряжения, соответственно Чем выше были температура и напряжение, тем больше было среднее количество случайных защелок для обоих типов TRNG, за исключением некоторых случаев.Даже при -20 ° C и 1,65 В количество случайных защелок достигло минимум 20 для ML-TRNG. Кроме того, мы заметили, что некоторые постоянные защелки меняются на случайные защелки при изменении окружающей среды. Количество случайных защелок для MN-TRNG, среднее значение которого составляло примерно 42, было более стабильным, чем для ML-TRNG, среднее значение которого составляло примерно 45. Качество случайных защелок На рисунках 12 и 13 показано, как качество случайных защелок в MN-TRNG и ML-TRNG соответственно.Здесь [a, b] и (a, b) обозначают закрытые и открытые интервалы соответственно. Например, [30%, 40%) представляют 30 % ≤ x <40 % , где x — это доля единиц в выходной последовательности. Мы считали, что качество случайных чисел одинаково в диапазоне от 0–10% до 90–100%. Таким образом, качество выходной последовательности было разделено на пять интервалов. Самая нижняя часть гистограммы, показывающая [40%, 60%], представляет случайные защелки, выводящие случайные числа высокого качества.Примерно 5% случайных защелок были качественными в любой среде. Кроме того, мы наблюдали, что качественная случайная фиксация температуры и напряжения стала низкокачественной при других температурах и напряжениях. Следовательно, высококачественные случайные защелки были изменены при изменении среды. Рис. 12 Качество случайных защелок (MN). Примерно 5% случайных защелок были качественными в девяти случаях температуры и напряжения Фиг.13 Качество случайных защелок (ML). Примерно 5% случайных защелок были качественными в девяти случаях температуры и напряжения Обсуждение нашего TRNG В любой среде было примерно 42 случайных защелки, и примерно 5% всех случайных защелок были высококачественными случайными защелками. Следовательно, ожидается, что в любой среде будет около двух высококачественных случайных защелок. Исходя из экспериментального результата в [2], мы ожидаем, что TRNG, включающий одну высококачественную случайную защелку, генерирует высококачественные случайные числа. No related posts. Оставить комментарийОтменить комментарий Ваш адрес email не будет опубликован. Обязательные поля помечены *