Реализация генератора случайных чисел на микроконтроллере MSP430

Введение

В семействе микроконтроллеров MSP430 низкочастотный генератор (VLO, very-lowfrequency oscillator) и программно управляемый генератор (DCO, digitally controlled oscillator) являются двумя самостоятельными системами с независимыми источниками тактирования. Поскольку источники тактирования разные, то временную разницу между этими системами можно использовать для получения потока псевдослучайных бит.

Действительно, на один такт осциллятора VL мы всегда получим одинаковое количество осцилляций DC, но поскольку источники тактирования независимы друг от друга, между нарастающим и ниспадающим фронтом VLO количество тактов DCO всегда будет либо четным, либо нечетным, и это непредсказуемо. Очень важно понимать, что четность этой величины непредсказуема, даже если известно ее предыдущее значение. Таким образом, мы можем просто отконфигурировать Timer_A для подсчета количества тактов DCO между двумя VLO-фронтами и, выделяя младший бит результата, составить случайное значение любой длины, например 16-разрядное целое.

Итак, устанавливаем таймер ‘А’ (Timer_A) в режим захвата, источником же основного тактирования SMCLK определяем DCO, он же будет источником импульсов для таймера ‘A’. За вспомогательное тактирование ACLK будет отвечать VLO, который одновременно послужит триггером захвата, то есть таймер ‘A’ считает количество тактов DCO между фронтами VLO. Количество тактов DCO автоматически сохраняется таймером в регистре захвата/сравнения (CCR). Младший бит регистра (CCR), посредством операции левого сдвига, сохраняем в регистре R12, и так 16 раз, пока получим 16-разрядную псевдослучайную величину.

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

В некотором смысле, мы пытаемся повысить ее энтропию.

Поступим следующим образом:

• После каждой операции выделения младшего бита регистра (CCR) мы поменяем значение регистра BCSCTL1, прибавив к его значению число пять (0x05). Это действие изменит содержимое битов RSEL регистра BCSCTL1, которые отвечают за выбор одного из внутренних резисторов DCO, то есть влияют на частоту DCO. Таким образом, после выборки каждого бита мы перенастраиваем частоту DCO, внося тем самым дополнительный элемент случайности. Необходимо оговориться, что для изменения битов RSELx мы могли бы прибавлять к регистру BCSCTL1 любое другое число, но, как показала практика, числа пять вполне достаточно, чтобы обеспечить необходимое отклонение частоты DCO по отношению к VLO.
• Следующий шаг заключается в динамическом изменении значения делителя основного модуля тактирования (биты DIVA). После каждой операции выделения младшего бита регистра (CCR) мы применяем операцию «исключающее ИЛИ» (XOR) к двум младшим битам регистра R12 и битам DIVA, тем самым опять же динамически меняя частоту.
• И, наконец, последняя хитрость: каждый выделенный бит будем записывать в результат (случайную величину) только после пяти циклов выборки, на основании мажоритарной системы, то есть из полученных пяти битов выбираем значение, вошедшее в выборку большее количество раз. Этот ход даст нам более равномерное распределение и, как следствие, позволит данному генератору пройти проверку одним из статических тестов.

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

Статические испытания

Поскольку известно, что при использовании детерминированных алгоритмов получаемая последовательность является не «чисто» случайной, а псевдослучайной, уместен вопрос: насколько близки эти последовательности по своему поведению к случайным? Для этого предлагалось и применялось множество разнообразных методов статистических испытаний. Один из статических тестов, рекомендованных FIPS (Federal Information Processing Standards), был включен в исходный код генератора случайных чисел. Это так называемый «покер-тест». Приведем краткое описание алгоритма данного теста.

Возьмем поток из 20 000 битов и последовательно разделим его на 5000 четырехбитных сегментов (тетрад). Так как возможно всего 16 вариантов таких сегментов, подсчитаем и запомним количество вхождений в нашу последовательность каждого из них и обозначим их как f( i ). Применим формулу:

Тест пройден, если 2,16 < X < 46,17.

Необходимо отметить, что данный тест приведен исключительно в качестве примера. Этот метод генерации псевдослучайных величин не проходил официальное тестирование FIPS и не имеет соответствующего сертификата.

Заключение

В последнее время в разговорах с разработчиками, особенно когда речь идет о случайных последовательностях, при упоминании приставки «псевдо-» все чаще можно услышать весьма негативные отзывы. По мнению многих специалистов, настоящий ГСЧ программным быть не может! Теперь такое можно услышать даже от людей, весьма далеких от разработки. С этим трудно спорить, и, по сути, они правы: действительно, хорошего распределения на чисто программном генераторе не получить, нужно обязательно привязаться хотя бы к какой-нибудь действительно случайной величине. Не зря же классические генераторы случайных чисел построены на всевозможных физических явлениях. Н апример, практически белый шум лавинного пробоя p-n-перехода дает очень неплохой результат. Но мы и не ставили перед собой задачу построить идеальный или близкий к идеальному ГСЧ, наша цель — получить пару-тройку случайных значений с неплохим распределением без использования сложной схемотехники, и при этом — с минимальными затратами. Понятно, что разработчики устройств шифрования и других устройств, где «слабый» ГСЧ может скомпрометировать всю систему, даже не посмотрят в нашу сторону. Однако такой способ генерации случайных величин вполне имеет право на существование и наверняка найдет не одно достойное применение.

Литература

1. Kaiser U. Hermes8: A Low-Complexity Low-Power Stream Cipher. http://eprint.iacr.org/2006/019.pdf
2. Schindler W. Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications, CHES2002 workshop. http://ece.gmu.edu/crypto/ches02/talks_files/Schindler.pdf
3. Shannon R. E. Systems Simulation // The Art and Sc. — Englewood Giffs, N.J.: Prentice-Hall, 1975.
4. FIPS PUB 140-2, National Institute of Standards and Technology. http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf
5. Random Number Generation Using the MSP430. http://www.ti.com/litv/pdf/slaa338.pdf
6. Associated code files. http://www.ti.com/litv/zip/slaa338