Можно ли генерировать случайные числа с помощью физических датчиков?

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

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

Предвзятость

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

При измерении аналогового входа, скажем, с 10-битным разрешением, в идеале диапазон чисел, собранных в результате измерения, будет охватывать все значения от 0 до 1024, и каждое значение будет встречаться с той же частотой (или вероятностью), что и любое другое значение из этого диапазона.

В действительности эти значения часто будут (более или менее) нормально распределены (распределены по Гауссу) вокруг некоторого среднего значения с некоторым характерным стандартным отклонением, например, около 500 при 10 битах на выборку.

Устранение предвзятости

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

Использование криптографических функций, таких как (односторонние) хеш-функции или алгоритмы шифрования, обычно также легко дает желаемый результат; однако за это приходится платить: «смешение» этих функций по замыслу чрезвычайно сильное, что делает невозможным определение качества (= случайности) исходных данных после преобразования. Даже самые простые детерминированные последовательности значений, такие как {1,2,3,4,5...}, при хешировании дают данные, которые, скорее всего, довольно хорошо пройдут любые статистические тесты на случайность, хотя они и не являются "случайными" в все.

Генерация энтропии на µC

Сроки

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

На самом деле энтропию можно получить даже из двух независимых источников тактового сигнала; например, синхронизируя циклы одних часов через другие часы. Это открывает пару очень интересных возможностей для микроконтроллеров Atmel AVR (которые используются в Arduino) в зависимости от возможностей микроконтроллера:

• Большинство AVR имеют внутреннюю память EEPROM. Операции записи в эту память синхронизируются с помощью специального таймера, который не зависит от основных системных часов (-, как сообщается, есть некоторые микросхемы (не типы!), где измерения показали, что это может быть не так)< em> (изменить: обратите внимание, что в некоторых AVR, например, ATTiny25/45/85, синхронизация EEPROM определяется внутренним RC-генератором, так что энтропия не может быть собрана, когда этот генератор также выбран в качестве источника системных тактовых импульсов) < /эм>; это может зависеть от основного источника тактового сигнала (внутренний R/C или внешний кристалл/резонатор). Следовательно, следует ожидать некоторого (действительно случайного) джиттера во времени, необходимом для записи в EEPROM, по отношению к основным системным часам, которые опять же можно измерить с помощью высокоскоростного таймера/счетчика.

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

• Многие AVR имеют возможность иметь выделенный таймер/счетчик, который синхронизируется с внешним кристаллом 32 кГц для повышения точности измерений в реальном времени. Этот внешний кристалл является еще одним источником событий, не связанных с основными часами. (Иначе лишний кристалл вообще был бы бесполезен...)

Последний кажется многообещающим из-за его потенциала относительно высокой пропускной способности: при синхронизации каждого тактового цикла 32 кГц с системным таймером, работающим значительно быстрее (коэффициент 600+ может быть достигнут на текущих AVR @ 20 МГц!) и консервативно предполагая только 1 бит энтропии на измерение, в результате получается 32000+ бит энтропии в секунду — намного больше, чем может когда-либо потреблять микроконтроллер.

РЕДАКТИРОВАТЬ: Тем временем я провел несколько простых тестов подхода таймера 32 кГц, и краткосрочные результаты кажутся довольно низкими. Верхняя граница генерируемой энтропии на образец кажется очень низкой, а я даже не тестировал образцы на наличие неочевидных паттернов, возникающих из-за более или менее регулярных фазовых сдвигов. Этот результат может быть связан с тем, что основной тактовый сигнал моего тестируемого устройства управляется внешним кристаллом, который, как можно ожидать, будет (в пределах точности измерений) столь же стабильным по частоте, как и кварц 32 кГц, при наблюдении в ограниченном временном диапазоне. Увеличение времени между двумя выборками (минуты?), вероятно, даст хорошую энтропию, но с очень низкой пропускной способностью. (Примечание: измеренный джиттер также может быть частично связан с различной задержкой прерывания в зависимости от машинной инструкции, выполняемой прямо в момент срабатывания прерывания.)

РЕДАКТИРОВАТЬ № 2: Похоже, что внутренний RC-генератор моего ИУ (ATmega1284) производит значительный джиттер частоты (несколько кГц/с); работа на этом генераторе действительно производит довольно большую энтропию (кбит/с) при синхронизации с внешним кристаллом 32 кГц.

В небольшом эксперименте я недавно исследовал первые два метода. На моем тестируемом устройстве синхронизация EEPROM обычно предпочтительнее WDT:

Синхронизация записи EEPROM дает около 4,82 бита энтропии на операцию записи, в то время как сторожевой таймер кажется более стабильным по частоте, давая около 3,92 бита на тайм-аут сторожевого таймера. Кроме того, времена записи в EEPROM кажутся гораздо более плавно распределенными по Гауссу, в то время как распределение WDT кажется несколько асимметричным и с большим количеством аберраций.

Nb: объединение нескольких «случайных» событий для одного измерения энтропии может фактически ухудшить полученную энтропию: быстрые случайные колебания в источнике могут частично компенсировать друг друга, давая значения результата с меньшим отклонением от среднего значения. Таким образом, вместо отсчета времени, например, одной секунды реального времени (32 000 циклов кристалла RTC), можно ожидать гораздо большей энтропии, если взять 32 000 тактов (по одному на каждый цикл кристалла) в течение одного и того же времени. время.

Неинициализированная оперативная память

В приложениях, скомпилированных с помощью Avr-gcc, обычно вся встроенная оперативная память очищается до 0x00 перед выполнением пользовательского кода, то есть main(). Помещение кода в ранний раздел .init обеспечивает доступ к необработанному неинициализированному содержимому ОЗУ до того, как оно будет перезаписано процедурами инициализации gcc.

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

Требования к пропускной способности

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

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

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

Предложение

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

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

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

/dev/urandom в Linux обычно реализуется таким образом.

Вывод

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

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

РЕДАКТИРОВАТЬ:

Подход PRNG может быть не лучшим выбором для криптографической генерации ключей. Для этого следует использовать только действительно случайные биты для создания безопасного ключа. Сбор такого количества энтропии может занять некоторое время (возможно, секунды), но, поскольку генерация ключей обычно не выполняется очень часто на µC, это вполне приемлемо. (На сильно загруженном сервере с сотнями или более соединений SSL (HTTPS) в секунду это будет совсем другая проблема...)

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

(С другой стороны, если количество энтропии в выходных данных источника может быть измерено или оценено, можно просто масштабировать длину ключа с коэффициентом (bitlength of key)/(entropy per bit sampled), а затем использовать необработанные данные с низкой энтропией непосредственно из источника энтропии для генерации этого более длинного ключа. , который будет иметь ту же общую энтропию, что и полностью случайный ключ исходной длины. Однако, если это действительно так, трюк зависит от того, как шифр обрабатывает ключи разной длины.)

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

Предположим, у вас есть датчик, который выводит значения в диапазоне от 0 до 200 с точностью 0,01. Скажем, это манометр, может, децибелметр. Вам нужно тщательно протестировать это и посмотреть на распределение значений для вашего конкретного датчика и окружающей среды, но я думаю, что цифры в позициях 10 ^ 0 и 10 ^ -1 вполне могут быть распределены равномерно и без видимого порядка.

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

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

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

Его можно найти в репозитории библиотеки Code.google.

Google: настоящий генератор случайных чисел

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