ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ Российский патент 2008 года по МПК G06F7/58 H03K3/84 

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

Известно устройство генерации случайных чисел, подключаемое к параллельному порту ЭВМ (см. патент США №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, следующих в случайном порядке.

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

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