ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ
PSEUDORANDOM NUMBER GENERATOR

Изобретение относится к вычислительной технике и электросвязи, предназначено для решения задач защиты компьютерной информации. Наиболее предпочтительной областью использования изобретения является реализация стохастических методов защиты информации.
В совокупности признаков заявленного изобретения используются следующие термины:
Регистры сдвига с линейной обратной связью (LFSR - Linear Feedback Shift Register) - простейшие генераторы псевдослучайных чисел (ГПСЧ), активно используемые при решении различных задач защиты информации. Структура устройства определяется видом двоичного характеристического многочлена Ф(х) (см. [Стохастические методы и средства защиты информации в компьютерных системах и сетях / М.А. Иванов, А.В. Ковалев, И.В. Чугунков и др. - М.: КУДИЦ-ПРЕСС, 2009, 602 с.] или [Иванов М.А., Чугунков И.В. Криптографические методы защиты информации. - М.: НИЯУ МИФИ, 2012, www.aha.ru/~msa]).
n
-1
-1
i
0
2
q-2
Конечное поле или поле Галуа GF(q) (GF - Galois Field, q=p - число элементов поля, р - простое, n - натуральное) - конечное множество элементов, обладающее следующими свойствами: 1) в поле определены две операции, одна условно называется сложением, другая - умножением; 2) для элементов поля α, β, γ справедливы соотношения α+β=β+α, αβ=βα, (α+β)γ=αγ+βγ; 3) в поле существуют нулевой и единичный элементы, обозначаемые соответственно как 0 и 1, для которых справедливо 0+α=α, 0α=0, 1α=α; 4) в поле для любого α≠0 существует обратный ему элемент по сложению, обозначаемый (-α), для которого справедливо α+(-α)=0; и обратный ему элемент по умножению, обозначаемый α, для которого справедливо αα=1; 5) любой ненулевой элемент поля можно представить в виде степени примитивного элемента ω: ∀α≠0 α=ω, таким образом, конечное поле можно представить в виде GF(q)={0, ω=1, ω, ω, …, ω}.
Генераторы псевдослучайных чисел (ГПСЧ) - основа стохастических методов защиты информации, применение ГПСЧ обеспечивает непредсказуемое поведение объекта и средств его защиты, позволяя тем самым защититься от активного противника.
Последовательности, формируемые генераторами на основе регистров сдвига с линейными обратными связями - LFSR (Linear Feedback Shift Register), функционирующих в конечных полях, являются важнейшим классом псевдослучайных последовательностей (ПСП). Основными достоинствами этих генераторов являются:
- простота программной и аппаратной реализации; удобство интегрального исполнения из-за регулярной структуры, максимальное быстродействие;
- гарантированно большой период и хорошие статистические свойства формируемых ПСП;
- возможность построения на их основе генераторов, обладающих свойствами, ценными при решении специфических задач защиты информации (формирование последовательностей произвольной длины, формирование последовательностей с предпериодом, формирование ПСП с произвольным законом распределения, построение генераторов, обладающих свойством самоконтроля, и т.п.).
Математический аппарат, лежащий в основе LFSR, - теория конечных полей или полей Галуа. Существует две конструкции LFSR - схема Фибоначчи и схема Галуа, при этом вторая конструкция имеет много интересных свойств, которые используются и в заявленном техническом решении.
LFSR, к сожалению, не являются непредсказуемыми, поэтому применяются при решении задач криптографической защиты информации лишь в качестве строительных блоков.
Исходная информация для построения двоичного LFSR - так называемый характеристический многочлен. Степень этого многочлена определяет разрядность регистра сдвига, а ненулевые коэффициенты - характер обратных связей.
2
i
N-1
2
1
0
i
N
N-1
2
Известен генератор псевдослучайных чисел, функционирующий в конечном поле GF(p), где р>2 - простое, состоящий из N регистров разрядности ]logp[, N блоков сложения в GF(p), N блоков умножения в GF(p), причем величина, на которую происходит умножение в (i+1)-м блоке умножения, равна коэффициенту a характеристического многочлена ϕ(х)=(х-1)λ(х)=x-ax-…-ах-ах-а, где i=0, 1, 2, …, (N-1), a∈GF(p), λ(х) - многочлен степени (N-1), примитивный над GF(p), выходы N-го регистра соединены со входами всех блоков умножения, выходы j-х блоков умножения соединены с первыми входами j-x блоков сложения, выходы которых соединены со входами j-x регистров, где j=1, 2, …, N, вторые входы всех блоков сложения образуют N групп управляющих входов генератора, выходы k-х регистров соединены со третьими входами (k+1)-х блоков сложения, выходы которых соединены со входами (j+1)-х регистров, где k=1, 2, (N-1). (М.А. Ivanov, B.V. Kliuchnikova, Е.А. Salikov, A.V. Starikovskii. New class of non-binary pseudorandom number generators. - Proceedings of Intelligent Technologies in Robotics, Moscow, Russia, 2019, pp. 255-262).
Недостатком известного генератора является сложность и зависимость длины формируемой последовательности от числа элементов поля, так как число запрещенных состояний устройства равно р.
n
n
n
N
N-1
2
n
n
n
i
2
1
0
i
Таким образом, наиболее близким по своей технической сущности к заявленному устройству является генератор псевдослучайных чисел, функционирующий в конечном поле GF(2), где n>1 - целое, состоящий из N регистров разрядности n, N блоков сложения в GF(2), блока управляющих воздействий и N блоков умножения в GF(2), причем величина, на которую происходит умножение в (i+1)-м блоке умножения, равна коэффициенту a характеристического многочлена ϕ(:с)=(х+1)λ(х)=x+a+…+ах+ах+а, где i=0, 1, 2, …, (N-1), a∈GF(2), λ(х) - многочлен степени (N-1), примитивный над GF(2), Выходы N-го регистра соединены со входами всех блоков умножения, выходы (j+1)-х блоков умножения и выходы j-x регистров соединены соответственно с первыми и вторыми входами j-x блоков сложения, выходы которых соединены со входами (j+1)-х регистров, где j=1, 2, (N-1), первые входы N-го блока сложения в GF(2) подключены к выходам первого блока умножения, а выходы соединены со входами первого регистра, вторые входы N-го блока сложения и третьи входы j-x блоков сложения подключены к соответствующим выходам блока управляющих воздействий [Иванов М.А., Саликов Е.А. Генератор псевдослучайных чисел. Патент РФ №2740339].
n
nN
n
Известное устройство функционирует в конечном поле GF(2) и формирует последовательность длиной 2-2+1. Недостатком известного устройства является избыточная сложность из-за наличия блока управляющих воздействий, формирующего последовательности управляющих сигналов.
Техническим результатом изобретения является упрощение устройства и увеличение длины формируемой псевдослучайной последовательности.
n
n
n
i
Поставленная цель достигается тем, что генератор псевдослучайных чисел, функционирующий в конечном поле GF(2), где n>1 - целое, состоящий из N регистров разрядности n, (N-1) блоков сложения в GF(2), N блоков умножения в GF(2), причем величина, на которую происходит умножение в (i+1)-м блоке умножения, равна коэффициенту a характеристического многочлена
N
N-1
2
N-1
2
1
0
ϕ(x)=(х+1)λ(x)=x+ax+…+ax+ax+a,
i
n
n
n
n
n
где i=0, 1, 2, …, (N-1), a∈GF(2), λ(х) - многочлен степени (N-1), примитивный над GF(2), выходы N-го регистра соединены со входами всех блоков умножения, выходы (j+1)-х блоков умножения и выходы j-x регистров, где j=1, 2, (N-1), соединены соответственно с первыми и вторыми входами j-x блоков сложения, дополнительно содержит N сумматоров по модулю 2, выходы (i+1)-х сумматоров по модулю 2 подключены ко входам (i+1)-х регистров, первые и вторые входы (i+1)-х сумматоров по модулю 2 подключены к выходам (i+1)-х блоков умножения и (i+1)-м группам управляющих входов генератора.
nN
Заявленный эффект обеспечивается за счет того, что из схемы ГПСЧ исключается блок управляющих воздействий, так как все управляющие сигналы - это константы, а диаграмма переключений генератора включает в себя два цикла длиной 2 - 2 и 2, т.е. длина формируемой последовательности не зависит от числа элементов поля.
n
n
n
n
1
2
3
1
2
3
На фиг. 1 показана схема генератора для случая GF(2), N=3, где 1.1, 1.2, 1.3 - регистры генератора Q, Q, Q; 2.1, 2.2 - блоки сложения в GF(2); 3.1, 3.2 - блоки умножения в GF(2), причем величина, на которую происходит умножение, определяется соответствующим коэффициентом характеристического многочлена; 4.1, 4.2, 4.3 - сумматоры по модулю 2; 5.1, 5.2, 5.3 - группы управляющих входов генераторы, соответственно c, с, с.
n
n
Генератор псевдослучайных чисел, в общем случае состоит из N регистров 1.1, 1.2, …, 1.N разрядности n, (N-1) блоков 2.1, 2.2, 2.(N-1) сложения в GF(2), N блоков 3.1, 3.2, 3.N умножения в GF(2), причем величина, на которую происходит умножение в (i+1)-м блоке умножения, равна коэффициенту а, характеристического многочлена
N
N-1
2
N-1
2
1
0
ϕ(х)=(х+1)λ(х)=x+ax+…+ах+ах+а,
i
n
n
n
n
где i=0, 1, 2, …, (N-1), a∈GF(2), λ(х) - многочлен степени (N-1), примитивный над GF(2), выходы N-го регистра 1.N соединены со входами всех блоков 3 умножения, выходы (j+1)-х блоков 3 умножения и выходы j-x регистров 1, где j=1, 2, …, (N-1), соединены соответственно с первыми и вторыми входами j-x блоков 2 сложения. Генератор содержит также N сумматоров 4.1, 4.2, …, 4.N по модулю 2, выходы (i+1)-х сумматоров 4 по модулю 2 подключены ко входам (i+1)-х регистров 1, первые и вторые входы (i+1)-х сумматоров 4 по модулю 2п подключены к выходам (i+1)-х блоков 3 умножения и (i+1)-м группам управляющих входов 5 генератора.
1
2
N-1
1
2
N-1
1
2
N
n
n
Если какой-либо коэффициент а, а, …, a характеристического многочлена равен 1, это эквивалентно умножению на 1 в соответствующем блоке 3 умножения, иначе говоря, его отсутствию. Если какой-либо коэффициент а, а, …, a характеристического многочлена равен 0, это эквивалентно отсутствию соответствующих блока 2 сложения и блока 3 умножения. Таким образом, число блоков 3 умножения равно числу не равных нулю или единице коэффициентов характеристического многочлена (на фиг. 2 и 5 это число равно двум). Если какой-либо управляющий сигнал c, с, …, c равен 0, это эквивалентно отсутствию соответствующего сумматора 4 по модулю 2. Таким образом, число сумматоров 4 по модулю 2 равно числу не равных нулю управляющих сигналов 5 (на фиг. 2 и 5 это число равно единице).
2
2
3
2
2
2
2
На фиг. 2 показан первый пример генератора для случая поля GF(2), когда характеристический многочлен степени N=3 имеет вид (х+1)(х+х+ω)=х+ωх+ω, где х+х+ω - многочлен, примитивный над GF(2). На фиг. 3 показано соответствие между различными формами представления элементов поля GF(2). На фиг. 4 показана диаграмма переключений генератора, схема которого приведена на фиг. 2.
3
2
3
3
3
На фиг. 5 показан второй пример генератора для случая поля GF(2), когда характеристический многочлен степени N=3 имеет вид (х+1)(х+ω)=х+ωх+ω, где х+ω - многочлен, примитивный над GF(2). На фиг. 6 показано соответствие между различными формами представления элементов поля GF(2). На фиг. 7 показана диаграмма переключений генератора, схема которого приведена на фиг. 5.
2
2
2
2
1
2
На фиг. 8 показан третий пример генератора для случая поля GF(2), когда характеристический многочлен степени N=2 имеет вид (х+1)(х+ω)=х+ωх+ω, где x+ω - многочлен, примитивный над GF(2). На фиг. 8 показаны также две диаграммы переключений вида 14-2 генератора для разных значений управляющих сигналов с, с.
nN
Генератор псевдослучайных чисел (ГПСЧ) работает следующим образом. Перед началом работы регистры 1 генератора устанавливаются в одно из состояний цикла длиной 2-2. Два состояния, входящие в цикл длиной 2, являются запрещенными. Цепь установки в исходное состояние на фиг. 1 не показана. Тактовые входы регистров 1 объединены и образуют тактовый вход ГПСЧ, который также не показан на фиг. 1.
n
nN
nN
nN
2
3
2
При поступлении тактовых импульсов ГПСЧ переключается в соответствии с уравнениями, приведенными на фиг. 1. Вне зависимости от используемого конечного поля GF(2) диаграмма переключений генератора всегда имеет вид (2-2)-2, т.е. состоит из двух циклов длиной 2-2 и 2. Выходная псевдослучайная последовательность длиной 2-2 считывается с выходов одного из регистров 1 генератора. В примерах ГПСЧ, приведенных на фиг. 4 и 7 диаграммы переключений имеют вид 62-2. В примерах ГПСЧ, приведенных на фиг. 8, диаграммы переключений имеют вид 14-2. ГПСЧ, схема которого приведена на фиг. 2, формирует псевдослучайную последовательность длиной 62 над GF(2); ГПСЧ, схема которого приведена на фиг. 5, формирует псевдослучайную последова-тельность длиной 62 над GF(2); ГПСЧ, схема которого приведена на фиг. 8, формирует псевдослучайные последовательности длиной 14 над GF(2).
Таким образом, техническим результатом изобретения является упрощение устройства и увеличение длины формируемой последовательности.
n
В устройстве-прототипе требуется дополнительная логика для реализации блока управляющих сигналов, которые меняются в процессе работы устройства. Число запрещенных состояний в устройстве-прототипе растет с ростом n и равно 2, в предлагаемом же изобретении число запрещенных состояний не зависит от n и всегда равно двум. Значения управляющих сигналов не меняются в процессе работы устройства и поэтому никакой дополнительной логики не требуется.
n
nN
nN
В устройстве-прототипе длина формируемой последовательности зависит от n и на 2 меньше максимально возможной длины, равной 2, в предлагаемом же изобретении длина формируемой последовательности не зависит от n и на 2 меньше максимально возможной длины, равной 2.