Способ генерации случайных чисел

Способ генерации случайных чисел

Иллюстрации

Показать все

Реферат

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

Известен способ генерации случайных чисел [1]. Способ генерации случайных чисел с использованием n-разрядного регистра сдвига с обратной связью, разрядом которого выбран q-ичный символ (q=2^l, l=8, 16 бит), в цепях обратной связи осуществляют не менее трех двухпараметрических операций над q-ичными символами на основе случайных таблиц замены Т_к, каждая из которых содержит 2^l неповторяющихся значений двоичных комбинаций длиной l, начальное заполнение регистра сдвига с обратной связью и таблиц случайной замены выполняют от физического датчика случайных чисел неповторяющимися значениями случайных чисел, для чего сравнивают очередное значение случайного числа с ранее записанными значениями случайных чисел, при совпадении нового значения числа с любым из ранее записанных новое значение отбрасывают, при несовпадении - записывают в очередной разряд регистра сдвига и очередную строку таблицы замены, для генерации очередного случайного числа выбирают пять значений, указывающих номера разрядов регистра сдвига, первая и вторая пары значений указывают номера разрядов регистра сдвига для выполнения соответственно первой и второй операций, операндами третьей операции являются результаты выполнения первых двух операций, операндами которых являются значения q-ичных символов, записанные в данном такте в разрядах регистра сдвига с указанными номерами, для выполнения всех операций находят в используемой таблице Т_к значение первого операнда и считывают из таблицы Т_к значение, которое отстоит на число строк используемой таблицы Т_к, совпадающее с двоичным значением второго операнда, результат выполнения третьей операции, являющийся очередным результатом генерации, записывают в последний выбранный разряд регистра сдвига, после чего производят сдвиг содержимого регистра сдвига на один q-ичный разряд.

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

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

Техническим результатом заявляемого изобретения является генерация последовательности чисел более случайных, чем в прототипе, близкой по характеристикам к белому шуму [6, стр.172-180].

Указанный технический результат достигается тем, что в известном способе генерации случайных чисел, заключающемся в начальном заполнении таблицы случайной замены, выполняемом от физического датчика случайных чисел неповторяющимися значениями случайных чисел, для чего сравнивают очередное значение случайного числа с ранее записанными значениями случайных чисел, отбрасывают новое значение при совпадении нового значения числа с любым из ранее записанных, записывают в очередную ячейку таблицы замены - при несовпадении, согласно изобретению значения случайных чисел s_kn, записанные в k-й строке n-го столбца таблицы случайной замены, используют как n-й параметр р_n k-й броуновской частицы q_k, где k=1,…, K, причем K - количество броуновских частиц, а n=3,…, N, причем N - количество параметров броуновских частиц, при этом параметры р₁ и р₂ используют как координаты в двумерном пространстве x_k, y_k, а параметр р₃ - как угол вектора движения φ_k броуновской частицы q_k, причем координаты x_k, y_k частицы q_k такие, что q_k располагается внутри области моделирования броуновского движения А, а угол вектора движения φ_k∈[0; 2π] рад; имитируют движение броуновских частиц q_k внутри области А путем периодического пересчета через промежуток времени Δt параметров p_n броуновских частиц q_k в соответствии с законами движения броуновских частиц в замкнутом пространстве с абсолютно упругими соударениями частиц между собой и со стенками области моделирования броуновского движения, с последующим сохранением пересчитанных параметров p_n броуновских частиц q_k в виде числа s_kn таблицы случайной замены; выделяют внутри области моделирования броуновского движения А область А', представляющей собой совокупность всех точек области А, в которых может находиться центр любой броуновской частицы; разбивают выделенную область А' на М равных по площади кусочков, причем М≥2, из которых выбирают ключевые кусочки a_i при этом i=1,…, I, где I - количество разрядов генерируемого случайного числа, причем 2≤I≤М; формируют значение i-го двоичного разряда очередного I-разрядного случайного двоичного числа Z путем анализа наличия центров броуновских частиц в ключевом кусочке a_i выделенной области А', присваивают i-му двоичному разряду числа Z значение 1, если в ключевом кусочке a_i находится центр хотя бы одной броуновской частицы, присваивают i-му двоичному разряду числа Z значение 0 в противном случае, возвращают сформированное I-разрядное случайное двоичное число Z.

