ОТКАЗОУСТОЙЧИВЫЙ СПЕЦИАЛИЗИРОВАННЫЙ ВЫЧИСЛИТЕЛЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ

Область техники, к которой относится изобретение

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

Уровень техники

а) Описание аналога

Известно вычислительное устройство, содержащее шифраторы, выходы которых подключены ко входам устройств сравнения, выходы которых подключены ко входам устройства управления, выходы которого подключены к постоянным запоминающим устройствам (ПЗУ), предназначенным для хранения констант ортогональных базисов и общего модуля системы, выходы которых подключены ко входам умножителей, к которым также подключены выходы шифраторов, на входы которых поступают значения наименьших неотрицательных вычетов по системе попарно простых и упорядоченных модулей системы, значения первого из которых поступают на вход первого умножителя и входы устройств сравнения. Выходы умножителей и выход ПЗУ, предназначенного для хранения констант общего модуля системы, подключены ко входам сумматора по общему модулю, выход которого является шиной выдачи результата вычислений (Финько, О.А. Контроль и реконфигурация аналого-цифровых устройств, функционирующих в системе остаточных классов / О.А. Финько // Электронное моделирование. Том №22.4.2000. - С. 92-103).

Недостаток известного устройства - отсутствие функциональных возможностей обеспечения отказоустойчивости устройства при вычислении двоичных псевдослучайных последовательностей (ПСП), идентичных ПСП, получаемым посредством классических генераторов на линейных рекуррентных регистрах сдвига (ЛРРС).

б) Описание ближайшего аналога (прототипа)

Наиболее близким по сущности технического решения заявленному устройству является вычислительное устройство, включающее в себя регистр памяти, входы которого являются входами устройства, к которому подключена шина подачи булевых переменных, блок памяти, предназначенный для хранения коэффициентов линейного числового полинома (ЛЧП), ко входу которого подключена шина подачи коэффициентов ЛЧП, блок памяти, предназначенный для хранения оснований системы, ко входу которого подключена шина подачи оснований системы, выходы которого вместе с выходами блока памяти хранения коэффициентов ЛЧП подключены ко входам блоков вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы, выходы которых вместе с выходами регистра памяти подключены ко входам множителей, выходы которых подключены ко входам многоместных сумматоров, выходы которых подключены ко входам блока решения системы сравнений с одним неизвестным, выход которого подключен ко входам блока сравнения и блока оператора маскирования, выход блока сравнения подключен ко второму входу блока оператора маскирования, выходы которого являются выходами устройства выдачи значений булевых функций (БФ) (Патент РФ №2579991, публ. 10.04.2016).

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

Раскрытие изобретения

а) Технический результат, на достижение которого направлено изобретение

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

б) Совокупность существенных признаков

Поставленная цель достигается тем, что в отказоустойчивый специализированный вычислитель систем БФ, содержащий регистр памяти, входы которого являются входами устройства, к которому подключена шина подачи т булевых переменных, блок памяти, предназначенный для хранения коэффициентов ЛЧП, ко входу которого подключена шина подачи коэффициентов ЛЧП, блок памяти, предназначенный для хранения оснований системы, ко входу которого подключена шина подачи оснований системы, выходы которого вместе с выходами блока памяти хранения коэффициентов ЛЧП подключены ко входам блоков вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы, выходы которых вместе с выходами регистра памяти подключены ко входам множителей, выходы которых подключены ко входам многоместных сумматоров, оператор маскирования; дополнительно введены блок памяти, предназначенный для хранения модулей системы, блоки памяти, предназначенные для хранения ортогональных базисов, выходы которых вместе с выходами многоместных сумматоров являются входами множителей, выходы которых вместе с выходами блока памяти, предназначенного для хранения модулей системы, являются входами многоместного сумматора по модулю системы, выход которого подключен ко входам блока контроля и управления и блока оператора маскирования, первый выход блока контроля и управления подключен ко второму входу блока оператора маскирования, выходы которого являются выходами устройства выдачи значений т БФ, второй выход блока контроля и управления подключен к входам блоков памяти, предназначенным для хранения ортогональных базисов и блока памяти, предназначенного для хранения модулей системы.

