автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм

На правах рукописи

005006809

РОЖКОВ МИХАИЛ ИВАНОВИЧ

Алгоритмические вопросы идентификации конечных автоматов по распределению выходных ш-грамм

Специальность: 05.13.19 - Методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ

диссертации па соискание ученой степени доктора технических наук

1 2 ЯНВ 2012

Москва-2011

005006809

Работа выполнена в ФГБОУ ВПО «Московский государственный институт электроники и математики (технический университет)»

Официальные оппоненты:

доктор физико-математических наук, доцент Алиев Физули Камилович, г. Москва

Ведущая организация (предприятие)

Национальный исследовательский ядерный университет «МИФИ», г. Москва

Защита состоится 21 февраля 2012 г. на заседании диссертационного совета Д 212.133.03 в МИЭМ по адресу: 109028, Москва, Б. Трехсвятительский пер., д. 3.

С диссертацией можно ознакомиться в библиотеке МИЭМ

Автореферат разослан «_»_20_г.

Ученый секретарь диссертационного совета

доктор технических наук, профессор Саксонов Евгений Александрович, г. Москва

доктор физико-математических наук, доцент Фомичев Владимир Михайлович, г. Москва

доктор технических наук

Леохин Ю.Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность решаемых в работе задач

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

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

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

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

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

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

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

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

ми автоматами (как правило, линейными для гарантирования большого периода).

Роль узлов усложнения заключается:

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

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

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

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

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

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

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

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

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

- повышения обоснованности оценок качества соответствующих ГСП;

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

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

Цель и задачи исследования

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

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

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

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

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

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

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

пункту 54 Перечня научно-технических проблем обеспечения информационной безопасности РФ («Разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики»).

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

Положения, выносимые на защиту

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

2. Методы и алгоритмы построения классов фильтрующих генераторов, обладающих заданными вероятностями выходных в-грамм. Оценки числа классов статистической неотличимости и их мощности для случая функционирования генератора с узлом выборки (в том числе нерегулярной) с шагом Ь>п/2, п -длина накопителя.

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

Личный вклад соискателя

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

Апробация результатов диссертации

Основные теоретические результаты диссертации докладывались на научных семинарах Академии криптографии РФ, Математического института РАН, МГУ им. М.В.Ломоносова, НИИ Автоматики.

Публикация результатов диссертации

Основные результаты диссертации опубликованы в 11 научных работах.

Структура диссертации

Диссертационная работа состоит из перечня условных обозначений, введения, грех глав, заключения, библиографического списка, приложения. Полный объем диссертации составляет 265 страниц, включая приложение на 34 страницах. Библиографический список состоит из 106 наименований, включая 11 публикаций соискателя.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

Пусть

(1=1,..,*)

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