Эти отличительные признаки по сравнению с прототипом позволяют сделать вывод о соответствии заявляемого технического решения критерию "новизна".

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

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

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

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

блок 1 - физический датчик случайных чисел;

блок 2 - запоминающее устройство (таблица случайной замены);

блок 3 - тактовый генератор (таймер);

блок 4 - вычислительное устройство;

блок 5 - устройство чтения случайных чисел.

Назначение блоков понятно из их названия.

Для простоты описания работы устройства будем использовать следующие условия и ограничения:

- в качестве области моделирования броуновского движения используют прямоугольную область;

- таблица случайной замены в каждой строке содержит координаты в двумерном пространстве x_k, y_k и угол вектора движения φ_k броуновских частиц q_k, где 1≤k≤K, K - количество броуновских частиц, причем r≤x_k≤L-r, r≤y_k≤Н-r; x_k, y_k - действительные числа, где L и Н - соответственно длина и высота прямоугольной области моделирования броуновского движения, r - радиус броуновской частицы, 0≤φ_k<2π рад (фиг.2);

- внутри области моделирования броуновского движения размера L×H выделяют область А размером (L-2·r)×(H-2·r), при этом центр области моделирования броуновского движения совпадает с центром выделенной области А;

- выделенную область А разбивают на 2ⁿ равных строк и 2ⁿ равных столбцов, где n - натуральное число, причем каждая ячейка a_ij, где i=1…2ⁿ - количество строк, j=1…2ⁿ - количество столбцов выделенной области А имеет размеры l×h, где l=(L-2·r)/2ⁿ, h=(H-2·r)/2ⁿ.

Осуществляют начальное заполнение таблицы случайной замены 2 от физического датчика случайных чисел 1 неповторяющимися значениями случайных чисел, для чего сравнивают очередное значение случайного числа с ранее записанными значениями случайных чисел, отбрасывают новое значение при совпадении нового значения числа с любым из ранее записанных, записывают в очередную ячейку таблицы замены - при несовпадении. После заполнения таблицы случайной замены передают сигнал инициализации работы устройства на блок 3. С блока 3 поступают тактовые сигналы на вычислительное устройство 4, которое при поступлении очередного тактового сигнала осуществляет пересчет изменяемых параметров x_k, y_k и φ_k всех броуновских частиц. С помощью блока 5 считывают очередное двоичное 2ⁿ-разрядное случайное двоичное число Z путем анализа наличия броуновских частиц, например, в первой строке выделенной области А следующим образом: присваивают j-му двоичному разряду числа Z значение 1, если в ячейке a_1j находится хотя бы одна броуновская частица, то есть существует хотя бы одна броуновская частица q_k такая, что ее координаты удовлетворяют условиям r+(j-1)·l≤x_k<r+j·l, r+(j-l)·h≤y_k<r+j·h, в противном случае присваивают j-му двоичному разряду числа Z значение 0.

Для улучшения статистических свойств генерируемой случайной последовательности можно использовать:

- считывание случайных чисел из произвольной строки или столбца таблицы;

- в качестве дополнительных параметров броуновских частиц q_k, хранимых в таблице случайной замены и учитываемых при имитации движения: радиусы r_k, массы m_k и скорости движения ν_k броуновских частиц, где 1≤k≤K, K - количество броуновских частиц;

- более сложную форму области моделирования броуновского движения, например, круглую (как показано на фиг.3), кольцеобразную или несимметричную.

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

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

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

В качестве физического датчика случайных чисел может быть использована частота процессора ЭВМ, запоминающее устройство (таблица случайной замены) может быть реализовано на базе любого машиночитаемого носителя информации [10, 11], тактовый генератор (таймер) - на базе кварцевого генератора и делителя частоты [5, 9], вычислительное устройство и устройство чтения случайных чисел - в виде специализированных устройств на микроконтроллерах по принципам и методам, описанным в [5-9], взаимное соединение блоков может быть реализовано по стандартным схемам подключения устройств [12].

