Алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм тема диссертации и автореферата по ВАК РФ 05.13.19, доктор технических наук Рожков, Михаил Иванович

• Рожков, Михаил Иванович
• доктор технических наук
• 2011

Оглавление диссертации доктор технических наук Рожков, Михаил Иванович

Обозначения.

Введение.

Глава 1. Суммирование цепей Маркова на конечной группе.

§1.1. Постановка задачи и вводные замечания.

§ 1.2. Случай произвольной конечной группы.

§ 1.3. Случай произвольной абелевой группы.

§ 1.4. Случай элементарной абелевой 2-группы.

§ 1.5. Случай циклической группы G=Zm

§ 1.6. Свойства «частичных» сумм заданного множества цепей

Маркова.

§ 1.7. Устойчивые цепи Маркова.

§ 1.8. Случай группы четвертого порядка.

§ 1.9. Случай циклической группы р - простое нечетное число, и рациональности матриц переходных вероятностей.

§ 1.10. О существовании вероятностных элементов специального вида в групповом кольце.

§ 1.11. О сложности проверки марковости сумм цепей Маркова на произвольной конечной абелевой группе.

Глава 2. Идентификация фильтрующих функций по частотам выходных Б-грамм.

§ 2.1. Общие условия статистической неотличимости фильтрующих функций.

§ 2.2. Основные результаты относительно условий неотличимости фильтрующих функций.

§ 2.3. Оценки мощности и числа классов статистической неотличимости.

§ 2.4. Упрощенные обозначения и формулировки полученных ранее результатов для случаев равновероятного входа и двоичного выхода

S 2.5. Вопросы классификации автоматов Rt{X,Xn,F2) по выборке с фиксированным шагом из выходной последовательности.

§ 2.6. Классификация автоматов Rf(X,Xn,F2) относительно распределения тграмм в выборке с шагом п-1 из выходной последовательности.

§ 2.7. Общие алгоритмы проверки неотличимости заданной пары автоматов

Ri(X,Xn,F2) и R<p(X,Xn,F2).

§ 2.8. Алгоритмы проверки равновероятности выходных m-грамм заданного автомата Rf(X,Xn,F2) при равновероятном входе.

§ 2.9. Алгоритмы для случая, когда функция равна сумме двух функций от непересекающихся наборов переменных.

§ 2.10. Оценка числа и мощности классов эквивалентности для общего случая функций, заданных на переходах цепи Маркова.

Глава 3. О некоторых классах нелинейных регистров сдвига, обладающих одинаковой цикловой структурой. $ 3.1. Условия биективности отображений специального вида.

§ 3.2. Случай поля GF(2).

§ 3.3. Оценки мощности классов эквивалентных функций

§ 3.4. Наиболее мощные классы эквивалентности и обобщенные композиции функций.

§ 3.5. Ортогональные системы двоичных функций, построенные с использованием нелинейной функции и линейного регистра сдвига.

Введение диссертации (часть автореферата) на тему «Алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм»

Важным элементом систем защиты информации являются генераторы случайных последовательностей (ГСП). Они используются для решения следующих задач:

-выработка маскирующих последовательностей при хранении и передаче информации;

-формирование ключевой информации;

-формирование случайных последовательностей (запросов) в алгоритмах аутентификации, электронной подписи, выработки общего секретного ключа;

-внесение неопределенности в работу аппаратно-программных средств защиты с целью закрытия побочных каналов утечки информации;

- внесение неопределенности в работу систем защиты при реализации концепции вероятностного шифрования.

Во многих случаях при построении ГСП с целью обеспечения необходимой скорости функционирования к ним предъявляются требования по простоте технической реализации. Особенно данное требование важно для ГСП, предназначенных для реализации на микропроцессорах интеллектуальных карт, обладающих сравнительно ограниченными вычислительными возможностями (см., например,[7]).

Широко использующийся в практических приложениях (каскадный) метод построения ГСП заключается в выработке результирующих последовательностей из исходных последовательностей с помощью некоторых автоматных преобразований (узлов усложнения). При этом исходные последовательности, как правило, не обладают всеми необходимыми требованиями «на случайность» (непредсказуемость других знаков выхода при известной их части) и вырабатываются либо физическими (программно-аппаратными) датчиками случайных чисел, либо исходными автоматами (как правило, линейными для гарантирования большого периода). Роль узлов усложнения заключается:

