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

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

Рубрика: Технические науки

Дата публикации: 19.12.2015 2015-12-19

Статья просмотрена: 4130 раз

Библиографическое описание:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тепловой шум

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Источник

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

Вопрос: а нет ли в современных процессорах CISC аппаратного ГСЧ? А если есть, то как с ним работать?

Вопрос просто для удовлетворения любопытства

1 ответ 1

Нашел в Википедии упоминание о RdRand. Процитирую здесь статью

RdRand это инструкция для генерации случайного числа при помощи встроенного генератора случайных чисел. RdRand доступен для архитектуры процессоров Ivy Bridge и является опциональным расширением набора инструкций Intel 64 и IA-32. Данный генератор случайных чисел соответствует стандартам безопасности и криптографическим стандартам, таким как NIST SP800-90, FIPS 140-2, и ANSI X9.82.

Описание

Для проверки поддержки процессором RDRAND можно использовать инструкцию CPUID . При наличии поддержки бит 30 регистра ECX оказывается установлен после вызова функции 01H инструкции CPUID. Опкод RDRAND 0x0F 0xC7 .

Компилятор С++, входящий в MS Visual Studio 2013, поддерживает RDRAND посредством функций _rdrand16_step(unsigned short *random_val) и _rdrand32_step(unsigned int *random_val) . Если удалось сгенерировать случайное число, используя аппаратный генератор процессора, функция возвращает 1, в противном случае возвращается 0. Само сгенерированное случайное число передается в память по указателю.

Алгоритм

Две пары чисел по 256 бит, полученных из аппаратного источника энтропии, передаются в аппаратный блок, выполняющий криптографический алгоритм AES в режиме CBC-MAC. Полученное 256-битное значение используется для инициализации ГПСЧ (CTR_DRBG из раздела 10.2.1 стандарта NIST SP 800-90, с использованием AES)

Источник

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

Про генераторы случайных чисел написано очень много, но почти всегда, когда дело доходит до реализации, подразумевается (или явно говорится), что речь идет об x86/x64 и других «взрослых» архитектурах. В то же время, форумы, посвященные разработке устройств на микроконтроллерах, пестрят вопросами «как мне сгенерировать случайное число на %controllername%?». Причем диапазон ответов простирается от «смотри гугл/википедию» до «используй стандартную функцию». Далеко не всегда эта «стандартная функция» есть и устраивает разработчика по всем параметрам, чаще наоборот: то числа получаются далеки от случайных, то скорость работы слишком мала, а то полученный код вообще не помещается в свободную память.
Попробуем разобраться, какие бывают алгоритмы генерации случайных чисел, как выбрать подходящий, а главное, в чем особенности реализации этих алгоритмов на контроллерах.

Оценка «случайности»

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

• Частотный тест. Состоит в подсчете количества нулей и единиц в последовательности битов. Единиц и нулей должно быть примерно поровну.
• Тест на последовательность одинаковых битов. Ищутся ряды одинаковых битов, вида 000. 0 или 111. 1. Распределение частот, с которыми встречаются ряды, в зависимости от их длины, должно соответствовать такому распределению для истинно случайного сигнала.
• Спектральный тест. К исходной последовательности применяется дискретное преобразование Фурье. Полученный спектр не должен иметь значительных пиков, которые говорили бы о наличии периодических свойств последовательности.
• Автокорреляционный тест. Подсчитывается значение корреляции между копиями последовательности, сдвинутыми друг относительно друга. Тест позволяет найти повторяющиеся участки в последовательности.

Существуют специальные наборы, включающие в себя десятки подобных тестов:
NIST — использовался в конкурсе AES для оценки алгоритмов шифрования.
DIEHARD — один из наиболее строгих существующих наборов.

Алгоритмы ГПСЧ

