Генератор псевдослучайных чисел
Владельцы патента RU 2756833:
федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский ядерный университет МИФИ" (НИЯУ МИФИ) (RU)
Изобретение относится к вычислительной технике и электросвязи, предназначено для решения задач защиты компьютерной информации. Техническим результатом изобретения является повышение безопасности использования устройства за счет усложнения анализа его функциональных возможностей неавторизованными лицами. Генератор псевдослучайных чисел, состоит из N D-триггеров, N сумматоров по модулю два, первой группы из (Ν-1) элементов И, дополнительно содержит вторую и третью группы из N элементов И и элемент ИЛИ-НЕ, выход которого подключен к первым входам всех элементов И второй группы, вторые входы которых образуют вторую группу из N ключевых входов генератора, выход первого элемента И второй группы соединен со вторым входом первого сумматора по модулю два, третьи входы сумматоров по модулю два образуют третью группу из N ключевых входов генератора, выходы (i+1)-х элементов И (i+1) второй группы соединены с четвертыми входами (i+1)-х сумматоров (i+1) по модулю два, выходы j-x D-триггеров подключены к первым входам j-x элементов И j третьей группы, вторые входы которых образуют четвертую группу из N ключевых входов генератора, а выходы подключены ко входом элемента ИЛИ-НЕ. 7 ил.
Изобретение относится к вычислительной технике и электросвязи, предназначено для решения задач защиты компьютерной информации. Наиболее предпочтительной областью использования изобретения является реализация стохастических методов защиты информации.
В совокупности признаков заявленного изобретения используются следующие термины:
Регистры сдвига с линейной обратной связью (LFSR - Linear Feed-back Shift Register) - простейшие генераторы псевдослучайных чисел (ГПСЧ), активно используемые при решении различных задач защиты информации. Структура устройства определяется видом двоичного характеристического многочлена Ф(х) (см. [Стохастические методы и средства защиты информации в компьютерных системах и сетях / М.А. Иванов, А.В. Ковалев, И.В. Чугунков и др. - М.: КУДИЦ-ПРЕСС, 2009, 602 с.] или [Иванов М.А., Чугунков И.В. Криптографические методы защиты информации. - М.: НИЯУ МИФИ, 2012, ххх с, www.aha.ru/~msa]).
Конечное поле или поле Галуа GF(q) (GF - Galois Field, q=pn - число элементов поля, p - простое, n - натуральное) - конечное множество элементов, обладающее следующими свойствами: 1) в поле определены две операции, одна условно называется сложением, другая - умножением; 2) для элементов поля α, β, γ справедливы соотношения α+β=β+α, αβ=βα, (α+β)γ=αγ+βγ; 3) в поле существуют нулевой и единичный элементы, обозначаемые соответственно как 0 и 1, для которых справедливо 0+α=α, 0α=0, 1α=α; 4) в поле для любого α ≠ 0 существует обратный ему элемент по сложению, обозначаемый (-α), для которого справедливо α+(-α)=0; и обратный ему элемент по умножению, обозначаемый α-1, для которого справедливо αα-1=1; 5) любой ненулевой элемент поля можно представить в виде степени примитивного элемента: ∀α ≠ 0 α=ωi, таким образом, конечное поле можно представить в виде GF(q)={0, ω0=1, ω, ω2, …, ωq-2}.
Logic Encryption (шифрование логической схемы цифрового устройства (ЦУ)) - технология запутывания логической схемы ЦУ для защиты от реверс-инжиниринга, иначе говоря, для скрытия функциональных возможностей ЦУ от неавторизованных лиц. Если обфускация программ - это направление, которое развивается уже очень давно, то обфускация аппаратуры - это направление, которое развивается сравнительно недавно, когда появилась новая угроза кибербезопасности - вредоносное аппаратное обеспечение (Malicious Hardware), при этом речь в первую очередь идет об аппаратных троянах и аппаратных закладках, которые могут внедрены в схему ЦУ на различных этапах производства интегральной схемы (ИС).
Блок замены (S-блок) - важнейший элемент всех без исключения блочных стохастических алгоритмов защиты информации и многих поточных стохастических алгоритмов защиты информации. От качества S-блоков напрямую зависит стойкость алгоритмов защиты информации (см. [Стохастические методы и средства защиты информации в компьютерных системах и сетях / М.А. Иванов, А.В. Ковалев, И.В. Чугунков и др. - М.: КУДИЦ-ПРЕСС, 2009, 602 с.] или [Иванов М.А., Чугунков И.В. Криптографические методы защиты информации. - М.: НИЯУ МИФИ, 2012, ххх с, www.aha.ru/~msa]).
Генераторы псевдослучайных чисел (ГПСЧ) - основа стохастических методов защиты информации, применение ГПСЧ обеспечивает непредсказуемое поведение объекта и средств его защиты, позволяя тем самым защититься от активного противника.
Последовательности, формируемые двоичными генераторами на основе регистров сдвига с линейными и нелинейными обратными связями - LFSR (Linear Feedback Shift Register) и NLFSR (Non Linear Feedback Shift Register), являются важнейшим классом псевдослучайных последовательностей (ПСП).
Основными достоинствами этих генераторов являются:
- простота программной и аппаратной реализации; удобство интегрального исполнения из-за регулярной структуры, максимальное быстродействие;
- хорошие статистические свойства формируемых последовательностей;
- возможность построения на их основе генераторов, обладающих свойствами, ценными при решении специфических задач защиты информации (формирование последовательностей произвольной длины, формирование последовательностей с предпериодом, формирование ПСП с произвольным законом распределения, построение генераторов, обладающих свойством самоконтроля, и т.п.).
Исходная информация для построения двоичного LFSR - так называемый характеристический многочлен. Степень этого многочлена определяет разрядность регистра сдвига, а ненулевые коэффициенты - характер обратных связей.
Известно двоичное устройство для генерации псевдослучайных чисел, состоящее из N D-триггеров, (Ν-1) блоков умножения в поле GF(2) и (Ν-1) блоков сложения в поле GF(2), при этом выход N-го D-триггера подключен ко входу первого D-триггера и входам всех блоков умножения, выход i-го блока умножения подключен к первому входу (N-i)-го блока сложения, второй вход которого соединен с выходом (N-i)-го D-триггера, а выход подключен ко входу (N-i+1)-го D-триггера, i=1, 2, 3, …, (Ν-1). (см. [APPARATUS AND METHOD FOR RANDOM NUMBER GENERATION. United States Patent №US 7 028 059; Apr. 11, 2006; FIG. 1, FIG. 1A] или [СПОСОБ ЛИНЕЙНОГО ПРЕОБРАЗОВАНИЯ (ВАРИАНТЫ). Описание изобретения к патенту Ru 259 87 81; 31.07.2015]).
Данная конструкция LFSR называется схемой Галуа. В случае ее использования выбор Ф(х) не ограничен только примитивными многочленами. Полезными свойствами обладают LFSR, соответствующими многочленам вида Ф(х)=(x+1)λ(x) и Ф(х)=(x+1)2λ(х), где λ(x) - примитивный. Кроме того двоичные N-разрядные генераторы Галуа могут использоваться для построения расширенных конечных полей вида GF(2N**).
Недостатком известного устройства являются ограниченные функциональные возможности.
Таким образом, наиболее близким по своей технической сущности к заявленному устройству является двоичный генератор псевдослучайных чисел, состоящий из N D-триггеров, N сумматоров по модулю два, группы из N элементов И, где N - степень характеристического двоичного многочлена, первый вход первого сумматора по модулю два является информационным входом генератора, выходы i-x D-триггеров, где i=1, 2, …, (N-1), соединены с первыми входами (i+1)-х сумматоров по модулю два, выходы j-х сумматоров по модулю два соединены с информационными входами j-x D-триггеров, где j=1, 2,…, Ν, выход N-го D-триггера соединен с первыми входами всех элементов И группы, вторые входы элементов И первой группы образуют группу управляющих входов генератора, выходы i-x элементов И группы соединены со вторыми входами i-х сумматоров по модулю два [см. PARALLEL OPERATION LINEAR FEEDBACK SHIFT REGISTER, US Patent Number 5 412 665, Jan. 10, 1992, fig. 1].
Недостатком известного решения является отсутствие защиты от реверс-инжиниринга. К причинам, препятствующим достижению указанного ниже технического результата, является то, что функциональные возможности известного устройства не скрываются от неавторизованных лиц.
В основе изобретения лежит задача построения ГПСЧ, в схему которого вводятся дополнительные логические элементы, чтобы скрыть его оригинальные функциональные возможности. Иначе говоря, это попытка максимально усложнить понимание логики работы защищаемой схемы для неавторизованных лиц. Шифрование логической схемы (по сути ее обфускация) меняет конструкцию ГПСЧ таким образом, что она работает правильно, только в том случае, если сигналы на дополнительных ключевых входах генератора принимают правильные значения
Указанный технический результат обеспечивается за счет того, что генератор псевдослучайных чисел, состоящий из N D-триггеров, N сумматоров по модулю два, первой группы из (N-1) элементов И, где N - степень характеристического двоичного многочлена, выходы i-х D-триггеров, где i=1, 2,…, (N-1), соединены с первыми входами (i+1)-х сумматоров по модулю два, выходы j-x сумматоров по модулю два соединены с информационными входами j-x D-триггеров, где j=1, 2,…, N, выход N-го D-триггера соединен с первыми входами всех элементов И первой группы и первым входом первого сумматора по модулю два, вторые входы элементов И первой группы образуют первую группу из (N-1) ключевых входов генератора, выходы i-х элементов И первой группы соединены со вторыми входами (i+1)-х сумматоров по модулю два, дополнительно содержит вторую и третью группы из N элементов И и элемент ИЛИ-НЕ, выход которого подключен к первым входам всех элементов И второй группы, вторые входы которых образуют вторую группу из N ключевых входов генератора, выход первого элемента И второй группы соединен со вторым входом первого сумматора по модулю два, третьи входы сумматоров по модулю два образуют третью группу из N ключевых входов генератора, выходы (i+1)-х элементов И второй группы соединены с четвертыми входами (i+1)-х сумматоров по модулю два, выходы j-x D-триггеров подключены к первым входам j-x элементов И третьей группы, вторые входы которых образуют четвертую группу из N ключевых входов генератора, а выходы подключены ко входом элемента ИЛИ-НЕ.
На фиг.1 показана схема заявленного устройства для случая N=4. В состав генератора входят N D-триггеров 1.1, 1.2, 1.3, 1.4; N сумматоров 2.1, 2.2, 2.3, 2.4 по модулю два; первая группа из (N-1) элементов И 3.1, 3.2, 3.3; вторая группа из N элементов И 4.1, 4.2, 4.3, 4.4; третья группа из N элементов И 5.1, 5.2, 5.3, 5.4; элемент 6 ИЛИ-НЕ. На фиг.1 показаны первая группа из (N-1) ключевых входов 7.1, 7.2, 7.3; вторая группа из N ключевых входов 8.1, 8.2, 8.3, 8.4; третья группа из N ключевых входов 9.1, 9.2, 9.3, 9.4; четвертая группа из N ключевых входов 10.1, 10.2, 10.3, 10.4. Тактовые входы D-триггеров подключены к тактовому входу генератора (на фиг.1 не показан). Цепь установки в исходное состояние на фиг.1 также не показана. Ключевые входы 7.1, 7.2 и 7.3 задают вид характеристического многочлена Ф(х). Ключевые входы 8.1, 8.2, 8.3 и 8.4 обеспечивают подключение выхода элемента 6 ИЛИ-НЕ к требуемым сумматорам 2. Ключевые входы 9.1, 9.2, 9.3 и 9.4 обеспечивают в случае необходимости инверсию сигналов на информационных входах соответствующих D-триггеров 1. Ключевые входы 10.1, 10.2, 10.3 и 10.4 обеспечивают подключение выходов требуемых триггеров 1 ко входам элемента 6 ИЛИ-НЕ.
На фиг.2-6 показаны эквивалентные схемы генератора в различных режимах. На фиг.2 показаны триггера 1.1, 1.2, 1.3, 1.4, сумматоры 2.2, 2.3, 2.4 по модулю два. На фиг.3 показаны триггера 1.1, 1.2, 1.3, 1.4, сумматор 2.2 по модулю два. На фиг.4 показаны триггера 1.1, 1.2, 1.3, 1.4, сумматоры 2.2, 2.3 по модулю два, элемент 11 НЕ. На фиг.5 показаны триггера 1.1, 1.2, 1.3, 1.4, сумматоры 2.2, 2.4 по модулю два, элемент 11 НЕ. На фиг.6 показаны триггера 1.1, 1.2, 1.3, 1.4, сумматор 2.2 по модулю два, элемент 6 ИЛИ-НЕ.
На фиг.7 показана базовая идея технологии Logic Encryption. На фиг.7 показаны защищаемое цифровое устройство 12 (в рассматриваемом случае - это ГПСЧ), 13 и 14 - соответственно входы и выходы защищаемого устройства, схема 15 преобразования ключей, первичные ключевые входы 16, преобразованные ключевые входы 17 устройства.
В состав генератора в общем случае входят N D-триггеров 1.1, 1.2,…, 1.N; N сумматоров 2.1, 2.2,…, 2.N по модулю два; первая группа из (N-1) элементов И 3.1, 3.2,…, 3.(N-1); вторая группа из N элементов И 4.1, 4.2,…, 4.N; третья группа из N элементов И 5.1, 5.2,…, 5.N; элемент 6 ИЛИ-НЕ. Генератор имеет первую группу из (N-1) ключевых входов 7.1, 7.2,…, 7.(N-1); вторую группу из N ключевых входов 8.1, 8.2,…, 8.N; третью группу из N ключевых входов 9.1, 9.2,…, 9.N; четвертую группу из N ключевых входов 10.1, 10.2,…, 10.N. Выходы i-x D-триггеров 1.i, где i=1, 2,…, (Ν-1), соединены с первыми входами (i+1)-х сумматоров 2.(i+1) по модулю два. Выходы j-x сумматоров 2.j по модулю два соединены с информационными входами j-x D-триггеров 1.j, где j=1, 2,…, N. Выход N-го D-триггера 1.N соединен с первыми входами всех элементов И 3.1, 3.2, 3.3 первой группы и первым входом первого сумматора 2.1 по модулю два. Вторые входы элементов И 3.1, 3.2, 3.3 первой группы образуют первую группу из (N-1) ключевых входов 7.1, 7.2, 7.3 генератора. Выходы i-x элементов И 3.i первой группы соединены со вторыми входами (i+1)-х сумматоров 2.(i+1) по модулю два. Выход элемента 6 ИЛИ-НЕ подключен к первым входам всех элементов И 4.1, 4.2,… 4.N второй группы, вторые входы которых образуют вторую группу из N ключевых входов 8.1, 8.2,…, 8.N генератора. Выход первого элемента И 4.1 второй группы соединен со вторым входом первого сумматора 2.1 по модулю два. Третьи входы сумматоров 2.1, 2.2,…, 2.N по модулю два образуют третью группу из N ключевых входов 9.1, 9.2,…, 9.N генератора. Выходы (i+1)-х элементов 4.(i+1) И второй группы соединены с четвертыми входами (i+1)-х сумматоров 2.(i+1) по модулю два. Выходы j-x D-триггеров 1.j подключены к первым входам j-x элементов И третьей группы 5.1, 5.2,…, 5.N; вторые входы которых образуют четвертую группу из N ключевых входов 10.1, 10.2,…, 10.N генератора, а выходы подключены ко входом элемента 6 ИЛИ-НЕ.
На фиг.2 показаны эквивалентная схема устройства и его диаграмма переключений при значениях сигналов на ключевых входах
где X - произвольное значение. При данных значениях сигналов на ключевых входах, характеристический многочлен генератора имеет вид Ф(х)=x4+x3+x3+x+1 - неприводимый над GF(2). Диаграмма переключений устройства имеет вид 5-5-5-1, иначе говоря, состоит из трех циклов длиной 5 и одного цикла длиной 1, включающего состояние "все нули", переходящее само в себя.
На фиг.3 показана эквивалентная схема устройства при значениях сигналов на ключевых входах
При данных значениях сигналов на ключевых входах, характеристический многочлен генератора имеет вид Ф(х)=x4+x+1 - примитивный над GF(2). Диаграмма переключений устройства имеет вид 15-1, иначе говоря, состоит из двух циклов: длиной 15, включающего все ненулевые состояния генератора и длиной 1, включающего состояние "все нули", переходящее само в себя. С выхода одного из триггеров 1 в этом случае снимается М-последовательность длиной 15, с выходов оставшихся триггеров снимаются сдвинутые копии той же последовательности. В этом режиме в качестве исходного состояния элементов памяти используется любое ненулевое состояние генератора.
На фиг.4 показана эквивалентная схема устройства при значениях сигналов на ключевых входах
При данных значениях сигналов на ключевых входах, характеристический многочлен генератора имеет вид
Ф(х)=(х+1)(х3+х2+1)=x4+x2+x+1,
где многочлен x3+x2+1 - примитивный над GF(2). Диаграмма переключений устройства имеет вид 14-2, иначе говоря, состоит из двух циклов: длиной 14 и длиной 2. При этом при правильной работе генератора значение свертки по модулю два содержимого элементов памяти в каждом следующем такте меняет свое значение. С выхода одного из триггеров 1 в этом случае снимается (М-1)-последовательность длиной 14. В этом режиме в качестве исходного состояния элементов памяти используется любое состояние цикла длиной 14.
На фиг.5 показана эквивалентная схема устройства при значениях сигналов на ключевых входах
При данных значениях сигналов на ключевых входах, характеристический многочлен генератора имеет вид
Ф(х)=(x+1)2(x2+х+1)=х4+х3+х+1,
где многочлен x2+x+1 - примитивный над GF(2). Диаграмма переключений устройства имеет вид 12-4, иначе говоря, состоит из двух циклов: длиной 12 и длиной 4. При этом при правильной работе генератора значение свертки по модулю два содержимого элементов памяти в каждом следующем такте меняет свое значение. С выхода одного из триггеров 1 в этом случае снимается (М-3)-последовательность длиной 12. В этом режиме в качестве исходного состояния элементов памяти используется любое состояние цикла длиной 12.
На фиг.6 показана эквивалентная схема устройства при значениях сигналов на ключевых входах
Диаграмма переключений устройства состоит из единственного цикла длиной 16. Как только генератор оказывается в состоянии 1000, на выходе элемента 6 ИЛИ-НЕ формируется сигнал логической 1, который "нейтрализует" сигнал логической 1 с выхода триггера 1.1. В результате устройство переключится в ранее запрещенное состояние 0000. Сигнал на выходе элемента 6 ИЛИ-НЕ по-прежнему равен 1, что приводит к переключению устройства в состояние 0100, т.е. возврату в основной цикл. С выхода одного из триггеров 1 в этом случае снимается (М+1)-последовательность длиной 16. В этом режиме исходное состояние элементов памяти может быть любым.
Возможность достижения заявленного технического результата изобретения обуславливаются тем, что функциональные возможности устройства скрываются от неавторизованных лиц за счет ввода в схему генератора дополнительных элементов и ключевых входов, при этом значения сигналов на ключевых входов принципиально меняют логику работы устройства, что обеспечивает защиту от реверс-инжинирига.
Таким образом, технический результат от использования изобретения заключается в повышении защищенности генератора псевдослучайных чисел.
Рассмотрим базовую идею технологии Logic Encryption (фиг 7a). Шифрование логической схемы цифрового устройства 12 дает возможность использовать дополнительные логические элементы в структуре ИС, чтобы скрыть ее оригинальные функциональные возможности. Иначе говоря, это попытка максимально усложнить понимание логики работы защищаемой схемы для неавторизованных лиц. Шифрование логической схемы (по сути ее обфускация) меняет конструкцию ИС таким образом, что она работает правильно, только в том случае, если сигналы на дополнительных ключевых входах 16 устройства принимают правильные значения. Схема обфускации предполагает использование дополнительной схемы 15 преобразования ключей, реализованной на основе блока памяти с защитой от НСД. Этот блок памяти устанавливается или активируется на заключительном этапе создания ИС перед ее продажей конечному потребителю.
Изобретение реализует эту идею для случая, когда защищаемое устройство - это генератор псевдослучайных чисел (PRNG) на основе генератора Галуа (фиг.7b). В зависимости от значений на преобразованных ключевых входах 17 устройство реализует одну из возможных диаграмм переключений, в том числе работая либо в режиме генерации М-последовательностей (фиг.3), либо в режиме генерации (М-1)-последовательностей (фиг.4), либо в режиме генерации (М-3)-последовательностей (фиг.5), либо в режиме генерации (М+1)-последовательностей (фиг.6). Ключевые входы первой группы обеспечивают задание произвольного характеристического многочлена, ключевые входы второй группы обеспечивают в случае необходимости подключение выхода элемента ИЛИ-НЕ ко входам соответствующих сумматоров по модулю два, ключевые входы третьей группы обеспечивают в случае необходимости инверсию сигналов на выходах сумматоров по модулю два, ключевые входы четвертой группы обеспечивают в случае необходимости подключение выходов соответствующих D-триггеров ко входам элемента ИЛИ-НЕ.
Генератор псевдослучайных чисел, состоящий из N D-триггеров, N сумматоров по модулю два, первой группы из (N-1) элементов И, где N - степень характеристического двоичного многочлена, выходы i-x D-триггеров, где i=1, 2,…, (N-1), соединены с первыми входами (i+1)-х сумматоров по модулю два, выходы j-x сумматоров по модулю два соединены с информационными входами j-x D-триггеров, где j=1, 2,…, N, выход N-го D-триггера соединен с первыми входами всех элементов И первой группы и первым входом первого сумматора по модулю два, вторые входы элементов И первой группы образуют первую группу из (N-1) ключевых входов генератора, выходы i-x элементов И первой группы соединены со вторыми входами (i+1)-х сумматоров по модулю два, отличающийся тем, что он дополнительно содержит вторую и третью группы из N элементов И и элемент ИЛИ-НЕ, выход которого подключен к первым входам всех элементов И второй группы, вторые входы которых образуют вторую группу из N ключевых входов генератора, выход первого элемента И второй группы соединен со вторым входом первого сумматора по модулю два, третьи входы сумматоров по модулю два образуют третью группу из N ключевых входов генератора, выходы (i+1)-х элементов И второй группы соединены с четвертыми входами (i+1)-х сумматоров по модулю два, выходы j-x D-триггеров подключены к первым входам j-x элементов И третьей группы, вторые входы которых образуют четвертую группу из N ключевых входов генератора, а выходы подключены ко входом элемента ИЛИ-НЕ.