-в получении результирующих последовательностей, обладающих «улучшенными» теоретико-вероятностными характеристиками по сравнению с исходными последовательностями;

-в усложнении аналитических связей между исходными и результирующими последовательностями.

При необходимости в схеме ГСП может использоваться несколько последовательных узлов усложнения.

Таким образом, при использовании каскадного принципа построения ГСП важной задачей является исследование вероятностных характеристик выходных последовательностей, образуемых из исходных последовательностей с заданными вероятностными свойствами с помощью узлов усложнения.

Важными для практических приложений являются случаи, когда исходные последовательности являются:

- последовательностями независимых случайных величин;

- последовательностями случайных величин, связанных простой однородной цепью Маркова;

- последовательностями, вырабатываемыми регистрами сдвига.

В качестве узлов усложнения широко используются узлы суммирования, нелинейные регистры сдвига, фильтрующие генераторы. При этом с точки зрения простоты реализации (особенно на микропроцессорах интеллектуальных карт) особый интерес представляют такого автоматы с малым числом состояний.

Актуальность проведения исследований вероятностных характеристик выходных последовательностей автоматных преобразований, моделирующих функционирование узлов ГСП, объясняется необходимостью:

- повышения обоснованности оценок качества соответствующих ГСП; выбора параметров соответствующих автоматов так, чтобы вероятностные характеристики выходных последовательностей соответствующих ГСП обладали заданными свойствами.

В этой связи важной является задача классификации узлов усложнения по вероятностным характеристикам выходных Б-грамм (оценка числа и мощности классов статистически неотличимых автоматов).

При этом составной частью данной проблематики является разработка эффективно реализуемых на ПЭВМ алгоритмов для вычисления сравнительных вероятностных характеристик выходных последовательностей конечных автоматов, описывающих функционирование узлов и блоков ГСП.

Целью диссертационной работы является разработка новых методов для описания вероятностных характеристик выходных последовательностей конечных автоматов, моделирующих функционирование узлов и блоков ГСП, и построение на их основе эффективных алгоритмов идентификации автоматов по вероятностям выходных э-грамм, а также получение оценок неоднозначности идентификации. В связи с этим задачами исследования являются:

1. Получение эффективно проверяемых условий, при которых сумма б>2 взаимно независимых простых однородных цепей Маркова, заданных на конечной абелевой группе, также является цепью Маркова с матрицей переходных вероятностей, независящей от начального распределения исходных цепей Маркова.

2. Построение методов разложения заданной цепи Маркова в сумму б>2 взаимно независимых цепей.

3. Разработка новых методов и эффективно реализуемых алгоритмов построения классов эквивалентности фильтрующих генераторов со случайным входом, обладающих заданными вероятностями выходных Б-грамм.

4. Получение оценок для числа и мощности классов эквивалентности.

5. Разработка методов и алгоритмов построения нелинейных регистров сдвига, обладающих одинаковой цикловой структурой.

Согласно паспорту специальности 05.13.19 данные задачи соответствуют пункту 14 области исследования специальности 05.13.19: «Принципы и решения (технические, математические, организационные) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности». Кроме того, данные задачи соответствуют пункту 54 Перечня научно-технических проблем обеспечения информационной безопасности РФ («Разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики»).

Единство решаемых в диссертации задач заключается в том, что они связаны с исследованием функций, заданных на переходах цепей Маркова, и задачами теории распределений на конечных абелевых группах.

Диссертация состоит из введения, трех глав, библиографического списка и приложения.

Заключение диссертации по теме «Методы и системы защиты информации, информационная безопасность», Рожков, Михаил Иванович

Основные результаты диссертации заключаются в следующем:

1. В главе 1 разработан новый метод на основе математического аппарата групповых колец, позволивший найти структуру матриц переходных вероятностей цепей Маркова на конечной абелевой группе, разложимых в сумму составляющих цепей, и описать связь данных матриц с матрицами составляющих цепей. На основе разработанного метода получены:

1.1. Новые эффективно проверяемые необходимые и достаточные условия марковости суммы цепей Маркова, заданных на конечной абелевой группе (теоремы 1.2.1, 1.5.6, 1.9.1); на основе данных условий предложены обладающие полиномиальной по |G| и s вычислительной сложностью алгоритмы проверки того, что сумма цепей Маркова с рациональными матрицами переходных вероятностей также является цепью Маркова.

