12750

Криптоанализ потокового шифра на основе использования алгоритма Месси-Берлекэмпа

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 9 Криптоанализ потокового шифра на основе использования алгоритма МессиБерлекэмпа Цель работы Изучить возможность криптоанализа потокового шифратора при помощи его замены эквивалентным линейным рекуррентным регистром ЛРР. ...

Русский

2013-05-03

140 KB

54 чел.

Лабораторная работа 9

Криптоанализ потокового шифра на основе использования алгоритма Месси-Берлекэмпа
Цель работы
Изучить возможность криптоанализа потокового шифратора при помощи  его замены  эквивалентным линейным рекуррентным регистром (ЛРР).
Используемое программное обеспечение
Для работы используется программа MBA.EXE
Задание
1. Найти длину ЛРР и  его полином обратных связей  по выходной последовательности этого ЛРР, используя алгоритм Месси-Берлекэмпа (MBA).
2. Найти полином обратных связей ЛРР, формирующий последовательность, эквивалентную последовательности полученной как произведение выходов заданного ЛРР.
3. Проверить, что эквивалентный ЛРР позволяет правильно предсказывать гамму, полученную от исходного нелинейного датчика.
4. Сделать выводы об эффективности атаки на потоковый шифр с использованием MBA.
Порядок выполнения работы
Для начала работы перейти в каталог, содержащий рабочие программы.
Запустить программу MBA.EXE.
1. Задать длину , произвольное начальное заполнение, примитивный полином обратных связей ЛРР и сгенерировать  выходную последовательность ЛРР.
2. Выбрать не менее  смежных выходных элементов ЛРР по п.1 и, используя MBA, проверить, что такая последовательность сформирована ЛРР, имеющем характеристический многочлен . Сравнить их с соответствующими данными по п.1.
3. Задать длину ЛРР  не более 15, полином обратных связей , произвольное начальное заполнение, а также номера двух отводов ячеек ЛРР для формирования произведения последовательностей. Сформировать последовательности.
4. Ввести в MBA не менее чем  последовательных символов произведения, взятых в произвольном месте периода. Рассчитать длину  ЛРР и эквивалентный полином обратных связей.
5. Задать начальное заполнение, совпадающее с началом последовательности-произведения, полином обратных связей, полученный в п.4 и сгенерировать выходную последовательность эквивалентного ЛРР.
6. Сравнить последовательность-произведение и выходную последовательность эквивалентного ЛРР для всех символов. Сделать выводы об эффективности такого метода криптоанализа.
Отчет
1. Титульный лист.
2. Начальное заполнение и примитивный полином по п.1, а также  соответствующую им  выходную последовательность ЛРР.
3. Выбранную последовательность для анализа MBA и найденный полином обратных связей по п.2.
4. Начальное заполнение, полином обратных связей  и номера ячеек памяти для формирования произведения по п. 3.
5. Последовательность-произведение и ее отрезок, выбираемый для анализа MBA.
6. Полином обратных связей эквивалентного ЛРР, полученный после применения MBA к выбранному отрезку последовательности произведения.
7. Результаты сравнения последовательности-произведения и выходной последовательности эквивалентного ЛРР по п.6.
Описание программы
Для выполнения лабораторной работы используется специально разработанная программа, содержащаяся в файле MBA.exe. Вид главного окна программы представлен на рис.1.
Рис.1. Главное окно программы
В самом начале работы с программой необходимо ввести исходные данные: длину используемого регистра, вид полинома обратных связей (коэффициенты полинома) и начальное заполнение ячеек регистра. Данные вводятся в пустые поля с соответствующими названиями. Если все данные введены верно, то будет активна кнопка Генерировать (рис.2).
Рис.2. Окно программы с введенными исходными данными
Также можно выбрать один из режимов генерации последовательности: обычный и с перемножением отводов регистра. Во втором случае станут доступны поля, в которых необходимо указать номера перемножаемых ячеек регистра (рис.3).
Рис.3. Метод генерации последовательности и номера отводов регистра
Для получения данных необходимо нажать кнопку Генерировать. После этого в центральной части окна будет показана последовательность, полученная на основе указанного полинома обратных связей и его начального заполнения, а также с учётом способа генерации, двоичная последовательность.
Рис.4. Полученная перемножением ячеек регистра двоичная последовательность
Далее необходимо выделить часть последовательности длиной, минимально необходимой для анализа алгоритмом Мэсси-Берлекампа, и скопировать ее в поле Анализируемая последовательность. После чего надо нажать кнопку Поиск полинома. Программа, используя алгоритм Мэсси-Берлекампа, найдёт эквивалентный последовательности полином и укажет его (рис. 5).
Рис. 5. Найденный по алгоритму Мэсси-Берлекампа полином
Отчет по лабораторной работе
«Криптоанализ потокового шифра на основе использования алгоритма Месси-Берлекэмпа»
(пример оформления)
Выполнил студент: Петров В.В.
Преподаватель: Яковлев В.А.
Пункт 1
Длина регистра: 6
Примитивный полином обратных связей: h(x) = x6 + x + 1 (коэффициенты полинома 1000011)
Начальное заполнение: 100000
Двоичная последовательность: 1000001111110101011001101110110100100111000101111001010001100001000001111110101011001101110110100100
Пункт 2
Выбранная для анализа цепочка: 011101101001
Длина найденного регистра: 6
Найденный полином обратных связей: h(x) = x6 + x + 1 (коэффициенты полинома 1000011)
Полученные результаты совпадают с исходными данными пункта 1.
Пункт 3
Длина регистра: 6
Примитивный полином обратных связей: h(x) = x6 + x + 1 (коэффициенты полинома 1000011)
Начальное заполнение: 100000
Номера перемножаемых отводов: 2 и 5
Двоичная последовательность:
0000111010000100100110011010010010000000010100100000000000000000000111010000100100110011010010010000
Пункт 4
Выбранная для анализа цепочка: 0000111010000100100110011010010010000000
Длина найденного регистра: 21
Найденный полином обратных связей: h(x) = x21 + x18 + x16 + x15 + x12 + x11 + x10 + x9 + x8 + x7 + x3 + x + 1 (коэффициенты полинома 1001011001111110001011)
Пункт 5
Длина регистра: 21
Полином обратных связей: h(x) = x21 + x18 + x16 + x15 + x12 + x11 + x10 + x9 + x8 + x7 + x3 + x + 1 (коэффициенты полинома 1001011001111110001011)
Двоичная последовательность:
0000111010000100100110011010010010000000010100100000000000000000000111010000100100110011010010010000
Пункт 6
Двоичные последовательности, полученные в п.п. 3 и 5 полностью совпадают.
Вывод: алгоритм Мэсси-Берлекампа можно успешно применять для определения эквивалентного полинома обратных связей для двоичной последовательности.
Контрольные вопросы
1. Какую задачу решает MBA?
2. Что такое линейная эквивалентная сложность двоичной последовательности?
3. Является ли полином обратных связей эквивалентного ЛРР примитивным?
4. Как выбрать нелинейные узлы усложнения  так,  чтобы они обеспечивали стойкость к атаке по MBA?
5. Какие нелинейные узлы вы знаете? Запишите булевы функции, составьте таблицы истинности.
Литература
1. В.И.Коржик “Конспект лекций по курсу “Основы криптографии”’.
2. В.И.Коржик, Д.В.Кушнир, ”Теоретические основы информационной безопасности телекоммуникационных систем”, СПбГУТ, 2000.


 

