Санкт-Петербургский национальный исследовательский университет
информационных технологий, механики и оптики
Информационная безопасность и защита информации
Лабораторная работа №3
«Алгоритм Берлекэмпа-Месси для нахождения коэффициентов обратной связи генератора псевдослучайной последовательности»
Выполнил:
студент гр. 4512
Смертина К
Гр 4516
Пак Денис
Санкт-Петербург
2012
Цель работы:
Ознакомиться с алгоритмом Берлекэмпа-Месси и по исходному отрезку псевдослучайной последовательности восстановить генератор, задающий обратные связи.
-
Описание алгоритма нахождения генератора ПСП
На вход подается последовательность z длины n.
-
Инициализация: r = 0, c(x) = 1, b(x) = 1.
-
При каждой итерации r(r = r + 1), вычисляется невязка как
-
Если невязка равна 0, то b(x) = xb(x), переходим к 5, в противном случае выполняем 4.
-
Формируем новый полином t(x) = c(x) + x*b(x). Сохраняем предыдущий полином: b(x) = c(x). Меняем связи регистра c(x) = t(x).
-
Если r < n, возвращаемся к 2. В противном случае работа закончена, результаты работы алгоритма - полином ЛРОС c(x) и линейная сложность последовательности z равная L = deg c(x).
-
Найденный полином и его линейная сложность
Полином равен 1+x+x^15. Линейная сложность равна 15.
Вывод по работе:
Был рассмотрен и изучен алгоритм Берлекэмпа-Месси для поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход алгоритма требуемой генерируемой последовательности. Данный алгоритм хорош тем, что он сразу решает две задачи – определение линейной сложности и нахождение коэффициентов полинома со сложностью порядка L^2.