Разработка блока вычисления индекса для системы нелинейного шифрования данных
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
им уровнем криптографической защиты.
Реализовать выражение (4.4) можно на основе использования умножителя по модулю p, однако время данной операции будет равно
, (4.6)
где -время выполнения модульного умножения.
Сократить время выполнения операции можно за счет использования индексов. В работе [6] показана возможность использования теории индексов для эффективной реализации операций мультипликативного типа (умножение, деление, возведение в степень). Число , являющееся решением сравнения
, (4.7)
называется индексом числа A и обозначается . Первообразный корень g называется основанием индекса.
В этой работе доказана теорема, согласно которой индекс J произведения простых целых чисел А1 , А2 ,тАж, Аk по модулю р равен сумме индексов сомножителей, взятой по модулю р -1, т.е.
,(4.8)
где i1 ,i2 ,тАж, ik - индексы положительных чисел A1 ,A2 ,тАж,Ak по модулю р при первообразном коде g.
Таким образом, очевидна возможность сведения операции умножения двух операндов А и В по модулю р к операции суммирования индексов iA, i B этих операндов при первообразном корне g по модулю р -1.
Аналогично можно доказать, что операцию возведения в степень (4.4) можно свести к операции индексов по модулю p -1.
Из изложенного следует, что для нахождения индекса какого-либо числа A по модулю p надо найти первообразный корень числа p, а затем найти решение сравнения (4.7) для данного первообразного корня. Следует отметить, что данная операция сравнима по сложности с процедурой вычисления дискретного логарифма в конечном поле.
Аналогичная ситуация возникает и в расширенных полях Галуа . Так как все элементы такого поля получаются с помощью порождающего полинома р(z), то в качестве первообразного корня можно выбрать z. Тогда любой элемент A(z) поля можно представить в виде
.(4.9)
Следовательно, справедливо
.(4.10)
При этом
. (4.11)
Так как значение показателя ? задано, то для реализации выражения необходимо определить значение индекса по модулю полинома p(z) из выражения. Рассмотрим расширенное поле Галуа GF(23). В данном поле определен порождающий полином p(z)=z3+z+1, который задает следующие элементы поля, различные формы которых приведены в таблице 4.1.
Таблица 4.1 - Представление элементов поля Галуа
Представление элементов поля Галуа GF(23)СтепенноеВекторноеПолиномиальное0011010z100z2011z+1110z2+z111z2+z+1101z2+1
Очевидно, что показатели степеней элементов поля крутятся по модулю .
Степенное или индексное представления ненулевых элементов удобны для выполнения мультипликативных операций и им обратных. Реализация данных операций приведена в таблице 4.2.
Таблица 4.2 - Степенное выполнение операций
ОперацияСтепенное представлениеУмножениеДелениеВозведение в степень хДискретный логарифм
Таким образом, очевидно, что переход к индексному представлению ненулевых расширенного поля Галуа GF(q) позволяет свести низкоскоростную операцию возведения в степень к операции умножения степеней первообразного элемента по модулю
Разработаем структуру шифратора, реализующего процедуру нелинейного шифрования на основе операции возведения в степень по модулю полинома с использованием индексного представления.
Такой шифратор должен содержать следующие блоки:
устройство для осуществления преобразования "элемент поля - индекс";
умножитель по модулю ;
устройство для осуществления преобразования "индекс - элемент поля".
Структура такого нелинейного шифратора показана на рисунке 4.1.
Рисунок 4.1 - Структура нелинейного шифратора
Приведенная на рисунке 4.1 структурная схема устройства реализует нелинейное шифрование потока данных с операцией возведения в степень элементов конечного поля Галуа GF(2v) согласно
. (4.12)
Последовательность исходного текста разбивается на блоки {а} длиной v разрядов и считается элементом поля Галуа в полиномиальной форме
Затем он поступает на вход устройства вычисления индекса по модулю. Данное устройство реализует следующую процедуру
(4.13)
где z первообразный элемент поля Галуа; - показатель степени элемента поля.
Полученное значение показателя степени l подается на первый вход умножителя по модулю 2v-1. На второй вход поступает ключ k, представляющий блок двоичных символов длиной v бит
(4.14)
На выходе умножителя получается результат
,(4.15)
который поступает на вход преобразователя "индекс-элемент поля". С выхода последнего снимается зашифрованное сообщение, согласно
(4.16)
Обратная процедура выполняется согласно выражения
.(4.17)
Зашифрованное сообщение в виде блока длиной v двоичных разрядов поступает на вход устройства вычисления индекса элемента поля GF(2v). С выхода последнего снимается
.(4.18)
Для определения значения степени l необходимо
,(4.19)
где - обратный мультипликативный элемент элементу k по модулю (2v -1).
Поэтому ключ k длиной v разрядов подается на вход устройства вычисления мультипликативного обратного элемента по модулю (2v -1), с выхода которого снимается значение
.(4.20)
Значения и в двоичном коде поступают на вход умножителя по модулю (2v -1), с выхода которого снимается значение
.
Данный результат, представляющий собой двоич