Генераторы случайных и псевдослучайных последовательностей на цифровых элементах задержки (основы теории и методы построения)

Во всех отраслях науки и техники исследователи сталкиваются с процессами и объектами сложной структуры. Нередко понятие «сложность» предполагает невозможность эффективно применять классические аналитические методы [1]. Ряд традиционных экспериментальных приемов решения также может не дать удовлетворительных результатов. Тогда постановка исследовательского эксперимента на основе имитационных моделей становится единственно реальной, ведущей к получению достаточно точных решений. Однако «имитация — всегда некий выборочный эксперимент, как только модель содержит одну или несколько случайных величин .» [2]. Для организации такого рода исследований необходимо формирование случайных величин, например, в форме временных последовательностей.

Аналогичные особенности присущи и для выполнения вычислений методом Монте-Карло (методом статистических испытаний), оптимизационных процедур методом случайного поиска, проведения реальных и модельных испытаний изделий объектов техники на надежность, реализации вероятностного тестирования и сигнатурного контроля, проведения специфичных измерений физических величин и т. п. [3−22]. В последние три десятилетия особую актуальность приобрело использование случайных парольно-ключевых последовательностей в задачах защиты информации в ЭВМ, телекоммуникационных и сетевых средствах, в частности, аппаратуре опознавания [23−34] .

Задача получения случайных чисел для ЭВМ может быть решена различными способами. Традиционно закрепились два подхода. Первый состоит в том, что в качестве основы случайных последовательностей используют некий реальный физический процесс, обладающий определенными свойствами и преобразованный в форму, пригодную для согласования с аппаратно-программными частями модели, в конечном итоге — с ЭВМ. Второй подход ориентирован на специальные математические преобразования, чаще всего в рекуррентной форме, позволяющие получить детерминированные числовые последовательности с характеристиками, близкими к действительно случайным процессам. Эти последовательности принято называть псевдослучайными. Отметим, что наибольшее значение для практики имеют числовые последовательности с равномерным (равновероятным) законом распределения, чему и уделено основное внимание в работе.

Известны многочисленные публикации, посвященные вопросам построения и анализа устройств формирования дискретных случайных сигналов, в частности генераторов случайных последовательностей (ГСП), основанных на использовании сложных физических явлений. Среди отечественных авторов следует отметить М. П. Бобнева, который впервые обобщил опыт применения генераторов случайных сигналов (1966 и 1971 г. г.). Заметный вклад в становление теории и практики применения физических ГСП внес A.M. Морозов. За последние 50 лет интерес к этой теме не снижается как у нас в стране, так и за рубежом.

Традиционные методы построения ГСП [3, 35−37] основаны на использовании таких источников шума, как резистор (тепловой шум), вакуумный диод (дробовой шум), полупроводниковый диод в режиме обратного смещения (шум электрического пробоя), газоразрядные (стабилитроны, тиратроны), радиоактивные, фотоэлектронные и др. При этом схемы генераторов должны содержать линейные усилители, фильтры, компараторы и прочие нецифровые компоненты и блоки.

В современной литературе, в том числе и в Интернет-ресурсах, также появляются сообщения о новых перспективных принципах построения ГСП. Например, авторы А. Стефанов (A. Stefanov) и др. (Швейцария, 1999 г.) утверждают об эффективности применения квантово-оптических процессов. Корпорация Toshiba объявила о генераторе, использующем специальные транзисторы на основе нитрида кремния с выраженными стохастическими свойствами. В работе [38, 39] описывается формирование двоичных случайных сигналов на основе параметрических генераторов.

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

В части анализа генераторов псевдослучайных последовательностей (ГПСП) известны фундаментальные работы отечественных ученыхА.И. Алексеева, JI.E. Варакина, В. Е. Гантмахера, Б. И. Глазова, В. И. Доценко, Н. Г. Дядюнова, Р. Х. Латыпова, А. И. Сенина, Г. И. Тузова, Р. Г. Фараджева, А. Г. Шереметьева, а также зарубежных — А. Гилла (А. Gill), C.B. Голомба (S.W. Golomb), Г. Нидеррайтера (H. Niderreiter), Р. Таусворта (R.C. Taus-worthe), А. Хаффмена (D.A Huffman), H. Цирлера (N. Zierler) и Б. Элспаса (В. Eispas). Теоретические и прикладные аспекты формирования и использования псевдослучайных последовательностей в современной области крипто-защиты представлены в ряде современных изданий, например, авторов М. А. Иванова, С. А Осмоловского, Б. Шнайера (В. Schneier) и др.

