Быстродействующий генератор случайных перестановок и сочетаний

Быстродействующий генератор случайных перестановок и сочетаний

Иллюстрации

Показать все

Реферат

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

Известно устройство генерации случайных последовательностей бит (см. патент US №07583155, МПК G06F 7/58). Устройство состоит из осциллирующего блока, который генерирует случайную последовательность бит при подаче на него шумового сигнала. Устройство также включает интегральную схему, обеспечивающую формирование случайной последовательности бит.

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

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

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

Известен генератор случайных чисел для электронных приложений (см. патент US №05871400, МПК A63F 9/21). Устройство содержит генератор на сдвиговых регистрах, в котором используются коэффициенты примитивного полинома порядка k для генерации случайных чисел, и второй генератор для формирования индекса случайного числа, хранящегося в массиве случайных чисел, полученных от генератора на сдвиговых регистрах.

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

Известны генераторы случайных перестановок и сочетаний, описанные в монографии Курейчика В.М. и др. «Комбинаторные аппаратные модели и алгоритмы в САПР»/ М.: «Радио и связь». 1990. C.185-203. Недостатками описанных генераторов являются относительно медленный спад автокорреляционных функций, генерируемых сочетаний и перестановок, низкое быстродействие при генерации некоррелированных случайных сочетаний и перестановок, возможность генерации ошибочных сочетаний, достаточно сложная конструкция при большой длине формируемых сочетаний и перестановок.

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

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

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

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

Поставленная задача решается тем, что быстродействующий генератор случайных перестановок и сочетаний состоит из блока регистров данных, выполненного с возможностью параллельной и последовательной загрузки данных q-разрядных двоичных чисел, и коммутационной матрицы, генератор имеет n q-разрядных выходов данных, образованных параллельными выходами блока регистров данных, m бинарных входов управляющих сигналов для подачи случайных сигналов от внешних источников, вход последовательной загрузки начальной строки перестанавливаемых данных, образованный входом последовательной загрузки блока регистров данных, бинарный вход управления последовательной и параллельной записью данных в блок регистров данных, вход тактовых импульсов блока регистров данных, причем параллельные q-разрядные выходы блока регистров данных электрически соединены с q-разрядными входами коммутационной матрицы, выходы коммутационной матрицы электрически соединены с параллельными q-разрядными входами блока регистров данных, коммутационная матрица имеет n q-разрядных входов, n q-разрядных выходов и состоит из переключателей, расположенных в матричном порядке по n/2 линиям и k=log₂n уровням, каждый переключатель имеет два q-разрядных входа X1, X2, два q-разрядных выхода Y1, Y2 и бинарный вход управляющего сигнала, переключатели реализуют логическую функцию бинарные входы управляющих сигналов переключателей матрицы образуют m бинарных входов управляющих сигналов генератора, каждый переключатель матрицы j-го уровня, где , расположенный на линии с номером i, электрически соединен одним выходом с входом переключателя j+1 уровня, расположенного на линии с номером

а другим выходом с входом переключателя j+1 уровня матрицы, расположенного на линии с номером

,

где INT - функция вычисления целой части от аргумента, каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j, входы переключателей первого уровня являются входами матрицы, выходы переключателей k-го уровня являются выходами матрицы.

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

1 - блок регистров данных;

2 - коммутационная матрица с топологией baseline;

- D₁ - D_n - параллельные q-разрядные входы блока регистра данных и выходы коммутационной матрицы;

- Q₁ - Q_n - параллельные q-разрядные выходы блока регистров данных и выходы генератора;

- S₁ - S_n - q-разрядные входы коммутационной матрицы;

- C₁ - C_m - бинарные входы генератора для подачи управляющих сигналов от внешних источников случайных сигналов;

- A₁ - A_n - начальная строка q-разрядных данных, загружаемая в блок регистров данных;

- - переключатели коммутационной матрицы;