Структурная схема предлагаемого устройства представлена на фиг. 1.

в) Причинно-следственная связь между признаками и техническим результатом Благодаря новой совокупности существенных признаков в устройстве реализована возможность:

- обнаружения возникающей ошибки;

- коррекции обнаруженной ошибки;

- восстановления достоверности функционирования посредством осуществления реконфигурации системы.

Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»

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

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

Краткое описание чертежей

Заявленное устройство поясняется чертежами, на которых показано:

фиг. 1 - отказоустойчивый специализированный вычислитель систем БФ;

фиг. 2 - общий вид ЛРРС;

фиг. 3 - общий вид ЛРРС (частный случай: образующий полином - трином).

Осуществление изобретения

Предлагаемое устройство предназначено для вычисления двоичных ПСП, идентичных ПСП, получаемым посредством классических генераторов на ЛРРС, с функцией обеспечения отказоустойчивости. Работа устройства основана на представлении систем рекурсивных характеристических уравнений ЛЧП.

Алгоритмы и устройства генерации ПСП, основанные на использовании рекуррентных логических выражений и неприводимых полиномов, наиболее простым по структуре из которых является ЛРРС (фиг. 2), считаются наиболее распространенными и проверенными практикой (Бабаш, А.В. Криптография / А.В. Бабаш, Г.П. Шанкин. - М.: СОЛОН-Р, 2002. - 575 с).

Структура ЛРРС определяется образующим многочленом:

где τ, t_i∈N а также полученным на его основе характеристическим уравнением:

где x_р, x_p+ti, c_j∈{0,1}; р∈N;

В терминах линейной алгебры очередной элемент ПСП x_p+τ выражения (1) вычисляется произведением (Песошин, В.А. Генераторы псевдослучайных и случайных чисел на регистрах сдвига: моногр. / В.А. Песошин, В.М. Кузнецов. - Казань: Казан. Гос. техн. ун-т, 2007. - 296 с.):

Для осуществления контроля ошибок вычислений в области цифровой схемотехники известны решения, основанные на использовании методов избыточного модулярного кодирования (Согомонян, Е.С. Самопроверяемые устройства и отказоустойчивые системы [Текст] / Е.С. Согомонян, Е.В. Слабаков. - М.: Радио и связь, 1989. - 208 с.). Для применения этих методов к генераторам ПСП необходимо предварительно решить задачу распараллеливания процесса вычислений ПСП.

Решение задачи основано на применении классических параллельных алгоритмов вычисления рекурсий (Ортега, Дж. Введение в параллельные и векторные методы решения линейных систем [Текст] / Дж. Ортега. - М.: Мир, 1991. - 365 с.).

В частности, ЛРРС длины τ реализующий данный метод, имеет т ячеек памяти, значения которых совместно образуют (начальное) состояние (x_q-1,0, …, x_q-1,t, …, x_q-1,τ-1). После первого такта работы ЛРРС выдаст x_q-1,0 и перейдет в состояние (x_q-1,1, …, x_q,0), где x_q,0=x_q-1,0⊕ x_q-1,t. Продолжая таким образом, ЛРРС генерирует ДСП. Общий вид данного ЛРРС представлен на фиг. 3.

Так, например, для характеристического уравнения:

где x_p+τ, x_p+t, xp∈{0,1}, соответствующего триному D(χ)=χ^τ+χ^t+1 (где τ - степень тринома; τ, t∈N; τ≥3; 1≤t≤τ-1).

Для рекурсии (2) построим систему характеристических уравнений (3):

Реализация системы (3) позволяет одновременно получить q-й блок ПСП, состоящий из τ элементов. Выразим правые части системы (3) через заданные начальные условия и представим ее как системубулевых функций (БФ)(4) от τ переменных:

где X_q-1=[x_q-1,0, …, x_q-1,τ-2 x_q-1,τ-1] - вектор начальных условий.

Используем правило представления БФ ƒ_j ЛЧП (Малюгин, В.Д. Параллельные логические вычисления посредством арифметических полиномов [Текст] / В.Д. Малюгин. - М.: Наука. Физматлит, 1997. - 190 с):