А также другие работы, которые могут Вас заинтересовать

22358. Аналитическое продолжение 680.5 KB
  Представляет большой интерес вопрос нельзя ли расширить область определения этой функции сохранив регулярность. Функцию регулярную в области содержащей и совпадающую с регулярной в области называют аналитическим продолжением функции на область . Если аналитическое продолжение регулярной функции в данную более широкую область определения возможно то оно возможно лишь единственным образом. В самом деле пусть существуют два аналитических продолжения и функции регулярной в области в одну и туже область .
22359. Римановы поверхности 55 KB
  Пусть дана многозначная аналитическая функция fz определенная в области D комплексной плоскости. Условимся рассматривать области Dk из которых в процессе аналитического продолжения строится область D как отдельные листы изготовленные в таком количестве экземпляров сколько значений имеет функция в данной области D. Пусть области D0 и D1 имеют общие части причем в одних из этих частей значения f0z и f1z совпадают а в других различны. Поверхность образованную из отдельных областей определения ветвей многозначной аналитической...
22360. Конформные отображения. Понятие конформного отображения 1.86 MB
  Предположим что задано непрерывное и взаимно однозначное отображение области D на некоторую область . Геометрически эта замена равносильна замене отображения отображением 3 которое называется главной линейной частью отображения 1. Отображение 3 можно переписать в виде 4 где: 5 не зависят от x и y. Отображение 4 представляет собой так называемое линейное аффинное преобразование плоскости .