- PE - бинарный вход управления последовательной и параллельной записью данных;

S - последовательный q-разрядный вход блока регистров данных для записи элементов начальной строки данных A₁-A_n;

- clk - вход тактовых импульсов.

Предлагаемый генератор состоит из блока регистров данных 1, выполненного с возможностью параллельной и последовательной загрузки данных, и коммутационной матрицы с топологией baseline 2. Генератор имеет n выходов данных, образованных выходами блока регистров данных, m бинарных входов управляющих сигналов, на которые подаются случайные сигналы от внешних источников, вход S последовательной загрузки начальной строки перестанавливаемых данных A₁-A_n, образованный входом последовательной загрузки блока регистров данных, бинарный вход управления последовательной и параллельной записью данных в блок регистров данных PE, вход тактовых импульсов блока регистров данных clk. Параллельные q-разрядные выходы блока регистров данных электрически соединены с q-разрядными входами коммутационной матрицы, выходы коммутационной матрицы электрически соединены с параллельными q-разрядными входами блока регистров данных. Элементы начальной строки A₁-A_n представляют собой бинарные строки длиной q и могут рассматриваться как двоичные числа разрядности q. Коммутационная матрица имеет n q-разрядных входов, n q-разрядных выходов и состоит из переключателей, расположенных в матричном порядке по n/2 линиям и k=log₂n уровням. Каждый переключатель имеет 2 q-разрядных входа X1, X2, 2 q-разрядных выхода Y1, Y2 и бинарный вход управляющего сигнала C. Переключатели реализуют логическую функцию Входы управляющих сигналов переключателей матрицы образуют m бинарных входов управляющих сигналов генератора. Выходы переключателей предыдущего уровня соединены с входами переключателей следующего уровня в соответствии с топологией сети baseline. Данная топология описана, например, в патенте US №5175539, МПК H04J 3/00. В соответствии с этой топологией каждый переключатель матрицы j-го уровня, где , расположенный на линии с номером i, электрически соединен одним выходом с входом переключателя j+1 уровня, расположенного на линии с номером

а другим выходом с входом переключателя j+1 уровня матрицы, расположенного на линии с номером

где INT - функция вычисления целой части от аргумента. Каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j. Входы переключателей первого уровня являются входами матрицы, выходы переключателей k-го уровня являются выходами матрицы.

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

Перед началом работы внешняя управляющая ЭВМ устанавливает высокий логический уровень на входе управления параллельной и последовательной записью блока регистров данных PE и по отрицательным перепадам тактовых импульсов на входе clk последовательно записывает элементы начальной строки данных A₁-A_n в регистры данных. После этого управляющая ЭВМ устанавливает низкий логический уровень на входе управления параллельной и последовательной записью блока регистров данных PE и по отрицательным перепадам тактовых импульсов на входе clk блока регистров данных генератор формирует на своих выходах случайные перестановки элементов начальной строки данных A₁-A_n. При этом с приходом каждого нового тактового импульса на вход clk на входы управляющих сигналов генератора C₁-C_m подаются новые бинарные случайные числа 0 или 1.

Если в строке A₁-A_n есть повторяющиеся элементы, на выходах генератора формируются случайные сочетания элементов этой строки. Если повторяющихся элементов нет, на выходах генератора формируются случайные перестановки элементов строки A₁-A_n. При этом перестановки и сочетания, формируемые данным генератором, имеют равномерную функцию распределения.

В качестве источника случайных бинарных сигналов, подаваемых на входы управляющих сигналов C₁-C_m, могут использоваться генераторы, описанные в книге Иванова М.А., Чугункова И.В. «Теория, применение и оценка качества генераторов псевдослучайных последовательностей». Например, при использовании генератора псевдослучайной последовательности на сдвиговом регистре с линейными обратными связями данные разрядов сдвигового регистра подаются на входы C₁-C_m. При этом тактовые импульсы clk используются для тактирования генератора на сдвиговом регистре, обеспечивая, таким образом, синхронизацию с предлагаемым генератором перестановок и сочетаний.

