Генератор случайных перестановок

Генератор случайных перестановок

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

Недостатком данного генератора является низкое быстродействие, поскольку для качественного перемешивания данных в сдвиговом регистре хранения перестановок чисел требуется не менее (2ⁿ) операций сдвига и транспозиций.

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

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

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

В результате перестановка формируется за 2ⁿ операций записи в регистр хранения перестановок кодов.

Изобретение поясняется чертежами, где на фиг.1 приведена блок-схема устройства, на фиг.2 - схема дешифратора номера ячейки записи для n=2.

1 - аналоговый генератор шума;

2 - формирователь импульсов;

3 - генератор псевдослучайной последовательности на сдвиговом регистре;

4 - блок управления;

5 - регистр хранения перестановок кодов;

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

7 - быстродействующий генератор;

8 - второй генератор псевдослучайной последовательности на сдвиговом регистре;

9 - дешифратор;

D₁ - логические элементы узлов дешифратора номера ячейки записи;

D₂ - логические элементы выходных каскадов дешифратора номера ячейки записи;

A₁, A₂ - входы дешифратора номера ячейки записи;

S₁, S₂, S₃, S₄ - выходы импульсов записи дешифратора номера ячейки записи;

S - вход импульса записи дешифратора номера ячейки записи;

R - вход импульса сброса триггеров логических элементов D2 дешифратора номера ячейки записи.

Генератор случайных перестановок состоит из аналогового генератора шума 1, соединенного через формирователь импульсов 2 с тактовым входом генератора псевдослучайной последовательности на сдвиговом регистре длиной n 3. Сдвиговый регистр 3 соединен n-разрядной шиной данных с блоком управления 4. Блок управления 4 соединен n-разрядной шиной данных с входами регистра хранения перестановок кодов 5. В состав устройства входит быстродействующий генератор импульсов 7, который электрически соединен своим выходом с вторым генератором псевдослучайной последовательности на сдвиговом регистре 8, электрически соединенным n-разрядной шиной данных с дешифратором номера ячейки записи 9, выходы которого электрически соединены с входами записи 2ⁿ n-разрядных ячеек регистра хранения перестановок кодов, а вход импульсов записи и сброса триггеров логических элементов электрически соединен с блоком управления. Блок управления 4 соединен также шиной данных и управления с интерфейсом с контроллером энергонезависимой памяти 6. В качестве интерфейса может быть использован любой стандартный интерфейс, используемый для подключения периферийных устройств к ЭВМ.

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

После включения генератора сигнал от аналогового генератора шума 1 через формирователь импульсов 2 подается на тактовый вход генератора псевдослучайной последовательности на сдвиговом регистре 3, на выходах данных которого формируется псевдослучайная последовательность кодов длиной n. Сдвиг данных происходит по переднему фронту импульсов. Тактовые импульсы от быстродействующего генератора 7 поступают на второй генератор псевдослучайной последовательности 8 на сдвиговом регистре, который также формирует на своих выводах данных псевдослучайную последовательность кодов длиной n. Частота следования тактовых импульсов быстродействующего генератора 7 в 2ⁿ раз выше средней частоты следования импульсов формирователя импульсов 2. Коды второго генератора псевдослучайной последовательности 8 на сдвиговом регистре поступают на входы дешифратора номера ячейки записи 9. Схема дешифратора для N=2 представлена на фиг.2. Каждый узел дешифрации выполнен в виде логических элементов D₁ с двумя входами x₁, х₂ и двумя выходами u₁, u₂, реализующих логическую функцию , u₂=х₁×х₂ и образующих двоичное дерево. Для предотвращения многократной записи данных в ячейки с одинаковым номером регистра хранения перестановок кодов выходные каскады дешифратора 9 выполнены на логических элементах D₂. Логические элементы D₂ имеют два входа x₁, x₂, два выхода u₁, u₂, вход сброса x₁ внутреннего триггера. Триггер устанавливается в состояние высокого логического уровня при осуществлении записи данным выходным каскадом дешифратора. Представленная ниже таблица истинности логических элементов D₂ иллюстрирует процесс записи кода в текущую ячейку или переноса в следующую ячейку. Если в текущем цикле работы запись в ячейку была осуществлена, данные переносятся в следующую ячейку и так далее до достижения пустой ячейки.

Таблица истинности логических элементов D2
x1	x2	x3	u1	u2	Примечание
0	0	0	0	0
0	1	0	0	1	запись в текущую ячейку
1	0	0	0	1	запись в текущую ячейку
1	1	0	0	4	запись в текущую ячейку
0	0	1	0	0
0	1	1	1	0	перенос в следующую ячейку
1	0	1	1	0	перенос в следующую ячейку
1	1	1	1	0	перенос в следующую ячейку

При поступлении от контроллера энергонезависимой памяти 6 сигнала запроса выдачи кода блок управления 4 по заднему фронту сигнала формирователя импульсов подает короткий импульс на вход S дешифратора 9 номера ячейки записи. По этому импульсу осуществляется запись кода второго генератора псевдослучайной последовательности 8 на сдвиговом регистре в ячейку регистра хранения перестановок кодов, номер которой определяется кодом второго генератора псевдослучайной последовательности на сдвиговом регистре и состоянием дешифратора. В процессе записи триггер выходного каскада дешифратора 9, осуществляющего запись, устанавливается в состояние с высоким логическим уровнем. Процесс повторяется 2ⁿ раз, после чего блок управления 4 подает сигнал сброса на вход R, по которому триггеры выходных каскадов дешифратора переходят в состояние с низким логическим уровнем. После формирования перестановки данные регистра хранения перестановок кодов записываются в энергонезависимую память через интерфейс с контроллером энергонезависимой памяти 6. Поскольку сигналы записи в регистр хранения перестановок кодов 5 имеют случайный характер, запись кодов сдвигового регистра с линейной обратной связью выполняется в ячейки со случайными номерами.

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

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