12749

Исследование свойств линейного рекуррентного регистра (ЛРР)

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

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

Лабораторная работа 8 Исследование свойств линейного рекуррентного регистра ЛРР Цель работы Изучить способы задания ЛРР и свойства генерируемых им последовательностей. Используемое программное обеспечение Для работы используется программа LRR.EXE З...

Русский

2013-05-03

168 KB

102 чел.

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

Исследование свойств линейного рекуррентного регистра (ЛРР)
Цель работы
Изучить способы задания ЛРР и свойства генерируемых им последовательностей.
Используемое программное обеспечение
Для работы используется программа LRR.EXE
Задание
1. Найти периоды выходных последовательностей ЛРР, заданных различными полиномами обратных связей и при различных начальных заполнениях.
2. Исследовать основные статистические свойства выходных последовательностей ЛРР на примитивном полиноме:
                               -«окна»,
                               -баланса нулей и единиц,
                               -серий,
                               -корреляционной функции.
3. Сделать выводы о соответствии результатов по п.1-2 теоретическим знаниям, полученным на лекциях.
Порядок выполнения работы
Для начала работы перейти в каталог, содержащий рабочие программы lab1.
Запустить программу LRR.EXE.
1. Задать длину ЛРР равной 4, полином обратных связей x4 + x3 + x + 1 и начальное заполнение 1110. Сгенерировать выходную последовательность ЛРР и найти зрительно ее период.
2. Выполнить п.1, изменив начальное заполнение на 1001.
3. Задать длину ЛРР равной 4, полином обратных связей x4 + x + 1. Сгенерировать выходные последовательности ЛРР при тех же двух начальных заполнениях, что и в п.1-2, и найти их периоды. Объяснить результаты, полученные в п.1-3.
4. Просмотрев таблицу примитивных полиномов, содержащуюся в файле poly.dat,открыв ее через блокнот и выбрать  произвольно примитивный полином степени не более 17. Задать произвольное начальное заполнение и сгенерировать выходную последовательность ЛРР.
5. Сравнить  последовательность ЛРР по п.4 с чисто случайной последовательностью, полученной, как “hot bits” из Интернет (чисто случайная последовательность заложена в программу). Сделать выводы о совпадении или несовпадении их свойств.
6. Рассчитать период, частость нулей и единиц, частость серий и вид автокорреляционной функции (АКФ) для последовательности, полученной в п.4. Сравнить полученные результаты с теоретическими знаниями, полученными на лекциях.
Отчет
1. Титульный лист.
2. Анализ свойств по п.1-3.
3. Примитивный полином по п.4, полученный период выходной последовательности ЛРР для этого полинома, автокорреляционная функция и ее значения на периоде.
4. Сравнение последовательности на выходе ЛРР и чисто случайной последовательности по п.5.
5. Частости нулей и единиц, частости серий и значения АКФ, рассчитанные в п.6.
Описание программы
Для выполнения лабораторной работы используется специально разработанная программа, содержащаяся в файле LLR.exe. Вид главного окна программы представлен на рис. 1.
Рис.1. Главное окно программы
В начале работы необходимо ввести исходные данные: длину используемого регистра, коэффициенты полинома обратных связей и начальное заполнение ячеек регистра, длину генерируемой последовательности. Данные вводятся в пустые поля с соответствующими названиями в левой части окна. Если все данные введены верно, то будет активна кнопка Генерировать (рис. 2).
Рис.2. Заполнение исходных данных
Для получения данных необходимо нажать кнопку Генерировать. После этого в нижней части окна в верхнем поле будет показана полученная на основе указанного полинома обратных связей и его начального заполнения двоичная последовательность, свойства которой исследуются в настоящей лабораторной работе. В нижнем поле будет представлена чисто случайная двоичная последовательность, представленная для сравнения с линейной рекуррентной последовательностью. После этого станут доступны ещё две кнопки: Статистика и График (на рис.3 обведены красным и зеленым соответственно).
Рис. 3. Сгенерированная двоичная последовательность
Для расчета статистических данных полученной двоичной последовательности (период, число серий и пр.) необходимо нажать кнопку Статистика. Рассчитанные величины будут показаны в нижней части окна программы. Для достаточно длинных последовательностей это может занять некоторое время.
Рис.4. Статистика двоичной последовательности
Кнопка График предназначена для просмотра графика корреляционной функции.
Рис.5.  График корреляционной функции примитивного полинома
Рис.6. График корреляционной функции не примитивного полинома
Статистические свойства выходных последовательностей ЛРР
  1.  Период.
