АЦП в качестве генератора случайных чисел


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

    Идея не нова и много кому приходила в голову. Я её реализовал в одном из своих старых проектов на 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;
    }
    

    Вот такая небольшая хитрость. Код восстанавливал по памяти, так что могут быть ошибки — о них прошу написать в ЛС.

    Буду очень рад мнению опытных людей о таком способе получения случайных чисел.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 34

      +7
      1. Ставим незаметно как можно ближе генератор «нужных» шумов
      2. Profit!!!
        +2
        Не думаю что сработает, так как помимо сигнала генератора по-прежнему будет полно других шумов.
          0
          Спорить не буду, но проверить надо.
            +1
            5-7 лет назад группа исследователей заморозила плату с АЦП (До порядка -70 градусов), и тем самым увеличила предсказуемость принимаемого с АЦП сигнала, так что способ влиять на АЦП — есть.

            Впрочем, способ создания генератора не нов (я им ещё на первом курсе универа пользовался), и подходит для любых целей, кроме создания криптоустойчивых систем, важно только брать последние три бита с АЦП, влияние внешних вакторов на которых минимально.
              +3
              Так то АЦП нужно подключать к генератору белого шума, а не просто в воздух вешать. Оставленный в воздухе вывод скорее всего будет ловить навдоку 50Гц. Ну и воздействовать на него внешним сигналом не составит труда. Да и просто закоротить на общий провод )))
              Как говорилось выше: для криптографии такой вариант абсолютно точно не подходит!
              А зачем тогда еще он нужен? Чем это лучше псевдослучайного rand()? На крайний случай инициализируйте генератор каким-нибудь числом вычисляемым в рантайме: например измеряйте время нажатия кнопки включения устройства или ещё что-то в этом роде.
              Итоговая «случайность» будет не хуже вашего метода.
                +3
                Ну, в некоторых приложениях всё же нужны случайности без криптостойкости. Те же самые китайские лампы настроения из-за отсутствия настоящей случайности горят всегда по одной и той же последовательности, что раздражает (отличная лампа настроения). Более того, даже разные лампы могут гореть одинаково.
                Ну а ещё, например, шаффл для плеера, роботы, игрушки, в том числе развивающие. Много где пригодится.
                Влияние 50 Гц на младший бит, по моему мнению, минимально. Если только вход АЦП не будет входить в ограничение.

                Идея, кстати, не нова. Лет пять назад видел статейку, в которой этот случайный байт использовался как затравка для софтового ГСЧ.
                  0
                  В общем я бы расценивал такой вариант как последний из возможных.
                  Примерно в таком порядке рассматриваю варианты:
                  -Если устройство требует пользовательского ввода — используем его(длительность нажатия кнопки) для инициализации ГСЧ.
                  -Если в контроллере есть eeprom, то можно просто инкрементить ячейку с инициализацией каждый раз при включении девайса.
                  -Трюки с АЦП.
                    0
                    А чем EEPROM проще генерации с использованием АЦП?

                    И использовать длительность нажатия кнопки не всегда получится. В устройстве просто может не оказаться кнопки.
                      0
                      А как же кнопка включения?
                        0
                        В таком устройстве скорее окажется слайдерный переключатель или тумблер, отрубающий батарейку.
            0
            Интересно глянуть на результат теста DieHard такого генератора)
              0
              Первой же строчкой в похожих публикациях идет статья о NISTовских тестах, было бы любопытно посмотреть.

              Ну и в первую очередь — проверьте 50 Герц.
              +2
              А возможна ли атака на ГСЧ на АЦП последовательного приближения, работающая на изменении входного сигнала в процессе преобразования? Младшие биты вычисляются последними, значит если во время их вычисления увеличить сигнал, то они станут единицами.
                0
                Это если взять дикий АЦП. В Мегах АЦП имеет УВХ, напряжение запоминается в УВХ в течении 2-х тактов и входное напряжение на результат измерения дальше не влияет.
                С УВХ уже несколько другие проблемы возникают — например фиксация в УВХ от источника с высоким внутренним сопротивлением(в Мегах она решена повторителем на входе) и фиксация напряжения в то время как оно значительно меняется во время выборки(2 такта на частоте работы АЦП — это уже от сотни килогерц).
                +2
                result = (result << 1) + (result & 0x01);

                Ф-ция всегда будет выдавать нули. Хороший такой random…
                  +13
                  image
                    0
                    Помниться когда я увидел впервые эту картинку я минут 15 смеялся.
                      +2
                      а getTommorowDate видели? :)
                        0
                        не нагугливается что-то…
                          +18
                          Long getTommorowDate(){
                            Thread.sleep(60 * 60 * 24 * 1000);
                            Return getCurrentDate();
                          }
                          
                    +2
                    Я ведь и сказал что по ошибкам — в ЛС… Сейчас исправлю.
                      +1
                      Зато сколько позитива в ветке
                    +3
                    Качество такого ГСЧ будет чуть выше плинтуса — слишком сильны будут корреляции с работой внутренних узлов контроллера, и с промышленной сетью в 50Гц.
                    Чтобы улучшить характеристики генератора — нужен источник шумов(полупроводник например) и усилитель, для исключения корреляции с работой контроллера и его периферийных узлов нужно серьёзно отфильтровать питание для усилителя и собственно источника шума, изолировать его от помех. Но и в таком случае характеристики генератора будут зависеть от температуры среды в которой работает схема и уровня радиоактивного излучения. Это просто надо иметь в виду, но в домашних условиях такой генератор будет работать гораздо лучше.
                      0
                      Угу. Лично я зашел сюда в надежде увидеть какое-то решение по созданию хорошего белого шума.
                      А так тут разве что собирать с килобайт «случайности» и в хеш, а потом этим инициировать ГПСЧ.
                      +2
                      Есть более изолированный вариант ГСЧ.

                      В варианте для AVR, он основан на нестабильности частоты RC генератора watchdog таймера по отношению к генератору тактовой частоты на кварце.

                      Вот пример реализации: gist.github.com/endolith/2568571

                        0
                        А где Von Neumann extractor?
                          0
                          Резальтаты тестов такого генератора было б интересно глянуть, насколько он случайный
                            +1
                            Вот здесь лежит библиотека для Arduino, которая считывает младший бит АЦП с неподключенного пина и применяет к нему «von Neumann whitening algorithm» для получения хороших («True») случайных чисел.
                              0
                              Успешно использую подобный генератор в шумовом синтезаторе Quantum DJ: warmplace.ru/hard/qdj/index_ru.php
                                +1
                                По странным обстоятельствам у меня бывает драйвер аудио чудит и не всегда плеер после снятия с паузы начинает воспроизведение с байта кратного семплу, в итоге для 16 бит иногда младший разряд становится старшим а старший младшим. На выходе получается шум(даже в паузах), но если прислушаться корреляция с музыкой есть!
                                Кстати, в схеме не подключен AGND, помимо того что это может стать причиной смерти МК это может добавить корреляции случайностей с работой внутренних узлов контроллера до такой степени что будут игнорироваться внешние воздействия ниже определенной величины.
                                И я кстати такие эксперименты совершенно случайно тоже проводил — на проводочек АЦП ловил полный размах по напряжению на входе на то что я в метре от схемы вставал/садился на кресло.
                                0
                                Действительно, нужно первым делом проверить проходят ли полученные числа по критериям случайности! Тестов полно таких.
                                Уверен, что для криптографии такой генератор не подойдет.
                                Лично проверял функцию rand() на ПК: хорошо подобранная и натасканная нейросеть предсказывает следующее число почти с 50% вероятностью.
                                  +2
                                  Реквестирую статью по этому поводу :)
                                    +1
                                    Я так понимаю речь идет про функцию rand().
                                    Статью я писать наверное не буду, но всё расскажу. ;)))
                                    Вот ссылка на методическое пособие по которому я это всё делал ещё в студенческие годы:
                                    iit1.mpei.ac.ru/pubkrug1.pdf
                                    Кроме теоретической части в пособии на стр. 163 дан пример анализа последовательности случайных чисел ПК любого из математических пакетов (MathCad, MatLab и д.р.). Там написано как и что делать, как обучить сеть и дана уже заранее хорошо подобранная под эту задачу топология нейросети.
                                    Нейросеть отличается способностью улавливать малейшие закономерности в данных, что и выплывает в функции rand(), которая генерирует не совсем случайные числа, а использует остаток от вычисления по довольно расширенной формуле.
                                    Практическая проверка показывает, что нейросеть угадывает числа rand() от 0 до 99 с высокой вероятностью и, как минимум, почти всегда попадает в диапазон +-5 от искомого числа.
                                    Желающие могут самостоятельно повторить эксперимент.
                                  0
                                  Следуя предложенному подходу, более надежно будет к упомянотуму входу АЦП подключить Волоконно-Оптический Гироскоп, вычесть постоянную составляющую сигнала. У ВОГ шумы имеют очень даже Нормальное Распределение и достаточно белые, т.е. с равномерной спектральной характеристикой. Жалко только стоимость тагого ГСЧ будет в сотни тыр.

                                  ГСЧ нужен не абы какой, а с требуемым распределением. Иначе он не лучше чем генераторы псевдослучайных чисел. Можно, например, взять несколько ГпСЧ (от трех штук), перемножить числа каждой выборки этих нескольких генераторов… но будет ли такой композитный генератор криптостойким? И не будет ли он выдавать «цветной шум»?

                                  Only users with full accounts can post comments. Log in, please.