22361. Преобразование Лапласа и ее доказательство 382 KB
  Это утверждение вытекает непосредственно из неравенства. Отсда следует, что, если, оставаясь внутри любого угла , где сколь угодно мало, причем эта сходимость равномерна относительно. Если, в частности, аналитическая...
22362. Свойства преобразования Лапласа 1.75 MB
  2 Изображения аналитичны не только в области но и всюду кроме . В дальнейшем будем обозначать через оригиналы их изображения: 3 Непосредственно из свойств интегралов получаем: I. линейное пространство функцииоригинала с показателем роста изоморфно пространству изображения. Переходя к изображениям и интегрируя по частям получим .
22363. Основной принцип теории пределов 635.5 KB
  Существует одна и только одна точка которая принадлежит всем отрезкам данной последовательности. Следовательно двух точек общих всем отрезкам нашей последовательности существовать не может; существование же одной такой точки доказано в теории иррациональных чисел. Существует единственная точка принадлежащая всем прямоугольникам данной последовательности. Пусть имеется бесконечная последовательность комплексных чисел 1 Число z называется предельным числом последовательности 1 если...
22364. Дробно-линейные отображения 824.5 KB
  Отображение инверсия преобразование симметрии относительно единичной окружности. Вообще точки и называют симметричными относительно окружности : если 1 они лежат на одном луче проходящем через точку 2 Преобразование переводящее каждую точку плоскости в точку симметричную относительно окружности называют симметрией относительно этой окружности или инверсией. Докажем основное свойство симметричных точек: Точки и тогда и только тогда являются симметричными относительно окружности когда они являются вершинами пучка...
22365. Расширенная комплексная плоскость 2.74 MB
  непрерывны функции и то ее графиком является некоторая кривая на комплексной плоскости. Тогда говорят что задана непрерывная кривая или просто кривая: 1 а уравнение 1 называют параметрическим уравнением этой кривой. Пусть кривая задана уравнением 1. вопервых кривая является упорядоченным множеством точек вовторых различным точкам кривой может отвечать одна и та же точка плоскости: если t = t при tt то точки z= t и z=t...
22366. Понятие сходящегося и расходящегося ряда 227.5 KB
  Понятие сходящегося и расходящегося ряда. Рассмотрим бесконечный ряд: 1 все члены ряда – комплексные числа образуем ∑ первых n членов этого ряда: 2 Давая n значения 123 мы получим бесконечную последовательность комплексных чисел S1S2Snсоответствующего ряда 1 . Обратно зная последовательность чисел Sn легко написать соответствующий ей ряд: S1S2S1SnSn–1 Говорят что ряд 1 сходится если соответствующая ему последовательность чисел Sn сходится в этом случае суммой ряда 1 называют предел указанной...