Высокопроизводительная схемотехническая реализация криптографического многоскоростного генератора скалярного произведения
Аннотация
Статья посвящена вопросам повышения производительности криптографических преобразований шифраторами поточных шифров, выполненных на основе генератора скалярного произведения. Такие генераторы являются разновидностью генераторов гаммы с неравномерным движением рекуррентных регистров сдвига, позволяющих улучшить статистические свойства получаемой последовательности. Их недостатком является то, что для получения одного знака гаммы необходимо подать несколько тактовых импульсов. В статье, на основе алгоритма переопределения функции обратной связи рекуррентного регистра сдвига, построена и описана схема генератора скалярного произведения, позволяющая за один такт вырабатывать один знак гаммы.
Ключевые слова: параллельные логические вычисления, криптографические преобразования, линейный рекуррентный регистр сдвига, поточные шифры, генераторы гаммы с неравномерным движением, генератор скалярного произведения
05.13.19 - Методы и системы защиты информации, информационня безопасность
Введение
Эффективным способом защиты информации, передаваемой по линиям связи всех типов, является шифрование передаваемых сообщений [1, 2]. Линейные рекуррентные регистры сдвига (ЛРРС) являются базовыми блоками для построения многих генераторов гаммы, однако сами по себе имеют достаточно низкую криптографическую стойкость. [1-3]. Одним из способов достижения нелинейной зависимости знаков гаммы от ключевых элементов генератора, является неравномерное движение информации в определенных узлах генератора, определяемое ключом [2, 3]. Изменение закона движения приводит к изменению исходной гаммы, увеличивая ее сложность. Необходимость сдвига регистров на разное количество шагов приводит к тому, что увеличивается количество тактов синхронизирующего генератора, необходимое для получения одного элемента гаммы. В данной статье, с использованием алгоритма параллельной реализации линейного рекуррентного регистра сдвига за счет переопределения булевой функции обратной связи, дающего возможность получать состояние рекуррентного регистра сдвига через произвольное количество тактов функционирования, приводится пример реализации одного из генераторов гаммы с неравномерным движением – генератора скалярного произведения.
1. Понятие генератора скалярного произведения
В генераторе скалярного произведения (рис. 1) используется два ЛРРС с разными тактовыми частотами и, возможно, разной длины [3]. ЛРРС 1 имеет длину n(1) и показатель скорости d(1), ЛРРС 2 соответственно – n(2) и d(2). Ключом является начальное состояние ЛРРС – X0(1) и X0(2). Отдельные биты этих ЛРРС объединены операцией логического умножения (AND), а затем, для получения выходного бита они объединяются посредством сумматора по модулю два, т. е. вычисление каждого i-ого бита гаммы осуществляется по алгоритму:
1. Сдвинуть ЛРРС 1 на d(1) шагов.
2. Сдвинуть ЛРРС 2 на d(2) шага.
3. Вычислить знак гаммы: yi= 
=xk(1)&xk(2).
Рис. 1. Генератор скалярного произведения
2. Сдвиг рекуррентного регистра сдвига на произвольное количество шагов за один такт функционирования
Рекуррентный регистр сдвига с обратными связями состоит из регистра сдвига и схемы, реализующей функцию обратной связи. К простейшему типу устройств данного класса относится рекуррентный регистр с линейной обратной связью (рис. 2, а). Функция обратной связи в таких регистрах задается операцией «сумма по модулю два» над некоторыми битами регистра. Номера этих битов определяются на основе полинома степени n [3]:
h(x)=xn+hn-1xn-1+hn-2xn-2+…+h2x2+h1x+h0,
где hi∈{0,1} – коэффициент связей.
Для обеспечения максимального периода псевдослучайной последовательности, генерируемой ЛРРС, образующий полином должен быть неприводимым и примитивным. На его основе строится линейное рекуррентное уравнение, которое при выполнении вычислений в 
имеет следующий вид [2]:
x(n-1)(t+1)=hn-1 xn-1&…+ h1 x1+ h0 x0. (1 )
Пример 1. ЛРРС, построенный на основе образующего полинома h(x)=x5+x2+1, показан на рис. 2, б.
Рис. 2 Линейный рекуррентный регистр сдвига (НУ – сигналы начальной установки, ОС – открытое сообщение, ЗС – зашифрованное
сообщение, а – разряды ЛРРС)
Для увеличения производительности возможно произвести переопределение булевой функции, описывающей функционирование ЛРРС, таким образом, чтобы за один такт функционирования получить несколько значений последовательности. Исходными данными для построения такой схемы будут: длина ЛРРС – n; начальное состояние ЛРРС – X=(xn-1,…, x1, x0); линейное рекуррентное уравнение f(X, H), построенное по образующему полиному h(x); количество моделируемых шагов работы – d.
Необходимо найти такую систему булевых функций F(X), задающую обратные связи при приведении ЛРРС к виду (рис. 3), позволяющему за один такт сдвинуть ЛРРС на d шагов.
Рис. 3 Приведение ЛРРС к параллельному виду
Каждое последующее состояние ЛРРС можно выразить через предыдущее. При этом значение самого старшего разряда вычисляется с помощью линейного рекуррентного уравнения (1), значения остальных разрядов вычисляются сдвигом вправо предыдущих значений ячеек РРС.
Зависимость состояния РРС Xt+1=[x(n-1)(t+1)… x0(t+1)] в определенный момент времени от предыдущего заполнения Xt=[x(n-1)t… x0t] можно задать системой логических выражений:
(2 )
где: t – предыдущее состояние ЛРРС, t+1 – последующее состояние РРС.
Вычисляя последовательно каждое последующее состояние РРС через предыдущее по системе логических выражений (2), можно построить зависимость состояния РРС через определенное число тактов функционирования Xt+d от начального заполнения X:
Каждое выражение, составляющее систему, является линейным полиномом Жегалкина. Каждое выражение будет полностью задано, если определены коэффициенты при переменных. Для формализации алгоритма определения выражений, описывающих состояние ЛРРС в определенный момент времени, коэффициенты при логических переменных удобно представить в виде матрицы, в которой строки будут соответствовать состоянию РРС в определенный момент времени, а столбцы — соответствовать начальному состоянию РРС:
,
где wij ∈{0,1}.
В начальный момент времени матрица коэффициентов будет иметь вид:
.
Для нахождения коэффициентов в следующий момент времени необходимо умножить матрицу на вектор коэффициентов линейного рекуррентного уравнения:
Wt+1=Wt×H, (3 )
полученный вектор подставить в первую строку матрицы, а остальные строки сдвинуть на одну вниз.
3. Демонстрационный пример реализации генератора скалярного произведения
Исходные данные:
Для ЛРРС 1 – n(1)=4, x(1)3(t+1)=x(1)1t+x(1)0t, d(1)=2.
Для ЛРРС 2 – n(2)=3, x(2)2(t+1)=x(2)2t+x(2)0t, d(1)=1.
Для ЛРРС 1 найдем функцию обратной связи, осуществляющую сдвиг на 2 шага за один такт функционирования.
(4 )
Схемотехническая реализация данного примера показана на (рис. 4).
Рис. 4. Модель генератора скалярного произведения
Описание схемы. ЛРРС 1 собран на триггерах D-триггерах DD3-DD6, функция обратной связи (4) реализована на элементах DD1, DD2. ЛРРС 2 собран на триггерах DD11-DD13 и сумматоре по модулю два DD10. Побитная конъюнкция соответствующих разрядов ЛРРС 1 и ЛРРС 2 осуществляется элементами DD7-DD9, DD14 – результирующий сумматор по модулю два.
Первые девять значений гаммы при начальном заполнении 1000 и 100 для ЛРРС 1 и ЛРРС 2 соответственно показаны в табл. 1. В таблице невыделенными остались строки, в которых записаны пропускаемые состояния ЛРРС 1. Запустив схему на выполнение, получаем гамму на выходе генератора скалярного произведения, соответствующую теоретическим вычислениям, причем каждый знак гаммы получает за один такт функционирования.
Таблица 1
Смена состояний генератора скалярного произведения
|
N такт |
x3(1) |
x2(1) |
x1(1) |
x0(1) |
|
x2(2) |
x1(2) |
x0(2) |
|
Г |
|
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
|
0 |
|
|
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
0 |
|
1 |
1 |
0 |
|
1 |
|
|
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
2 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
|
1 |
|
|
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
3 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
|
0 |
|
|
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
4 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
|
0 |
|
|
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
5 |
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
|
1 |
|
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
6 |
0 |
1 |
1 |
1 |
|
0 |
0 |
1 |
|
1 |
|
|
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
7 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
|
0 |
|
|
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
8 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
|
1 |
|
|
0 |
0 |
1 |
0 |
|
|
|
|
|
|
|
9 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
|
1 |
Таким образом, при незначительном усложнении схемы (в данном примере на один двухвходовый сумматор по модулю два) получили схемотехническую реализацию генератора скалярного произведения, в котором для получения знака гаммы необходим всего один такт функционирования вместо двух при классическом способе реализации. Описанный алгоритм переопределения функции обратной связи ЛРРС может использоваться для построения схем более сложных генераторов гаммы скалярного произведения при произвольных значениях длин регистров n(1) и n(2) и показателях скоростей d(1) и d(2).
Литература:
1.Основы криптографии: Учебное пособие/ Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. — М.: Гелиос АРВ, 2001. — 480 с.
2. Фомичев В. М. Дискретная математика и криптология: Курс лекций/ Под общ ред. Н. Д. Подуфалова. — М.: Диалог-МИФИ, 2003. — 400 с.
3.Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: Издательство ТРИУМФ, 2003. – 816 с.