Любая последовательность, сгенерированная по жестко заданному алгоритму, не может считаться истинно случайной, поэтому, ведя речь об алгоритмических генераторах, употребляют термин псевдослучайная последовательность. Любой генератор псевдослучайных чисел (ГПСЧ) рано или поздно зацикливается, другое дело в том, что это «поздно» может наступить через несколько миллисекунд, а может через несколько лет. Длина цикла зависит от размера внутреннего состояния генератора N (фактически, это объем памяти, нужный генератору), и составляет от 2 (N/2) до 2 N бит.
Алгоритмов ГПСЧ придумано огромное множество, но далеко не все они удобны для реализации на микроконтроллерах. Мы сильно ограничены в быстродействии и доступном объеме памяти, многие контроллеры не поддерживают вещественную арифметику и даже команды умножения. Помня о подобных ограничениях, рассмотрим некоторые известные алгоритмы.

Линейный конгруэнтный метод

Очередной член последовательности рассчитывается по формуле
X_i+1 = (aX_i + c) mod m
Число m определяет максимальный период последовательности, целые числа a и c — «магические» коэффициенты. Число m разумно выбирать равным степени двойки, в таком случае опреация приведения по модулю сводится к отбрасыванию старших битов. Для того, чтобы получить максимальный период, нужно соблюдать следующие условия:
— c и m должны быть взаимно простыми,
— a-1 должно быть кратно p для всех простых делителей p числа m,
— если m кратно 4 (а в нашем случае оно будет кратно), то и a-1 должно быть кратно 4.
Есть еще одна тонкость: в качестве результата следует брать только старшие биты переменной состояния X, так как для младших бит статистические параметры случайности значительно хуже. Линейный конгруэнтный алгоритм обычно реализован в качестве стандартного rand() во многих библиотеках.

Плюсы:

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

Минусы:

• требуется операция умножения;
• не все биты одинаково случайны.

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

Метод Фибоначчи с запаздываниями

В этом алгоритме используется соотношение
X_i = X_i-a — X_i-b,
где переменная состояния X — беззнаковое целое. Величины запаздываний a и b берутся не какие угодно, а строго определенные, для достижения максимального качества рекомендуются пары (17,5), (55,24) или (97,33). Чем больше запаздывания, тем больше период и лучше спектральные свойства последовательности. С другой стороны, для работы генератора требуется хранить max предыдущих чисел, что не всегда приемлемо. Также для запуска генератора нужно max чисел, которые обычно получают при помощи более простого ГПСЧ.

Плюсы:

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

Минусы:

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

Резюме: очень качественный, но ресурсоемкий алгоритм.

Регистр сдвига с линейной обратной связью

Переменная состояния хранится в регистре длины N. Генерация следующего состояния включает два шага:

1. Подсчитывается значение бита C = X_i1 xor X_i2 xor… X_ik, где i1, i2… ik — номера битов регистра, называемые отводами.
2. Регистр сдвигается на 1 бит вправо, крайний левый бит принимает значение С.

Выходом генератора является крайний правый (или крайний левый, или любой другой) бит регистра, то есть псевдослучайная последовательность генерируется по одному биту за итерацию. При правильно выбранных номерах отводов период генератора составит 2 N — 1. «Минус один», так как существует запрещенное нулевое состояние регистра. Номера отводов для N от 3 до 168 можно посмотреть в этом документе.
Кроме описанной выше конфигурации, которая, кстати, называется конфигурацией Фибоначчи (не путать с одноименным методом ГПСЧ!), существует т.н. конфигурация Галуа.

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

Плюсы:

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

Минусы:

• нужно проверять начальное значение на неравенство нулю.

Резюме: очень быстрый и довольно качественный алгоритм.

Криптостойкие алгоритмы