В табл. В1 кратко перечислены основные достоинства и недостатки использования случайных и псевдослучайных последовательностей. Предполагается, что эти сигналы тактированы по времени и дискретизированы по величине (процессы типа «дискретная ордината-дискретное время»), что является наиболее удобной формой представления случайности в ЭВМ.

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

Необходимо различать два вида физической реализации ГПСП. Это либо специальный электронный блок (устройство), сопряженный с ЭВМ, либо программный датчик псевдослучайных чисел в форме алгоритмической реализации в какой-либо языковой среде.

Таблица В1.

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

Случайные Псевдослучайные.

А. Непредсказуемость: невозможА. Гарантированная и сколь угодно выность экстраполяции, интерполяции и воссокая точность формирования основных статистановление предыстории. стических характеристик.

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

О ляемого вероятностными моментами и модля подтверждения полученного результата. и ментными функциями сколь угодно высоГ. Возможность традиционного схемон кого порядка. технического построения устройств формирос Г. Отсутствие взаимоподобия (изования последовательностей и их сопряжение с т морфизма) структур последовательностей и ЭВМ. в структур моделируемых объектов. Д. Возможность полной функциональа ной замены специальных устройств формирования последовательностей программными реализациями на ЭВМ.

А. Ограниченная точность формиА. Полная предсказуемость: возможрования основных статистических характеность экстраполяции, интерполяции и восстаристик. новление предыстории.

Б. Подверженность влиянию дестаБ. Периодичность: наличие основного билизирующих факторов на точность и стапериода цикла при статистически ненаблю.

Н ционарность работы. даемых периодах малых циклов. е В. Невозможность повторного (мноВ. Детерминизм, потенциально выявд гократного) формирования последовательляемый вероятностными моментами и моо ности для подтверждения полученного рементными функциями высокого конечного с зультата. порядка. т Г. Специальные, иногда уникальные Г. Возможность наличия неконтролиа методы схемотехнического построения уструемых свойств взаимоподобия (изоморфизма) т ройств формирования последовательностей структур последовательностей и структур мок и их сопряжения с ЭВМ. делируемых объектов. и Д. Невозможность полной функциональной замены специальных устройств формирования последовательностей программными реализациями на ЭВМ.

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

Алгоритмически ГПСП — это чаще всего рекуррентная процедура вида: д (г)= ра{} -1), а (г — 2),., а{г — т)], где а (г), а (г -1), а (г — 2),., а (г — га) — последний фрагмент формируемой последовательности- / - тактовое времяГ — функция или совокупность операций над предысторией <з (/-1), а (г-2),., <я (/ - т), чтобы получить новое значение а (г) — т — натуральное число, выражающее длину предыстории.

Большинство известных алгоритмов подразумевают достаточно сложную в вычислительном отношении функцию К Поэтому предполагается только программная форма. Однако имеется ряд рекуррентных алгоритмов, которые эффективно реализуются аппаратно в форме специального электронного цифрового блока или внутреннего функционального узла микропроцессора [40, 41]. Причем быстродействие таких аппаратных ГПСП обычно значительно выше, чем программных датчиков (с тем же алгоритмом), что выделяет его как предпочтительное решение для сопряжения с высокопроизводительными информационно-вычислительными системами.

