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

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

Одними из основных элементов, используемых при решении таких задач, являются генераторы случайных и псевдослучайных чисел (ГСЧ и ГПСЧ), от качества и быстродействия которых существенно зависят результаты решения поставленных задач. Известны фундаментальные работы в области генерирования случайных и псевдослучайных чисел [3−15], а также большое количество патентов и авторских свидетельств, которые говорят о всевозрастающем интересе к этим областям. Решению таких задач посвящены работы ученых: Бакановича Э. А., Билинского И. Я., Бобнева М. П., Бондаренко Б. П., Бусленко Н. П., Бухараева Р. Г., Гавела Я., Гантмахера В. Е., Гладкого B.C., Глова В. И., Голенко Д. И., Гондарева В. П., Данильченко И. А., Дапина О. И., Добриса Г. В., Ермакова С. М., Захарова В. М., Кирьянова Б. Ф., Кузнецова В. М., Левина В. К., Леусенко А. Е., Мансурова P.M., Мельникова Ю. Н., Менькова A.B., Морозевича А. Н., Морозова A.M., Орлова М. А., Песошина В. А., Пестрякова В. Б., Полляка Ю. Г., Романкевича A.M., Свердлика А. Н., Сергеева H.H., Соболя И. М., Столова Е. Л., Судакова Д. М., Тарасова В. М., Таусворта Р., Урецкого Я. С., Хамитова Г. П., Чабдарова Ш. М., Четверикова В. М., Шрейдера Ю. А., Яковлева В. В., Ярмолика В. Н. и других.

В отечественной и зарубежной литературе основное внимание при формировании псевдослучайных чисел уделено ГПСЧ, построенным на основе регистра сдвига с линейной обратной связью (с сумматорами по модулю два) [10, 13, 15-^30], причем в большинстве работ рассматриваются последовательности максимальной длины или М-последовательности.

Известно построение ГПСЧ с использованием инверторов в цепи обратной связи регистра сдвига [31, 32]. Однако статистические характеристики чисел, генерируемых такими ГПСЧ, изучены еще недостаточно.

ГПСЧ успешно используются для защиты информации в ПЭВМ и сетях, для шифрования данных или сообщений, поскольку ключ для их расшифрования на приемной стороне строится с помощью идентичного ГПСЧ [28, 31, 33]. Для создания средств криптографической защиты информации необходимо использовать генераторы нелинейных псевдослучайных последовательностей [34], которые исследованы еще недостаточно.

Разработка высококачественных и быстродействующих ГСЧ с равномерным законом распределения является актуальной задачей. Большие успехи в этой области получены в Казанской научной школе, где предложено строить генераторы случайных последовательностей (ГСП) и чисел целиком на цифровой элементной базе с неавтономным источником шума [35, 36]. Перспективным остается создание комбинированных ГСЧ, построенных на основе ГПСЧ [6, 10, 15, 35−40].

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

Для достижения поставленной цели необходимо решить следующие задачи:

— исследовать статистические характеристики псевдослучайных чисел на основе комбинаций прямых и инверсных Ми (М-1)-последовательностей;

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

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

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

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

Научная новизна работы заключается в следующем:

— предложен метод построения ГПСЧ на основе комбинаций прямых и инверсных Ми (М-^-последовательностей. Обобщены известные результаты и исследованы статистические характеристики псевдослучайных чисел на основе прямых и инверсных последовательностейисследован генератор нелинейных псевдослучайных последовательностей, относящийся к классу комбинированных генераторов и состоящий из трех линейных генераторов, один из которыхуправляющий, и мультиплексора. Каждый из трех генераторов является автономной линейной последовательностной машиной. Разработана математическая модель для двух генераторов — управляющего и управляемого. Определен способ вычисления длины циклов и предложен подход для определения статистических свойств выходных нелинейных псевдослучайных последовательностей;

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

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

Основные положения и результаты диссертационной работы докладывались и обсуждались на:

— Всесоюзной научно-технической конференции «Вероятностные методы и средства» (Новгород, 1983 г.);

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

— Всесоюзном научно-техническом семинаре «Сетевая обработка информации» (Москва, 1990 г.).- научно-техническом семинаре «Аппаратные средства защиты информации и статистического моделирования в персональных ЭВМ» (Казань, 1991 г.);

— научно-технической конференции Казанского научного центра РАН (Казань, 1991 г.);

— Всероссийской научно-практической конференции «Проблемы защиты информации в системе высшей школы» (Обнинск, 1993 г.);

Международной научно-технической конференции «Развитие и применение открытых систем» (Казань, 1994 г.);

— юбилейной научной и научно-методической конференции КГТУ им. А. Н. Туполева (Казань, 1997 г.);

— Международной конференции и выставке «Безопасность информации» (Москва, 1997 г.);

На защиту выносятся:

— метод построения ГПСЧ на основе комбинаций прямых и инверсных Ми (М-1) — последовательностейрезультаты исследований генератора нелинейных псевдослучайных последовательностей, состоящего из управляющего и управляемого генератора на регистрах сдвига с линейными обратными связями;

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

Технические решения защищены 3 авторскими свидетельствами и 1 патентом.

Работы проводились по госбюджетным и хоздоговорным темам: -по комплексному договору с НИИ ВС Казанского НПО ВС по теме «Исследование и разработка специализированных процессоров ЭВМ (Ряд 2 и Ряд 3) для сети ЭВМ». Приказом Минвуза СССР № 1238 от 29.12.81 г. данная тематика включена в координационный план НИР вузов Минвуза СССР в области вычислительной техники;

— по конкурсной теме РАН «Методы и средства криптографической защиты информации от несанкционированного использования в ПЭВМ и ЛВС»;

— по хозяйственному договору с ассоциацией «Татинформ» по защите информации при автоматизации деятельности правоохранительных органов РТ;

— по программе НИР АН РТ по теме «Построение криптосистемы на основе генераторов нелинейных псевдои случайных последовательностей»;

— по Межвузовской программе «Методы и технические средства обеспечения информационной безопасности».

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений.

Основные результаты работы заключаются в следующем:

1. Предложен метод построения ГПСЧ на основе комбинаций прямых и инверсных Ми (М-^-последовательностей. Обобщены известные результаты и исследованы статистические характеристики псевдослучайных чисел. Показано, что использование комбинаций прямых и инверсных последовательностей при формировании многоразрядных псевдослучайных чисел позволяет изменять периодическую АКФ чисел. Для формирования некоррелированных псевдослучайных чисел необходимо использовать инверсную М-последовательность для старшего разряда чисел, а для остальных разрядов — прямые М-последовательности. В этом случае модуль нормированной периодической АКФ уменьшается примерно в 2 раза при т<�п, а «фон» АКФ уменьшается в.

Отл.

2 раз. Предложен ГПСЧ, позволяющий формировать произвольные псевдослучайные последовательности, в том числе Ми (М-1)-последовательности.

2. Исследован генератор нелинейных псевдослучайных последовательностей, относящийся к классу комбинированных генераторов и состоящий из трех линейных генераторов, один из которыхуправляющий, и мультиплексора, причем каждый из трех генераторов является автономной линейной последовательностной машиной. Разработана математическая модель для двух генераторов — управляющего и управляемого. Определен способ вычисления длины циклов и предложен подход для определения статистических свойств выходных нелинейных псевдослучайных последовательностей. Доказана теорема о примитивности матрицы соединений автомата для случая, когда длина п управляющего генератора значительно больше длины т управляемого генератора и (2ш-1)-простое число, что свидетельствует о равновероятности появления символов 0 и 1.

3. Предложен ГСП на основе двух генераторов асинхронных случайных сигналов (управляющего и управляемого) с динамически изменяемой обратной связью. Управляющий генератор построен на последовательно соединенных сумматорах по модулю два с обратной связью в соответствии с выбранным полиномом синхронной модели генератора (М-^{-последовательности.} Управляемый генератор содержит последовательно соединенные управляемые формирователи импульсов с обратной связью, определяемой базовым полиномом синхронной модели генератора М-последовательности. На управляемые формирователи импульсов подаются сигналы с выходов сумматоров по модулю два управляющего генератора. С целью улучшения равномерности распределения выходного случайного процесса сигналы управляющего и управляемого генераторов дополнительно суммируются по модулю два.

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

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

ЗАКЛЮЧЕНИЕ

.