где результат вычисления БФ ƒ_j(x₁, …, х_n) соответствует значению младшего разряда двоичного представления результата вычисления L_j(x₁, …, х_n).

Получим систему ЛЧП:

Получим общий ЛЧП:

где h_j∈Z, или

Окончательный результат образуется путем реализации оператора маскирования .

Оператор маскирования служит для определения значения t-ой БФ представления U=(а_r … а_t … а₂а₁)₂ (запись (…)₂ означает запись в 2-ичной системе счисления), то есть (Шмерко, В.П. Теоремы Малюгина: новое понимание в логическом управлении, проектировании СБИС и структурах данных для новых технологий [Текст] / В.П. Шмерко // Автоматика и телемеханика. - 2004. - №6. - С. 104-112).

Таким образом, полученный ЛЧП (5) позволяет реализовать q-й блок ПСП длины τ. Значения полученного блока ПСП будут являться начальным заполнением для ЛЧП, реализующего следующий блок последовательности длиной равной τ.

Пример 1 Для 6-ти разрядного ЛРРС, структура которого определяется образующим триномом D(χ)=χ⁶+χ+1 и характеристическим уравнением x₆=х₀⊕x₁, система уравнений участка ПСП длины τ=6 примет вид:

Запишем систему характеристических уравнений, как систему БФ:

Получим систему ЛЧП:

Получим обший ЛЧП:

U=L(X_q-1)=1025x_q-1,0+1029x_q-1,1+20x_q-1,2++80х_q-1,3+320x_q-1,4+1280x_q-1,5.

Пусть x_qq-1,1=x_q-1,2=x_q-1,5=0, x_q-1,1=x_q-1,3=x_q-1,4, тогда

Таким образом, посредством одного ЛЧП получим q-блок ПСП длины τ=6 идентичной ПСП, получаемой посредством классического генератора на ЛРРС.

В модулярной арифметике (МА) целое неотрицательное число А может быть однозначно представлено набором остатков по основаниям МА р₁<р₂< … <р_η<p_η+1< … <р_κ.

где P_η=р₁р₂ … р_η>А; |⋅|_р - наименьший неотрицательный вычет числа «⋅» по модулю р; р₁<р₂< … <р_η<p_η+1< … <р_κ - попарно простые; j=1, 2, …, η, η+1, …, κ (Акушский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.).

При этом остатки МА α₁, α₂, …, α_η считаются информационными, a α_η+i, …, α_κ - контрольными (избыточными). Сама МА является в этом случае расширенной, где Р_κ=P_ηp_η+1 … р_κ, и охватывает полное множество состояний, представляемых всеми к вычетами. Эта область будет являться полным диапазоном МА [0,Р_κ) и состоять из рабочего диапазона [0,Р_η), где Р_η=р₁р₂ … р_η, определяемого неизбыточными основаниями МА, и диапазона, определяемого избыточными основаниями [P_η,P_κ), представляющего недопустимую область. Это означает, что операции над числом А выполняются в диапазоне [0,Р_κ). Поэтому, если результат операции МА выходит за пределы P_η, то делается вывод об ошибке вычислений. Полученные числа меньшие P_η будем называть правильными, равные или большие Р_η - неправильными (Акушский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.).

Для осуществления контроля ошибок арифметических вычислений при реализации ЛЧП (5) рассмотрим систему, заданную основаниями р₁, p₂, … , p_η, … , р_κ. Представим каждый коэффициент h_i ЛЧП (5) в виде (6), построим систему малоразмерных ЛЧП вида:

Малоразмерность ЛЧП системы (7) будет обеспечиваться малой величиной коэффициентов определяемых выбранными основаниями системы p₁, …, p_η, …, р_κ.

Подставив в (7) значения остатков системы по соответствующим основаниям для каждого коэффициента h_i ЛЧП (5), а также значения переменных x_q-1,0, …, x_q-1,τ-1 получим избыточный модулярный код (МК), представленный системой ЛЧП (7):

(u⁽¹⁾, u⁽²⁾, …, u^(η), …, u^(κ))_МК,

где u⁽¹⁾, u⁽²⁾, …, u^(η), …, u^(κ) - целые числа.

Решим систему выражений с одним неизвестным:

Так как основания р₁, p₂, … , p_η, … , р_κ попарно просты, то в соответствии с известными положениями теории чисел единственным решением системы (8) является выражение:

где

Вхождение результата вычисления (9) в рабочий диапазон (контрольное выражение):

означает отсутствие обнаруживаемых ошибок вычислений.

Пример 2 Пусть q-й блок участка ПСП представлен одним ЛЧП вида:

L(Х_q-1)=65x_q-1,0+69x _q-1,1+20x _q-1,2+80x _q-1,3.

Выберем основания системы: p₁=2, р₂=3, р₃=5, р₄=11, р₅=13, где р₅ - контрольное основание.

Рабочий и полный диапазоны системы в этом случае равны: Р₄=р₁р₂р₃р₄=330 и Р₅=Р₄р₅=4290 соответственно.

Представим каждый коэффициент ЛЧП в виде набора остатков по выбранным основаниям системы:

h₁=65=(1,2,0,10,0)_МA,

h₂=69=(1,0,4,3,4)_МA,

h₃=20=(0,2,0,9,7)_МA,

h₄=80=(0,2,0,3,2)_МA.

Построим систему (7):

Пусть x_q-1,0=x_q-1,1=x_q-1,3=1, x_q-1,2=0, тогда u⁽¹⁾=2, u⁽²⁾=4, u⁽³⁾=4, u⁽⁴⁾=16, и u⁽⁵⁾=6, получим избыточный МК: (2,4,4,16,6)_МК.

Решим систему (8):

в соответствии с (9) получим: U=214.

Так как результат вычисления U удовлетворяет 0≤U<330, то будем считать, что при вычислениях ошибка допущена не была, либо произошла необнаруживаемая ошибка.

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

После локализации неисправного оборудования, например, одного канала функционирования МА, операция реконфигурации выполняется вычислением из системы:

по «правильным» основаниям МА:

где - ошибочный остаток; B_i,j - ортогональные базисы; i,j=1, …, η,…, κ; i≠j; μ_i,j вычисляется из сравнения: Составляется табл. 1, содержащая значения ортогональных базисов и модулей системы для условий возникновения однократной ошибки по каждому основанию МА.

Пример 3 Допустим, что при вычислении решения системы (11) обнаружена ошибка, например, по основанию p₂. В соответствии с (12) вычислим U*, используя табл. 1. Получим:

Предлагаемое устройство содержит: шину 13 подачи значений τ булевых переменных x_q-1,0, x_q-1,1, …, x_q-1,τ-1, шину 14 подачи коэффициентов h₁, …, h_τ ЛЧП, шину 15 подачи оснований системы (информационные: p₁, …, p_η; контрольные: p_η+i,…,р_κ), регистр памяти 1, блок памяти 2 коэффициентов h₁, …, h_τ ЛЧП, блоки 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы, множители 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4η.τ, …, 4.κ.1, …, 4.κ.τ, блок памяти 5 оснований p₁, …, р_η, p_η+1, …, р_κ системы, многоместные сумматоры 6.1, …, 6.η, …, 6.κ, блоки памяти ортогональных базисов 7.1, …, 7.η, …, 7.κ, множители 8.1, …, 8.η, …, 8.κ, блок памяти модулей системы 9, многоместный сумматор по модулю системы 10, блок контроля и управления 11, блок оператора маскирования 12, выходы 16.1, …, 16.τ выдачи значений τ БФ ƒ_q,0(X_q-1), …, ƒ_q,τ-1(X_q-1) соответственно.

Шина 13 подачи значений τ булевых переменных x_q-1,0, x_q-1,1, …, x_q-1,τ-1 является входом регистра памяти 1, шина 14 подачи коэффициентов ЛЧП является входом блока памяти 2 коэффициентов h₁, …, h_τ ЛЧП, предназначенного для их хранения, шина 15 подачи оснований системы является входом блока памяти 5 оснований p₁, …, р_η, p_η+1, …, р_κ системы, предназначенного для их хранения, выходы блоков памяти 2 и 5 являются входами блоков 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по соответствующим основаниям системы, выходы которых вместе с выходами регистра памяти 1 являются входами множителей 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4η.τ, …, 4.κ.1, …, 4.κ.τ, выходы которых являются входами многоместных сумматоров 6.1, …, 6.η, …, 6.κ, выходы которых являются входами множители 8.1, …, 8.η, …, 8.κ, ко вторым входам которых присоединены выходы блоков памяти ортогональных базисов 7.1, …, 7.η, …, 7.κ, предназначенных для их хранения; выходы множителей 8.1, …, 8.η, …, 8.κ являются входами многоместного сумматора по модулю системы 10, ко второму входу которого присоединен выход блока памяти модулей системы 9, предназначенного для их хранения; выход многоместного сумматора по модулю системы 10 подключен к входам блока контроля и управления 11 и блока оператора маскирования 12, выход блока управления и контроля 11 является вторым входом блока оператора маскирования 12, выходы которого являются выходами устройства выдачи значений τ БФ ƒ_q,0(X_q-1), …, ƒ_q,τ-1(X_q-1) соответственно.

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

В исходном состоянии в блоки 2 и 5 памяти занесены по шинам 13 и 14 коэффициенты h₁, …, h_τ ЛЧП и основания p₁, …, р_η, p_η+1, …, р_κ системы соответственно, с их выходов на входы блоков 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы поступают коэффициенты ЛЧП (5) и основания системы. В момент времени, соответствующий началу преобразований, на входы регистра памяти 1 из шины 13 поступают значения булевых переменных x_q-1,0, x_q-1,1, …, x_q-1,τ-1. С выходов регистра памяти 1 и блоков 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы на входы множителей 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4η.τ, …, 4.κ.1, …, 4.κ.τ поступают наименьшие неотрицательные вычеты и значения булевых переменных x_q-1,0, x_q-1,1, …, x_q-1,τ-1. С выходов множителей 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4η.τ, …, 4.κ.1, …, 4.κ.τ на входы многоместных сумматоров 6.1, …, 6.η, …, 6.κ поступают произведения С выходов многоместных сумматоров 6.1, …, 6.η, …, 6.κ и блоков памяти ортогональных базисов 77.1, …, 7.η, …, 7.κ на входы множителей 8.1, …, 8.η, …, 8.κ поступают числовые результаты вычисления ЛЧП u⁽¹⁾, …, u^(η), …, u^(κ) и значения ортогональных базисов B_1,j,…, B_η,j, …, B_κ,j соответственно. С выходов множителей 8.1, …, 8.η, …, 8.κ, а также блока памяти модулей системы 9 на входы многоместного сумматора по модулю системы 10 поступают произведения u⁽¹⁾B_1,j, …, u^(η)B_η,j, …, u^(κ)B_κ,j и значение модуля системы Р_κ. Значения u⁽¹⁾, …, u^(η), …, u^(κ) являются избыточным МК, представленным системой ЛЧП (7): (u⁽¹⁾, u⁽²⁾, …, u^(η), …, u^(κ))_МК, где u⁽¹⁾, …, u^(η), …, u^(κ) - целые числа. С выхода многоместного сумматора по модулю системы 10 на входы блока управления и контроля 11 и блока оператора маскирования 12 поступает числовой результат вычисления (9). Вхождение результата вычисления (9) в рабочий диапазон (контрольное выражение): 0≤U≤Р_η означает отсутствие обнаруживаемых ошибок вычислений. Таким образом, при отсутствии ошибок вычислений с блока управления и контроля 11 на вход блока оператора маскирования 12 поступает сигнал, разрешающий выполнять операцию маскирования, в противном случае - запрещающий. С выхода блока оператора маскирования 12 получим значения БФ ƒ_q,0(X_q-1), …, ƒ_q,τ-1(X_q-1), которые соответствуют элементам q-то блока ПСП x_q-1,0, x_q-1,1, …, x_q-1,τ-1. В случае запрещающего сигнала (при обнаружении ошибки вычислений) выполняется локализация неисправного оборудования, с блока управления и контроля 11 на блоки памяти ортогональных базисов 7.1, …, 7.η, …, 7.κ и блок памяти модулей системы 9 поступает информация об используемых при повторных вычислениях ортогональных базисов и модулей системы. Вычисления выполняются согласно (9) и табл. 1.