Какое наименьшее и простое начальное число для генератора случайных чисел?

40

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

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

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

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

Место на печатной плате крайне ограничено (может подойти только несколько самых маленьких SMD-деталей), поэтому я ищу самое маленькое и простое из возможных решений. Поэтому я исключу такие причудливые решения, как настоящие аппаратные средства ГСЧ, радиоприемники и т. Д.

Все, что у меня есть, это 16-битный таймер-счетчик в процессоре и неиспользуемый порт-порт, который имеет доступ к АЦП.

Мое текущее решение состоит в том, чтобы просто использовать резистор (настолько неточный, насколько это возможно), чтобы подать примерно половину напряжения питания на вывод АЦП, и подать на ГСЧ первое значение преобразования АЦП. Однако в настоящее время большинство 10% резисторов имеют погрешность менее 1% (было бы забавно представить лицо поставщика, когда я скажу им, что мы хотим найти резисторы SMD самого низкого качества, которые они могут найти), поэтому существует очень высокая вероятность несколько единиц, начиная с одного семени.

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

У кого-нибудь есть лучшее предложение? Не требуется, чтобы семена были равномерно распределены, но чем равномернее распределение, тем лучше. 16-битное начальное число с совершенно равномерным распределением было бы слишком хорошей мечтой, чтобы быть правдой, но я думаю, что приличного распределения на 5 или 6 битов может быть достаточно.

ВСЗ
источник
12
«Было бы забавно представить лицо поставщика, когда я скажу им, что мы хотим найти SMD-резисторы худшего качества, которые они могут найти», - было бы еще смешнее, если бы значение этого резистора было неопределенным на электрической схеме, и сказать Люди, работающие на производстве, что эта одна часть должна быть припаяна вручную после того, как печатная плата выходит из машины размещения, из корзины, где мы смешали все значения резисторов, которые у нас есть. - Потому что я ищу не ГСЧ, а семя . Поэтому, если он генерирует одно и то же значение почти каждый раз, когда это не так уж и плохо, важно быть разными на разных устройствах.
вс
8
Почему бы не записать случайное значение в память EEPROM во время производственного программирования? Таким образом, вы можете использовать самый интересный ГСЧ, который вам нравится, так как он будет только у программистов, а не конечных устройств. (Благодарю @immibis: ваш «немного другой файл программного обеспечения» дал мне идею.)
Calrion
2
Так что для ясности на 100% проблема заключается в том, что они могут начинать в одной и той же последовательности, а не в том, что они могут разойтись со временем, верно?
июня
2
Выбор вашей ГСЧ имеет значение: кому-то нужны семена хорошего качества, кому-то нет. Например, для Xorshift любое начальное число, кроме 0, будет работать и работать одинаково хорошо. Даже небольшая разница в исходном семени приведет к совершенно другой стартовой позиции в цикле ГСЧ.
curiousdannii
3
Вы можете объединить все ответы АЦП со статистикой и временем для еще большей случайности. Например, измерьте, сколько тактов процессора требуется, пока вы не возьмете N выборок, где младшие 3 младших бита равны 101, и M выборок, где младшие 3 младших бита равны 110. Расширьте эту концепцию по желанию.
WJL

Ответы:

24

Поместите параллельный резистор и конденсатор между выводом A / D и массой. Сделайте резистор достаточно высоким, желательно намного выше требуемого сопротивления входного сигнала для АЦП. Сделайте постоянную времени RC около 10 мкс. Например, 100 кОм и 100 пФ звучат как хорошая комбинация.

Чтобы получить значение с некоторой случайностью, поднимите на некоторое время высокий вывод, затем установите его на высокий импеданс и через несколько мкс возьмите A / D показание. В частности, если вы правильно используете время сбора АЦП, напряжение, которое он увидит, будет зависеть от значений R и C, тока утечки на контактах, других близлежащих шумов и температуры.

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

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

