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

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

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

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

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

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



Взять аналог "реального мира" измерения обычно являются хорошим источником[энтропия](https://en.wikipedia.org/wiki/Entropy_%28information_theory%29) (a.k.a. реальные случайные данные). Аналоговые источники всегда имеют некоторый непредсказуемый шум, который может быть «собран». Однако, как было указано ранее, измеренные данные редко оказываются непредвзятыми.

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

Bias
----

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

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

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

De-biasing
----------

Таким образом, для генерации случайных значений с желаемыми свойствами (см. Выше) необходимо выполнить некоторое смещение: A[экстрактор случайности](https://en.wikipedia.org/wiki/Randomness_extractor) какой-то нужен

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

Generating entropy on a µC
--------------------------

### Timing

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

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

* Most AVRs have internal EEPROM memory. Write operations to this memory are timed by a dedicated timer which is independent of the main system clock (- reportedly there are some chips (not types!) where measurements indicated that this may not be the case)*(edit: note that in some AVRs, ATTiny25/45/85 for example, the EEPROM timing is derived from the internal RC oscillator, so that no entropy can be gathered when this oscillator is also selected as the system clock source)*; this may depend on the main clock source (internal R/C vs. external crystal/resonator). Therefore, there is some (truly random) jitter to be expected in the time it takes to write to the EEPROM with respect to the main system clock, which again can be measured be a high-speed timer/counter.
* Newer AVRs have the capability to let the watchdog timer generate a software interrupt instead of a hardware reset. The watchdog timer is by design controlled by its own independent clock source, which yields the relative jitter one can measure.
* Many AVRs have the capability to have a dedicated timer/counter be clocked from an external 32kHz crystal for improved accuracy of real-time measurements. This external crystal is another source of events uncorrelated with the main clock. (Otherwise there would be no use in the extra crystal in the first place...)

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

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

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

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

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

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

### Uninitialized RAM

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

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

Bandwidth requirements
----------------------

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

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

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

Proposal
--------

Когда нужны сильные случайные числа, нередко объединяют один или несколько источников реальной энтропии с сильным[ПСЧ](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)используя энтропию, собранную для (повторного) посева PRNG каждый раз, когда доступна новая энтропия.

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

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

Linux & APOS; s[`/dev/urandom`](https://en.wikipedia.org/wiki//dev/random) обычно реализуется таким образом.

Conclusion
----------

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

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

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

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

Для создания качественных битропотоков с высокой энтропией, подходящих для генерации ключей[экстрактор случайности](https://en.wikipedia.org/wiki/Randomness_extractor) как упомянуто выше должно быть использовано.

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



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

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

Можно найти на[Code.google хранилище библиотеки](https://code.google.com/p/avr-hardware-random-number-generation/)



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

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