л(1Н|р(0(&Ь)||, &ЬеО, ¡=1,2,. ..,5. Под суммой цепей Маркова Г(1) понимается последовательность

Г={у.,Т2,..}, ъ=± у% Н,2,...

¡л 1

Решается задача получения эффективно проверяемых условий, при которых сумма б>2 марковских последовательностей также является простой одно-

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

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

Узлы суммирован™ широко используются в схемах ГСП. Важным при этом является вопрос о том, насколько узел суммирования улучшает статистические характеристики исходных последовательностей.

Задачи, решаемые в главе 1, являются обобщением аналогичных задач, связанных с изучением распределений сумм независимых случайных величин на конечных абелевых группах, которые рассматривались ранее в работах Н.Н.Воробьева, Ю.Н.Горчинского, Б.В.Рязанова, Г.П.Щанкина, В.И.Шерстнева и других.

В теоретическом плане рассматриваемые задачи касаются известной процедуры укрупнения состояний цепей Маркова. Условия сохранения марковости при укрупнении состояний простой однородной цепи Маркова исследовались в совместных работах В.К.Захарова и О.В.Сарманова и работах других авторов (Берке, Розенблат, Кемени, Снелл). Проверка условий марковости суммы цепей Маркова в общем случае связана с перебором I в |" вариантов, где 5 - число суммируемых цепей, то есть сложность имеет экспоненциальный характер по числу суммируемых цепей.

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

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

- построены полиномиальные по |(Э| и б алгоритмы проверки марковости суммы в>2 цепей Маркова с рациональными матрицами переходных вероятностей;

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

- получено описание устойчивых цепей Маркова.

Для заданной матрицы переходных вероятностей л=||р(д,Ь)||, под

характеристическими элементами (функциями) се строк понимаются элементы Р(ё) группового кольца ВО:

Р(§)=1 Р(&Ь)-Ь.

11 еС

Теорема 1.2.1. Элементы последовательности Г связаны в простую однородную цепь Маркова с некоторой матрицей переходных вероятностей не зависягцей от начального распределения исходных цепей если и только если в кольце Ий справедливы соотношения

п П р0)м (1.2.1)

1=1 1=1

для любых элементов сг; (¿=группы О таких, что

в &

¡=1 ¡=1

Есл и соотношения (1.2.1) имеют м ест о, т о величин ы

р(&Ю-к и р("Ш

связаны в кольце ВО следующим образом: ¡-1 1=1

Известно, что в случае абелевой группы в групповое кольцо Бв разлагается в прямую сумму полей.

Ввиду указанного разложения важным является следующее утверждение. Лемма 1.3.1. Если р'1'^), ей, г-1,2,...,з. являются элементами произвольного поля то соотношения (1.2.1) выполняются тогда а только тогда, когда выполнено одно аз условий:

а) существует такое]е{1,2что р®(%)=0 для всех '¿еС, где 0 - нулевой элемент поля 2*.'

б) существует такой гомоморфизм / группы С в мультипликативную группу поля <2*, при котором для каждого у е{1,2,...,з} и geG справедливо равенство

где 0 — нулевой элемент группы й.

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

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

Теорема 1.3.9. Если Б - абелева группа, то сумма цепей Маркова Г*0 с матрицами переходных вероятностей ^=\\р(''g,heG, 1—1,2,...,$, является цепью Маркова Г с матрицей переходных вероятностей тг=\\(1/\С\)\\ в том и только том случае, когда характеристические элементы

Л. а; л

II ев

строк матриц связаны в кольце ОС соотношениями

РФ(£)Ы,>(8)Л>, ё^С, ¡=1,2,.....г,

где сР е ОС такие, что

п ^ = ь.

1=1 Ь6С

Для циклической группы С=Хт вычетов по модулю числа ш кольцо ОО изоморфно кольцу 0[2]/(гш-1) многочленов по модулю многочлена 2™-1.

В этом случае проверка условий теоремы 1.3.9 сводится к вычислению наибольших общих делителей соответствующих многочленов и ее сложность составит 0(|0|3-б).

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

Следовательно, применение узла суммирования к устойчивым цепям Маркова не выводит за пределы простых однородных цепей Маркова (и в этом смысле не приводит к улучшению статистических характеристик результирующей последовательности).

Для заданного непустого множества БсС через Р(8) будем обозначать следующий элемент кольца БО:

Р(Б)=£ о(Ь).И,

II ей

где о(Ь)=(1/|5|) при ЪеБ и а(Ь)=0 при ЬгБ.

Теорема 1.7.1. Цепь Маркова Г со значениями в конечной абелевой группе С и с матрицей переходных вероятностей g,heG, является устой-

чивой в том и только том случае, когда существуют подгруппа НсС! и гомоморфизм <р: С—К}/Н, для которых выполнены равенства

(здесь под понимается смежный класс группы С? по ее подгруппе Н, являющийся образом элемента geG при гомоморфизме <р: О-^С/П, в частности, Р(0)=Н).

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

В частности, для элементарной абелевой 2-группы 0=(Р2)П сложность проверки соответствующих условий марковости составляет 0(5-|С|2-1о£|0|)=0(2ь-п-з) операций в поле действительных или рациональных чисел.

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

Данные вопросы связаны с исследованием автомата 11((Х,ХП,0), перерабатывающего входные последовательности ХьХг,... элементов множества X в выходные УьУг,-.. , У^й посредством функции £ Хп—Ю:

1=1,2,...

При этом входная последовательность ХьХ2,... рассматривается как последовательность независимых случайных величин со значениями в множестве X.

Идентификация автомата ^ХД"^) заключается в нахождении функции Г по известной выходной последовательности и неизвестном входе.

Вопросы идентификации такого сорта автоматов по распределению выходных Б-1рамм изучались в работах Б.А.Севастьянова, В.Г.Михайлова, А.Е.Жукова, В.П.Чистякова, О.А.Логачева, С.В.Смышляева, В.В.Ященко и других авторов.

Для случая произвольного конечного автомата со случайным входом вопросы, связанные с изучением распределений выходных й-грамм, рассматривались Р.Г.Бухараевым. Однако в силу сложности математических задач многие практически важные вопросы в данном направлении исследований все еще остаются нерешенными.

Основным направлением исследований главы 2 является построение эффективно реализуемых на вычислительной технике алгоритмов проверки статистической неотличимости (эквивалентности) автоматов Я{(Х,Х",0), получение оценок мощности и числа классов эквивалентных автоматов.

Для решения поставленных задач в диссертации развивается метод, связанный с исследованием вероятностных характеристик линейных комбинаций выходных знаков (полагается, что множество в - абелева группа).

Глава 2 состоит из десяти параграфов.

В §§ 2.1-2.3 вводятся основные понятия и получены основные результать: для общего случая.

Для заданной функции ф:Х'—>С через Цф) обозначим элемент группового кольца Бв, задаваемый следующим образом

Мф)=Е 1Фе1'8>

где под |ф£| понимается вероятность принятия функцией ф значения geG.

При этом мы предполагаем, что координаты векторов хеХ1 являются независимыми случайными величинами, распределение которых задается вероятностями рл на элементах множества X, £ Рх=1,Рх>0-

.<€ А"

Пусть Нс{1,2,...,п-1} - фиксированное подмножество множества Н0={1,2,...,п-1}.

8Ш(Н) -множество векторов з=(8(1),з(2),...,з(г-1)) таких, что 1<г<ш, «(¡)еН. В случае г=1 соответствующий вектор будем называть пустым вектором и обозначать б=0.

в(Н)=и 5т(Н).

Пусть задано произвольное множество «В» отображений группы «О» в себя. Тогда при ЬеВ и под произведением Ь^ понимается образ элемента § при отображении Ь:С—>0.

Пусть заданы:

£Хп->0,8=(5(1),5(2),...Хг-1))е8г(Н), Ъ=(ЬьЪ2,...,Ъг)еВг. Через Г[в,Ь] обозначим отображение множества хгп"8(1'""""5(г"1' в О, задаваемое следующим образом:

ф>,Ь](х)=Ь,-Я;хь.. .,хп)+Ь2-)Г(хмп+ь.. .,х2п_5П))+Ъ31(х:п.5ам2)+ь.. .,х3п.5(1Ь(2))+. . .+

Если э=0, то под понимается функция Ьг£

Определение 2.1.2. Функции ЬХ'-^С и (р:Хп^С будем называть

a) (т,Н)-неотличимыми, если Х(А>,Ь])=Л((р|>,Ь]) для любых 5=(5(1);5(2),...,5(г-1))б8т(Н)) Ь=(Ь1;Ь2,...,Ьг)еВг;

b) (с°,Н)-неотличимьши, если они (т,Н)-неотличимы при всех т=1,2,...;

c) неотличимыми (и использовать при этом обозначение £-ср) , если они (со,Н0)-неотличимы для Н0= {1,2,... ,п-1}.

Будем также говорить, что Г и ср различимы парой векторов в=(з(1),5(2),...,5(г-1))£8т(И) иЬ=(ЪьЪ2,...,Ъг)еВг, если Щ^Ь])^^,!)]).

Определение 2.2.6. Пусть Н - заданное подмножество множества {1,2,...,п-1}, У=УьУ2,-.- - выходная последовательность автомата Я/<Х,ХЛ,С). Тогда т-грамму

У«1)У«2). • -Укт), ¡(1)<1(2)<.. .<(т), назовем (ш,Н)-граммой, если для любого ке {1,2,...,т-1} существует число с1.=сЦк)еН такое, что ¡(к+1)-1(к)=п-<1>.

С точки зрения уменьшения сложности «прямого» алгоритма вычисления вероятностей выходных т-грамм на основе полного перебора всех входных последовательностей заданной длины, важным является получение оценок длины т, при которой из совпадения распределений выходных (т,Н)-грамм (для заданной пары автоматов) следует их совпадение при всех натуральных т.

Теорема 2.2.7. Пусть в - произвольное конечуюг множество, ср и \рг -произвольная пара отображений из X" в в, 11 - максимальный элемент множества Не{1,2,...,11-1}. Пусть при этом автоматы Я^Х.Х^) и Л^(Х,ХП,С) обладают одинаковым распределением выходных (т,Щ-грамм для т=2-|Х|ь-1.

Тогда данные автоматы обладают одинаковым распределением выход-пых (т,Н)-грамм для любого натурального т.

При 11=п-1 результат теоремы 2.2.7 является улучшением оценки ш=2-|Х|п-1, вытекающей из полученных ранее результатов Р.Г.Бухараева по идентификации вероятностных автоматов.

Теорема 2.2.11. Пусть С - конечное поле,/- произвольное отображение

из X в в, И - максимальный элемент множества Нс{1,2.....п-1}. Пусть при

этом автомат ЩХХ, й) обладает равновероятным распределением выходных (т,Н)-грамм для т^рс/1. Тогда данный автомат обладает равновероятным распределением выходных (т,Н)-гралш при любом фиксированном те{1,2,...}.

Следствие 2.2.12. Пусть О - конечное поле, /- произвольное отображение из Гей Пусть при этом автомат ЩХХ,0) обладает равновероятным распределением выходных т-граым для т=(ХГ'. Тогда данный автомат обладает равновероятным распределением выходных т-грамм при любом фиксированном т е{1,2,...}.

Пусть М(1),...>ад - различные классы (оо,Н)-неотличимых функций, на которые распадается множество всех функций £ХП->С; 1=П(Н) - число классов

(°°>Н)-неотличимости (при случайном выборе функции £Х"-»С), Ь - максимальный элемент множества Н. Теорема 2.3.2.

1. Если Х=С={0,1} и п>21г, тогда для числа / классов (<щН)-неотличимости справедлива оценка:

(оо,Н)-неотличимостн,

ЦМ(1)\

- среднее значение мощности класса

2. Пусть С={0,1}, п > 2Ъ и распределение вероятностей на элементах входного алфавита X - равномерное. Тогда для числа г классов (°о,Ц)-неотличимости справедлива оценка:

1<(\Х\п-п+1)у,

где у=\Х\2''.

Теорема 2.3.3. При выполнении условий теоремы 2.3.2 для среднего значения Q мощности классов (сс,Н)-неотличимости имеет место оценка: 0>со/ г,

где со - число всех отображений ^Х'—Хз , т=1/,

у=2т - дляусловий части 1 теоремы

и

/.1=(\Х["~2Н+1), 1/=\Х\2>1 - для условий части 2 теоремы.

В § 2.4 для случая равновероятного распределения на элементах входного множества X даны более простые аналоги основных понятий, введенных ранее для общего случая. Получены новые результаты относительно распределения выходных т-грамм автоматов Я{(Х,Хп,р2), в том числе описаны новые классы функций без запрета.

Утверждение 2.4.3. Если автомат ЩРгТ^г) обладает равномерным распределением выходных т-грамм для т=2"~', тогда данный автомат обладает равномерным распределением выходных т-грамм при любом фиксированном те{1,2,...}.

Отметим, что ранее С.Н.Сумароковым аналогичный результат был получен для ш= 22 •

В §§ 2.5-2.6 рассматриваются вопросы классификации автоматов 11){Х,ХП,Р2) относительно вероятностей встречаемости т-грамм в выборке с шагом п-Ь из выходной последовательности. При этом наиболее значимые результаты, касающиеся оценок мощности классов эквивалентности и их числа,

получены для случая классификации автоматов Я^Рг^)"^) относительно распределения значений линейных функций (от знаков выхода) с минимальным зацеплением аргументов.

При заданной функции £ Х°->Р2 через А=А(0 обозначим матрицу (аи)=(ац(0)> У=0,1, у которой элементы а^ вычисляются по формуле

*У= I .....

Кроме того, под А.,(1), 1=1,2,... понимаем величины

Х, = М0 = е"(А(0У-еА, 1=1,2,... , е^=(1,...,1).

Утверждение 2.6.2. Распределение выходных т-грамм в выборке с шагом п-1 из выходной последовательности автомата Л/Л, для любого

т е{ 1.2,...} полностью задается распределением трехграаш.

При заданном исходном множестве функций <3={£Х"-»Р2} через Мг будем обозначать класс неотличимости, содержащий функцию ГеС^, а через М(А.,Д2Дз) класс неотличимости, соответствующий тройке Х1Д2Д3.

Показано, что среди классов Мг =М(0,А.2(0Лз(0) в множестве сбалансированных функций £ХП—>Р2 класс наибольшей мощности соответствует автоматам (Рз^Л) с равновероятным распределением выходных т-грамм в выборке с шагом п-1 из выходной последовательности (т=1,2,...).

При этом мощность такого класса при п—>оо составляет |М(0,0,0)1= 22"я'-2-п+3, а мощность любого класса М(?ц Д2Дэ) при п-^оо не превосходит величины

2(1+о(1))-|М(0,0,0)|.

В §§2.7-2.9 разработаны детерминированные алгоритмы 2.7.2, 2.7.4, 2.9.4 и 2.9.8 проверки статистической неотличимости автоматов К((Х,Х",0) для случая бинарного выхода (|С|=2) и бернуллиевского входа. При этом алгоритм 2.7.4 использует только модульные арифметические операции над целыми числами стандартной длины.

Применительно к двоичным автоматам Rf(F2,(F2)n,F2) сложность реализации алгоритмов 2.7.2 и 2.7.4 оценивается соответственно в 0(24") арифметических операций в поле действительных (рациональных) чисел и 0(25") модульных арифметических операций над целыми 32-битными числами. Для реализации этих алгоритмов требуется память объемом 0(22") ячеек.

В приведенном ниже алгоритме 2.7.2 для заданной функции F=F(xb...,x„), X"->F2, через

A(F)=(a„p(F)), а.РеХ""1, а=(аь..„«„_,), Р=(Рь-,Р,м), (а„ pj€X), обозначается квадратная матрица размера I Хп"'| х| Хп"'|, элементы которой определены следующим образом:

а„р(р)=(-1)вд-рх..у=(у1,у2,--.,у0)=(аь...,ап.ьрп-1),х=р[1.1. При этом аар=0, если не существует вектора (уьУ2,---,Уп) длины п, начало которого (yi,y2,...,y„-i) совпадает с (ai,...,an.i), а окончание (у2,у3,...,уп) совпадает с (Pb---)Pn-l)-

Алгоритм 2.7.2.

0. Слроим матрицы Af>i =A(i-f) и А,,.( = А(гф), i=0,l;

1. Вычисляем векторы bfii= (р^-А^;) иЬ^= (р^' Афд), где P^iPo.aeX""1) - вектор-строка вероятностей ра векторов asX""1.

Если wtbr.^w^j) (под w(b) понимается сумма в поле действительных чисел координат вектора Ь) для некоторого ie{0,l}, тогда f и ф находятся в разных классах, и алгоритм завершен.

В противном случае полагаем i=l и строим базу Вь состоящую из максимального числа линейно независимых векторов множества {b,,b2}. где

bi=(bf-1, ЬфЛ), b2=(bf0, b9,0)

(при этом под (c,d) понимается вектор, началом которого является вектор "с", а окончанием вектор "d"), и переходим к следующему шагу.

Пусть BM={b]=(C|,d|),...,br(i.i)=(Cr(i-n,dr(i-i))} есть база, построенная на шаге i-1. Тогда на шаге i строим векторы (с,-А^Д-А,у) для всех t=l,2,...,r(i-l) и j=0,l.

Если для некоторых ^ выполнено неравенство у^А^и^А,,.,), то £ и ср находятся в разных классах, и алгоритм завершен.

В противном случае сравниваем ранги следующих множеств векторов г(ь1)=гапё{В,1},

г0=гап§{ ВмиКс.-АцД-Аад)! 1=1,2,...,г(И); ¿=0Д>>.

Если г(1-П=т(Г). то Р-ф, и алгоритм завершен. Если г(И)<г(1), то строим базу В|, состоящую из Вм и г(1)-г(1-1) дополнительных векторов из множества

так, чтобы полученные г(1) векторов были линейно независимы, и переходим к следующему шагу ¡+1.

Сложность алгоритма оценивается величиной 0(|Х|4") операций в поле действительных (рациональных) чисел. Кроме того, для реализации алгоритма требуется 0(|Х[2п) ячеек памяти.

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

Пусть вероятности рх являются рациональными числами, т.е. для некоторых целых I и 1(х):

рх=1(хК', 1(х)>0, £ 1(х) = I, хеХ.

хеХ

Заметим, что для определения неотличимости функций { и <р в алгоритме 2.7.2 вместо вектора р~* можно взять любой вектор Ео^О, а вместо матриц Ау и А^ - матрицы егА^ и £гАф.;, ¡=0,1, е,*0. При этом вместо величии Х(£Ь) и А.(ср,Ь), ЬеС1, вычисляются и сравниваются величины £0'(£1)Ш'ЦОД и Е0-(£1)т-^((р,Ь)). Если положить £о=10_!, £1=1, то вектор Е0р^ и матрицы Е|-А^ , Е|-А,у будут целочисленными.

В этой связи для дальнейшего рассмотрения полагаем, что в алгоритме 2.7.2 вектор р^ заменен целочисленным вектором t^'-p"*, а матрицы Af,-, и Аф.; заменены целочисленными матрицами t-Af.i и t-A^.;.

Пусть р - заданное простое число. Будем называть функции f и ср неотличимыми по модулю р (используя при этом обозначение f~cp (mod р)), если вывод о неотличимости этих функций есть результат работы алгоритма 2.7.2 при условии, что все использующиеся в нем целочисленные матрицы и векторы рассматриваются над полем Zp вычетов по модулю р. В противном случае будем говорить, что функции f и ф отличимы по модулю р.

Другими словами, f~cp (mod р), если для любых m =1,2,... и beGm целочисленные величины f1+m"'-X(f,b) и t"+ra"'-A.(cp,b) равны по модулю р.

Для заданного множества pi,...,ps различных простых чисел через Q(Pi,-,Ps) обозначим множество всех пар {f,cp} функций таких, что f~(p (mod р) для любого pe{pb...,ps}.

Теорема 2.7.3. Пусть pi,...,ps - набор ^ различных простых чисел, для которых выполнено неравенство

I logifpi > (2 \Х\"'1 +,1-2) -log2(t) +1 (2.7.6)

Тогда f~q> в том и только том случае, если f~(p (mod р) для любого р e{ph...,ps}.

Таким образом, если вероятности элементов входного множества X рациональны, можно использовать алгоритм, основанный на выявлении принадлежности заданной пары функций f,<p множеству Q(p],...,ps), который фактически заключается в s-кратном применении алгоритма 2.7.2 с использованием модульных операций в соответствующих полях ZP.

Алгоритм 2.7.4.

На этапе j исследуется, являются ли функции f и <р неотличимыми по модулю pj. Если установлено, что функции отличимы по модулю р^ то алгоритм завершает работу. В противном случае осуществляется переход к этапу j+1.

Для простоты обозначений полагаем p=pj. Тогда этап j состоит из следующих шагов (при этом предполагается, что j=l, либо уже установлено, что f~<p (mod р) для всех ре {pb...,pj_!}.

0. Строим целочисленные матрицы Af.j = t-A(i-f) и AT.i = t-A(i-ip), i=0,l, рассматриваемые как матрицы над полем Zp вычетов по модулю р.

1. Вычисляем целочисленные векторы

bf,i=(tn"' p^-Af.i) и Ъ^гГ'.р^Ам), рассматриваемые как векторы над полем Zp (здесь, как и в алгоритме 2.7.2, р~>=(ра,а£Хп~') - вектор-строка вероятностей ра векторов аеХп"').

Если wibfj^wib^j) (mod р) для некоторого ie{0,l}, тогда {f,(p} gQ(pi,...,ps), и алгоритм завершен (под w(b) понимается сумма в поле Zp координат вектора Ь).

В противном случае полагаем j=l и строим базу В), состоящую из максимального числа линейно независимых векторов множества {ЪьЬг}, где

bi=(bti, ЬфЛ), b2=(bf.0, Ьф.0), и переходим к следующему шагу.

Пусть Bj.i={bi=(cbdi),...,br(j.i)-(cr(j.j),dj(j.i))} есть база, построенная на шаге j-1. Тогда на шаге j строим векторы (c,-Af.i,d,-Alp для всех t=l,2,...,r(j-l) и ¡=0,1.

Если для некоторых i,t выполнено неравенство w(CfAf.i)^w(dfAl|),i) (mod р), тогда {f,cp} gQ(pi,...,ps), и алгоритм завершен.

В противном случае срав1шваем ранги следующих множеств векторов (напомним, что векторы рассматриваются над полем Zp) г(И)=гап«{Вя},

r(j)=nmg{ Bj.Iu{(c,-Af,i)dt-A<p,i)| t=],2,...,r(j-l); i=0,l}}.

Если, Г0"1)=ГС))> то (то(1 р), и переход к этапу

то строим базу В;, состоящую из В,.( и г(])-г(]-1) дополнительных векторов из множества

{(с-А^.ёЛр,;)! (с,с1)еВ>ь 1=0,1}

так, чтобы полученные г® векторов были линейно независимы, и переходим к следующему шагу 1.

Пусть q - стандартная длина (в битах) целых чисел для использующегося типа процессора. Пусть также {р1>р2>—>р3>.-.} заданное множество различных простых чисел, не превосходящих . Тогда для проверки соотношения (2.7.6) (при реализации алгоритма 2.7.4) можно воспользоваться следующими оценками.

Пусть

2ч/2>р,>р2>...>2р.

Тогда неравенство (2.7.6) будет выполнено при выполнении неравенства

5>р-1-((2-|Х|"-1 +п-2)-1о&(1)+1). Таюш образом, сложность алгоритма 2.7.4 по числу операций в сравнении с алгоритмом 2.7.2 может возрасти не более чем в 5 раз, где 5 = р1-((2-|Х|п",+п-2)-1о22(1)+1)+1, и составит О([Х|5п-1о§20 модульных операций над целыми числами.

Рассмотрим далее случай {=2. который соответствует двоичному входному алфавиту Х={0,1}. В этом случае неравенство (2.7.6) будет выполнено, если верно неравенство: р-э > 2° +п-1.

Пусть д=32 (случай использования 32 разрядного процессора) и используются простые числа из промежутка от 216 до 215. Число простых чисел в этом промежутке равно 3030. Минимальные значения в, удовлетворяющие при р=15 неравенству > 2" +п-1, приведены ниже в таблице 1.

Таблица 1

N 3 4 5 6 7 8 9

Б 1 2 .3 5 9 18 35

N 10 11 12 13 14 15 16

Б 69 138 274 547 1094 2186 4371

Таким образом, при использовании простых чисел из промежутка от 216 до 215 алгоритм 2.7.4 позволяет устанавливать неотличимость любой пары булевых функций от п<16 переменных.

На основе алгоритмов 2.7.2 и 2.7.4 получена полная классификация булевых функций ог 4 переменных ^х^^аО по распределению вероятностен выходных я-грамм соответствующих автоматов (Р2)4,Р2) при условии равновероятного входа. Получены также все двоичные функции без запретов от п=5 переменных, а также квадратичные функции при п=6 и п=7.

Что касается алгоритмов 2.9.4 и 2.9.8, то они предназначены для проверки статистической неотличимости двоичных автоматов 1^2,(Рг)2" Л), функция выхода которых есть сумма двух функций от непересекающихся аргументов £= № (х.1 ,х2,... ,х„)+^(хп+1 ,хп+2, • • ■ ,х2„).

Указанные алгоритмы имеют сложность 0(25п), и для их реализации требуется память порядка 0(2'°). Сложность же реализации в данном случае общего алгоритма 2.7.2 составила бы 0(28") операций и 0(24") ячеек памяти.

При этом получены оценки длины I, при которой совпадение вероятностей выходных {-грамм у соответствующих автоматов К^ХД2"^) равносильна их статистической неотличимости.

Теорема 2.9.3, Если функции £=№,£>) и <р=(<р1,<р2) являются I-неотличимыми для Г-=2\Х\"~' +п-1, тогда они неотличимы.

Теорема 2.9.7. Если автомат К/Х.Х1"^, /=(/¡,/0, обладает равновероятным распределением выходных ?-грамм для 1=\Х\л~'+п-1, тогда данный автомат обладает равновероятным распределением выходных т-грамм для любого фиксированного т=1,2,....

Отметим, что данные оценки для величины t значительно ниже общих оценок (t=2-|X|2n*'-l, t=|X|2n"'), применимых для любой функции f:X2n->F2.

В §§ 3.1-3.4 главы 3 рассматриваются вопросы построения классов автономных регистров сдвига R(f)=R(G°,5f) с нелинейной обратной связью f: Gn —> G, функции переходов которых 6(=ЗКУьУ2,---,Уп)=(У2!Уз,---,Уп,%ьУ2,-.-,Уп)) обладают заданной цикловой структурой.

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

Пусть множество G - конечное коммутативное кольцо. Определение 3.1.10. Функции f,cp:Gn-^G будем называть эквивалентными (и использовать обозначение f~(p), если для некоторой биекции X:Gn—>G" выполняется уравнение Коши:

Х-8ГХ"'=5Ф

Пусть Цг)=]Г a¡ z'_1 eG[z] - многочлен над кольцом G, í=.i

(p:Gn"m+l—>G - функция от (n-m+1) аргументов, m<n.

Через А.»ф и <рЛ будем обозначать отображения (функции) G°—>G следующего вида:

(А..ф)(х)= ¿ a¡ ф(х;,х|+1,...,Xj+n.m), (ф.А.)(х)=ф(А1(х),Л2(х),...,Ап.т+1(х)),

/--I

где x=(xi,x2,...,xn)eG", Aj(x)=¿ агхи.ь j-=l,2,...,n-m+l.

í-t

Определение 3.1.11. Пусть L:Gn->G - фиксированное отображение, A.(z)=¿ a¡-zMeG[z], ф:С~т+|—>G.

Тогда функцию будем называть (<рД,Ь)-композицией, если

Дх)=(<рЛ)(х)+Ь(х), (3.1.3)

и (>.,ф,Ь)-композицией, если

ПхНХ.ф)(х)+Цх).

Каждой функции ^С—>0, являющейся (фД,Ь)-композицией, поставим в соответствие множество МхД, состоящее из функций

В теоремах 3.2.6 и 3.2.7 наиболее широко отражены условия эквивалентности (Х.,ф,Ь) и (фЛ,Ь) композиций.

Пусть Х(г)=2] аГ2"1е¥2[т.], а]=аш=1, т>1. Через Лх обозначим подпространство, порожденное (в множестве линейных булевых функций) функциями агх„2 а;-х;+0.т}, и через Ла^) - смежный класс по подпро-

странству Лх, содержащий заданную линейную функцию g. Через МпО^.-.-ЛХ 1;еО, будем обозначать циклическую пхп матрицу с первой строкой

Теорема 3.2.6. Пусть функг/ия £:(Р2)П—>¥2 является (<р.Х,Ь)-композицией и задана представлением (3.1.3).

Тогда фунщии Г(х)=(ф«Х)(х)+Цх) и 11(х)=(^»ф)(х)+Цх) являются эквивалентными, если выполнено одно из условий:

1. ЬеЛх(я), а1х„.т^+1;

2. ЬеЛд^), g=x1 и циклическая матрица Мп(аьа2,...,ат) является невырожденной;

»-1

3. ЬеЛд^), ё=Х\, (Х(2),2+1)=1, г\ п=р - простое число такое, что чис-

¿=0

до два является первообразным корнем по модулю р;

4. ЬеЛ,М е=х1, (Х(г),г+1 )=1, п=2в, <1 б {1,2,...};

5. LeAx(g), g=xbA.(z)=f; ги, (X(z),z+l)=l, (n,m)=l;

6. *.(z)=l+z+z2, LeAx(g), где

g(x)e{ xi+xn_2+xn.,, xi+xn.2+x„, x,+xn.i+x„} при nsO (mod 3), g(x)s { xi+xn.2+x„.b X|, xi+xn.i+x„} при nsl (mod 3), g(x)e { xb x,+xn.2+xn> x,+x„.i+xn} при n=2 (mod 3).

Теорема 3.2.7. Пусть функция f:(F2)"-»F2 является (<f>,X,L)-K0Mn03mjueii и задана представлением (3.1.3), X(z)=gr...-gk есть разложение многочлена X(z) в произведение неприводимых множителей g;(z), i-l,2,...,k (многочлены gi не обязательно различны).

Пусть при этом для каждого фиксированного ie {1,2,...,к} функция f(x)=(cp.X,)(x)+L(x)=((9»(>./gi))«gi)+L(x), рассматриваемая как ((p.(>Vgi),gj,L)-композиция, удовлетворяет одному из условий 1-6 (не обязательно одному и тому же при разных i) теоремы 3.2.6.

Тогда функции множества M>.(f) попарно эквивалентны.

Отметим, что использующийся в работе способ построения эквивалентных функций на основе (<p,X,L) и (Х,(р,Ь)-композиций приводит к классам эквивалентных функций M(f), которые имеют одну и ту же степень нелинейности.

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

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

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

Пусть - задание преобразования (Р2)п-КР2)т в виде системы

координатных функций;

6г. - подстановочное преобразование векторов пространства (Р2)а, осуществляемое регистром сдвига с аффинной функцией обратной связи

Ь=Ь(х1,х2,...,хп)'=2] Ь;Х;+Ь(|, Ь;б{0,1}, 1)1=1, действующее на вектор

х=(хьх2,...,хп)е(Р2)" по правилу

51.(х1 ,х2,... ,хп)=(х2,х3>... ,х„,Цх, ,х2>... ,хп)); - отображение (Рг)"—>(Рг)" задаваемое следующей системой координатных функций

(ГАИадСхМВДДСбО«),...^((50п-'(х))), хе(Р2)п. Ранее в главе 3 рассматривались некоторые классы биективных отображений соответствующих регистрам сдвига с нелинейной функцией обратной связи Ь.

Систему (множество) булевых функций от п переменных (^Гг,...,^), т<п, будем называть ортогональной, если при любых двоичных Я.ьЯ.2,...Лт система уравнений >^=Г,(х), j=l,2,...,m, имеет ровно 2п"га решений в (Рг)"- Необходимым условием биективности отображения А=(£51.) является ортогональность любого подмножества его координатных функций.

В работе получено полное описание класса нелинейных функций от трех переменных 5=Г(хьХ2,...,хп)=Г(ХьХ2,Хз) и соответствующих аффинных функций

Цх|

,х2,..,,хп)—Ь,Х(+Ьв, при которых система булевых функций (У!,У2,---,Уп-|), у,=^(50"'(х)), является ортогональной.

Теорема 3.5.1. Пусть ri>3, Фi^{xlx2\x3+d,xi+ d2x2+d„/d,-=0,1}, <p2={xi+x2xi+d,xi+d1xi+d0, !di=0,1}, ffci.x;.....-О еФ, wl>2,

L(xhxb...,x,i =x, + £ b0, bie{0,l}. i-2

Тогда система функций yi,y2,...,y„.i, yi-fifSj)''1 (х)), является ортогональной в том и только том случае, если выполнены условия

1) n=2k+I - нечетное число;

2) di+d,=l;

3)/еф1 11 Ь_, = Ь3=...=Ьп=0, Либоf£Ф2 U Ь2=Ь4=...=Ьп.1 = 0.

Теорема 3.5.6. Пусть п> 5, f-f(xi,x2,x3) — нелинейная функция от трех ар-

п

гументов, L(x],x2, ...,xj = х; + Ьрс,- + Ь0, Ь/е{0,1).

Тогда система функций (у'иуг, ■■■.Уп-i), yi~f((8[)'~'(х)), является ортогональной в том и только том случае, если п-нечетно и функции/и L удовлетворяют условиям теоремы 3.5.1.

В определенных случаях необходимым условием биективности отображения (f,5i,) является отсутствие у функции f запретов.

Утверждение3.5.8, Пусть n>2k4+k'lf=f(xhx2,...,xk), deg(f)>l, k>l. Если ортогональна система функций (уиУ2,—,Уп-0- yi~f((S{/'(х)), тогда функ-гцш f, рассматриваемая как функция от к переменных, не имеет запретов.

Как показано А.В.Саранцевым, в классе функций, фигурирующих в условиях теоремы 3.5.1, существуют функции f и L, отвечающие биективному отображению (f,Sj_).

ЗАКЛЮЧЕНИЕ

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

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

1. В главе 1 разработан новый метод на основе математического аппарата групповых колец, на основе которого получено:

1.1. Новые эффективно проверяемые необходимые и достаточные условия марковости суммы цепей Маркова, заданных на конечной абелевой группе; основанные на данных условиях и обладающие полиномиальной по |0| и б вычислительной сложностью алгоритмы проверки того, что сумма цепей Маркова с рациональными матрицами переходных вероятностей также является цепью Маркова ([1],[6]).

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

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

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

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

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

2.1. Получены верхние оценки для числа классов неотличимых автоматов ^{ХД"^) относительно вероятностей т-грамм в выборке из выходной последовательности (в том числе и нерегулярной) с шагом ([2]).

2.2. Разработаны детерминированные алгоритмы проверки статистической неотличимости автоматов К[{Х.ХГ,,С) для случая бинарного выхода (|С|=2) и бернуллиевского входа.

Применительно к двоичным автоматам И^Р:,^)"^) сложность реализации данных алгоритмов оценивается соответственно в 0(24п) арифметических операций в поле действительных (рациональных) чисел и 0(25п) модульных арифметических операций над целыми 32-битными числами. На основе данных алгоритмов проведена полная классификация автоматов К^г^У^) длины п=4, а также получено описание всех двоичных функций без запретов от пяти переменных ([4]).

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

Г(хьх2,.. .,Х2п)=Г1(ХЬХ2,. • .,ХП)+Г2(хп , [,хп .,х2„) есть сумма двух функций от непересекающихся аргументов. Сложность данных алгоритмов 0(25"), и для их реализации требуется память 0(23п) ячеек ([4]).

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

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

Рекомендации по практическому использованию результатов

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

2. Результаты глав 2 и 3 могут быть использованы при построении и обосновании свойств ГСП на основе использования неавтономных и автономных фильтрующих генераторов. Примерами данного вида ГСП являются схемы типа А5, DECIM, GRAIN, ORYX, LIL1-128 и др. Данные результаты могут быть также полезны при построении ГСП с заданными характеристиками выхода на основе нелинейных регистров сдвига и фильтрующих генераторов небольшой длины.

3. Результаты диссертации использовались ФГУП «НТЦ «Атлас» при выборе параметров и обосновании свойств датчика псевдослучайных чисел для отечественного бесконтактного микроконтроллера, предназначенного для использования в паспортно-визовых документах нового поколения, о чем имеется соответствующий акт о внедрении.

Кроме того, результаты диссертации используются в качестве учебно-методических материалов в МИЭМ (для студентов, обучающихся по специальности 090102 - «Компьютерная безопасность»).

Список публикаций соискателя по теме диссертации

Статьи в научных журналах:

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

2. Рожков М.И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм. Часть 1. — Обозре-

ние прикл. и промышл. матем., сер. дискрета, матем., 2008, т. 15, в. 4, с. 613-630.

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

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

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

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

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

Учебно-методические материалы:

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

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

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

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

зХ

ДЛЯ ЗАМЕТОК

Подписано в печать 14.11.2011. Формат 60x84/16 Бумага типографическая. Ризография. Тираж экз. Заказ № Московский государственный институт электроники и математики (технический университет) 109028, Москва, Б. Трехсвятительский пер., д. 3. Отдел информационной полиграфии Департамента информационных технологий Московского государственного института электроники и

математики

Тел.: 8-(495)-916-88-73, 8-(495)-916-89-25

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

Введение.

Глава 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. Ортогональные системы двоичных функций, построенные с использованием нелинейной функции и линейного регистра сдвига.

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

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

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

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

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

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

Во многих случаях при построении ГСП с целью обеспечения необходимой скорости функционирования к ним предъявляются требования по простоте технической реализации. Особенно данное требование важно для ГСП, предназначенных для реализации на микропроцессорах интеллектуальных карт, обладающих сравнительно ограниченными вычислительными возможностями (см., например,[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 Перечня научно-технических проблем обеспечения информационной безопасности РФ («Разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики»).

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.