Блок регистров состоит из q последовательно-параллельных регистров длиной n. При этом могут быть использованы, например, регистры К155ИР1, описанные в справочнике В.Л.Шило «Популярные цифровые микросхемы» М.: Радио и связь. 1989. с.107-110. Для получения регистра необходимой длины n используется несколько регистров К155ИР1. При этом параллельный выход последнего разряда первого регистра соединяется с последовательным входом следующего регистра и т.д. Если числа A₁-A_n имеют несколько разрядов (q>1), в блок объединяются несколько n-разрядных регистров параллельно. При этом тактовые входы этих регистров блока соединяются между собой. Входы разрешения параллельной загрузки РЕ этих регистров также соединяются между собой. Первый разряд чисел A₁-A_n поступает на последовательный вход первого регистра, второй - на последовательный вход второго регистра и т.д., разряд q поступает на последовательный вход регистра с номером q. Вход S, выходы Q₁-Q_n, входы D₁-D_n блока регистров имеют q разрядов. При этом первый разряд берется с первого регистра, второй - со второго и т.д. На фиг.4 приведена возможна схема соединения шести регистров К155ИР1 блока регистров данных для хранения чисел A₁-A₈, имеющих q=3 разряда.

Таким образом, в зависимости от внешних источников управляющих сигналов предлагаемый генератор обеспечивает формирование псевдослучайных или случайных перестановок и сочетаний исходной строки из n=2^k чисел A₁-A_n. Перестановки и сочетания на выходе генератора имеют равномерное распределение. Генератор обладает высоким быстродействием, поскольку преобразования выполняются параллельно. Для получения любой случайной перестановки или сочетания из числа возможных достаточно подать 2 импульса на вход clk, так как последовательное соединение двух коммутационных сетей с топологией baseline обеспечивает формирование на выходе любой перестановки входных данных. Аппаратная сложность предлагаемого генератора растет практически линейно с ростом n, что дает возможность получения случайных перестановок и сочетаний элементов строк большой длины.

Быстродействующий генератор случайных перестановок и сочетаний, характеризующийся тем, что состоит из блока регистров данных, выполненного с возможностью параллельной и последовательной загрузки данных q-разрядных двоичных чисел, и коммутационной матрицы, генератор имеет n q-разрядных выходов данных, образованных параллельными выходами блока регистров данных, m бинарных входов управляющих сигналов для подачи случайных сигналов от внешних источников, вход последовательной загрузки начальной строки перестанавливаемых данных, образованный входом последовательной загрузки блока регистров данных, бинарный вход управления последовательной и параллельной записью данных в блок регистров данных, вход тактовых импульсов блока регистров данных, причем параллельные q-разрядные выходы блока регистров данных электрически соединены с q-разрядными входами коммутационной матрицы, выходы коммутационной матрицы электрически соединены с параллельными q-разрядными входами блока регистров данных, коммутационная матрица имеет n q-разрядных входов, n q-разрядных выходов и состоит из переключателей, расположенных в матричном порядке по n/2 линиям и k=log₂n уровням, каждый переключатель имеет два q-разрядных входа X1, Х2, два q-разрядных выхода Y1, Y2 и бинарный вход управляющего сигнала, переключатели реализуют логическую функцию бинарные входы управляющих сигналов переключателей матрицы образуют m бинарных входов управляющих сигналов генератора, каждый переключатель матрицы j-го уровня, где расположенный на линии с номером i, электрически соединен одним выходом с входом переключателя (j+1)-го уровня, расположенного на линии с номером , а другим выходом с входом переключателя (j+1)-го уровня матрицы, расположенного на линии с номером , где INT - функция вычисления целой части от аргумента, каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j, входы переключателей первого уровня являются входами матрицы, выходы переключателей k-го уровня являются выходами матрицы.