Проблема оптимизации шифрования информации

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

А. А. Набебин
Проблема оптимизации шифрования информации
Аннотация: описаны линейные регистры сдвига с обратной связью (ЛРСОС). Методами абстрактной алгебры (поля Галуа) дано их математическое описание. Предложен алгоритм шифрования информации с помощью рекуррентных последовательностей, вырабатываемых с помощью ЛРСОС.
Ключевые слова: линейный регистр сдвига с обратной связью, поле Галуа, неприводимый полином, примитивный полином, рекуррентная последовательность, шифрование.
Регистры сдвига с обратной связью широко используются в потоковых шифровальных схемах. Мы рассмотрим наиболее часто используемые в практике линейные регистры сдвига с обратной связью (ЛРСОС). Основной задачей при проектировании ЛРСОС является задача построения примитивного полинома из Zp[x] над Zp, то есть полинома в поле Галуа GF (p) с коэффициентами из Zp =
{0,1,2,_, p-1} со сложением и умножением чисел из Zp по модулю
простого числа p.
Определение. Полином f (x) из Zp[x] неприводим над Zp, если f (x) не может быть представлен как произведение двух полиномов положительной степени из Zp[x].
Утверждение. Для всякого целого m & gt- 1 существует нормированный неприводимый полином степени m из Zp[x].
Алгоритм тестирования полинома из Zp[x] на неприводимость
ВХОД. Простое число p и нормированный полином f (x) степени m из Zp[x].
ВЫХОД. Ответ на вопрос: «Является ли полиномf (x) неприводимым над Zp?».
1. u (x) := x.
2. Для і от 1 до [ml 2] выполнить следующее.
2.1. u (x) := u (x)p (modf (x)) — d (x) := нодf (x), u (x)-x).
2.2. Если d (x) ф 1, то вернуть «приводимый».
3. Вернуть"неприводимый".
Определение. Неприводимый полином f (x) из Zp[x] есть примитивный полином, если x есть генератор для мультипликативной группы Z рт всех ненулевых элементов конечного поля F м = Zp[x]/(f (x)).
Утверждение. Для всякого целого m & gt- 1 существует нормированный примитивный полином степени m над Zp.
Алгоритм тестирования полинома из Zp[x] на примитивность
ВХОД. Простое число р- целое m & gt- 1- все различные простые делители rl, r2, …, rt числа pm1- нормированный неприводимый полиномf (x) степени m из Zp[x].
ВЫХОД. Ответ на вопрос: «Примитивен ли полином f (x)?»
1. Для і от 1 до t выполнить следующее.
1.1. l (x) := х (рР-1)/^ (mod f (x)).
1.2. Если (x) ф 1, то вернуть «не примитивный».
2. Вернуть «примитивный».
Набебин Алексей Александрович, кандидат физико-математических наук, доцент кафедры программного обеспечения вычислительной техники РГСУ.
Базовое образование: факультет вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова.
Основные публикации: «Сборник заданий по дискретной математике» (2009), «Дискретная математика» (2010).
Сфера научных интересов: математическая логика, теория алгоритмов, теория конечных автоматов, дискретная математика, высшая математика.
Линейный регистр сдвига с обратной связью
Пусть/(х) = хт + ат1 х™'-1 + а т2хт2 + … + а1х + ад = 0 уравнение, где/(х) есть нормированный примитивный полином из Ъ [х] степени т & gt- 1. Тогда
хт = а, хт-1 а, X т-2 … а, х-ап. (1)
т-1 т-2 10 '- & gt-
Последовательность зд, з1, 5^… элементов поля Ър, удовлетворяющая соотношению
5 = а, 5, а, 5, … аз, аз, п = 0,1,. (2)
п+т т-1 п+т-1 т-2 п+т-2 1 п+1 и п '- '- '- & gt-
называется однородной линейной рекуррентной последовательностью (ОЛРП) порядка т над полем Ър. Полином/(х) называется характеристическим полиномом для ОЛРП зд, з1, з2,… Соотношение (2) называется однородным линейным рекуррентным соотношением порядка т над полем Ър. Первые члены зд, з1,…, 5т1 однозначно определяют всю последовательность и называются ее начальными значениями.
ОЛРП можно получать с помощью ЛРСОС. Это электронные преобразователи, перерабатывающие информацию, заданную с помощью элементов поля Ър. Линейные регистры сдвига строятся с помощью конструктивных элементов трех типов. Это сумматоры, усилители, задержки (триггеры) (рис. 1).
Рис. 1 Сумматор
Усилитель
Задержка
ЛРСОС, вырабатывающий последовательность ОЛРП, удовлетворяющую соотношению (2), изображен на рис. 2.
Рис. 2
Длина ЛРСОС есть степень т полинома/(х). В начале работы каждый элемент задержки й., 7=0,1,…, т- 1, содержит некоторое начальное заполнение з. На следующем такте работы каждый элемент задержки содержит заполнение $. +г Поэтому выход регистра сдвига с обратной связью есть последовательность элементов з1, з2,… Всякая выходная последовательность регистра сдвига является (чисто) периоди-
ческой. Начальное заполнение $ 0=0, $ 1=0,., $т-2=0, $т-1=1 называется импульсом. ОЛРП, порожденная импульсом, называется импульсной последовательностью. Если характеристический полином /(х) для ОЛРП примитивен, то минимальный период ОЛРП имеет наибольшую длину и равен рт1. Для приложений особый интерес представляют рекуррентные последовательности, имеющие (очень) большой минимальный период. Последовательности, вырабатываемые ЛРСОС, близки к случайным. ОЛРП используются в потоковых шифрах. Ключом шифра является примитивный полином с достаточно большим значением рт1, обеспечивающий получение импульсной последовательности с большим минимальным периодом.
Пример. Полином /(х) = х3 + 173×2 + 211х + 183 из Ър[х], р=257, т=3, примитивен. Полиному /(х) соответствует импульсная последовательность 5, 7 = 0,1,. с минимальным периодом рт-1 = 2573−1 = 16 974 592.
Шифрование. Пусть k=3. Пусть «Send $ 100 to him» есть шифруемый текст t- v = (83 101 110 100 32 36 49 48 48 32 116 111 32 104 105 109) есть вектор (длины 16) кодов ASCII символов текста t- 5 = (84 163 154 179 1 182 53 48 149 142 232 38 214 141 85 164) есть вектор длины 16 импульсной последовательности между позициями 3 и 18 (табл. 1) — шифротекст есть вектор c = v+5 (mod p) = (167 7 7 22 33 218 102 96 197 174 91 149 246 245 190 16).
Таблица 1
і 0 1 2 3 4 5 6 7 8 9 10
5 і 0 0 1 84 163 154 179 1 182 53 48
і 11 12 13 14 15 16 17 18 19 20 21
5 і 149 142 232 38 214 141 85 164 107 206 181
Дешифрование. Вектор v = cs (mod p), откуда исходный текст есть t.
При аппаратной реализации ЛРСОС полиномы f (x) берутся из Zp[x] при p=2. Таков, например, используемый в качестве европейского стандарта для цифровых сотовых мобильных телефонов поточный шифр A5, который состоит из трех ЛРСОС длины 19, 22 и 23. Выходом является XOR трех ЛРСОС. Для аналогичных
целей используются также поточные шифры RC4, SEAL, другие шифры.
Литература:
1. Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988.
2. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. — 1996.

ПоказатьСвернуть
Заполнить форму текущей работой