Ключові слова: паралельні логічні обчислення, криптографічні перетворення, лінійний рекурентний регістр зсуву, потокові шифри, генератори гами з нерівномірним рухом, генератор скалярного твори
Вступ
Ефективним способом захисту інформації, що передається по лініях зв'язку всіх типів, є шифрування переданих повідомлень [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) = x n + hn-1x n-1 + hn-2x n-2 + ... + h2x2 + h1x + h0,
де hi ∈ - коефіцієнт зв'язків.
Для забезпечення максимального періоду псевдослучайной послідовності, що генерується ЛРРС, який утворює поліном повинен бути не приводиться і примітивним. На його основі будується лінійне рекурентне співвідношення, яке при виконанні обчислень в має такий вигляд [2]:
x (n-1) (t + 1) = hn-1 x n-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 ∈.
У початковий момент часу матриця коефіцієнтів матиме вигляд:
.
Для знаходження коефіцієнтів в наступний момент часу необхідно помножити матрицю на вектор коефіцієнтів лінійного рекурентного рівняння:
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 (1) і n (2) і показниках швидкостей d (1) і d (2).
Високопродуктивна схемотехнічна реалізація криптографічного багатошвидкісного генератора скалярного твори
Завантажити цю статтю в форматі doc або pdf
Зроблено в СКНЦ ВШ ПФУ