Периодом называется наименьшее целое число  такое, что для элементов последовательности выполняется соотношение ,
Период линейной рекуррентной последовательности , где  – порядок примитивного полинома. Период рекуррентной последовательности  на примитивном полиноме находится как .
  1.  Серия.
Серией длины  называется последовательность из  одинаковых символов, окруженных другими символами. На периоде ЛРР максимальной длины, число серий равно длины 1 равно 1/2 от общего количества серий, 1/4 всех серий длины 2, 1/8 всех серий длины 3 и так далее.
  1.  Окно.
Если «окно» шириной n перемещать вдоль выходной последовательности ЛРР на примитивном полиноме, то каждый из  ненулевых наборов будет виден в окне только один раз.
  1.  Баланс.
Число нулей на периоде линейной рекуррентной последовательности в точности равно
,
а число единиц равно
.
Отсюда: частость появления нулей и единиц вычисляется так
,      
  1.  Автокорреляционная функция (АКФ).
АКФ называется
,
- линейная рекуррентная последовательность,
- линейная рекуррентная последовательность, сдвинутая на  тактов.
Для линейной рекуррентной последовательности максимального периода
,
.
Отчет по лабораторной работе
«Исследование свойств линейного рекуррентного регистра (ЛРР)»
(пример оформления)
Выполнил студент: Петров В.В.
Преподаватель: Яковлев В.А.
Пункт 1
Длина регистра: 4
Полином обратных связей: h(x) = x4 + x3 + x + 1 (коэффициенты полинома 11011)
Начальное заполнение: 1110
Двоичная последовательность: 1110001110001110001110001110001110001110001110001110001110001110001110001110001110001110001110001110
Период двоичной последовательности: 6
Пункт 2
Длина регистра: 4
Полином обратных связей: h(x) = x4 + x3 + x + 1 (коэффициенты полинома 11011)
Начальное заполнение: 1001
Двоичная последовательность:
1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001
Период двоичной последовательности: 3
Пункт 3
Длина регистра: 4
Примитивный полином обратных связей: h(x) = x4 + x + 1 (коэффициенты полинома 10011)
Начальное заполнение: 1110
Двоичная последовательность:
1110101100100011110101100100011110101100100011110101100100011110101100100011110101100100011110101100
Период двоичной последовательности: 15
Длина регистра: 4
Примитивный полином обратных связей: h(x) = x4 + x + 1 (коэффициенты полинома 10011)
Начальное заполнение: 1001
Двоичная последовательность:
1001000111101011001000111101011001000111101011001000111101011001000111101011001000111101011001000111
Период двоичной последовательности: 15
Пункт 4
Длина регистра: 15
Примитивный полином обратных связей: h(x) = x15 + x11 + x7 + x6 + x2 + x + 1 (коэффициенты полинома 1000100011000111)
Начальное заполнение: 100100011010011
Двоичная последовательность:
1001000110100110011011100101110100010111001110000111101100110001100111000001011001100100111110000110
Период двоичной последовательности: 32767
Пункт 5
Период двоичной последовательности: 32767
Частость появления нулей и единиц: 0,500015259
Частость серий:
8193 серии длины 1
4096 серий длины 2
2048 серии длины 3
1024 серии длины 4
512 серий длины 5
Автокорреляционная функция: константа R(k) = -3,05185094 * 10-5, для k0.
Контрольные вопросы
1. Что такое ЛРР и чем он задается?
2. Что такое примитивный полином?
3. Каким может быть период ЛРР?
4. Зависит ли период от начального заполнения?
5. Задайте полином обратных связей, который при любом начальном заполнении дает период равный длине ЛРР.
6. Как выбрать полином обратных связей, чтобы обеспечить максимально возможный период выходной последовательности? Чему равен этот период?
7. Каково соотношение нулей и единиц на максимальном периоде, какова частость серий и вид АКФ?
8. Можно ли непосредственно использовать ЛРР в качестве датчика гаммы потокового шифра?
Литература
1. В.И.Коржик “Конспект лекций по курсу “Основы криптографии”’.
2. В.И.Коржик, Д.В.Кушнир, ”Теоретические основы информационной безопасности телекоммуникационных систем”, СПбГУТ, 2000.


 

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

