High-speed pseudorandom sequence generators based on cellular automata.pdf Клеточным автоматом (КлА) называется модель с дискретным временем, состоящаяиз множества ячеек памяти, упорядоченных в периодическую n-мерную решетку[1]. Значениями ячеек являются элементы некоторого конечного множества. Длякаждой ячейки выбирается ее окрестность, которая используется для определения значенияячейки на следующем такте работы по некоторому заранее заданному правилу.Для классических клеточных автоматов выполняются свойства однородности и локальности.Однородность означает, что все ячейки КлА являются неразличимыми посвоим свойствам; кроме того, для решения проблемы краевых клеток противоположныекрая решетки отождествляются, то есть двумерная решетка закручивается в тор.В соответствии со свойством локальности в окрестность каждой ячейки входят толькоячейки, удаленные от нее на расстояние не более заданного.В нашей работе мы рассматриваем однородные двумерные булевы клеточные автоматыс прямоугольными ячейками. Окрестность ячейки включает подмножество ячеек,непосредственно смежных с данной, а также, возможно, ее саму. В качестве правила,определяющего новое значение ячейки на следующем такте работы, используетсябулева функция, которую мы будем называть локальной функцией связи (ЛФС). АргументамиЛФС являются значения всех ячеек из окрестности данной. ИспользованиеКлА с большей размерностью решетки или более широкой окрестностью увеличиваетчисло аргументов ЛФС и делает ее реализацию непрактичной.Мы вводим понятие лавинного эффекта в клеточных автоматах по аналогии с лавиннымэффектом, введенным Хорстом Фейстелем [2] в 1973 г. для оценки свойствкриптографических преобразований. Лавинный эффект показывает, насколько сильноизменяется поведение КлА во времени при изменении значения одной ячейки. Еслиизменения распространяются по решетке равномерно во всех направлениях с максимальновозможной линейной скоростью (в данном случае составляющей одну ячейкуза такт работы) и при этом затрагивают половину всех ячеек на каждом такте работы,то такой лавинный эффект мы называем оптимальным.Для оценки лавинного эффекта вводятся две числовые характеристики: интегральнаяи пространственная. Первая отражает отношение числа изменившихся ячеек к общемуих количеству, вторая - линейную скорость распространения изменений по решеткеКлА. Компьютерное моделирование показало, что характеристики приближаютсяк оптимальным по мере увеличения числа аргументов ЛФС, которое совпадаетс мощностью окрестности ячейки. При этом характеристики для функций от 8 и 9аргументов являются практически идентичными.Также в работе исследуется влияние свойств ЛФС и размеров решетки на функционированиеклеточного автомата. Мы показываем, что необходимым условием равномерногозаполнения ячеек решетки является равновесность локальной функции связи.Кроме того, рассматриваются пространственные периоды в заполнении решетки,которые существенно снижают временной период КлА. Для уменьшения вероятностивозникновения пространственных периодов следует выбирать в качестве размероврешетки простые числа; вероятность также уменьшается при увеличении числа аргументовЛФС.В состав генератора ПСП на основе двумерных булевых КлА входят два клеточныхавтомата и регистр сдвига с линейной обратной связью (РСЛОС). Размеры решеткиодинаковы для обоих автоматов и составляют 37 х 11 ячеек. Окрестность каждойячейки состоит из ячеек, непосредственно смежных с ней, что соответствует ЛФСот 8 аргументов. В качестве выхода клеточного автомата используются значения ячеек,входящих в подрешетку размера 32 х 8, что обеспечивает выработку каждым КлА256 бит за один такт работы. Для каждого клеточного автомата используется своясобственная равновесная локальная функция связи.Выход РСЛОС на каждом такте работы прибавляется по модулю 2 к значениюодной из ячеек каждого клеточного автомата. Лавинный эффект позволяет гарантировать,что период внутренних состояний клеточных автоматов будет не меньшепериода выходной последовательности РСЛОС. Мы считаем, что для практическогоприменения генератора достаточно использовать РСЛОС длины 63, что обеспечиваетпериод выходной последовательности КлА не менее 2,4 1021 бит.Выход генератора формируется посредством сложения по модулю 2 выходных последовательностейобоих клеточных автоматов, что позволяет существенно улучшитьстатистические свойства выходной последовательности генератора, увеличить ее периоди затруднить восстановление внутреннего состояния генератора по выходнымзначениям.Автором был разработан прототип аппаратной реализации предложенного генераторана ПЛИС Altera Cyclone II (EP2C35F672C6). Выходная последовательность генератораподавалась напрямую на выводы микросхемы ПЛИС, а также записываласьдля дальнейшего анализа во внутреннюю память.Параллельная структура клеточных автоматов позволила достичь формированиявыхода генератора за один такт синхронизации схемы. Рабочая частота схемы составила100 МГц; учитывая, что на каждом такте работы генератор формирует 256 битвыходной последовательности, скорость ее выработки составила 23,8 Гбит/с.Анализ статистических свойств выходной последовательности проводился при помощинабора тестов NIST [3], предназначенного для выявления статистических отклоненийисследуемой последовательностиот истинно случайной. В результате тестированиягенераторов с различными локальными функциями связи клеточных автоматовбыли обнаружены функции, при которых генератор успешно проходит все тестыиз набора. Для сокращенной версии генератора, в которой один из двух клеточныхавтоматов отключен и не вырабатывает выходную последовательность, таких функцийобнаружено не было; тем не менее сокращенный генератор может использоватьсяв приложениях с менее жесткими требованиями к статистическим свойствам ПСП.В настоящее время ведется работа над программной реализацией генератора, использующейв качестве вычислительного устройства графический адаптер ПЭВМ, чтопозволит говорить о возможности массового применения разработанных алгоритмов.Кроме того, другими объектами исследований являются неоднородные клеточные автоматы,в которых окрестность каждой ячейки выбирается случайным образом, но неизменяется в процессе работы. Неоднородные КлА обладают существенно лучшимихарактеристиками по сравнению с рассмотренными выше, а также позволяют строитьнамного более эффективные реализации.

Скачать электронную версию публикации