генератор случайных чисел

Формула изобретения

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

Описание изобретения к патенту

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

Известно устройство генерации случайных чисел, подключаемое к параллельному порту ЭВМ (см. патент США №6763364, МПК G06F 1/02; G06F 7/58). Устройство содержит источник белого шума и усилитель, работающий в высокочастотном диапазоне. Низкочастотное ограничение используется для обеспечения широкой полосы и удаления шумов усилителя 1/f. Компаратор с задержкой 10 нс преобразует аналоговый сигнал в двоичный. Сдвиговый регистр преобразует последовательный сигнал в 4-х битный параллельный код.

Недостатком данного устройства является то, что в выходном потоке R_i,i=1,...,n возможно появление одинаковых чисел R_i=R_j , i j, что недопустимо для управляющих чисел побитовой перестановки. Кроме этого для осуществления побитовой перестановки двоичного вектора данных a_i, i=1,...,n, необходимо множество 2ⁿ чисел длины n, что также не обеспечивает данное устройство.

Известно устройство псевдослучайного генератора чисел, в котором использован сдвиговый регистр с линейной обратной связью и нелинейная схема (см. патент США №5566099, МПК G06F 7/58; G09C 1/00). Устройство генерирует псевдослучайные числа с заданным распределением. Генератор имеет сдвиговый регистр, к которому подключен выход нелинейной схемы, схему установки случайных начальных значений в сдвиговый регистр с линейной обратной связью и сдвиговый регистр, и сумматор для сложения предопределенных битов параллельного выхода регистра и выхода псевдослучайного потока чисел.

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

Наиболее близким к предлагаемому решению является известный генератор n-значной псевдослучайной последовательности (ПСП), содержащий n элементов И, блок управления, снабженный n выходами, первые входы которых соединены с соответствующими выходами блока управления, n сумматоров по модулю два и n регистров сдвига, причем выходы j-го (где ) и 1-го разрядов первого регистра сдвига подключены соответственно к первому и второму входам первого сумматора по модулю два, выход k-го и (i+1)-го разрядов 1-го регистра сдвига подключены соответственно к первому и второму входам 1-го сумматора по модулю два, выход первого сумматора по модулю два соединен с информационным входом одноименного регистра сдвига и с одноименным выходом блока управления, выход каждого регистра сдвига подключен к второму входу одноименного элемента И, выходы элементов И являются выходами генератора (патент на изобретение РФ 2081450, МПК G06F 7/58).

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

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

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

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

Изобретение поясняется чертежом, на котором приведена блок-схема устройства.

1. Аналоговый генератор шума.

2. Формирователь импульсов.

3. Сдвиговый регистр с линейными обратными связями.

4. Блок управления.

5. Сдвиговый регистр хранения перестановок чисел.

6. Интерфейс с контроллером энергонезависимой памяти.

Предлагаемое устройство состоит из аналогового генератора шума (1), соединенного через формирователь импульсов (2) с тактовым входом генератора ПСП на сдвиговом регистре с линейными обратными связями (3) длиной n, которой объединенной тактовой шиной и n разрядной шиной данных соединен с блоком управления (4). Блок управления (4) соединен тактовой шиной, n разрядной шиной данных, а также n разрядным входом данных с тактовым, последовательным n разрядным входом и последовательным n разрядным выходом сдвигового регистра хранения перестановок чисел (5) соответственно. Блок управления (4) соединен также шиной данных и управления с интерфейсом с контроллером энергонезависимой памяти (6). Формирователь импульсов содержит компаратор и преобразует аналоговый сигнал генератора шума в случайную бинарную последовательность. Аналоговый генератор шума - любой генератор, выходной сигнал, которого меняется по случайному закону. Это может быть динамический хаотический генератор, например, на диоде Ганна (Коростелев Г.Н., Сотов Л.С.«Сложная динамика генераторов на диоде Ганна с низкочастотным контуром» Изв. вузов. Радиотехника иэлектроника. 1989. N9. Т.34. С.1925-1929.) или генератор, основанный на усилении микрофлуктуаций в системах с большим числом степеней свободы (тепловых, дробовых шумов и т.п.). Сдвиговый регистр с линейными обратными связями предназначен для генерации псевдослучайной последовательности длиной n. Блок управления содержит стандартный генератор тактовых импульсов, счетчик, логику управления и предназначен для организации начальной загрузки псевдослучайной последовательности из регистра (3), операций сдвига и перестановок данных в сдвиговом регистре (5). Интерфейс с контроллером энергонезависимой памяти стандартный, например, USB.

Устройство работает следующим образом.

По сигналу запроса выдачи серии 2ⁿ случайных чисел (чисел), подаваемого контроллером интерфейса энергонезависимой памяти 6 на блок управления 4, сигнал от аналогового генератора шума 1 через формирователь импульсов 2 подается на тактовый вход сдвигового регистра с линейными обратными связями 3. Сдвиг происходит по переднему фронту сигнала на тактовом входе. Одновременно блок управления 4, используя внутренний тактовый генератор и счетчик импульсов, формирует сигнал начальной загрузки. По этому сигналу данные с параллельных выходов регистра 3 через блок управления подаются на n-разрядный последовательный вход данных сдвигового регистра хранения перестановок чисел 5. В процессе начальной загрузки в регистр 5 загружаются 2ⁿ уникальных псевдослучайных чисел разрядности n с равновероятной функцией распределения. Для обеспечения условия случайности после загрузки выполняется фаза сдвигов и случайных перестановок загруженных чисел. Данные в сдвиговом регистре хранения перестановок чисел 5 циклически сдвигаются по заднему фронту сигнала тактового генератора блока управления 4. Перестановка двух n разрядных чисел выполняется в блоке управления по переднему фронту сигнала тактового генератора блока управления, при условии высокого уровня сигнала на выходе формирователя импульсов, в противном случае перестановки не происходит. Поскольку сигнал с формирователя импульсов имеет случайный характер и не коррелирован с генератором тактовых импульсов блока управления, выполняется случайная перестановка чисел. Полное перемешивание чисел возникает за k 2ⁿ⁺³ операций сдвига и перестановок. Далее начинается фаза передачи сформированных чисел из блока управления через интерфейс с контроллером энергонезависимой памяти.

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