1.2. Описание цепей Маркова на конечной абелевой группе, разложимых в сумму составляющих цепей (теорема 1.3.3).

1.3. Необходимые и достаточные условия, при которых сумма цепей Маркова с одной и той же матрицей переходных вероятностей также является цепью Маркова (теорема 1.3.7).

1.4. Необходимые и достаточные условия того, чтобы сумма цепей Маркова, заданных на конечной абелевой группе, приводила к результирующей цепи с равновероятной матрицей переходных вероятностей (теорема 1.3.9).

1.5. Описание устойчивых цепей Маркова (теорема 1.7.1).

2. В главе 2 диссертации разработан новый метод изучения вероятностей выходных s-грамм, связанный с исследованием вероятностных характеристик линейных комбинаций знаков выходной гаммы. На основе разработанного метода получены следующие результаты:

2.1. Получены верхние оценки для числа классов неотличимых автоматов Rt(X,Xn,G) относительно вероятностей m-грамм в выборке из выходной последовательности (в том числе и нерегулярной) с шагом h> * п теоремы 2.3.2-2.3.3).

2.2. Разработаны детерминированные алгоритмы (2.7.2 и 2.7.4) проверки статистической неотличимости автоматов Rt{X,Xn,G) для случая бинарного выхода (|G|=2) и бернуллиевского входа. При этом алгоритм 2.7.4 использует только модульные арифметические операции над целыми числами стандартной длины.

Применительно к двоичным автоматам Rf(F2,(F2)n,F2) сложность

4п реализации алгоритмов 2.7.2 и 2.7.4 оценивается соответственно в 0(2 ) арифметических операций в поле действительных (рациональных) чисел и

0(25п) модульных арифметических операций над целыми 32-битными числами. Для реализации этих алгоритмов требуется память объемом 0(22п) ячеек.

На основе данных алгоритмов проведена полная классификация (по классам неотличимости) автоматов 11^2,(Рг)"^) длины п=4, а также получено описание всех двоичных функций без запретов от пяти переменных.

