Генерация случайных чисел на микроконтроллерах



    Про генераторы случайных чисел написано очень много, но почти всегда, когда дело доходит до реализации, подразумевается (или явно говорится), что речь идет об x86/x64 и других «взрослых» архитектурах. В то же время, форумы, посвященные разработке устройств на микроконтроллерах, пестрят вопросами «как мне сгенерировать случайное число на %controllername%?». Причем диапазон ответов простирается от «смотри гугл/википедию» до «используй стандартную функцию». Далеко не всегда эта «стандартная функция» есть и устраивает разработчика по всем параметрам, чаще наоборот: то числа получаются далеки от случайных, то скорость работы слишком мала, а то полученный код вообще не помещается в свободную память.
    Попробуем разобраться, какие бывают алгоритмы генерации случайных чисел, как выбрать подходящий, а главное, в чем особенности реализации этих алгоритмов на контроллерах.


    Оценка «случайности»


    Применения для ГСЧ могут найтись самые разные, от игрушек до серьезной криптографии. Соответственно, и требования, предъявляемые к генератору, тоже сильно варьируются. Для оценки качества (уровня «случайности») генератора существуют специальные тесты. Вот самые основные из них:
    • Частотный тест. Состоит в подсчете количества нулей и единиц в последовательности битов. Единиц и нулей должно быть примерно поровну.
    • Тест на последовательность одинаковых битов. Ищутся ряды одинаковых битов, вида 000...0 или 111...1. Распределение частот, с которыми встречаются ряды, в зависимости от их длины, должно соответствовать такому распределению для истинно случайного сигнала.
    • Спектральный тест. К исходной последовательности применяется дискретное преобразование Фурье. Полученный спектр не должен иметь значительных пиков, которые говорили бы о наличии периодических свойств последовательности.
    • Автокорреляционный тест. Подсчитывается значение корреляции между копиями последовательности, сдвинутыми друг относительно друга. Тест позволяет найти повторяющиеся участки в последовательности.

    Существуют специальные наборы, включающие в себя десятки подобных тестов:
    NIST — использовался в конкурсе AES для оценки алгоритмов шифрования.
    DIEHARD — один из наиболее строгих существующих наборов.

    Алгоритмы ГПСЧ


    Любая последовательность, сгенерированная по жестко заданному алгоритму, не может считаться истинно случайной, поэтому, ведя речь об алгоритмических генераторах, употребляют термин псевдослучайная последовательность. Любой генератор псевдослучайных чисел (ГПСЧ) рано или поздно зацикливается, другое дело в том, что это «поздно» может наступить через несколько миллисекунд, а может через несколько лет. Длина цикла зависит от размера внутреннего состояния генератора N (фактически, это объем памяти, нужный генератору), и составляет от 2(N/2) до 2N бит.
    Алгоритмов ГПСЧ придумано огромное множество, но далеко не все они удобны для реализации на микроконтроллерах. Мы сильно ограничены в быстродействии и доступном объеме памяти, многие контроллеры не поддерживают вещественную арифметику и даже команды умножения. Помня о подобных ограничениях, рассмотрим некоторые известные алгоритмы.

    Линейный конгруэнтный метод

    Очередной член последовательности рассчитывается по формуле
    Xi+1 = (aXi + c) mod m
    Число m определяет максимальный период последовательности, целые числа a и c — «магические» коэффициенты. Число m разумно выбирать равным степени двойки, в таком случае опреация приведения по модулю сводится к отбрасыванию старших битов. Для того, чтобы получить максимальный период, нужно соблюдать следующие условия:
    c и m должны быть взаимно простыми,
    a-1 должно быть кратно p для всех простых делителей p числа m,
    — если m кратно 4 (а в нашем случае оно будет кратно), то и a-1 должно быть кратно 4.
    Есть еще одна тонкость: в качестве результата следует брать только старшие биты переменной состояния X, так как для младших бит статистические параметры случайности значительно хуже. Линейный конгруэнтный алгоритм обычно реализован в качестве стандартного rand() во многих библиотеках.

    Плюсы:
    • максимально возможный период для заданного размера переменной состояния;
    • достаточно быстрый;
    • часто уже реализован в библиотеке компилятора.

    Минусы:
    • требуется операция умножения;
    • не все биты одинаково случайны.

    Резюме: быстрый и простой алгоритм для не очень ответственных применений.

    Метод Фибоначчи с запаздываниями

    В этом алгоритме используется соотношение
    Xi = Xi-a — Xi-b,
    где переменная состояния X — беззнаковое целое. Величины запаздываний a и b берутся не какие угодно, а строго определенные, для достижения максимального качества рекомендуются пары (17,5), (55,24) или (97,33). Чем больше запаздывания, тем больше период и лучше спектральные свойства последовательности. С другой стороны, для работы генератора требуется хранить max{a,b} предыдущих чисел, что не всегда приемлемо. Также для запуска генератора нужно max{a,b} чисел, которые обычно получают при помощи более простого ГПСЧ.

    Плюсы:
    • не требует операций умножения;
    • все биты случайного числа равнозначны по статистическим свойствам.

    Минусы:
    • требует большого объема памяти;
    • требует большого массива чисел для запуска.

    Резюме: очень качественный, но ресурсоемкий алгоритм.

    Регистр сдвига с линейной обратной связью


    Переменная состояния хранится в регистре длины N. Генерация следующего состояния включает два шага:
    1. Подсчитывается значение бита C = Xi1 xor Xi2 xor… Xik, где i1, i2… ik — номера битов регистра, называемые отводами.
    2. Регистр сдвигается на 1 бит вправо, крайний левый бит принимает значение С.

    Выходом генератора является крайний правый (или крайний левый, или любой другой) бит регистра, то есть псевдослучайная последовательность генерируется по одному биту за итерацию. При правильно выбранных номерах отводов период генератора составит 2N — 1. «Минус один», так как существует запрещенное нулевое состояние регистра. Номера отводов для N от 3 до 168 можно посмотреть в этом документе.
    Кроме описанной выше конфигурации, которая, кстати, называется конфигурацией Фибоначчи (не путать с одноименным методом ГПСЧ!), существует т.н. конфигурация Галуа.

    Вместо того, чтобы использовать для генерации нового крайнего левого бита сумму битов отводной последовательности, выполняется XOR каждого бита отводной последовательности с крайним правым битом, затем выполняется циклический сдвиг всего регистра вправо. Эта схема сложнее для понимания, но проще в реализации, так как все опрерации XOR можно выполнить одновременно. По длине периода и качеству псевдослучайных чисел схемы Фибоначчи и Галуа эквивалентны.

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

    Минусы:
    • нужно проверять начальное значение на неравенство нулю.

    Резюме: очень быстрый и довольно качественный алгоритм.

    Криптостойкие алгоритмы

    Для применения в криптографии к ГПСЧ предъявляется еще одно существенное требование: необратимость. Все перечисленные выше алгоритмы этим свойством не обладают: зная несколько выходных значений ГПСЧ, можно, решив несложную систему уравнений, найти параметры алгоритма (те самые «магические» константы a, b, с и т.д). А зная параметры, можно воспроизвести всю псевдослучайную последовательность.
    В качестве криптографически стойкого алгоритма ГПСЧ можно использовать любой достаточно сильный блочный шифр. Выбрав секретный ключ, можно получать блоки псевдослучайных чисел, применяя алгоритм к последовательным натуральным числам. Для N-битного блочного шифра период будет не больше 2N. Безопасность такой схемы полностью зависит от секретности ключа.
    Все современные криптографические алгоритмы проходят проверку на использование в качестве ГПСЧ, то есть, используя сертифицированный алгоритм, не нужно специально заботиться о статистических и спектральных свойствах выходного потока. Переживать нужно только о вычислительной «прожорливости» криптоалгоритмов. Если требуется выполнять большое количество операций шифрования, имеет смысл выбрать контроллер с аппаратными криптографическими блоками. Часто в таких контроллерах есть и весьма неплохой криптостойкий аппаратный ГПСЧ.

    Источники энтропии


    Как уже было сказано, используя только детерминированные алгоритмы, невозможно сгенерировать истинно случайное число. Поэтому обычно применяется связка ГПСЧ + внешний источник энтропии. Источник энтропии используется для задания начального значения для ГПСЧ, а задача последнего сводится к обеспечению спектральной и статистической чистоты последовательности. Что же можно использовать в качестве источника энтропии? Да практически что угодно.

    Активность пользователя

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

    Аналого-цифровой преобразователь

    Во многих контроллерах есть встроенные АЦП. И во многих контроллерах они весьма посредственного качества, сделанные просто «чтобы было». Младшие биты результата АЦП почти всегда содержат значительный шум, даже если измеряется постоянное напряжение. Это можно использовать: подключите вход АЦП к напряжению питания через делитель, проведите несколько десятков измерений, возьмите младшие биты — вот вам отличное случайное число. Если АЦП содержит встроенный предусилитель, включите его, он тоже шумит.

    Асинхронные генераторы

    Можно использовать разницу периодов двух несинхронизированных тактовых генераторов. Большинство контроллеров содержат, например, сторожевой таймер. Для повышения надежности он тактируется от отдельного генератора, никак не связанного с основным тактовым сигналом. Достаточно подсчитать число тактов основного тактового сигнала за один период сторожевого таймера. Если подобрать периоды так, чтобы счетчик за время измерения многократно переполнился, можно получить достаточно случайное число. Недостаток этого метода — он требует много времени, до нескольких секунд.

    Часы реального времени

    Если в схеме есть часы реального времени, можно использовать их текущие показания для инициализации ГПСЧ. Например, преобразовав текущие дату/время в формат Unix time, мы получим сразу 32 бита, которые никогда больше не повторятся, если только не снимать показания чаще одного раза в секунду. Использование реального времени дает уникальность значений, но не дает никакой непредсказуемости, поэтому лучше комбинировать данный способ с другими.

    RC-цепь

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

    Выводим на этот порт сигнал «0» — конденсатор разряжается. Переключаем порт в режим входа — конденсатор начинает заряжаться. Когда напряжение на нем достигнет порога, вход переключится из состояния «0» в «1». Время заряда сильно зависит от многих факторов: напряжаения питания, дрейфа параметров RC-цепи, нестабильности порога, температуры, утечек, помех. Измеряя его с достаточной точностью и беря младшие биты, можно получить хорошую случайность.

    Аппаратный генератор шума

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

    Для того, чтобы порог срабатывания компаратора не влиял на статистические свойства полученного сигнала, применяют два генератора шума, работающие на один компаратор:


    Заключение


    Напоследок расскажу одну историю из жизни. Началась она с очередного заданного на форуме вопроса «как мне сгенерировать случайное число на контроллере?». Автор вопроса пояснил, что делает в качестве курсового проекта устройство, эмулирующее бросание игральной кости. После нескольких безуспешных попыток разобраться в алгоритмах, топикстартер поделился своим решением: он просто бросил 1000 раз настоящий кубик и забил полученными числами всю свободную память контроллера. Генератор с блеском прошел все тесты на «случайность», учитывая то, что за время демонстрации израсходовал меньше трети своего «запаса».
    Следовательно, такое решение тоже имеет право на жизнь, особенно если предъявляются очень строгие требования к случайности чисел, но они требуются не слишком часто. Учитывая стремительно падающие цены на память, может быть разумным снабдить устройство флешкой с «запасом хаоса», которого хватит на все время жизни устройства.
    Благодарю за внимание!

    UPD1: Как было справедливо отмечено в комментариях, если предполагается атака на ГСЧ, и у злоумышленника будет аппаратный доступ к устройству, применять внешние источники энтропии нужно с большой осторожностью, так как не составляет большой сложности подменить сигнал от внешнего источника. Следует использовать внутренние источники, можно в дополнение к внешним.
    Также хорошая идея — накапливать энтропию все свободное время, а использовать ее тогда, когда требуется сгенерировать очередное случайное число. Обычно в таких случаях используется т.н. Entropy pool — массив, над которым периодически выполняется одна из функций ГПСЧ, и куда постоянно подмешиваются данные из источников энтропии.

    UPD2: Во многих случаях полезно содержимое Entropy pool (извините, не знаю нормального русского перевода) сохранять в EEPROM для того, чтобы после выключения-включения устройства не накапливать его заново. Это отностится, прежде всего, к получению энтропии методом асинхронных генераторов: при достаточно стабильных условиях после каждого включения может генерироваться одна и та же последовательность.
    Если ожидается атака, примите меры против подмены содержимого EEPROM. Если позволяет контроллер, заблокируйте чтение/стирание/запись при помощи lock-битов, при включении контролируйте целостность EEPROM, хотя бы с помощью простейших контрольных сумм.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 39

      +4
      Отличная статья, спасибо. Интересный случай с кубиком :)
        0
        На счет кубика — много раз слышал об использование такого трюка :).
        • UFO just landed and posted this here
          +5
          Хорошей идеей будет собирать внешние события ДО того, как будет нужно сгенерить число, и сохранять их в EEPROM, чтобы сброс питания не приводил к одинаковым результатам.

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

          Так что, ИМХО, только внутренние источники, зависящие от внешних параметров, и не сбрасывающиеся при пропадании питания. Причем сколько там получится обычных таймеров за один watchdog — получим несколько чисел (последовательных). Надо разницу фаз брать, причем примешивать к предыдущим значениям, а таймер переиничивать в main, с задержками, зависящими от предыдущего сгенеренного числа, к примеру…
            0
            Спасибо за дополнения, добавил в статью.
              0
              А по поводу сохранение переменной состояния в EEPROM — не вижу особых преимуществ. Атака в данном случае очень простая: выключаем питание, перешиваем EEPROM нужными нам данными, включаем обратно, PROFIT!11
              Далеко не все контроллеры имеют возможность залочить EEPROM от изменения при помощи программатора.
                +2
                Преимущества просты:
                1. сквозная генерация чисел. Часто видел людей, которые завязывались на таймеры, потом включали прибор, и у них — 2,4,19,3… выключали, включали — 2,4,19,3… то есть одинаковое поведение после ресета. Просто потому что прибор лежит в кондиционированном помещении, стабильность генераторов хорошая, последовательность всегда одинаковая. А тут она будет продолжаться.
                2. Да, не все, но как правило, все же лочат. Многие лочат так, что стереть можно только вместе с прошивкой.
                3. Можно писать в EEPROM программы, но это уже от применяемого контроллера зависит. Насколько я знаю, считать EEPROM сложно, проще стереть и записать нули. Но это просто добавляется проверка на чистоту EEPROM/CRC.
                  +1
                  Умные мысли добавлены в статью :)
                  0
                  *сохранениЯ
                  • UFO just landed and posted this here
                      0
                      Плавающий бит использовали на ПЗУ стираемых ультрафиолетом. В микроконтроллерах такой финт не пройдет. Хотя, если во время записи отключить питание…
                        0
                        Рисунок такой ПЗУ размещен в начале статьи.
                          0
                          Если во время записи отключить питание...

                          В прошлых ревизиях контроллеров ATMega (кажется) был такой баг, что при пониженном (но еще в пределах номинального) напряжении питания запись в EEPROM вызывала случайные повреждения содержимого случайных ячеек. Пользу из этого бага никто так и не научился извлекать :)
                        0
                        С EEPROMомом есть другая фишка, ведь он мягко говоря не вечен!
                        Его можно задрючить так, что отдельные адреса будут дохлые, и их можно считать, и даже попытаться изменить их состояние, только оно уже не изменится :-)

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

                        PS. И раз уж речь пошла про системы шифрования, не стоит забывать о таком инструменте исследования как напильник, микроскоп и контакты к кристаллу, это всё лишь вопрос бюджета.
                      0
                      Спасибо!
                      Кажется, это первая относительно «взрослая статья» по микроконтроллерам на хабре!

                      от себя добавлю:
                      1 еще в качестве источникоа энтропии можно использовать встроенный датчик температуры (он обычно и делается не калиброваным)

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

                      думаю, в приложениях где действительно нужна безопасность есть смысл использовать именно их!
                        0
                        Да, про аппаратное шифрование упомянул. Проблема в том, что такие контроллеры — относительная редкость. Из того, что встречал, большинство семейств ориентированы на применение в смарт-картах, отсюда низкая универсальность, малое число выводов, мало полезной периферии… А криптография и защита от вторжения там да, на уровне!
                          0
                          фрискейл делает на кортекс м4 с огромной кучей периферии и ног за сотню
                            0
                            а еще у кого-нибудь м4 появились? не в курсе? я только анонсы встречал
                              0
                              осенью ST обещают и то это будут инженерные образцы только. насколько я знаю только фрискейл пока
                        0
                        отличная статья!
                        вот например, в бытовом компьютере zx-spectrum, чтобы очень быстро получить достаточно рандомное значение использовали регистр регенерации R, это простой 8-битный счетчик, который увеличивается каждый раз при выполнении цикла регенерации. насколько я знаю, такой прием можно использовать много где. (ведь, при генерации выскакивающих врагов особая рандомизация и не нужна, пожалуй, вообще достаточно таблицы =)

                        так же с sinclair basic была команда RANDOMIZE, которая задавала вектор рандомизации. в прошивке функция рандома была относительно простая и, насколько я помню, генерировала ответ на основе считывания прошивки. вот RANDOMIZE и задавал смещение от начала, как-то так.
                        подробней например, можно тут. www.worldofspectrum.org/ZXBasicManual/zxmanchap11.html
                          0
                          Насколько понял из статьи по ссылке, там использовался линейный конгруэнтный метод, причем не с самыми лучшими параметрами. Но особо сильный рандом там и не нужен.
                            0
                            Да, в Z80 можно было использовать регистр R.
                            А в x86 есть команда rdtsc.
                            +2
                            хорошие результаты еще дают сочетания регистр сдвига с линейной обратной связью и клеточного автомата

                            image
                              0
                              а что такое клеточный автомат?
                                0
                                Клеточный автомат это по сути набор ячеек, состояние каждой из которых задается определенным правилом и зависит от состояния соседних ячеек.
                                  0
                                  о, это как game of life получается!
                                    0
                                    ну да, чем то похоже, только в применение к генераторам ПСП поле игры будет одномерным. и в случае «умирания всей жизни» будет использована инжекция «живых клеток».
                                      0
                                      Можно использовать правила жизни при которых вырождения не происходит.
                                      Например бесконечное саморазмножение, но ИМХО применение такого рода правил будет эквивалентно танцам со сдвиговыми регистрами…
                                0
                                Получится ли реализовать клеточный автомат при приемлимых вычислительных затратах? Насколько понимаю, на каждом такте придется пробегать по всему регистру и модифицировать каждый бит, причем по довольно сложной логической формуле.
                                  +1
                                  Видел два ГПСЧ на основе клеточного автомата.
                                  первый описан здесь.
                                  а второй — из математики — cellular automaton rule 90
                                  Обоими можно поиграться в Randomness.
                                  0
                                  Про «никогда больше не повторится» для 32-битного unix time — не совсем верно, если быть педантичным, в 2038 году он завернется (Y2K38 bug, аналогично более известному Y2K).
                                  Хотя разумеется крайне маловероятно, что девайсина будет использоваться настолько долго, чтобы это было критично
                                    0
                                    Не проблема, отсчитывайте в цикле. Вряд ли ваше устройство проработает без перерыва 2^32 секунд
                                    0
                                    Отличная статья. Я разрабатываю методы исследования источников энтропии. Был бы рад провести тесты ваших контролеров.
                                      0
                                      У меня самого руки чешутся провести аппаратные тесты, все никак не доберусь до своих любимых железяк :)
                                      Если вы проверите что-то из описанного на практике — буду только признателен.
                                        0
                                        Давно хочу поиграться с шумом стабилитронов.
                                        Есть мнение что на качество шума отдельно взятого диода можно мистическим образом воздействовать.
                                        Ибо теоретически, схема с одним шумистором питаемым источником ТОКа, была бы вполне эквивалентна схеме с двумя. Ведь нет статистической разницы между подкидыванием одной монеты, и двух…
                                        Но старые перцы, говорят что де факто, она есть, и что-то смещает гаусово распределение.
                                        В приведённой в статье схеме, это можно было объяснять плаваньем порога компаратора, и режима стабилитрона, но если использовать для его питания источник тока, то плавать ему некуда. И поэтому реально есть схемы с двумя шумелками, ибо даже мистические факторы, будут воздействовать на обе шумелки, и распределение вероятностей получится равномерным.
                                          0
                                          Есть более простое объяснение, почему используют два диода. Даже забудем на время, откуда именно берется шумовой сигнал (обозначим напряжение шума Uш(t)). Нам нужно его оцифровать, для этого используется компаратор. Как работает компаратор? Если Uш > Uпорог, на выходе 1, если Uш < Uпорог, на выходе 0, все просто. Сложность в том, чтобы подобрать Uпорог так, чтобы 0 и 1 в полученной последовательности встречались с равной вероятностью.
                                          А теперь возьмем два источника шума. На выходе компаратора будет 1, если Uш1 > Uш2, и 0, если Uш1 < Uш2. Если источники шума одинаковые, оба события равновероятны.
                                            0
                                            Именно так, смещаем порог или сигнал относительно него, и получаем сдвиг распределения, но это всё замечательно лечится электронным путём, так что совершенно не реагирует на внешние факторы, вроде температуры, радиации, электрического или магнитного поля.
                                            0
                                            Вы правы, по-хорошему, шумящий стабилитрон нужно питать от источника тока. Схема в статье предельно упрощена, просто для иллюстрации принципа. А бывают еще теплые ламповые генераторы шума, на спецальных лампах (вроде 2Д2С), специально для того предназначенных. При соблюдении режимов работы лампы она выдает шум со строго заданным заранее известным распределением.
                                          0
                                          Был бы рад применить ваши исследования источников энтропии в своем Randomness Framework =)

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