Для применения в криптографии к ГПСЧ предъявляется еще одно существенное требование: необратимость. Все перечисленные выше алгоритмы этим свойством не обладают: зная несколько выходных значений ГПСЧ, можно, решив несложную систему уравнений, найти параметры алгоритма (те самые «магические» константы a, b, с и т.д). А зная параметры, можно воспроизвести всю псевдослучайную последовательность.
В качестве криптографически стойкого алгоритма ГПСЧ можно использовать любой достаточно сильный блочный шифр. Выбрав секретный ключ, можно получать блоки псевдослучайных чисел, применяя алгоритм к последовательным натуральным числам. Для N-битного блочного шифра период будет не больше 2 N . Безопасность такой схемы полностью зависит от секретности ключа.
Все современные криптографические алгоритмы проходят проверку на использование в качестве ГПСЧ, то есть, используя сертифицированный алгоритм, не нужно специально заботиться о статистических и спектральных свойствах выходного потока. Переживать нужно только о вычислительной «прожорливости» криптоалгоритмов. Если требуется выполнять большое количество операций шифрования, имеет смысл выбрать контроллер с аппаратными криптографическими блоками. Часто в таких контроллерах есть и весьма неплохой криптостойкий аппаратный ГПСЧ.

Источники энтропии

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

Активность пользователя

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

Аналого-цифровой преобразователь

Во многих контроллерах есть встроенные АЦП. И во многих контроллерах они весьма посредственного качества, сделанные просто «чтобы было». Младшие биты результата АЦП почти всегда содержат значительный шум, даже если измеряется постоянное напряжение. Это можно использовать: подключите вход АЦП к напряжению питания через делитель, проведите несколько десятков измерений, возьмите младшие биты — вот вам отличное случайное число. Если АЦП содержит встроенный предусилитель, включите его, он тоже шумит.

Асинхронные генераторы

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

Часы реального времени

Если в схеме есть часы реального времени, можно использовать их текущие показания для инициализации ГПСЧ. Например, преобразовав текущие дату/время в формат Unix time, мы получим сразу 32 бита, которые никогда больше не повторятся, если только не снимать показания чаще одного раза в секунду. Использование реального времени дает уникальность значений, но не дает никакой непредсказуемости, поэтому лучше комбинировать данный способ с другими.

RC-цепь

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

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

Аппаратный генератор шума

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

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

Заключение

Напоследок расскажу одну историю из жизни. Началась она с очередного заданного на форуме вопроса «как мне сгенерировать случайное число на контроллере?». Автор вопроса пояснил, что делает в качестве курсового проекта устройство, эмулирующее бросание игральной кости. После нескольких безуспешных попыток разобраться в алгоритмах, топикстартер поделился своим решением: он просто бросил 1000 раз настоящий кубик и забил полученными числами всю свободную память контроллера. Генератор с блеском прошел все тесты на «случайность», учитывая то, что за время демонстрации израсходовал меньше трети своего «запаса».
Следовательно, такое решение тоже имеет право на жизнь, особенно если предъявляются очень строгие требования к случайности чисел, но они требуются не слишком часто. Учитывая стремительно падающие цены на память, может быть разумным снабдить устройство флешкой с «запасом хаоса», которого хватит на все время жизни устройства.
Благодарю за внимание!

UPD1: Как было справедливо отмечено в комментариях, если предполагается атака на ГСЧ, и у злоумышленника будет аппаратный доступ к устройству, применять внешние источники энтропии нужно с большой осторожностью, так как не составляет большой сложности подменить сигнал от внешнего источника. Следует использовать внутренние источники, можно в дополнение к внешним.
Также хорошая идея — накапливать энтропию все свободное время, а использовать ее тогда, когда требуется сгенерировать очередное случайное число. Обычно в таких случаях используется т.н. Entropy pool — массив, над которым периодически выполняется одна из функций ГПСЧ, и куда постоянно подмешиваются данные из источников энтропии.

UPD2: Во многих случаях полезно содержимое Entropy pool (извините, не знаю нормального русского перевода) сохранять в EEPROM для того, чтобы после выключения-включения устройства не накапливать его заново. Это отностится, прежде всего, к получению энтропии методом асинхронных генераторов: при достаточно стабильных условиях после каждого включения может генерироваться одна и та же последовательность.
Если ожидается атака, примите меры против подмены содержимого EEPROM. Если позволяет контроллер, заблокируйте чтение/стирание/запись при помощи lock-битов, при включении контролируйте целостность EEPROM, хотя бы с помощью простейших контрольных сумм.

Источник