2.3. Разработаны алгоритмы (2.9.4 и 2.9.8) для проверки статистической неотличимости двоичных автоматов Я^Рг,^)2"^), функция выхода которых ф£ьх2,. .,х2п)=^(хьх2,. .,хп^2(хп +1,хп +2,. .,х2п) есть сумма двух функций от непересекающихся аргументов. Данные алгоритмы имеют сложность 0(25п), и для их реализации требуется память порядка 0(23п). Сложность же реализации в данном случае общего алгоритма 2.7.2 составила бы 0(28") операций и 0(24") ячеек памяти.

3. В главе 3 настоящей работе предложен новый подход к оценке длины периода нелинейных регистров сдвига. Этот подход связан с построением классов функций обратной связи Мф, при которых соответствующие регистры сдвига обладают одинаковой цикловой структурой. В таком случае для расчета цикловой структуры всего класса регистров достаточно исследовать структуру одного (наиболее удобного для изучения) представителя.

Описание регистров сдвига, изоморфных заданному регистру 11(0, связано со сложной задачей построения специального вида биективных отображений, которые являются решениями уравнений Коши, соответствующих парам изоморфных регистров сдвига.

В настоящей работе получено описание частных классов такого сорта биекций, приведших к построению соответствующих классов изоморфных нелинейных автоматов (теоремы 3.2.7 и 3.2.6). При этом наиболее мощные из описанных классов имеют мощность 4-(п-2) и отвечают регистрам сдвига с квадратичными функциями обратной связи. Путем исследования на ЭВМ представителей этих классов для п < 27 выделены классы, отвечающие регистрам, которые обладают циклом длины 2"-1.

ЗАКЛЮЧЕНИЕ

В целом на основании выполненных исследований в диссертационной работе разработаны теоретические положения, совокупность которых можно квалифицировать как новое крупное достижение в разработке методов и алгоритмов получения вероятностных характеристик выхода конечных автоматов, моделирующих работу генераторов псевдослучайных последовательностей.

Единство решаемых в диссертации задач заключается в том, что они связаны с исследованием функций, заданных на переходах цепей Маркова, и задачами теории распределений на конечных абелевых группах.

Согласно паспорту специальности 05.13.19 данные задачи соответствуют пункту 14 области исследования специальности 05.13.19: «Принципы и решения (технические, математические, организационные) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности». Кроме того, данные задачи соответствуют пункту 54 Перечня научно-технических проблем обеспечения информационной безопасности РФ («Разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики»).

Список литературы диссертационного исследования доктор технических наук Рожков, Михаил Иванович, 2011 год

1. Алферов А.П., Зубов А.Ю., Кузьмин A.C., Черемушкин A.B. Основы криптографии (учебное пособие). М., Гелиос АРВ, 2001. 480с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

3. Берлекэмп Э. Алгебраическая теория кодирования. М., Мир, 1971. 477с.

4. Болотов A.A., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006. - 280 с.

5. Бухараев Р. Г. Основы теории вероятностных автоматов. —М., Наука, 1985.

6. Воробьев H.H. Сложение независимых случайных величин на конечных абелевых группах. -Матем. сб., 1954, т. 34(76), № 1.

7. Варфоломеев А.А, Запечников C.B., Маркелов В.В., Пеленицын М.Б. Интеллектуальные карты и криптографические особенности их применений в банковском деле: Учебное пособие. М.: МИФИ, 2000. 188 с.

8. Гилл А. Введение в теорию конечных автоматов. М., Наука, 1966.

9. Глухов М.М., Елизаров В.П., Нечаев A.A. Алгебра: Учебник. В 2-х т. Т. 1. -М.: Гелиос АРВ, 2003. 336 с.

10. Глебский Ю. В. Кодирование с помощью конечных автоматов. — Докл. АН СССР, 1961, т. 141, № 5, с. 1054-1057.

11. Глебский Ю. В. Осуществимые последовательности в конечных автоматах. —В сб. Проблемы кибернетики. Вып. 5. М., Физматгиз, 1961, с. 279-282.

12. Глебский Ю. В. Кодирование с помощью автоматов с конечной внутренней памятью. —В сб. Проблемы кибернетики. Вып. 7. М., Физматгиз, 1962, с. 127-149.

13. Горчинский Ю. Н., Круглов И. А., Капитонов В. М. Вопросы теории распределений на конечных группах. — В сб.: Труды по дискретной математике. Т. 1. М.: ТВП, 1997, с. 85-112.

14. Жуков А. Е., Чистяков В. П. Матричный подход к исследованию прообразов выходной последовательности конечного автомата. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 1994, т. 1, в. 1, с. 108-117.

15. Захаров В.К., Сарманов О.В. Укрупнение состояний цепи Маркова и стационарное изменение спектра. ДАН СССР, 1965, т. 160, № 4, с. 762-764.

16. Ивченко Г.И., Медведев Ю.И. Математическая статистика. М. «Высшая школа», 1992. 303 с.

17. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. М.: КУДИЦ-ОБРАЗ, 2003.-240 с.

18. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970.

19. Копытцев В. А. О некоторых случайных заведомо совместных системах уравнений. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 1994, т. 1, в. 1, с. 56-84.

20. Колесников О. В. Использование запретов дв'оичных функций при решении систем уравнений. — Обозрение прикл. и промышл. матем., сер. дискретн. матем., 1995, т. 2, в. 3, с. 483-493.

21. Кэртис Ч., Райнер И. Теория представлений конечных групп и ассоциативных алгебр. М., Наука, 1969.

22. Лапшин A.B. Статистическое оценивание распределения слагаемого по серии наблюдений суммы независимых случайных величин на конечной абелевой группе. В сб.: Труды по дискретной математике. Т. 4. - М.: ФИЗМАТЛИТ, 2001, с. 129-148.

23. Логачев O.A., Смышляев C.B., Ященко В.В. Новые методы изучения совершенно уравновешенных булевых функций. Дискрет, матем., 2009, т. 22, №2, с. 51-74.

24. Левенштейн В. И. О некоторых свойствах кодовых систем. — Докл. АН СССР, 1961, т. 140, № 6, с. 1274-1277.

25. Левенштейн В. И. Об обращении конечных автоматов. — Докл. АН СССР, 1962, т. 147, № 6, с. 1300-1303.

26. Лидл Р., Нидеррайтер Т. Конечные поля: в 2-х томах. М., Мир, 1988. 822с.

27. Математические и компьютерные основы криптологии: Учебное пособие/Ю.С.Харин, В.И.Берник, Г.В.Матвеев, С.В.Агиевич. Мн.: Новое знание, 2003. - 382с.

28. Михайлов В. Г. О числе прообразов у выходной последовательности автомата. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 1994, т. 1, в. 1, с. 118-121.

29. Михайлов В. Г. Обобщение теоремы о числе прообразов у выходной последовательности автомата. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 1994, т. 1, в. 1, с. 122-125.

30. Михайлов В. Г. Асимптотическая нормальность логарифма числа прообразов выходной последовательности конечного автомата. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 1994, т. 1, в. 1, с. 126-135.

31. Михайлов В. Г., Чистяков В. П. О задачах теории конечных автоматов, связанных с числом прообразов выходной последовательности. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 1994, т. 1, в. 1, с. 7-32.

32. Подколзин А. С., Учшумлич . Ш. М. О решении систем автоматных уравнений. — Дискрета, матем., 1990, т. 2, в. 1, с. 94-103.

33. Проскурин Г. В. Задача различения гипотез о параметрах процесса обобщенного скользящего суммирования. — Дискрета, матем., 1993, т. 5, в. 3, с. 44-63.

34. Рожков М.И. К вопросу построения ортогональных систем двоичных функций с использованием регистра сдвига. Лесной Вестник, вып. 3, 2011, с. 164-169.

35. Рожков М. И. О суммировании цепей Маркова на конечной группе. — В сб.: Труды по дискретной математике. Т. 3., с. 195-214. М.: ФИЗМАТЛИТ, 2000.

36. Рожков М.И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных ш-грамм. Часть 1. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 2008, т. 15, в.4, с. 613-630.

37. Рожков М.И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных ш-грамм. Часть 2. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 2008, т. 15, в.5, с. 785-806.

38. Рожков М.И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных т-грамм. Часть 3. — Обозрение прикл. и промышл. матем., сер. дискрета, матем., 2009, т. 16, в. 1, с. 35-60.

39. Рожков М.И. О некоторых классах нелинейных регистров сдвига, обладающих одинаковой цикловой структурой. Дискрет, матем., 2010, т. 22, №2, с. 96-119.

40. Рожков М.И. Суммирование марковских последовательностей на конечной абелевой группе. Дискрет, матем., 2010, т. 22, № 3, с. 44-62.

41. Рожков М.И. Криптографические методы защиты информации на основе несимметричных криптосистем. Учебное пособие. М., МГИЭМ, 2000. 137 с.

42. Рожков М.И. Алгебра. Основы теории конечных групп, колец, полей. Учебное пособие. М., МГИЭМ, 2009. 82 с.

43. Рожков М.И. Криптографические методы защиты информации. Методические указания для самостоятельных работ. М., МГИЭМ, 2010. 27 с.

44. Рожков М.И. Криптографические протоколы. Методические указания для самостоятельных работ. М., МГИЭМ, 2010. 27 с.

45. Рязанов Б.В., Шанкин Г.П. Критерий равномерности распределения суммы независимых случайных величин на примарной циклической группе. -Дискретная математика (1997), том 9, - вып.1, с. 95-103.

46. Саранцев A.B. Построение регулярных систем однотипных двоичных функций с использованием регистра сдвига. Лесной Вестник, № 1(32), 2004, с. 164-169.

47. Саранцев A.B. Дисс. Канд. Тех. Наук (05.13.19 - Методы и системы защиты информации, информационная безопасность). - М., 2010. - 140с.

48. Сарманов О.В., Захаров В.К. Меры зависимости между случайными величинами и спектры стохастических ядер и матриц. Математический сборник, 1960, т. 52(94), № 4, с. 953-990.

49. Севастьянов Б.А. Исследование вероятностной зависимости выхода автомата от некоторых характеристик входа. В сб.: Труды по дискретной математике. Т. 5. -М.: ФИЗМАТЛИТ, 2002, с. 219-226.

50. Севастьянов Б.А. Условное распределение выхода автомата без памяти при заданных характеристиках входа. Дискретная математика, т. 6, в. 1, - 1994, с. 34-39.

51. Севастьянов Б. А., Нистяков В. П. О числе входных последовательностей, соответствующих выходной последовательности конечного автомата. — Обозрение прикл. и промышл. матем., сер. дискретн. матем., 1994, т. 1, в. 1, с. 96-107.

52. Смышляев C.B. Барьеры совершенно уравновешенных булевых функций. -Дискретная математика (2010), том 22, - вып.2, с. 66-79.

53. Солодовников В.И. О полугруппе, порожденной автоматными отображениями обратимого автомата. Труды по дискретной математике. Том 4, с. 231-242. М.: ФИЗМАТЛИТ, 2001.

54. Сумароков С. Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств. — Обозрение прикл. и промышл. матем., сер. дискретн. матем., 1994, т. 1, в. 1, с. 33-55.

55. Смирнов В. Г. Системы булевых уравнений рекуррентного типа. — Обозрение прикл. и промышл. матем., сер. дискретн. матем., 1995, т. 2, в. 3, с. 477-482.

56. Феллер В. Введение в теорию вероятностей и ее приложения, т. 1, М. Мир, 1967,-498 с.

57. Фомичев В.М. Симметричные криптосистемы. Краткий обзор криптологии для шифрсистем с секретным ключом. Учебное пособие. М., МИФИ, 1995. -44с.

58. Фомичев В.М. Дискретная математика и криптология. Курс лекций /под общей редакцией Н.Д.Подуфалова. М.: ДИАЛОГ - МИФИ, 2003. - 400с.

59. Чистяков В. П. Матричные функции от траекторий цепей Маркова. — Теор. вер. и ее примен., 1982, т. XXVIII, в. 2, с. 239-246.

60. Шерстнев В.И. Случайная величина, равномерно распределенная на конечной абелевой группе, как сумма независимых слагаемых. Теория вероятн. и ее применен., 1998, т. 43, в. 2, с. 397-403.

61. Шерстнев В.И. Разложение равномерного распределения на конечной абелевой группе. В сб.: Труды по дискретной математике. Т. 4. - М.: ФИЗМАТЛИТ, 2001, с. 315-318.

62. Холл М. Комбинаторика. М., Мир, 1970.

63. Anderson R. "Solving a class of stream ciphers", Cryptologia, 14(3):285-288, 1990.

64. Anderson R. "Faster attack on certain stream ciphers", Electr. Lett., 29(15): 13221323,1993.

65. Anderson R. "Why Cryptosystems Fail", in Communications of the ACM, v. 37, no. 11, pp. 32-40, 1994.

66. Anderson R. Searching for the Optimum Correlation Attack. Fast Software Encryption Second International Workshop, Springer-Verlag, 1995, pp. 137143.

67. Berlekamp E.R. Distribution of cyclic matrices in finite field. Duck. math. J., 1966, v. 31, N 1.

68. Burke C., Rosenblatt M. A Markovian function of a Markov chain. Ann. Math. Stat., (1958) 29, 1112-1122.

69. Bruer J.O. "On nonlinear combinations of linear shift register sequences", in Proc. IEEE ISIT, les Arcs, Frans, (June 1982), 21-25.

70. Cain T.R., Sherman A.T. "How to Break Giffords Cipher", in Proceedings of the 2nd ACM Conference on Computer and Communications Security (ACM, Nov. 94), pp. 198-209.

71. Cain T.R., Sherman A.T. "How to Break Giffords Cipher", CRYPTOLOGIA, v. XXI, 1997, n. 3, pp. 237-286.

72. Dickson L.E. Linear Groups. New York: Dover Publications, 1901, - 312 p.

73. Dawson E., Clark A. "Divide and conquer attacks on certain classes of stream ciphers", Cryptologia XVIII, n. 1, 1994, pp. 25-40.

74. Fredricksen H. A class of nonlinear de Bruijn cycles. J. Comb. Theory (A), 1975, N 19, p. 192-199.

75. Forre R. A Fast Correlation Attack on Nonlinearly Feedforward Filtered

76. Golomb S. W. Shift Register Sequences. San Francisco: Holden-Day, 1967.

77. Games R.A. and Chan A.H. A fast algorithm for determining the complexity of a binary sequences with period 2n. IEEE Trans, on Inform. Theory, v. IT-29, N 6, 1983.

78. Games R.A. There are no de Bruijn Sequences of Span n with Complexity 2n"'+n+l. Journal of Comb. Theory, Ser. A, v. 34, N 2, p. 248, 1983.

79. Gollman D., Chambers W.G. "Clock-controlled shift registers : A review", IEEE J. Selected Areas Commun., v. 7, pp. 525-533, 1989.

80. Golic J. D. "On the linear complexity of functions of periodic GF(q)-sequences", IEEE Trans. Inform. Theory, v. IT-35, pp. 69-75, Jan. 1989.

81. Golic J. D., Mihaljevic M.J. "A noisy clock-controlled shift register cryptanalytic concept based on sequence comparison approach", Advances in Cryptology -Eurocrypt 90, Lecture Notes in Computer Science, v. 473, pp. 487-491, SpringerVerlag, 1990.

82. Golic J. D. "On the security of shift register based keystream generators". In Fast Software Encryption, Cambridge Security Workshop, December 1993, pp. 90100, Springer-Verlag, Berlin, 1994.

83. Golic J. D. "Intrinsic statistical weakness of keystream generators". Advances in Cryptology Asiacrypt 94, pp. 91-103, Springer-Verlag, Berlin, 1995.

84. Golic J. D. " Towards fast correlation attacks on irregularly clocked shift registers", Advances in Cryptology Eurocrypt 95, pp. 248-262, Springer-Verlag, Berlin, 1995.

85. Golic J. D. "On the security of nonlinear filter generators". In Fast Software Encryption Third International Workshop, Cambridge, February 1996, pp. 173188, Springer-Verlag, Berlin, 1996.

86. Golic J. D. "Cryptanalyses of Alleged A5 Stream Cipher", Advances in Cryptology Eurocrypt 97, Lecture Notes in Computer Science, v. 1233, pp. 239255, Springer-Verlag, Berlin, 1997.

87. Huffman D. A. Canonical forms for information loss less finite state logical mashines. —IRE Trans. Circuit Theory, 1959, v. 6, spec, suppl., p. 41-59.

88. Kjeldsen K. On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions. J. Comb. Theory (A), 1976, N 20, p. 154-169.

89. Kannan R., Lenstra A.K., Lovasz L. Polinomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Number. Math. Of Comput., v. 50, № 181, p. 235-250, 1988.

90. Lenstra A.K., Lenstra H. W., Lowasz J.L. Factoring polynomials with rational coefficients Math. Ann. 1982, v. 261, p. 515-534.

91. Landau S. & Miller G. Solvability by Radicals is in polynomial Time, Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, p. 140-151.

92. Lempel A. On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers. IEEE Transactions Computers, 1970, C-19, p. 1204-1209.

93. Lempel A., Etzion T. On the Distribution of de Bruijn Sequences of Given Complexity. IEEE Trans, on Inform. Theory, v. IT-30, N 4, 1984.

94. Lempel A., Etzion T. Construction of de Bruijn Sequences of minimal complexity. IEEE Trans, on Inform. Theory, v. IT-30, N 5, 1984.

95. Meier W., Staffelbach O. "Fast Correlation attacks on certain stream ciphers". Journal of Cryptology, v. 1, 1989, pp. 159—176.

96. Peterson W.W. Error-Correcting Codes, John Wiley & Sons, Inc., New York, 1961.

97. Rose G. F. Output completeness in sequential machines. — Proc. Amer. Math. Soc., 1962, v. 13, № 4, p. 611-614.

98. Rizzi A. On the sum (modulo m) of two statistical variables. Bol. Un. Mat. Ital., (5) 13-A (1976), p. 163-167.

99. Sangjin L., Seongtaek C., Sangjoon P., Sungmo P. Conditional Correlation Attack on Nonlinear Filter Generators. Advances in Cryptology - ASIACRYPT-96, LNCS 1163, p. 360-367, 1997.

100. Stream cipher project of the European Network of Excellence in Cryptology. Available at http://www.ecrypt.eu.org/stream/

101. Yoeli M., "Nonlinear Feedback Shift Registers", IBM Development Lab., Poughkeepsie, N.Y., Tech. Report TR00.809,1961.

102. Yoeli M., "Counting with Nonlinear Binary Feedback Shift Registers", IEEE Transactions on Electronic Computers, Vol. EC-12, 1962, pp. 357-361.

103. Zierler N., "Linear Recurring Sequences", Linear Sequential Switching Circuits, W. Kautz ed., Holden-Day Inc., San Francisco, 1965.

104. Zurawiecki J. Boolean shift registers. Demonstratio mathematica, 1977, v. 10, N3-4, p. 405-415.