Олин Латроп
источник
Это звучит хорошо. Обязательно проверьте входной импеданс на АЦП - у серии Atmega8 аналоговый входной импеданс составляет 100 мегагерц, что делает значение резистора Олина немного низким.
stefandz
3
@stef: входной импеданс и импеданс сигнала, необходимые для правильного преобразования, - это две разные вещи. Да, входной импеданс очень высок, потому что это CMOS. Тем не менее, существует максимальный предел импеданса для сигнала, чтобы он мог заряжать образец и удерживать крышку в течение указанного времени, а также преодолевать любые утечки, которые могут иметь штырьки.
Олин Латроп
2
извините, из вашего ответа я подумал, что вы ссылаетесь на входное сопротивление, а не на исходное сопротивление. 10k - это максимальное максимальное сопротивление источника, указанное Atmega8, так что ваш ответ точен. Для справки, крышка S / H внутри 14pF, на случай, если кому-то будет интересно.
Стефандз
2
@stef: я отредактировал ответ, чтобы сделать это более понятным.
Олин Латроп
Вы пропустили лунную фазу и праздничные дни. Также рукой машет полезное дополнение, особенно если низкое содержание С и плохо экранированное.
Рассел МакМэхон
23

Некоторые возможные варианты:

  1. Предварительно запрограммируйте уникальный последовательный адрес для каждого устройства. Если у вас есть достаточно хороший алгоритм RNG, то даже последовательный список последовательных адресов даст совершенно разные результаты.

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

  3. Используйте транзистор BJT и создайте бета-зависимый усилитель. Это можно прочитать из АЦП для семян.

  4. Конденсаторы / индукторы, как правило, имеют гораздо худший допуск, чем резисторы. С их помощью вы можете построить какую-то схему фильтра (RC, RL, LC) и измерить выход с помощью АЦП.

helloworld922
источник
5
Я голосую за вариант 1, это решение с нулевым счетом, которое приведет к тому, что последовательности никогда не будут совпадать. Серийный номер и генератор RND могут сказать, что 16 битов делают любые устройства незначительными шансами подражать чужому образцу.
KalleMP
1
Мне также нравится решение один. Если вы используете простой алгоритм хеширования, все будет хорошо, даже если у вас есть последовательные серийные номера.
magu_
6
Хорошая особенность варианта 1 заключается в том, что некоторые устройства поставляются со встроенными серийными номерами (обычно это микросхемы, связанные с сетью / радиочастотами), поэтому вам даже не нужен отдельный шаг для записи серийных номеров
slebetman
3
Даже мусорный ГСЧ, такой как LCG , « будет давать совершенно разные результаты для последовательного списка последовательных адресов» . Я голосую за 1 тоже.
BlueRaja - Дэнни Пфлугхофт
3
Если у вас есть источник времени, то его использование в качестве основы для переключения на начальное число поможет сместить вещи между циклами. Добавьте к этому серийный адрес / номер или MAC-адрес, если он есть на вашем устройстве, и вы также исправите соответствие между устройствами. Я видел некоторое программное обеспечение, которое постоянно хранит некоторые или все случайные числа, сгенерированные для использования в качестве начального числа, даже после перезагрузки. Если ваши устройства имеют разное время работы, они должны разойтись.
TafT
8

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

Вы можете попробовать использовать неинициализированную память в микроконтроллере. Хитрость заключается в том, чтобы найти биты, которые имеют наиболее «сбалансированные» триггеры и на самом деле случайные. Процедура состоит в том, чтобы прочитать всю память, сбросить и повторить несколько раз, чтобы измерить, какие биты действительно случайны. Затем вы используете эту карту для считывания достаточного количества случайных битов для заполнения вашего PRNG или LFSR!

Этот метод должен дать вам случайные начальные числа, даже с идентичным оборудованием, более подробная информация (и ссылки) доступны в этой хакерской статье

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

Esoterik
источник
1
Вам действительно не нужно выяснять, какие биты являются случайными. Выполнение XOR всех байтов даст вам случайный результат, даже если только 8 битов являются случайными. И, как показано на рисунке, фактические значения могут быть не случайными во временном смысле, они достаточно уникальны - это именно то, что нам нужно здесь.
MSalters
1
Если вы можете найти PRNG, который позволяет вам «смешивать» энтропию, то это может быть даже лучше, чем опция XOR-then-seed. Итерируйте по неинициализированной памяти и смешайте байты с PRNG. Например, посмотрите мою простую случайную библиотеку C - функцию mix .
Крейг МакКуин,
Это не даст вам крипто-качественную случайность.
@CamilStaps конечно не будет.
Навин
1
Это не будет работать. Неинициализированная память - это неопределенное поведение, если у меня есть операционная система, и я не имею никакого контроля над тем, какая часть памяти будет назначена моей программе, а какая была раньше. На микроконтроллере без ОС это не так. Особенно с AVR, потому что там все ОЗУ будет равно нулю, если прошло достаточно времени для того, чтобы конденсаторы были опорожнены потреблением тока при отключении питания.
вс
7

