Разработка блока вычисления индекса для системы нелинейного шифрования данных
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ный блок длиной v разрядов, поступает на вход преобразователя "индекс-элемент поля", где реализуется выражение
,(4.21)
где - первообразный элемент поля GF(2v), порождаемый неприводимым многочленом .
В результате данных преобразований получается открытое сообщение а(z), которое поступает к пользователю.
Известно, что процедуры выполнения мультипликативных арифметических операций по модулю требуют значительных временных затрат. Так, согласно чтобы вычислить степень , где m - элемент некоторого кольца, а n - натуральное число, достаточно выполнить не более умножений. Сократить время выполнения мультипликативных арифметических операций по модулю можно за счёт перехода к обработке индексов элементов полей Галуа.
Согласно существует примитивный элемент ?, такой, что все нулевые элементы поля могут быть представлены в виде степени элемента ?. Заменяя ? на полином z, можно получить полиномиальное представление элементов поля , где ?(z) - примитивный полином расширенного поля GF(pv); i=0,1, тАж, pv -2.
При этом логарифмы степенного представления образуют целочисленное представление индекса
i=ind ?= log? ? mod ?(z)(4.22)
Взаимное отображение множества элементов {ai} поля GF(pv) на множество их индексов {i=0,1, тАж, pv -2 } позволяет свести операции умножения и возведения в степень элементов GF(pv) к соответствующим операциям сложения и умножения по модулю g = pv -1.
Рассмотрим различные формы представления ненулевых элементов поля GF(24) с порождающим полиномом ?(x)=z4+z+1, приведены в таблице 4.3.
Таблица 4.3 - Формы представления элементов поля
ПолиномиальноеВекторноеИндексное10001?0z0010?1z20100?2z31000?3z+10011?4z2+z0110?5z3+z21100?6z3+z+11011?7z2+10101?8z3+z1010?9z2+z+10111?10z3+z2+z1110?11z3+z2+z+11111?12z3+z2+11101?13z3+11001?14
Рассмотрим процедуру зашифрования потока данных с помощью операции возведения в степень по модулю ?(x)=z4+z+1. Пусть имеем последовательность бит открытого текста а=101000111100тАж Данная последовательность разбивается на блоки по 4 бит в каждом и представляем их в полиномиальной форме. Получаем
a1(z)=1010=z3+z.
a2(z)=0011=z+1.
a3(z)=1100=z3+z2.
Ключевая последовательность снимается с различных выходов генератора ПСП и имеет следующий вид k=001011010111тАж Данная последовательность разбивается на блоки по 4 бит в каждом. Получаем
1(z)=0010=210.
k2(z)=1101=1310.
k3(z)=0111=710.
Определим значение первого блока зашифрованных данных, согласно (4.12)
?1(z)=(1010)2 mod z4+z+1=(z3+z)2 mod z4+z+1=(z6+z2) mod z4+z+1=z3.
Определим значение второго блока зашифрованных данных
?2(z)=(0011)13 mod z4+z+1=(z+1)13 mod z4+z+1=
=(z12+z8+z4+1)(z+1) mod z4+z+1=z3+z+1
Определим значение третьего блока зашифрованных данных
?3(z)=(1100)7 mod z4+z+1=(z3+z2)7 mod z4+z+1=z3+z2+z+1.
Реализуем эти операции шифрования с помощью индексного представления. В этом случае имеем
a1(z)=1010=z3+z . индекс l1= 9.
a2(z)=0011=z+1. индекс l1= 4.3(z)=1100=z3+z2. индекс l1= 6.
Найдем произведения индексов и ключевых данных по модулю 15. Получаем значение
?1 = l1 k1 mod15=(9*2)mod 15 = 18 mod 15= 3.
?2 = l2 k2 mod15=(4*13)mod 15 = 52 mod 15= 7.
?3 = l3 k3 mod15=(6*7)mod 15 = 42 mod 15= 12.
Для определения значений блоков зашифрованных данных воспользуемся таблицей 4.3. Полученные значения индексов будут соответствовать элементам расширенного поля Галуа
?1(z)=z3;
?2(z)=z3+z+1;
?3(z)=z3+z2+z+1.
Применение индексного представления позволило получить одинаковые результаты. Произведем разработку устройства, осуществляющего преобразование "элемент поля Галуа - индекс".
4.3 Разработка блока вычисления индекса
Для сокращения временных затрат реализации выражения (4.12) было разработано устройство для вычисления индекса по значению элемента поля Галуа. Для этого воспользуемся данными приведенными в таблице 4.3 соответствия между векторным и индексным представлением. Составим таблицы истинности, с помощью которых осуществим разработку комбинационных устройств. Так как степень порождающего полинома равна четырем, то таких таблиц необходимо - четыре. Затем по данным таблицам составляются совершенная конъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма. Для проведения минимизации схемных решений воспользуемся картами Карно. После этого определяются минимальная конъюнктивная нормальная форма и минимальная дизъюнктивная нормальная форма. Затем осуществляется перевод в соответствующий в монобазис. После осуществления такой операции производится построение комбинационной схемы. В таблице 4.4 приведено соответствие между элементами расширенного поля Галуа GF(24) и индексным представлением.
Таблица 4.4 - Соответствие элемент поля Галуа - индекс
ЭлементИндексЭлементИндекс000100000101100000100001101010010100001001111010100000111110101100110100111111000110010111011101110001101001111010110111
Таблица истинности для старшего разряда индекса показана ниже.
Таблица 4.5 - Таблица истинности i(3)=f(A,B,C,D)
№ набораА (a3)B(a2)C(a1)D(a0)i3100010200100300110401000501011601100701111810000910011101010111101101211000131101114111011511111
В качестве аргументов таблицы истинности выступают разряды элемента расширенного поля Галуа. Для удобства их обозначили переменными A, B, C, D. Составим две карты Карно для получения двух минимальных форм.
Рисунок 4.2 - Карта Карно
МДНФ i(3) =
Рисунок 4.3 - Карта Карно
МКНФ i(3) =
Представим таблицу истинности для комбинационной схемы, используемой для вычисления второго разряда индекса. Затем определим с помощью карт Карно выражения для минимальной конъюнктивной нормальной формы и