Эффективным для аппаратной реализации алгоритмом формирования последовательности псевдослучайных двоичных символов а (г) является следующее рекуррентное выражение: т-1 а (0 = (В.1) 1 где т — максимальное значение временного сдвига (в тактах) — коэффициенты С (е{0,1} задаются специальным образомсуммирование производится по модулю два. Аппаратное построение такого генератора предполагает использование регистра сдвига (как блока цифровых элементов задержки) и сумматоров по модулю два [42−65]. Простота практической реализации и предельное для синхронных устройств быстродействие сочетается с высоким качеством статистических характеристик. Несмотря на то, что сумма по модулю два является нелинейной функцией действительных переменных, в случае представления в классе переключательных функций она относится к линейной. Поэтому в литературе закрепилось название таких ГПСП как «регистр сдвига с линейной обратной связью». В зарубежных публикациях они обозначены аббревиатурой «LFSR» (Linear Feedback Shift Register). Наиболее предпочтительный режим работы регистра организуется за счет специального подключения к его разрядам цепи линейной обратной связи (ДОС), обеспечиваемого коэффициентами С, в формуле (В.1). В этом случае формируется так называемая последовательность максимальной длины или М-последовательность.

Характерной особенностью любого ГПСП является периодичность его работы. В случае автоматного представления устройства значение временного цикла Т имеет порядок 2 т, где т — число элементов однотактной задержки (триггеров, ячеек памяти). Чтобы значительно снизить влияние недостатков ГПСП, а некоторые полностью убрать (см. табл. В.1: недостатки псевдослучайных последовательностей соответственно Б и В) для реального времени работы Т, целесообразно обеспечить выполнение соотношения Т «Тц .

Так, например, при га = 56 (что требует на сегодня относительно малых затрат ресурсов современных аппаратных средств БИС, включая микропроцессоров) и частоте тактовых импульсов Fm = 3 ГГц (как внутренней частоте современных микропроцессоров) получаем: Тц «250 суток непрерывной (!) работы. Такая величина цикла обеспечивает, наряду с высокими точностными показателями, практически любое реальное время имитационного моделирования или сеанса информационной связи в защищенном режиме.

Одним из первых исследователей свойств регистра сдвига с ДОС является Д. А. Хаффмен [60]. На протяжении более 50 лет этот объект тщательно анализируется в многочисленных статьях и монографиях как у нас в стране, так и за рубежом. Тем не менее, остается ряд нерешенных вопросов фундаментального плана и, что особенно важно, актуальных для практического использования. Поэтому часть материала диссертации посвящено обобщению ранее выявленных свойств ГПСП и описанию новых результатов, придающим этому объекту дополнительные полезные свойства.

Замена га-разрядного регистра сдвига ГПСП на п цифровых элементов асинхронной (не тактируемой) задержки позволяет ввести интерпретацию алгоритма (В.1) в форме где, в отличие от первоначального вида,? и т. непрерывные значения соответственно реального времени формирования и временного сдвига у'-ым элементом асинхронной задержки.

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

Эти флуктуации порождаются сложными физическими явлениями стохастического характера и являются неотъемлемыми свойствами любого электронного компонента, в том числе и цифрового элемента. При указанных условиях выражение (В.2), как математическая модель, описывает процедуру формирования случайного двоичного процесса асинхронного типа. Таким образом, известный алгоритм псевдослучайности (В.1) превращается в аналитическую основу (В.2) аппаратного принципа формирования действительно случайных процессов, причем с использованием цифровой элементной базы. Этот принцип в схемотехническом виде как новое техническое решение был защищен автором диссертации в ряде изобретений с наиболее ранним приоритетом от 1979 г. [66]. Использование некоторых изобретений привело к инженерным разработкам ГСП, внедренных в реальные проекты.

Аналогичная техническая идея, спустя 25 лет, была описана в статье И. Ж. Голича (ГЦ). воПс, Италия) [67]. Однако достаточно полных теоретических исследований такого рода устройств предложено не было. Несмотря на простое схемотехническое решение генераторов такого типа и лаконичность математического представления, возникает ряд трудностей практического.

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

Для формирования процесса, временные параметры которого в существенной степени определяются асинхронными задержками цифровых элементов, целесообразно по-новому оценить известные методы построения ГСП на основе совпадения импульсов двух и более последовательностей с нестабильными частотами [68−76]. Перспективна также идея использования де-терминированно-хаотического поведения моделей ГСП и ГПСП [77−80], выделяя при этом варианты, в которых основной аргумент — это непрерывно-временная задержка дискретных сигналов.

В плане использования схемотехники и технологии БИС целесообразно выделить два направления, активно развиваемых в публикациях последних лет по ГСП. Первое направление использует естественные флуктуационные свойства процессов, формируемых блоками синхронизации на основе автоподстройки задержки (системы DLL — Delay Lock Loop) или фазы (системы PLL — Phase Lock Loop) [81, 82]. Однако аналоговый характер построения этих специфичных блоков в цифровых БИС существенно ограничивает перспективность этого направления. Особенность второго подхода выражается в применении цифровых линий задержки, формирующих так называемые «физически неповторимые функции» (Physical Unclonable Functions) [83]. При этом стохастичность результирующего сигнала обеспечивается свойством метастабильности триггерного устройства фиксации, что характеризуется заметной нестационарностью и существенной зависимостью от внешних возмущающих факторов. Поэтому, несмотря на полную цифровую реализацию устройства, целесообразность дальнейшего его развития в целом сомнительна, но факт использования цифровых элементов задержки заслуживает внимания.

На рис. В.1 изображена классификация моделей генераторов на основе задержек в виде абстрактных (математических) объектов и в форме структурных (схемотехнических) реализаций как электронных устройств (выделенных серым фоном). Показаны также типичные направления теоретического исследования и практического построения цифровых генераторов.

Синхронные объекты включают в себя алгоритмические и схемотехнические представления счетчиковых структур, формирующих как простые периодические импульсные процессы, так и сложно-периодические, в частности псевдослучайные в тактовом времени. Примерами таких технических объектов являются классические двоичные счетчики, кольцевые регистры и полиномиальные счетчики (типа Ы^Я).

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

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

Ч С.

И < к я ы о о У я 2 н я о. о и я ы о <и сг я.

И я я 2 V > л"' Я', о, я 'к .3 я.

Я — к «§.

Л 1-й.

М.4*.

Модели цифровых генераторов на элементах задержки.

Асинхронные цифровые.

Асинхронные цифровые периодические Цифровые хаотические.

Синхронные цифровые.

Цифровые сложно-периодические Синхронные цифровые периодические.

Цифровые стохастические.

Генераторы-? ^^ импульсов/ 'Г.

Г' г «, ^.

I хаотических I и почти-| периодических I процессов.

1 енсраторыл — .случайных?, процессов'-" .

Генераторы -1 псевдо-случайных процессов,;

Счетчиковыс'-' устройства Дагч и к и с л у ч, а йн ы хс и ми ол о в, генераторы случайных чисел К 3.

X А.

4 и ч о 2 к.

X ь И га & о ю < ро ы н И Й и к> о.

Рис.

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

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

Заслуживает особого внимания методы совместного использования ГСП и ГПСП в так называемых комбинированных ГСП (КГСП). Существенный вклад в разработку таких генераторов внесли Я. Гавел (J. Havel), В. И. Глова, Г. В. Добрис, В. М. Захаров, Б. Ф. Кирьянов, P.M. Мансуров, В. А. Песошин, E.JI. Столов, Р. Ф. Федоров, Г. П. Хамитов, В. В. Яковлев, В. Н. Ярмолик. Методы комбинирования сложных физических явлений и математических алгоритмов в процессах формирования случайных чисел являются наиболее плодотворными в деле создания высокотехнологичных изделий. Это направление было использовано в данной работе, что, во-первых, способствовало тематическому объединению вопросов построения и анализа ГСП и ГПСП. Во-вторых, идея описания комбинированных структур автоматными представлениями синхронных и асинхронных генераторов привела к техническим решениям, вполне адаптированных к технологиям цифровых интегральных схем, включая БИС.

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

Объектом исследования в данной работе являются элементы и устройства формирования цифровых случайных и псевдослучайных сигналов. Предмет исследования — генераторы случайных и псевдослучайных последовательностей на цифровых элементах задержки. Цель диссертационной работы — развитие научных основ и методов построения цифровых генераторов случайных и псевдослучайных последовательностей с повышенным быстродействием и точностью. Эта цель достигается решением научной проблемы, заключающейся в разработке основ теории, принципов построения, методов анализа и синтеза генераторов случайных и псевдослучайных сигналов на цифровой элементной базе, для чего сформулированы основные задачи диссертационного исследования:

— анализ современного состояния основ схемотехнического построения цифровых генераторов случайных и псевдослучайных сигналовопределение базовых моделей элементарных цифровых генераторов, частотный и временной анализ их поведения;

— выявление типичных закономерностей формирования корреляционных зависимостей для периодических процессов;

— анализ циклических свойств синхронных моделей генераторов, формирующих линейные рекуррентные последовательности однородного и неоднородного вида;

— исследование свойств элементов задержки двоичных сигналов в непрерывном времени как основных компонентов цифровых генераторов асинхронного типа;

— теоретическое и экспериментальное исследование генераторов асинхронных случайных процессов, их структурных, вероятностных и корреляционных свойствопределение условий автогенерации цифровых сигналов в непрерывном времени;

— описание свойств датчиков случайных символов и особенностей их применения в технических средствах защиты информацииавтоматные представления датчиков и разработка методов их синтеза;

— практические разработки генераторов случайных и псевдослучайных последовательностей.

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

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

— закономерности формирования реперных точек периодических корреляционных функцийминимизация длины выборки и оценочных процедур для сложно-периодических сигналов;

— структурные, вероятностные и автокорреляционные свойства (М-1) — и.

М-3^последовательностей и условия их получения- -аналитические оценки нелинейности и свойств фильтрации асинхронных элементов задержки в цепочечном и циклическом использовании в цифровых генераторах;

— фрактальные свойства моделей асинхронных генераторов в случае формирования детерминированно-хаотического процесса при несоизмеримых и нефлуктуирующих задержкахвероятностный автомат асинхронного типаметод вероятностного анализа марковской модели асинхронного генератора с учетом флуктуаций задержекметод анализа и формализованные условия устойчивости генерации асинхронного процесса;

— метод условных вероятностей и дисперсий для оценки степени непредсказуемости формируемых генераторами случайных процессов;

— синхронно-асинхронные автоматные описания датчика случайных символов и методы их синтеза.

Практическая ценность работы заключается в создании схемотехнических основ построения генераторов дискретных случайных сигналов на цифровой элементной базе, допускающих применение технологий интегральных микросхем, включая БИС. Это основано на разработках.

— принципов построения генератора асинхронного случайного процесса и инженерных методик настройки его структуры на максимально плотный базовый многочлен (М-1^{последовательностипрограммных} и физических моделей генераторов для экспериментальных исследований статистических и структурных свойств формируемых процессов;

— основных функциональных схем датчиков случайных символовформального метода построения датчика посредством структурного синтеза асинхронного автомата;

— характерных построений реальных датчиков, генераторов случайных и псевдослучайных последовательностей на цифровых микросхемах малой и большой степени интеграции.

Реализация и внедрение результатов работы. Материал диссертации представляет собой теоретическое обобщение ряда НИР и ОКР, выполненных на кафедре ЭВМ (Компьютерных систем) КГТУ им. А. Н. Туполева более чем за 30-летний период работы автора в данном направлении.

Основными объектами внедрения являются полузаказные БИС ГСЧ Н1582ВЖ2−0105, 1537ХМ2У-135 и 1537ХМ2АУ-215, выпускаемые мелкосерийными партиями с 1992 г. по настоящее время (г. Зеленоград, ОАО «Ангстрем»). ДСС на микросхемах малой степени интеграции внедрены в блок статистического моделирования (г. Казань, каф. ЭВМ КАИ, 1978 г.), устройство ввода случайных чисел ЕС 6903 (установочная серия, г. Казань, Казанский завод (КЗ) ЭВМ, 1981 г.), терминальную ЭВМ ЕС 1007 (г. Казань, КЗ ЭВМ, 1986 г.). Одноплатные ГСЧ внедрены в специализированное техническое средство защиты информации (г. Ленинград, НИИ «Нептун», 1987 г.) и специализированную вычислительную систему (г. Минск, НИИ ЭВМ, 1990 г.). Для экспериментальных целей были изготовлены ГСЧ на основе технологий БИС: по гибридной технологии (г. Казань, каф. МиК КАИ, 1986 г.), на микропроцессорных секциях К1804ВС2 (г. Казань, каф. ЭВМ КАИ, 1990 г.), на ПЛИС фирмы ХШпх (г. Казань, каф. КСИБ КГТУ-КАИ, 2001 г.), микросхема Н1537ХМ1−192 на базовых матричных кристаллах (экспериментальная партия, г. Зеленоград, ОАО «Ангстрем», 2005 г.).

Результаты диссертации использованы при выполнении НИР:

— «Нетрадиционные принципы формирования случайных сигналов для цифровой техники», «Информационные технологии, системы и средства компьютерного моделирования структурно-сложных объектов», «Микроэлектронные методы формирования кодовых последовательностей для информационного обмена и защиты в вычислительных и телекоммуникационных системах», «Цифровые методы и средства формирования случайных сигналов для систем защиты информации» по единому заказ-наряду Министерства образования и науки Российской Федерации (1989;2004 гг.);

— «Системы криптозащиты информации на основе генераторов нелинейных последовательностей в ПЭВМ и сетях», «Система авторской защиты информации в ПЭВМ на основе полисинхронных генераторов рекуррентных последовательностей», «Перспективные технологии создания радиочастотных и цифровых устройств радиоэлектроники и энергетики для наукоемких отраслей производств» по плану приоритетных фундаментальных и прикладных исследований Академии наук Республики Татарстан (1997;2006 гг.);

— «Интегрированные аппаратно-программные средства для проектирования и моделирования цифровых микроэлектронных устройств», «Цифровые технологии построения и исследования стохастических устройств с выраженными свойствами непредсказуемости», «Аппаратно-программные средства моделирования цифровых устройств формирования труднопредсказуемых случайных последовательностей» по программе развития приоритетных направлений науки в РТ на 2001;2005 годы (фонд НИОКР Академии наук Республики Татарстан);

— «Исследование процессов формирования случайных чисел и методов контроля их стохастических свойств» (1996 г.), «Исследование и разработка методов построения генераторов случайных чисел на программируемых логических интегральных схемах» (1999 г.) по хоздоговорам с Казанским научно-исследовательским институтом радиоэлектроники;

— «Исследование и разработка перспективных вычислительных структур для ЕС ЭВМ. Разработка блока статистического моделирования» (1977 г.), «Исследование и разработка специализированных процессоров ЕС ЭВМ (Ряд 2 и 3) для сети ЭВМ» (1981;1984 гг.), «Устройства вычислительной техники для статистического моделирования» (1987 г.), по хоздоговорам с Казанским заводом ЭВМ.

Научные и практические результаты диссертации используются в учебном процессе КНИТУ-КАИ им. А. Н. Туполева при изучении студентами дисциплин «Схемотехника» по специальности «Информационная безопасность телекоммуникационных систем», «Электроника» по специальности «Комплексная защита объектов информатизации», а также для магистрантов по специальности «Элементы и устройства вычислительной техники и информационных систем» в дисциплинах «Элементы и устройства комбинированных вычислительных машин» и «Приложения теории линейных последовательно-стных машин». Разработан лабораторный практикум «Генераторы случайных чисел».

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на международных конференциях: «Проблемы теоретической кибернетики» (г. Москва, 2002 г.). «Инфокоммуни-кационные технологии глобального информационного общества» (г. Казань, 2003, 2004 и 2005 гг.), «Информационные и телекоммуникационные системы и технологии» (г. Санкт-Петербург, 2007 г.), «Физика и технические приложения волновых процессов» (г. Казань, 2007 г.), «Проблемы техники и технологий телекоммуникаций» (г. Казань, 2008 г.) — всесоюзных, всероссийских конференциях и симпозиумах: «Вероятностные вычислительные методы и средства» (г. Москва, 1978 г.), «Проблемы создания преобразователей формы информации» (г. Киев, 1980 г.), «Вероятностные автоматы и их приложения» (г. Казань, 1983 г., г. Тбилиси, 1986 г.), «Методы и средства измерения физических величин» (Н. Новгород, 1998, 2000 гг.) — республиканской конференции «Вероятностные методы и средства» (г. Новгород, 1983 г.) — всесоюзных и российских школах-семинарах: «Вероятностные автоматы и их приложения» (п. Славск, 1978 г., г. Иркутск, 1981 г., г. Киев, 1984 г.), «Флуктуации и шумы в сложных системах» (г. Казань, 2004 г.) — городских семинарах «Методы моделирования» (г. Казань, 2004, 2006, 2009 гг.) и регулярных научно-технических конференциях КГТУ-КАИ.

Публикации. По теме диссертации опубликовано 80 научных работ, в том числе: 1 монография, 19 статей в научных журналах и сборниках, из них 11 в журналах, рекомендованных ВАК для опубликования результатов докторских диссертаций, 29 авторских свидетельств и патентов.

Структура и объем диссертационной работы. Диссертация состоит из введения, шести глав, заключения и списка литературы, включающего 247 наименований. Материал работы изложен на 347 страницах текста компьютерной верстки, в том числе основная часть — на 313 страницах. Работа содержит 105 рисунков и 22 таблицы.

Выводы по главе 6.

1. Выделена основная область практического применения результатов диссертации — построение устройств формирования случайных и псевдослучайных последовательностей с использованием цифровой элементной базы. Подробно вопросы синтеза рассмотрены в отношении ДСС.

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

3. Представлена структура ДСС в виде композиции ГАСП, как источника физической случайности, и устройства фиксации, обеспечивающего стандартное сопряжение с остальными частями цифровой системы.

4. Исследованы источники возникновения характерных погрешностей работы датчика и связь их с быстродействием. Получена эмпирическая формула оценки максимальной частоты синхронизации. Отмечено, что в случае применения ГАСП многоконтурного типа, скорость работы ДСС становится сравнимой с быстродействием детерминированных цифровых устройств, построенных на той же элементной базе.

5. Описана особенность применения ДСС и ГСЧ для формирования па-рольно-ключевых последовательностей, используемых в технических средствах защиты информации. Обоснована применимость метода функции степени детерминированности поведения динамической системы для исследования свойств предсказуемости цифровых источников случайных сигналов. Предложены методы условных вероятностей и дисперсий для оценки степени непредсказуемости формируемых генераторами случайных процессов.

6. Статистические характеристики ДСС в значительной степени определяются соответствующими характеристиками ГАСП. Экспериментально установлено, чем больше контуров обратной связи организовано в схеме генератора, тем в среднем сильнее проявляются стохастические свойства. Также способствует организации более выраженного стохастического режима настройка структуры обратной связи на базовый многочлен (М-1)-последовательности.

7. Исследована связь структуры многочленов (М-1)-последовательностей, заданных коэффициентами в виде восьмеричных наборов, с характерными элементами схемотехнической организации контуров обратной связи ГАСП. Решены задачи максимизации плотности такого базового многочлена, в результате чего разработаны две методики настройки структуры генератора на образующий многочлен, наиболее приближенный к максимально плотному при заданной размерности генератора.

8. Для решения задач синтеза ДСС предложено его рассмотрение в виде связанных между собой вероятностных автоматов синхронного и асинхронного типа. Сформулированы требования к выбору элементов внутреннего алфавита асинхронной модели.

9. Описаны следующие три основные функциональные схемы ДСС по способам организации работы его внутренних компонентов: подключения УФ к ГАСП, включения УФ с разрывом обратной связи ГАСП и включения УФ без разрыва обратной связи ГАСП. Приведены примеры соответствующих логических схем датчиков. Отмечено, что качество статистических характеристик выходной синхронной последовательности и быстродействие датчиков по третьей схеме достигаются наиболее высокими. В общем, диапазон технической сложности построения ДСС в зависимости от требуемого качества и быстродействия простирается от 0,25 корпуса микросхемы малой степени интеграции до БИС.

10. Разработан формальный метод синтеза ДСС. Он основан на доопределении вероятностного автомата асинхронного типа до детерминированного асинхронного автомата, структурный синтез которого дает возможность получить логическую схему датчика. Отмечена целесообразность использования комбинации формального и эвристического методов синтеза. Приведена методика такого построения.

11. Разработан ряд ДСС и ГСЧ, ориентированных на применение цифровой элементной базы, как малой степени интеграции, так и БИС. Основными объектами внедрения являются БИС ГСЧ Н1582ВЖ2−0105, 1537ХМ2У-135 и 1537ХМ2АУ-215, выпускаемые мелкосерийными партиями с 1992 г. по настоящее время (ОАО «Ангстрем», г. Зеленоград) для систем опознавания «свой-чужой».

12. Кратко описаны возможности применения моделей ГАСП для построения цифровых устройств формирования случайных сигналов с управляемыми и регулируемыми законами распределения и корреляционными свойствами, генераторов случайных потоков простейшего типа и с последействием, генераторов случайного напряжения, генераторов случайных процессов различной физической природы.

ЗАКЛЮЧЕНИЕ

.

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

При проведении исследований по тематике диссертации получены следующие научные и практические результаты:

1. Проведен анализ современного состояния основ построения цифровых генераторов случайных и псевдослучайных сигналовопределены две базовые модели элементарных кольцевых генераторов (КГ) на цифровых элементахгенератор-повторитель (ГП) и генератор-инвертор (ГИ) — проведен частотно-временной анализ их поведения. Показано, что КГ формирует в автономном режиме двоичные процессы телеграфного типа с непрерывным временем в форме простых, сложно-периодических и инверсно-сегментных импульсных последовательностей. Временной анализ ГП и ГИ определил основные свойства и характеристики формируемых ими процессов.

2. Выявлены типичные закономерности формирования корреляционных зависимостей для периодических процессов. Показана целесообразность оценивания математического ожидания, дисперсии, АКФ и ВКФ на минимальном периоде процессов, формируемых цифровыми генераторами в псевдослучайном режиме. Обоснованы характерные реперные значения ПАКФ и закономерности формирования остальных отсчетов, что допускает сокращение количества вычислений на выборке длиной в цикл в 2 раза, а для инверсно-сегментных импульсных последовательностей — в 4 раза.

3. Проведен анализ циклических свойств синхронных моделей генераторов, формирующих линейные рекуррентные последовательности однородного и неоднородного вида. Исследованы ГПСП с линейной обратной связью как генераторы Фибоначчи и Галуа. Для однородных и неоднородных ЛРП получено обобщенное выражение производящей функции, в которое входит константа а0 е {0,1}. Доказано, что множество циклов (ш + 1)-го порядка при а0 = О состоит из объединения множеств циклов га-го порядка при а0=0 и а0= 1. Выделен класс ЛРП, который можно использовать для генерирования псевдослучайных последовательностей и как модельную основу случайных процессов. Определены структуры и исследованы свойства (М-1) — и (М-3)-последовательностей, особенностями которых являются равновероятное распределение двоичных символов и знакопеременные АКФ. В развитие теории ГПСП в форме генератора Галуа доказано, что на разных выходах регистра генератора могут формироваться различные ЛРП. Разработана методика идентификации формируемых последовательностей из анализа циклов, запрещенных для псевдослучайного режима.

4. Исследованы свойства элементов задержки двоичных сигналов в непрерывном времени в форме логических повторителей и инверторов как основных компонентов цифровых асинхронных генераторов. Определены величины нелинейных задержек для одного ЦЭ и для гс-звенных цепочек. Получены аналитические соотношения для задержек логических уровней, значений временных порогов фильтрации коротких импульсов и сформулированы условия сохранения длительностей. Обоснована предпочтительность использования в АЭЗ инверторов. Разработан метод оценки разбросов средних задержек на основе применения условных вероятностных моментов к описанию группы однотипных элементов АЭЗ. Экспериментально оценены коэффициенты вариации задержки ЦЭ. Для нормальных условий эксплуатации они находятся в пределах: стт3 = 10~4 — 3 • Ю-3.

5. Теоретически и экспериментально исследованы структурные, вероятностные и корреляциионые свойства случайных процессов, формируемых асинхронными генераторамиопределены условия автогенерации цифровых сигналов в непрерывном времени. Представлен ГАСП как подкласс автономных асинхронных автоматов. В случае несоизмеримых нефлуктуирующих задержек обосновано возникновение детерминированно-хаотического режима, структурные свойства и фрактальные размерности которого сопоставимы с треугольником Серпинского. Исследовано влияние флуктуирующих задержек в АЭЗ на возникновение стохастического режима ГАСП. Введено понятие вероятностного автомата асинхронного типа, на основе чего исследованы структурные и вероятностные свойства процессов на выходе марковской модели ГАСП. Для двух связанных элементарных КГ получены аналитические выражения вероятностных и корреляционных свойств формируемых случайных процессов. Найдены формализованные условия автогенерации цифровых сигналов в непрерывном времени. Разработаны программные и физические модели ГАСП для экспериментального исследования статистических и структурных характеристик процессов.

6. Описаны свойства датчиков случайных символов и особенности их применения в технических средствах защиты информациидатчики представлены автоматными моделями, на основе которых разработаны методы их синтеза. Исследованы вероятностные и автокорреляционные свойства аппаратно реализованных цифровых генераторов в форме ДСС, композиционно состоящие из ГАСП и УФ. Отмечены универсальные свойства идеального ДСС как элементарного вероятностного автомата. Адаптирован известный метод оценки степени непредсказуемости формируемых последовательностей применительно к ДСС и ГСП. Даны автоматные описания функционирования ДСС и предложены основные функциональные схемы датчиков. Разработаны методики настройки структуры ГАСП на максимально плотные базовые образующие многочлены (М-1^{последовательностей.} Предложены принципы построения ГАСП и методы синтеза ДСС.

7. Практически разработан и внедрен ряд генераторов случайных и псевдослучайных числовых последовательностей. Основным объектом внедрения являются полузаказные БИС ГСЧ Н1582ВЖ2−0105, 1537ХМ2У-135 и 1537ХМ2АУ-215, выпускаемые мелкосерийными партиями с 1992 г. (ОАО «Ангстрем», г. Зеленоград) для систем опознавания «свой-чужой». Погрешность работы БИС генераторов серии 1537ХМ по равновероятности и некоррелированности не превышает величины 6 • 10−4 при быстродействии до 8 МГц. Представленные разработки характеризуются высокой технологичностью устройств как изделий за счет применения цифровой БИС и полного исключения аналоговых элементов. По сравнению с ранее используемым генератором в аппаратуре опознавания новые устройства имеют повышенные более чем на порядок точность и быстродействие.