Что я сделал для MP3-плеера со случайной возможностью, так это просто использовал разные последовательные начальные числа при каждом включении. Я начал с 1 и сохранил его в EEPROM, чтобы при следующем цикле питания я использовал 2 и т. Д. Это было на ATMEGA168. Как отметил helloworld922, даже простое последовательное начальное число будет генерировать совершенно разные псевдослучайные последовательности.

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

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

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

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

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

Кевин Уайт
источник
5

АЦП - очень хороший источник случайности.

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

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

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

CL.
источник
2
Я не уверен, что шум Джонсона подходит в этом приложении; На STP резистор на 10 МГц в полосе пропускания 10 кГц имеет 40uVшум Джонсона. Вам понадобится> 14-битный АЦП или схема усилителя, чтобы разумно измерить это.
helloworld922
STP не очень актуален. Температура может быть специально повышена, но дополнительные 60 градусов по сравнению с STP - это всего лишь 10% дополнительного шума.
MSalters
1
Аналогичным подходом будет использование дробового шума в диоде. en.wikipedia.org/wiki/Noise_generator#Shot_noise_generators
командный боб
2

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

Еще одна мысль: как связать несколько устройств вместе, чтобы они включались одновременно? Если они включены последовательно, добавьте какой-нибудь конденсатор, чтобы (n + 1) -ое устройство запускалось через несколько тактов после n-го устройства. В идеале, конденсаторы будут разряжаться очень быстро при выключении устройства, поэтому при каждом запуске / перезапуске между последовательностями будет больший разрыв.

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

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

Michaels
источник
1
возможно, подключите большую розетку к аналоговому штырьку и возьмите несколько показаний «сетевой гул», чтобы посеять ГСЧ.
Ясен
1
@Jasen, все устройства, подключенные к одному и тому же удлинителю, будут видеть один и тот же сетевой шум.
Ян Рингроз
2

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

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

Коврики
источник
2

Как насчет расширения вашей первоначальной идеи преобразования AD на основе переменного резистора путем добавления LDR или термистора? (Первым нужно было бы иметь возможность «смотреть» снаружи, я не знаю, возможно ли это; но изменение в освещении может быть выше, чем изменение температуры среди устройств, начатых примерно в одно и то же время, примерно в одном и том же месте. ..)

Хаген фон Айцен
источник
1
Термисторы входят с другим полезным свойством. Несколько серий от большинства производителей имеют огромную дисперсию и неточность. Это еще больше «улучшит» результат.
Ariser
1

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

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

  2. 1-проводные устройства Dallas используют только один контакт, и каждый из них имеет уникальный 64-битный серийный номер. Вы можете использовать это как семя.

Loganf
источник
1
Мне нравится 2, но, к сожалению, запчасти DS довольно дорогие.
Ariser
Не используйте производственную метку времени для случайного качества криптографии, это предсказуемо.
2
@CamilStaps Для применения ОП криптографическое качество не требуется
Хаген фон Айцен
1
@HagenvonEitzen верно, но другие могут прийти к этому вопросу в поисках случайности крипто-Q, так что стоит упомянуть.
4
@CamilStaps Вздох , кажется, вы отказались от человечества :) Неужели слишком сложно ожидать от кого-то, кто хочет использовать ответ от electronicsSE в криптографических целях, чтобы они были хотя бы достаточно осторожны, чтобы прочитать вопрос, на который он должен ответить? ? Семена "16bit" или "5 o5 6 bit" не являются крипто-Q, даже если они генерируются группой кошек Шредингера :)
Hagen von Eitzen
1

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

Не забудьте использовать минимально возможное время конвертации.

Другим решением может быть генератор шума, подключенный к выводу АЦП.

jnk0le
источник
2
Я сделаю некоторые измерения, но если я правильно помню, плавающий вывод АЦП читает 0или близко к 0. Я проверю это снова, чтобы увидеть, так ли это.
вс
1
Мне интересно, это читается 0при плавании?
Бенс Кауликс
2
Проблема в том, что это может сработать на плате разработки и потерпеть неудачу в конечном продукте.
вс