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

Ответ 1

Измерения аналогового "реального мира" обычно являются хорошим источником entropy (реальные случайные данные a.k.a.). У аналоговых источников всегда есть непредсказуемый шум, который можно "собрать". Однако, как указывалось ранее, измеренные данные редко не предвзяты.

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

Уклон

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

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

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

De-смещение

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

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

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

Timing

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

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

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

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

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

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

EDIT: Между тем, я провел несколько простых тестов по таймеру 32 кГц, а краткосрочные результаты выглядят довольно низкого качества. Верхняя граница генерируемой энтропии на образец кажется очень низкой, в то время как я даже не тестировал образцы для неочевидных паттернов, происходящих из более или менее регулярных фазовых сдвигов. Этот результат может быть обусловлен тем, что у моего DUT были свои основные часы, обусловленные внешним кристаллом, который, как ожидается, будет (в пределах точности измерений) одинаково стабильным по частоте в качестве кварца 32 кГц при наблюдении в течение ограниченного интервала времени. Увеличение времени между двумя образцами (минуты?), Вероятно, вернет хорошую энтропию, но с очень низкой полосой пропускания. (N.b.: Измерение дрожания также может быть частично связано с изменением задержки прерывания в зависимости от машинной команды, выполняемой в момент срабатывания прерывания.)

EDIT # 2: Похоже, что внутренний RC-генератор моего DUT (ATmega1284) вызывает значительный джиттер частоты (несколько кГц/с); работа на этом осцилляторе, по-видимому, производит довольно много энтропии (kBits/s) при синхронизации с внешним кристаллом 32 кГц.

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

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

N.b: Агрегация нескольких "случайных" событий для одного измерения энтропии может фактически деградировать полученную энтропию: быстрые случайные колебания в источнике могут частично компенсировать друг друга, давая результаты с меньшим отклонением от среднего значения. Таким образом, вместо времени, например, одного реального времени (32 тыс. Циклов кристалла RTC) можно ожидать гораздо большей энтропии от приема 32k таймингов (по одному для каждого цикла кристалла) в течение того же времени.

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

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

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

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

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

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

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

Предложение

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

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

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

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

Заключение

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

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

EDIT:

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Можно найти в Репозиторий библиотеки Code.google

Ответ 4

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

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