Использование хаотического дискретного отображения в устройстве генерации последовательности случайных двоичных чисел

ТРУДЫ АСПИРАНТОВ

УДК 681.3

Борисов А.И., Сизов А.С.

ИСПОЛЬЗОВАНИЕ ХАОТИЧЕСКОГО ДИСКРЕТНОГО ОТОБРАЖЕНИЯ В УСТРОЙСТВЕ ГЕНЕРАЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ДВОИЧНЫХ ЧИСЕЛ

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

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

Существующие средства динамической модификацией КД при администрировании в РВС имеют низкий уровень автоматизации и используют программные средства модификации ключевых данных на основе генераторов

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

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

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

Так устройство "генератор потока случайных сигналов", приведенный в [2], содержит генератор периодических импульсов, источник шума, датчик потока случайных импульсов и обеспечивает формирование потока случайных сигналов с регулируемым коэффициентом автокорреляции. Однако данный генератор формирует поток случайных событий без преобразования в поток двоичных чисел.

Устройство для генерации случайных чисел с использованием хаоса с непрерывным временем, приведенное в [3], содержит три компаратора, генератор периодических импульсных сигналов, блок теста последовательностей, логический элемент для устранения смещения. Данное устройство производит генерацию областных двоичных последовательностей, необратимых случайных битов по областям в соответствии с распределением, на основе автономного или неавтономного хаотического генератора с непрерывным временем. Однако использование отображения с непрерывным временем приводит к повышению требований к производительности вычислительного устройства и необходимости корректирующих воздействий по распределению выходной последовательности.

Устройство для генерации случайных чисел, приведенное в [4], содержащее источник белого шума, высокочастотный аналогово-цифровой преобразователь, сдвиговый регистр накопления, блок двухуровневой коррекции с операцией XOR и накопитель, подключаемое и запитываемое с использованием параллельного порта ЭВМ, производит генерацию последовательности для использования в процессах обработки на ЭВМ. Однако в устройстве нет целевого контроля и коррекции распределения генерируемого хаотического сигнала.

Наиболее близким к предлагаемому решению является генератор случайных чисел, разработанный в [5]. Это устройство, состоящее из аналогового генератора шума, n-разрядного сдвигового регистра с линейными обратными связями, n-разрядного сдвигового регистра хранения перестановок чисел, с использованием случайной инициализации регистров и случайных перестановок обеспечивает формирование множества 2n уникальных чисел длины n, следующих в случайном порядке. Однако процедура генерации случайных чисел на сдвиговых регистрах имеет ограничение в использова-

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

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

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

Рис. 1 - Структурно-функциональная организация устройства генерации последовательности случайных двоичных чисел

Работа устройства генерации последовательности случайных двоичных чисел состоит в следующем.

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

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

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

Рис. 2 - Структурно-функциональная организация блока преобразования с

хаотическим перемешиванием

Для достижения поставленной цели в устройстве предлагается использовать дискретное хаотическое отображение - «треугольное» отображение (1), математическая простота которого позволяет определить хаотические свойства порождаемой им последовательности [6].

( 1 Л А( x) = r 1 - 2 -

V

2

x

Для треугольного отображения показатель Ляпунова равен X=ln2r с изменением знака при r=1/2. Он служит параметром, характеризующим каноническое детерминировано-хаотическое поведение. Итерируемая функция при r>1/2 порождает хаотическую последовательность. При r=1 хаотическое поведение характеризуется постоянной стационарной плотностью p(x)=1 и дельта-коррелированными итерациями C(m)=5m0/12.

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

ной последовательности генератора наблюдаются при параметре r равном 1, но в области действительных чисел, представленных в дискретном виде с плавающей точкой, такое значение параметра r делает поведение треугольного отображения подобным битовому сдвигу с потерей значащих разрядов генерируемого значения. Для предотвращения процесса потери значащих разрядов, показанной на рис. 3, выбор параметра r ограничивается интервалом (1-1e-6; 1), параметра х0 - интервалом (0; 0.5).

Рис. 3 - Потеря значащих разрядов при r = 1

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

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

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

Контроллер с интерфейсом энергонезависимой памяти осуществляет накопление битовой последовательности с передачей по команде ЭВМ запрашиваемого объема случайных бит для прикладного использования и освобождения области, содержащей переданные данные для дальнейшего заполнения, формируя тем самым буфер и корректируя перепады объемов запрашиваемых данных.

Генератор последовательности случайных двоичных чисел реализован на базе перепрограммируемой логической интегральной схемы (ППЛИС) Virtex 4 XC4VSX35, генератора 50МГц, процессора цифровой обработки сигналов (ЦОС) TMS320F2810, быстродействующего ЗУ1 объемом 64кб, подключенного непосредственно к ППЛИС и работающего на частоте ППЛИС, ЗУ2 объемом 128Мб. Устройство устанавливается в стандартную шину PCI персонального компьютера, с которого производится загрузка рабочих конфигураций ППЛИС и процессора ЦОС. Выходные данные забираются из устройства посредством стандартного контроллера PCI с использование режима прямого доступа к памяти (ПДП).

Выводы.

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

Библиографический список

1. Р.М.Кроновер Фракталы и хаос в динамических системах. Основы теории. Москва: Постмаркет, 2000. с. 150-159

2. Генератор потока случайных сигналов: пат. 2127899 Рос. Федерация № 98104559/09; заявл. 18.02.1998; опубл. 20.03.1999. с. 1-2.

3. Генерация случайных чисел с использованием хаоса с непрерывным временем: пат. 2440602 Рос. Федерация №2009104431/08; заявл. 03.08.2006; опубл. 10.09.2010. с. 1-2.

4. Random number generator and generation method: patent 6763364 B1 United States; published on 13-Jul-2004. pp. 1-4

5. Генератор случайных чисел: пат. 2340931 Рос. Федерация

№2007111405/09; заявл. 28.03.2007; опубл. 10.12.2008. с. 1-2.

6. Шустер Г. Детерминированный хаос. - M.: Мир, 1988. с 31-40.