17293. Моделі загроз та порушників безпеки 127.5 KB
  Лекція 3. Моделі загроз та порушників безпеки Поняття загрози інформації Безпечна або захищена система це система із засобами захисту які успішно і ефективно протистоять визначеним загрозам безпеки. Виходячи із цього першим кроком в побудові захищеної системи є ід
17294. Політика безпеки 103.5 KB
  Лекція 4. Політика безпеки Поняття політики безпеки Фундаментальним поняттям захисту інформації є політика безпеки ПБ або політика захисту. Важливість цього поняття важко переоцінити існують ситуації коли правильно сформульована політика є чи не єдиним механізм
17295. Вступ до криптології 111 KB
  Лекція 5. Вступ до криптології Виключно важливим механізмом захисту інформації є криптографія. Оскільки цей складний і широкий розділ математики вимагає окремого детального вивчення тут подамо лише основні відомості з криптології. Проблема захисту інформації шляхом...
17296. Віруси. Загальні відомості 92.5 KB
  Лекція 6. Віруси. Загальні відомості Створенням будьякої комп'ютерної програми її автор переслідує певну мету. Іноді їм можуть бути допущені помилки і написана програма буде робити не зовсім те що спочатку задумувалося або навіть зовсім не те. Однак кожна програма обов'...
17297. Методи та засоби антивірусного захисту 111 KB
  Лекція 7. Методи та засоби антивірусного захисту Загальні відомості Усі знають що для захисту від шкідливих програм потрібно використовувати антивіруси. Але в той же час нерідко можна почути про випадки проникнення вірусів на захищені антивірусом комп'ютери. У кожном...
17298. Методи захисту від спаму 92.5 KB
  Лекція 9. Методи захисту від спаму Одна з найбільших проблем при роботі з електронною поштою це небажані повідомлення комерційного характеру а просто кажучи спам. Крім незручностей пов'язаних з позбавленням від спаму спам це ще й прямі збитки для підприємства: вит
17299. Засоби захисту від спаму 155 KB
  Лекція 9. Засоби захисту від спаму Загальні відомості Спам давно вже перестав бути просто нав'язливою рекламою. Технології які використовують спамери для розсилки пошти небезпечні для корпоративних інформаційних систем. Вони використовують шкідливий мобільний код
17300. Шпигунське програмне забезпечення. Шпигунські війни: spyware і боротьба з ним 64 KB
  Лекція 10. Шпигунське програмне забезпечення Шпигунські війни: spyware і боротьба з ним По даним Earthlink програми що відносяться до категорії spyware сьогодні встановлені майже на 90 комп'ютерів підключених до Мережі є й більш вражаючі цифри. Причому мова йде не про один п...
17301. Шпигунські програми й методи захисту від них 135.5 KB
  Лекція 11. Шпигунські програми й методи захисту від них Програмне забезпечення й апаратні пристрої призначені для прихованого спостереження за діяльністю користувачів персональних комп'ютерів одержали останнім часом саме широке поширення. У світовій мережі Інтернет