Доброго времени суток! Решил рассказать о простом и интересном способе получения честных случайных чисел на микроконтроллерах, не имеющих на борту аппаратного генератора случайных чисел. Достаточно, чтобы у микроконтроллера был АЦП и один свободный вход. Подробности под катом.
Идея не нова и много кому приходила в голову. Я её реализовал в одном из своих старых проектов на STM8S003F3, так что примеры кода будут к этому чипу, хотя перенести код на любую другую архитектуру не составит труда.
Суть заключается в том, что при измерении напряжения при помощи АЦП младшие биты результата наиболее подвержены шумам. Мы используем этот факт себе на пользу — будем делать несколько замеров, и записывать младший бит результата (как самый «шумный»). Таким образом сделав 8 измерений можно получить совсем случайный байт.
Ухудшим результаты измерения насколько это возможно. Установим наименьшее время выборки, а вывод микроконтроллера, на котором расположен вход АЦП, повесим «в воздухе», никуда не подтягивая и ни к чему не подключая. Чем больше шума — тем лучше.
Инициализация АЦП:
CLK_PCKENR2 |= 0x08; //Подаём тактирование на АЦП
ADC_CR1 = MASK_ADC_CR1_ADON; //Включение
ADC_CR2 = MASK_ADC_CR2_ALIGN;
ADC_CR3 = 0;
ADC_CSR = 4; //Выбор канала
Функция получения случайного байта:
unsigned char GetRandom(void) {
unsigned char i, result;
result = 0;
for (i = 0; i < 8; i++) {
ADC_CR1 = MASK_ADC_CR1_ADON; //Старт преобразования
while (ADC_CSR == 4); //Ждём установки флага окончания преобразования
result = (result << 1) + (ADC_DRL & 0x01);
ADC_CSR = 4; //Сбрасываем флаг окончания преобразования
}
return result;
}
Вот такая небольшая хитрость. Код восстанавливал по памяти, так что могут быть ошибки — о них прошу написать в ЛС.
Буду очень рад мнению опытных людей о таком способе получения случайных чисел.
Комментарии (34)
ishevchuk
12.06.2015 10:18Интересно глянуть на результат теста DieHard такого генератора)
qbertych
12.06.2015 10:45Первой же строчкой в похожих публикациях идет статья о NISTовских тестах, было бы любопытно посмотреть.
Ну и в первую очередь — проверьте 50 Герц.
qbertych
12.06.2015 10:51+2А возможна ли атака на ГСЧ на АЦП последовательного приближения, работающая на изменении входного сигнала в процессе преобразования? Младшие биты вычисляются последними, значит если во время их вычисления увеличить сигнал, то они станут единицами.
Alexeyslav
12.06.2015 11:13Это если взять дикий АЦП. В Мегах АЦП имеет УВХ, напряжение запоминается в УВХ в течении 2-х тактов и входное напряжение на результат измерения дальше не влияет.
С УВХ уже несколько другие проблемы возникают — например фиксация в УВХ от источника с высоким внутренним сопротивлением(в Мегах она решена повторителем на входе) и фиксация напряжения в то время как оно значительно меняется во время выборки(2 такта на частоте работы АЦП — это уже от сотни килогерц).
qw1
12.06.2015 11:02+2result = (result << 1) + (result & 0x01);
Ф-ция всегда будет выдавать нули. Хороший такой random…
MuLLtiQ
12.06.2015 11:06+13
HWman
12.06.2015 11:56Помниться когда я увидел впервые эту картинку я минут 15 смеялся.
roboter
12.06.2015 12:00+2а getTommorowDate видели? :)
mrsom
12.06.2015 12:16не нагугливается что-то…
johniek_comp
12.06.2015 12:24+18Long getTommorowDate(){ Thread.sleep(60 * 60 * 24 * 1000); Return getCurrentDate(); }
Alexeyslav
12.06.2015 11:18+3Качество такого ГСЧ будет чуть выше плинтуса — слишком сильны будут корреляции с работой внутренних узлов контроллера, и с промышленной сетью в 50Гц.
Чтобы улучшить характеристики генератора — нужен источник шумов(полупроводник например) и усилитель, для исключения корреляции с работой контроллера и его периферийных узлов нужно серьёзно отфильтровать питание для усилителя и собственно источника шума, изолировать его от помех. Но и в таком случае характеристики генератора будут зависеть от температуры среды в которой работает схема и уровня радиоактивного излучения. Это просто надо иметь в виду, но в домашних условиях такой генератор будет работать гораздо лучше.
Mendel
12.06.2015 15:29Угу. Лично я зашел сюда в надежде увидеть какое-то решение по созданию хорошего белого шума.
А так тут разве что собирать с килобайт «случайности» и в хеш, а потом этим инициировать ГПСЧ.
exmachine
12.06.2015 14:36+2Есть более изолированный вариант ГСЧ.
В варианте для AVR, он основан на нестабильности частоты RC генератора watchdog таймера по отношению к генератору тактовой частоты на кварце.
Вот пример реализации: gist.github.com/endolith/2568571
Stas911
12.06.2015 15:31Резальтаты тестов такого генератора было б интересно глянуть, насколько он случайный
NightRadio
14.06.2015 20:32Успешно использую подобный генератор в шумовом синтезаторе Quantum DJ: warmplace.ru/hard/qdj/index_ru.php
Alexeyslav
15.06.2015 17:13+1По странным обстоятельствам у меня бывает драйвер аудио чудит и не всегда плеер после снятия с паузы начинает воспроизведение с байта кратного семплу, в итоге для 16 бит иногда младший разряд становится старшим а старший младшим. На выходе получается шум(даже в паузах), но если прислушаться корреляция с музыкой есть!
Кстати, в схеме не подключен AGND, помимо того что это может стать причиной смерти МК это может добавить корреляции случайностей с работой внутренних узлов контроллера до такой степени что будут игнорироваться внешние воздействия ниже определенной величины.
И я кстати такие эксперименты совершенно случайно тоже проводил — на проводочек АЦП ловил полный размах по напряжению на входе на то что я в метре от схемы вставал/садился на кресло.
AIV_Electronics
17.06.2015 08:23Действительно, нужно первым делом проверить проходят ли полученные числа по критериям случайности! Тестов полно таких.
Уверен, что для криптографии такой генератор не подойдет.
Лично проверял функцию rand() на ПК: хорошо подобранная и натасканная нейросеть предсказывает следующее число почти с 50% вероятностью.Mendel
17.06.2015 10:25+2Реквестирую статью по этому поводу :)
AIV_Electronics
17.06.2015 11:03+1Я так понимаю речь идет про функцию rand().
Статью я писать наверное не буду, но всё расскажу. ;)))
Вот ссылка на методическое пособие по которому я это всё делал ещё в студенческие годы:
iit1.mpei.ac.ru/pubkrug1.pdf
Кроме теоретической части в пособии на стр. 163 дан пример анализа последовательности случайных чисел ПК любого из математических пакетов (MathCad, MatLab и д.р.). Там написано как и что делать, как обучить сеть и дана уже заранее хорошо подобранная под эту задачу топология нейросети.
Нейросеть отличается способностью улавливать малейшие закономерности в данных, что и выплывает в функции rand(), которая генерирует не совсем случайные числа, а использует остаток от вычисления по довольно расширенной формуле.
Практическая проверка показывает, что нейросеть угадывает числа rand() от 0 до 99 с высокой вероятностью и, как минимум, почти всегда попадает в диапазон +-5 от искомого числа.
Желающие могут самостоятельно повторить эксперимент.
HomoLuden
25.06.2015 17:49Следуя предложенному подходу, более надежно будет к упомянотуму входу АЦП подключить Волоконно-Оптический Гироскоп, вычесть постоянную составляющую сигнала. У ВОГ шумы имеют очень даже Нормальное Распределение и достаточно белые, т.е. с равномерной спектральной характеристикой. Жалко только стоимость тагого ГСЧ будет в сотни тыр.
ГСЧ нужен не абы какой, а с требуемым распределением. Иначе он не лучше чем генераторы псевдослучайных чисел. Можно, например, взять несколько ГпСЧ (от трех штук), перемножить числа каждой выборки этих нескольких генераторов… но будет ли такой композитный генератор криптостойким? И не будет ли он выдавать «цветной шум»?
toxicdream
1. Ставим незаметно как можно ближе генератор «нужных» шумов
2. Profit!!!
EighthMayer Автор
Не думаю что сработает, так как помимо сигнала генератора по-прежнему будет полно других шумов.
toxicdream
Спорить не буду, но проверить надо.
ozonar
5-7 лет назад группа исследователей заморозила плату с АЦП (До порядка -70 градусов), и тем самым увеличила предсказуемость принимаемого с АЦП сигнала, так что способ влиять на АЦП — есть.
Впрочем, способ создания генератора не нов (я им ещё на первом курсе универа пользовался), и подходит для любых целей, кроме создания криптоустойчивых систем, важно только брать последние три бита с АЦП, влияние внешних вакторов на которых минимально.
mrsom
Так то АЦП нужно подключать к генератору белого шума, а не просто в воздух вешать. Оставленный в воздухе вывод скорее всего будет ловить навдоку 50Гц. Ну и воздействовать на него внешним сигналом не составит труда. Да и просто закоротить на общий провод )))
Как говорилось выше: для криптографии такой вариант абсолютно точно не подходит!
А зачем тогда еще он нужен? Чем это лучше псевдослучайного rand()? На крайний случай инициализируйте генератор каким-нибудь числом вычисляемым в рантайме: например измеряйте время нажатия кнопки включения устройства или ещё что-то в этом роде.
Итоговая «случайность» будет не хуже вашего метода.
SquareIronBox
Ну, в некоторых приложениях всё же нужны случайности без криптостойкости. Те же самые китайские лампы настроения из-за отсутствия настоящей случайности горят всегда по одной и той же последовательности, что раздражает (отличная лампа настроения). Более того, даже разные лампы могут гореть одинаково.
Ну а ещё, например, шаффл для плеера, роботы, игрушки, в том числе развивающие. Много где пригодится.
Влияние 50 Гц на младший бит, по моему мнению, минимально. Если только вход АЦП не будет входить в ограничение.
Идея, кстати, не нова. Лет пять назад видел статейку, в которой этот случайный байт использовался как затравка для софтового ГСЧ.
mrsom
В общем я бы расценивал такой вариант как последний из возможных.
Примерно в таком порядке рассматриваю варианты:
-Если устройство требует пользовательского ввода — используем его(длительность нажатия кнопки) для инициализации ГСЧ.
-Если в контроллере есть eeprom, то можно просто инкрементить ячейку с инициализацией каждый раз при включении девайса.
-Трюки с АЦП.
SquareIronBox
А чем EEPROM проще генерации с использованием АЦП?
И использовать длительность нажатия кнопки не всегда получится. В устройстве просто может не оказаться кнопки.
Alexeyslav
А как же кнопка включения?
SquareIronBox
В таком устройстве скорее окажется слайдерный переключатель или тумблер, отрубающий батарейку.