Источники информации

1. Осмоловский С.А. Способ генерации случайных чисел. Патент на изобретение №2246129 от 10.02.2005.

2. Шредер. М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001. - 528 с.

3. P.M.Кроновер. Фракталы и хаос в динамических системах. Основы теории. М.: Постмаркет, 2000. - 352 с.

4. Нечаев И.А. Конструкции на логических элементах цифровых микросхем. - М.: "Радио и связь", 1992. - 123 с.

5. Белов А.В. Создаем устройства на микроконтроллерах. - СПб.: Наука и техника, 2007. - 304 с.

6. Конструкторско-технологическое проектирование электронной аппаратуры. Учебник для вузов. Серия: Информатика в техническом университете. Под ред. Шахнова В.А. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2003. - 528 с.: ил.

7. Суворова Е., Шейнин Ю. Проектирование цифровых систем на VHDL. Серия "Учебное пособие". - СПб.: БХВ-Петербург, 2003. - 576 с.: ил.

8. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. Серия: Информатика в техническом университете. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. - 288 с.: ил.

9. Новиков Ю.В. Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. - М.: Мир, 2001. - 379 с.

10. Левин В.И. Носители информации в цифровом веке / Под общ. ред. Д.Г.Красковского. - М.: КомпьютерПресс, 2000. - 256 с.: ил.

11. Гук М. Дисковая подсистема ПК. - СПб.: Питер, 2001. - 336 с.: ил. Пей Ан. Сопряжение ПК с внешними устройствами. - М.: ДМК Пресс, 2003. - 320 с. ил.

Способ генерации случайных чисел, заключающийся в начальном заполнении таблицы случайной замены, выполняемом от физического датчика случайных чисел неповторяющимися значениями случайных чисел, для чего сравнивают очередное значение случайного числа с ранее записанными значениями случайных чисел, отбрасывают новое значение при совпадении нового значения числа с любым из ранее записанных, записывают в очередную ячейку таблицы замены - при несовпадении, отличающийся тем, что значения случайных чисел s_kn, записанные в k-й строке n-го столбца таблицы случайной замены, используют как n-й параметр р_n k-й броуновской частицы q_k, где k=1,…, К, причем К - количество броуновских частиц, a n=3,…, N, причем N - количество параметров броуновских частиц, при этом параметры p₁ и p₂ используют как координаты в двумерном пространстве x_k, у_k, а параметр p₃ - как угол вектора движения φ_k броуновской частицы q_k, причем координаты х_k, у_k частицы q_k такие, что q_k располагается внутри области моделирования броуновского движения А, а угол вектора движения φ_k∈[0; 2π] рад; имитируют движение броуновских частиц q_k внутри области А, путем периодического пересчета через промежуток времени Δt параметров р_n броуновских частиц q_k в соответствии с законами движения броуновских частиц в замкнутом пространстве с абсолютно упругими соударениями частиц между собой и со стенками области моделирования броуновского движения, с последующим сохранением пересчитанных параметров р_n броуновских частиц q_k в виде числа s_kn таблицы случайной замены; выделяют внутри области моделирования броуновского движения А область А', представляющей собой совокупность всех точек области А, в которых может находиться центр любой броуновской частицы; разбивают выделенную область А' на М равных по площади кусочков, причем М≥2, из которых выбирают ключевые кусочки а_i, при этом i=1,…, I, где I - количество разрядов генерируемого случайного числа, причем 2≤I≤М; формируют значение i-го двоичного разряда очередного I-разрядного случайного двоичного числа Z путем анализа наличия центров броуновских частиц в ключевом кусочке а_i выделенной области А', присваивают i-му двоичному разряду числа Z значение 1, если в ключевом кусочке а_i находится центр хотя бы одной броуновской частицы, присваивают i-му двоичному разряду числа Z значение 0 в противном случае, возвращают сформированное I-разрядное случайное двоичное число Z.