Аналіз комбінаторно-алгебраїчних моделей ін’єктивних дискретних перетворювачів інформації

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Аналіз комбінаторно-алгебраїчних моделей ін'єктивних дискретних перетворювачів інформації

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Загальна характеристика роботи

Актуальність теми. Проблема аналізу поведінки ін'єктивних дискретних перетворювачів інформації, біля витоків якої стояв К. Шеннон, є однією з центральних проблем кібернетики. Інтерес до цієї проблеми в значній мірі викликано її прикладним значенням, зумовленим потребами сучасних інформаційних технологій. Ця проблема має і самостійний теоретичний інтерес для теорії автоматів, теорії булевих функцій та комбінаторного аналізу, які завдяки криптографії за останню декаду отримали інтенсивний розвиток за рахунок виділення напрямків, що суттєво спираються на моделі та методи сучасної алгебри та теорії чисел.

Задачі аналізу комбінаторно-алгебраїчних моделей ін'єктивних дискретних перетворювачів інформації автоматного типу виникають у криптографії при передобчисленнях, призначених для руйнування частот та дифузії інформації, а також при побудові алгоритмів потікового шифрування. Зростаючі вимоги до якості сучасних шифрів ставлять питання про теоретичний аналіз обчислювальної стійкості алгоритмів, які реалізовано даними моделями. Це зумовлено тим, що широкий спектр недостатньо теоретично пророблених з позиції криптографії, часто недостатньо порівнянних одна з одною моделей, призводить до того, що зараз основним методом дослідження обчислювальної стійкості криптографічних алгоритмів є статистичний аналіз їх якості. Недоліки, які припускаються на цьому етапі, а також стрімкий розвиток засобів обчислювальної техніки є основними причинами достатньо частого перегляду криптографічних стандартів у всьому світі.

Ін'єктивні дискретні перетворювачі, представлені булевими функціями, досліджено О.О. Молдовяном та О.О. Логачовим, а абстрактними скінченними автоматами - Ш. Івеном, Д. Хаффменом, та А.А. Курмітом. Сучасний стан проблеми аналізу автомата по його зовнішній поведінці представлено у дослідженнях О.В. Бабаша. Аналізу рекуррентних послідовностей над кільцем, які розглядаються в якості моделей псевдовипадкових генераторів, присвячені дослідження О.С. Кузьміна, В.Л. Куракіна, О.А. Нечаєва. Теоретико-числові моделі ін'єктивних дискретних перетворювачів досліджено У. Діффі, Н. Кобліцем, Р. Рівестом, А. Шаміром, М.Е. Хеллменом, Л. Едельманом, комбінаторно-алгебраїчні моделі - М.М. Глуховим та Д.Р. Стінсоном, а стохастичні моделі - А.Ю. Зубовим та С.О. Осмоловським. Увесь спектр моделей ін'єктивних дискретних перетворювачів, призначених для вирішення модельних задач криптографії, розглянуто О.П. Алферовим, Ж. Брассаром, Б. Шнайєром.

Дисертаційна робота є логічним розвитком досліджень О.П. Алферова, О.В. Бабаша, А. Гілла, О.Ю. Зубова, О.С. Кузьміна, В.Л. Куракіна, О.О. Молдовяна, О.О. Нечаєва, С.О. Осмоловського, Д.В. Сперанського, О.В. Черемушкіна.

Робота присвячена аналізу ін'єктивних дискретних перетворювачів інформації автоматного типу, представлених комбінаторно-алгебраїчними моделями, та призначених для вирішення модельних задач криптографії. Досліджено автоматні моделі, представлені у вигляді: а) ансамблю операцій підстановки, який реалізовано комбінаторними конструкціями спеціального типу, керованного псевдовипадковим генератором; б) системою рівнянь над скінченним кільцем.

Прикладна актуальність досліджень визначена розвитком математичних основ криптографії, призначених для розробки теоретичних методів аналізу і синтезу сучасних шифрів. Теоретичне значення та актуальність визначаються тим, що досліджуються нові нетривіальні класи автоматів.

Зв'язок роботи з науковими програмами. Дослідження з проблеми дисертаційної роботи проводилися у відповідності з планами наукових досліджень ІПММ НАН України у рамках наступних відомчих тем НАН України: «Алгебраїчні, комбінаторні, логічні та еволюційні методи дослідження дискретних та безперервних систем та їх застосування до задач ідентифікації та керування» (державний реєстраційний номер 0104U000863) - 2004-2008 рр., «Вирішення задач захисту інформації на основі динамічних систем над скінченними алгебраїчними системами» (державний реєстраційний номер 0105U000270) - 2005-2006 рр., «Обернені задачі теорії керування і сучасні комунікаційні технології» (державний реєстраційний номер 0107U000466) - 2007 р.-т.ч.

Мета і задачі дослідження. Метою дисертаційної роботи є систематичний дескриптивний, алгоритмічний та метричний аналіз комбинаторно-алгебраїчних моделей автоматного типу деяких класів ін'єктивних дискретних перетворювачів інформації.

У роботі ставляться і вирішуються наступні задачі:

- побудувати скінченний автомат, для якого псевдовипадковий генератор керує бінарним відношенням, що реалізує сім'ю ін'єктивних дискретних перетворювачів інформації, представленої у неявному вигляді, та для якої існує швидкий алгоритм, що один за одним породжує елементи другої проекції бінарного відношення;

- з позиції вирішення модельних задач криптографії дослідити клас лінійних автоматів над кільцем ( просте число, );

- з позиції вирішення модельних задач криптографії дослідити Guckenheimer and Holmes cycle автомат та free-running автомат над кільцем , які є скінченно-автоматними аналогами модельних хаотичнх динамічних систем, та у рівняннях яких присутні поліноми 3-го ступеня й експонента.

Об'єкт дослідження - ін'єктивні дискретні перетворювачі інформації.

Предмет дослідження - комбінаторно-алгебраїчні моделі деяких класів ін'єктивних дискретних перетворювачів інформації, які призначені для вирішення модельних задач криптографії.

Дослідження у роботі виконано згідно наступних двох позицій. По-перше це розробка та аналіз призначених для вирішення модельних задач руйнування частот букв та дифузії інформації математичних моделей, у яких псевдовипадковий генератор керує бінарним відношенням, що представляє у неявному вигляді ансамбль операцій підстановки. По-друге, це систематичний аналіз лінійних та деяких класів нелінійних симетричних автоматів над скінченним кільцем.

Методи дослідження. Теоретичну основу досліджень складають моделі та методи комбінаторного аналізу, дискретної математики, теорії скінченних алгебраїчних систем, теорії чисел, теорії автоматів та теорії систем.

Наукова новизна результатів. У дисертаційній роботі отримано такі нові результати:

- вперше досліджено дискретний перетворювач, побудований на основі керуємого бінарного відношення, яке представлено регулярною комбінаторною структурою, та призначений для вирішення задачі руйнування частоти букв у початковому тексті;

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

- систематично досліджено клас лінійних автоматів над скінченим кільцем; виділені підмножини автоматів, які допускають обернення, а також множини автоматів які характеризуються в термінах матриць та графів переходів; досліджено еквівалентність автоматів та їх внутрішніх станів;

- систематично досліджено клас симетричних нелінійних автоматів над скінченним кільцем, для яких зміна внутрішніх станів здійснюється згідно поліномів 3-го ступеня, або згідно з показниковою функцією;

- охарактеризовано множини нерухомих точок для досліджуваних у роботі автоматів над скінченним кільцем;

- вирішено задачі параметричної ідентифікації та ідентифікації початкового внутрішнього стану для досліджуваних у роботі автоматів над скінченним кільцем.

Всі отримані в роботі результати є новими, достовірними, завершеними і строго доведеними.

Практичне значення отриманих результатів. Робота має теоретичний характер. Розроблені у роботі моделі, які призначені для вирішення задач руйнування частот букв та дифузії інформації доведено до алгоритмів, що можуть бути використані при розробці математичного забезпечення, яке реалізує нестаціонарні потікові шифри. Розроблені у роботі методи вирішення задач параметричної ідентифікації, ідентифікації початкового внутрішнього стану, та аналізу множини нерухомих точок для автоматів над скінченним кільцем можуть бути використані при теоретичному аналізі обчислювальної стійкості потікових шифрів, які побудовано з використанням цих автоматів.

Особистий внесок. Усі наукові результати, які ввійшли до дисертаційної роботи, одержано здобувачем особисто і самостійно. Науковому керівнику належить загальна постановка задачі. Дисертанту належать фактичні результати робіт. У спільній публікації дисертанту належать тверження 1.6, 1.7 та наслідки 1.8, 1.9, п. 1.4, пп. 2.1-2.3, п. 6.6 та розділ 5, у яких відображені основні результати дисертації.

Апробація результатів. Основні результати роботи доповідалися та обговорювалися на:

- IX-му Міжнародному семінарі «Дискретная математика и ее приложения» (ДМ-07) (РФ, м. Москва, МДУ, 2007 р.);

- VI-й Сибірській науковій школі-семінарі з міжнародною участю «Компьютерная безопасность и криптография» (SIBERCRYPT'07) (РФ, м. Горно-Алтайськ, ТДУ і ГАДУ, 2007 р.);

- VII-й Міжнародній конференції «Идентификация систем и задачи управления» (SICPRO'08) (РФ, м. Москва, ІПУ РАН, 2008 р.);

- VII-й Сибірській науковій школі-семінарі з міжнародною участю «Компьютерная безопасность и криптография» (SIBERCRYPT'08) (РФ, м. Красноярськ, ТДУ і СДАЕУ, 2008 р.);

- IX-й Міжнародній конференції «Системний аналіз та інформаційні технології» (SAIT'08) (м. Київ, Національний технічний університет «Київський політехнічний інститут», 2008 р.);

- 3-му Міжнародному радіоелектроному форумі «Прикладна радіоелектроніка. Стан та перспективи розвитку» (МРФ-2008) (м. Харків, ХНУРЕ, 2008 р.);

- Міжнародній науковій школі-конференціх «Тараповские чтения» (м. Харків, ХНУ, 2008 р.);

- VIII-й Міжнародній конференції «Идентификация систем и задачи управления» (SICPRO'09) (РФ, м. Москва, ІПУ РАН, 2009 р.);

- семінарах відділу теорії керуючих систем і лабораторії дискретної математики і прикладної алгебри Інституту прикладної математики і механіки НАН України (2005-2009 рр.).

Публікації. Основні результати дисертації опубліковано в 17 роботах, з яких 8 - статті у фахових періодичних виданнях, затверджених ВАК України, 1 - монографія (у співавторстві), 5 - доповіді, що опубліковані у працях міжнародних конференцій, 3 - тези доповідей міжнародних конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, чотирьох розділів, розбитих на підрозділи, висновків та списку використаних джерел. Загальний обсяг дисертації - 128 сторінок. Список використаних джерел містить 111 найменувань і розташований на 10 сторінках.

Основний зміст роботи

криптографія алгоритмічний автомат дискретний

У вступі обґрунтовується актуальність дисертаційного дослідження автора, формулюються мета і завдання дослідження, предмет, об'єкт і методи дослідження, наукова новизна, апробація результатів роботи, подається короткий виклад результатів дисертаційної роботи.

У першому розділі виконується огляд робіт за темою дисертації, наведено необхідні теоретичні відомості, обгрунтована постановка задач, які вирішено у дисертації. Ці задачі, по своїй суті, є спеціальною деталізацією проблеми взаємодії керуючої та керованої систем (керуючого автомата та його операційного середовища), біля витоків якої стояли В.М. Глушков та К. Шеннон.

Аналіз загальної моделі шифру заміни О.П. Алферова, її деталізацій О.О. Молдовяна для керованих операцій підстановки та переставлення, теоретичних криптографічних властивостей булевих фукнкцій, систематично досліджених О.О. Логачовим, та стохастичного перетворення С.О. Осмоловського, інтерпретованого, як ансамбль шифрів, логічно приводить до поняття такого керованого бінарного відношення, що

Умова 1.1. Кероване бінарне відношення повинно бути представлено у неявному вигляді.

Умова 1.2. Необхідно побудувати швидкий алгоритм, який для кожного елемента 1-ї проекції керованого бінарного відношення породжує, один за одним, елементи відповідної 2-ї проекції для кожної фіксованої їх нумерації.

Тому при побудові широкого класу шифрів заміни актуальна наступна задача.

Задача 1.1. Побудувати скінченний автомат для якого псевдовипадковий генератор керує бінарним відношенням, що реалізує сім'ю ін'єктивних дискретних перетворювачів інформації та задовольняє умовам 1.1 та 1.2.

Вирішення цієї задачі для руйнування частот букв та дифузії інформації - модельних задач криптографії розлянуто у розділі 2.

Дослідження О.В. Бабаша сучасного стану проблеми синтезу автомата по його поведінці, аналіз О.С. Кузьміна, В.Л. Куракіна, О.А. Нечаєва рекурентних послідовностей над кільцем, які розглядаються у якості моделей псевдовипадкових генераторів, приводять до наступної задачі.

Задача 1.2. З позиції вирішення модельних задач криптографії дослідити клас лінійних автоматів над кільцем .

Актуальність даної задачі, вирішенню якої присвячено розділ 3, обумовлена тим, що ці автомати визначають новий нетривіальний клас автоматів, а також тим, що ці автомати є математичною моделлю широкого класу керованих псевдовипадкових генераторів, які використовуються при побудові кандидатів на сучасні потікові шифри.

Застосування модельних хаотичних динамічних систем до задач перетворення інформації логічно приводять до використання аналогів над скінченним кільцем таких систем при побудові потікових шифрів. П. Ошвіним, А.М. Рукліджем та Р. Штурманом досліджено симетричні модельні хаотичні динамічні системи, а саме: Guckenheimer and Holmes cycle, у рівняння якої входять поліноми 3-го ступеня, та free-running система, у рівняння якої входить показникова функція. Наявність групи симетрій часто дає змогу суттєво спростити аналіз системи, а вирішення нелінійних рівнянь над скінченним кільцем, та обчислення дискретного логарифму є модельними задачами криптографії. Тому як з позиції теорії автоматів, так і з позиції застосування при побудові потікових шифрів аналогів над кільцем модельних хаотичних динамічних систем актуальною є наступна задача.

Задача 1.3. З позиції вирішення модельних задач криптографії дослідити Guckenheimer and Holmes cycle автомат і free-running автомат над кільцем .

Вирішенню цієї задачі присв'ячено розділ 4.

У другому розділі вирішено задачу 1.1 у контексті вирішення 2-х модельних для етапу передобчислень задач криптографії: руйнування частот букв та дифузії інформації.

У підрозділі 2.1 охарактеризовано загальну модель нестаціонарного поточного шифру, в рамках якої проводяться подальші дослідження.

У підрозділі 2.2 побудовано наступну загальну модель дискретного перетворювача, який вирішує задачу руйнування частот букв у початковому тексті.

Нехай , , , де та , , де , є число входжень букви у слово , , де , .

Відносну частоту входжень букви у словах мови визначено рівністю , де - таке число, що , а - таке найменше число, що для усіх . Рівність

забезпечують припущення:

1) - двійковий дріб, що обчислений з точністю до ;

2) .

Регулярна комбінаторна структура для мови визначена в роботі як бінарне відношення , де , що задовольняє наступним п'яти умовам:

1) ;

2) ;

3) , де ;

4) ємкісна складність представлення кожної множини у неявному вигляді є ;

5) існує алгоритм , який для кожної фіксованої нумерації елементів кожної множини породжує -й елемент, та по -му елементу порождує -й елемент з часовою та ємкісною складністю та .

Доведено наступну теорему.

Теорема 2.1. Для мови множина регулярних комбінаторних структур є непустою.

Запропоновано алгоритм 2.1 перетворення язика у язик у алфавиті .

Доведено наступні теореми.

Теорема 2.2. Відносна частота появи кожноє букви у словах язика дорівнює .

Теорема 2.3. Часова та ємкісна складність перетворення алгоритмом 2.1 слова у слово в алфавиті дорівнює, відповідно,

,

,

де та є часова та ємкісна складність заповнення псевдовипадковим генератором масиву такими числами, що .

Виявлено умови, за яких алгоритм 2.1 руйнує частоти з лінійним уповільненням. Охарактеризовано обчислювальну стійкість алгоритму 2.1, як потікового шифру. Показано, що для деталізації бінарного відношення , можуть бути обрані шари фіксованого радіусу або грані одиничного кубу.

У підрозділі 2.2 побудовано алгоритм 2.2 дифузії інформації у двійковій послідовності , який засновано на використанні таких підгруп симетричної групи , що:

1) ємкісна складність представлення кожної групи у неявному вигляді дорівнює ;

2) існує алгоритм , який для кожної фіксованої нумерації елементів групи породжує -й елемент, та по -му елементу породжує -й елемент з часовою та ємкісною складністю та .

Побудовано деталізацію цього алгоритму у випадку, коли підгрупа породжується таким графом з вершинами та з майже регулярною структурою, що:

1) кількість гамільтонових шляхів між двома фіксованими вершинами є субекспонентою від кількості ребер;

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

Таким чином, у другому розділі розроблено загальний підхід до вирішення модельних задач криптографії, який спирається на поняття керованого бінарного відношення.

У третьому розділі вирішено задачу 1.2.

У підрозділі 3.1 викладено апарат лінійної алгебри над кільцем , необхідний для досліджень у розділах 3 та 4.

,

,

де - множина усіх -матриц над кільцем , - множина усіх , для яких існує обернена матриця, та .

У підрозділі 3.2 введено досліджувані моделі, а саме клас автоматів Мілі

,

та клас автомаів Мура

,

де , а є, відповідно, внутрішній стан, вхідний та вихідний символ у момент .

Виділено підмножини автоматів , які допускають обернення. Доведено наступну теорему.

Теорема 3.2. для кожного .

Охарактеризовано потіковий шифр, який визначається парою автоматів .

У підрозділі 3.3 охарактеризовано підмножини автоматів , , , та , де є множина усіх таких , що функція переходів є переставленням множини станів для кожного вхідного символа, - множина усіх приведених , - множина усіх , які мають стани-близнюки, а - множина усіх , для яких граф переходів - повний граф з петлями.

Доведено наступні теореми.

Теорема 3.4. та для кожного .

Теорема 3.5. для кожного .

Теорема 3.6. для кожного .

Теорема 3.7. Для кожного

,

.

Нехай , та , де є множина усіх таких діагональних матриць, що на головній діагоналі розташовано елементи, для яких існують зворотні елементи, а та , де - множина усіх таких діагональних матриць , що на головній діагоналі розташовано елементи, для яких існують зворотні елементи.

Доведено наступні теореми.

Теорема 3.3. для кожного .

Теорема 3.8. Для кожного

,

.

У підрозділі 3.4 досліджено еквівалентність автоматів та їх внутрішніх станів.

Доведено наступні теореми (через позначено операцію, зворотню до операції ).

Теорема 3.9. Ініціальні автомати

,

еквивалентні, якщо задовільнено умови:

а) ;

б) ;

в) для кожного існує таке та, навпаки, для кожного існує таке , що ;

г)  ;

д) .

Наслідок 3.3. Внутрішні стани та автомата еквивалентні, якщо задовільнено умови:

а) ;

б) для усіх .

Теорема 3.10. Ініціальні автомати

,

еквівалентні, якщо задовільнено умови:

а) ;

б) для кожного існує таке та, навпаки, для кожного існує таке , що ;

в) .

Наслідок 3.4. Внутрішні стани та автомата еквівалентні, якщо для усіх .

У підрозділі 3.5 вирішено задачі параметричної ідентифікації та ідентифікації внутрішнього стану для автомата .

Доведено наступну теорему.

Теорема 3.11. Якщо , а експериментатор має можливість керувати входом та ініціалізацією автомата , а також повністю спостерігати його вихід, то:

1) кожна з матриць та ідентифікується за допомогою -кратного експерименту висоти 1;

2) якщо , то ідентифікація кожної з матриць і зводиться до роз'язку систем лінійних рівнянь -го порядку над кільцем , які побудовано в результаті -кратного експерименту висоти 2.

Встановлено, що якщо , то параметрична ідентифікація автомата характеризується наступним чином:

а) пошук кандидатів на матрицю зводиться до розв'язку систем лінійних рівнянь , побудованих за допомогою -кратного експерименту висоти 2;

б) пошук можливих кандидатів на матрицю зводиться до розв'язку систем лінійних рівнянь , побудованих за допомогою -кратного експерименту висоти 2;

в) ідентифікація матриць та зводиться до розв'язку при відомих матрицах , систем нелінійних рівнянь

(1)

для усіх та .

Встановлено, що, ідентифікація матриць автомата зводиться до розв'язку систем нелінійних рівнянь

(2)

для усіх та .

Встановлено, що для автомата ідентифікація початкового стану характеризується наступним чином:

а) якщо , то , тобто ідентифікація початкового стану зводиться до розв'язку системи лінійних рівнянь, побудованої за допомогою простого эксперименту довжини 1;

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

Встановлено, що для автомата ідентифікація початкового стану характеризується наступним чином:

а) якщо , то , тобто ідентифікація початкового стану зводиться до розв'язку системи лінійних рівнянь, побудованої за допомогою простого эксперименту довжини 1;

б) якщо або , то розв'язками системи є множина кандидатів на початковий стан, а ідентифікація початкового стану з точністю до класу еквівалентних станів зводиться до перевірки рівнянь (2).

У підрозділі 3.6 досліджено множину нерухомих точок словарної функції, яку реалізує ініціальний автомат .

Нехай .

Доведено наступну теорему.

Теорема 3.12. Для автомата при кожному початковому стані для усіх множина складається з усіх таких вхідних слів , що:

1) якщо , то - розв'язок системи рівнянь

;

2) якщо , то - розв'язок системи рівнянь

.

Встановлено умови, при яких множина є пустою, скінченною або нескінченною множиною.

У підрозділі 3.7 побудовано канонічні форми для автомата . Для такої форми усі матриці, які присутні у рівняннях, що визначають функціонування автомата, є елементами множин та , де складається з таких матриць , що , , а - нульова -матриця.

У підрозділі 3.8 знайдено рекурентні співвідношення, які характеризують варіацію поведінки автомата за умови варіації його параметрів, початкового внутрішнього стану, або вхідної послідовності. Ці рекурентні співвідношення є основою для створення методів диференціального та інтегрального аналізу шифрів, побудованих на основі пари автоматів . Перехід від булевої функції до словарної функції є принципово новим моментом такого аналізу.

У підрозділі 3.9 досліджено одновимірні лінійні автомати з лагом .

Нехай - клас усіх автоматів

,

 - клас усіх автоматів

,

а - множина усіх автоматів , які допускають обернення.

Доведено наступну теорему.

Теорема 3.13. Автомат - сильно зв'язаний автомат, якщо для елемента існує зворотній елемент.

Нехай - множина усіх сильно зв'язаних автоматів , а .

З доведення теореми 3.13 випливають наступні наслідки.

Наслідок 3.15. для кожного .

Наслідок 3.16. Для кожного діаметр графу переходів кожного автомата дорівнює .

Наслідок 3.17. для кожного .

Наслідок 3.18. для кожного .

Доведено наступну теорему.

Теорема 3.14. Для кожного функція переходів автомата є переставленням множини станів для кожного вхідного символа, якщо для елемента існує зворотній елемент.

Нехай - множина усіх таких , що функція переходів є переставленням множини станів для кожного вхідного символа, а .

З доведення теореми 3.14 випливають наступні наслідки.

Наслідок 3.19. для кожного .

Наслідок 3.20. для кожного .

Таким чином у третьому розділі з позиції вирішення модельних задач криптографії методами теорії автоматів, сучасної алгебри та теорії систем проведено систематичний аналіз класу лінійних автоматів над кільцем .

У четвертому розділі вирішено задачу 1.3.

У підрозділі 4.1 введено досліджувані моделі, а саме клас автоматів

,

де , для елементів існують зворотні елементи, а , та клас автоматів

,

де - аналог логістичного відображення, для елементів існують зворотні елементи, а .

Встановлено, що кожний автомат , а також кожний автомат допускає обернення.

У підрозділі 4.2 досліджено клас автоматів . Доведено наступну теорему.

Теорема 4.1. Автомат не є сильно зв'язанним.

З доведення теореми 4.1 випливає наступний наслідок.

Наслідок 4.1. Підавтомат автомата , який визначається множиною станів є зведеним, його функція переходів є переставленням множини станів для кожного вхідного символа , а діаметр графа переходів дорівнює 1.

Доведено наступну теорему, яка встановлює, що структура автомата можє суттєво відрізнятися від структури підавтомата, визначеного множиною станів .

Теорема 4.2. Якщо , то множина станів

автомата під дією кожного вхідного символа переходить у стан .

Наслідок 4.2. Якщо , то у автомата функція переходів не є переставленням множини станів ні для якого вхідного символа .

Еквівалентність станів автомата охарактеризовано наступним чином.

Теорема 4.3. Для автомата множина станів, які еквівалентні стану визначається розв'язками нелінійної системи рівнянь

.

Наслідок 4.3. Еквівалентні стани автомата - стани-близнюки.

Вирішення задачі параметричної ідентифікації автомата охарактеризовано наступним чином.

Твердження 4.3. Для автомата ідентифікація параметрів здійснюється простим експериментом довжини 1.

Теорема 4.4. Для автомата ідентифікація параметрів та здійснюється 2-кратним експериментом висоти 1.

Теорема 4.5. Якщо , то для автомата ідентифікація параметрів та зводиться до розв'язку системи двох лінійних рівнянь, побудованої за допомогою простого експерименту довжини 1.

Встановлено, що для автомата вирішення задачі ідентифікації початкового стану зводиться до пошуку множини розв'язків нелінійної системи рівнянь

,

а нееквівалентні елементи множини (якщо такі є) необхідно розрізнити діагностичним експериментом.

Охарактеризовано множину нерухомих точок словарної функції, яку реалізує ініціальний автомат . Встановлено умови, при яких ця множина є пустою, скінченною, або нескінченною множиною.

У підрозділі 4.3 досліджено клас автоматів .

Доведено наступну теорему.

Теорема 4.6. Автомат не є сильно зв'язним.

З доведення теореми 4.6 випливає наступний наслідок.

Наслідок 4.4. Підавтомат автомата , який визначається множиною станів є зведеним, його функція переходів є переставленням множини станів для кожного вхідного символа, а діаметр графа переходів дорівнює 1.

Функція переходів автомата не є переставленням множини станів ні для якого , бо множина станів переходить у стан .

Еквівалентність станів автомата охарактеризовано наступним чином.

Теорема 4.7. Для автомата множина станів, які еквівалентні стану визначається розв'язками нелінійної системи рівнянь

.

З доведення теореми 4.7 випливає наступний наслідок.

Наслідок 4.6. Еквівалентні стани автомата - стани-близнюки.

Множина станів, які еквівалентні стану , може бути обчислена наступним чином. Нехай належить показнику , тобто - таке найменше натуральне число, що . Представимо компоненти стану у вигляді , де . Тоді

. (3)

Обчисливши для кожних розв'язки систем

,

необхідно обрати ті з них, які задовольняють систему рівнянь (3).

Вирішення задачі параметричної ідентифікації автомата охарактеризовано наступним чином.

Твердження 4.8. Для автомата ідентифікація параметрів здійснюється простим експериментом довжини 1.

Теорема 4.8. Якщо , а є елемент, для якого існує зворотній елемент, то ідентифікація параметрів та автомата зводиться до розв'язку системи двох рівнянь

, (4)

побудованої за допомогою простого експерименту довжини 1.

Якщо для елемента не існує зворотній елемент, то розв'язки системи (4) визначають клас автоматів, для якого методами теоріїї автоматів необхідно вирішити задачу ідентифікації автомата.

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

Охарактерізовано множину нерухомих точок словарної функції, яку реалізує ініціальний автомат . Встановлено умови, при яких ця множина є пустою, скінченною або нескінченною множиною.

Таким чином, у четвертому розділі з позиції вирішення модельних задач криптографії методами теорії автоматів, сучасної алгебри та теорії систем проведено систематичний аналіз двох класів нелінійних симетричних автоматів над кільцем .

Висновки

Дисертаційну роботу присвячено систематичному дескриптивному, алгоритмічному та метричному аналізу комбінаторно-алгебраїчних моделей ін'єктивних дискретних перетворювачів інформації автоматного типу, призначених для вирішення модельних задач криптографії.

Сформулюємо основні результати дисертаціїї:

- вперше досліджено дискретний перетворювач, побудований на основі керованого бінарного відношення, яке представлено регулярною комбінаторною структурою, та призначений для вирішення задачі руйнування частоти букв у початковому тексті;

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

- систематично досліджено клас лінійних автоматів над скінченним кільцем; виділено підмножини автоматів, які допускають обернення, а також множини автоматів, які характеризуються в термінах матриць та графів переходів; досліджено еквівалентність автоматів та їх внутрішніх станів;

- систематично досліджено класи симетричних нелінійних автоматів над скінченним кільцем, для яких зміна внутрішніх станів здійснюється згідно поліномів 3-го ступеня, або згідно з показниковою функцією;

- охарактеризовано множини нерухомих точок для досліджуваних у роботі автоматів над скінченним кільцем;

- вирішено задачі параметричної ідентифікації та ідентифікації початкового внутрішнього стану для досліджуваних у роботі автоматів над скінченним кільцем.

Ці результати є новими, завершеними і математично доведеними, мають теоретичне значення для теорії автоматів та комбінаторного аналізу і прикладне значення для розробки математичних основ криптографії.

Крім цього, в дисертації отримано низку цікавих результатів:

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

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

Результати дисертації отримано за допомогою моделей та методів комбінаторного аналізу, дискретної математики, теорії скінченних алгебраїчних систем, теорії чисел, теорії автоматів та теорії систем.

Список опублікованих робіт за темою дисертації

1. Скобелев В.В. Построение стойких к частотному анализу криптосистем на основе регулярных комбинаторных структур // Искусственный интеллект. ? 2004. ? №1. ? С. 88-96.

2. Скобелев В.В. Симметрические динамические системы над конечным кольцом: свойства и сложность идентификации // Труды ИПММ НАНУ. ? 2005. ? Т.10. ? С. 184-189.

3. Скобелев В.В. Об обратимых матрицах над кольцом // Труды ИПММ НАНУ. ? 2006. ? Т.13. ? С. 185-192.

4. Скобелев В.В. Анализ линейных автоматов над кольцом // Труды ИПММ НАНУ. ? 2007. ? Т.14. ? С. 162-173.

5. Скобелев В.В. Перечисление линейных автоматов над конечным кольцом // Дискретная математика и ее приложения: IX международный семинар, 18-23 июня 2007 г.: материалы семинара - М: Изд-во мех.-мат. факультета МГУ, 2007. ? С. 178-181.

6. Скобелев В.В. Шифры на основе линейных БПИ-автоматов над кольцом // Вестник Томского государственного университета. Приложение. - 2007. - №23. ? С. 118-122.

7. Скобелев В.В. Исследование структуры множества линейных БПИ-автоматов над кольцом // Доповіді НАНУ. ? 2007. ? №10. ? С. 44-49.

8. Скобелев В.В. Анализ структуры класса линейных автоматов над кольцом // Кибернетика и системный анализ. ? 2008. ? №3. ? С. 60-74.

9. Скобелев В.В. Задача идентификации линейных автоматов над кольцом // Идентификация систем и задачи управления (SICPRO 08): VII международная конференция, 28-31 января, 2008 г.: труды конференции. - М: ИПУ РАН, 2008. ? С. 1154-1185. - 1 электрон. опт. диск (CD-ROM): 12 см. - Систем. требования: Pentium-266; 32 Mb RAM; CD-ROM Windows 98/2000/NT/XP. - имя контейнера: procdngs. - имя файла: 1154.

10. Скобелев В.В. Характеристики линейных одномерных автоматов с лагом над конечным кольцом // Труды ИПММ НАНУ. ? 2008. ? Т.16. ? С. 190-196.

11. Скобелев В.В. Характеристики линейных автоматов над конечным кольцом // Тараповские чтения: международная научная школа-конференция, 21-25 апреля, 2008 г.: сборник материалов. - Харьков: ХНУ, 2008. - С. 210-211.

12. Скобелев В.В. Анализ free-running автомата над конечным кольцом // Системний аналіз та інформаційні технології: X міжнародна науково-технічна конференція, 20-24 травня, 2008 р.: матеріали конференції. Київ: НТУУ, «КПІ», 2008. - С. 405.

13. Скобелев В.В. Анализ симметричных автоматов над конечным кольцом // Прикладная электроника. Состояние и перспективы развития: 3-й международный радиоэлектронный форум, 22-24 октября 2008 г.: сборник научных трудов, Т. 5. - Харьков: АНПРЭ, ХНУРЭ. - С. 276-277.

14. Скобелев В.В. Разрушение частот букв на основе регулярных комбинаторных структур // Труды ИПММ НАНУ. ? 2008. ? Т.17. ? С. 185-193.

15. Скобелев В.В. Характеристика неподвижных точек линейных автоматов над конечным кольцом // Прикладная дискретная математика. ? 2008. ? №1. ? С. 126 - 130.

16. Скобелев В.В. О сложности идентификации симметричных автоматов над конечным кольцом // Идентификация систем и задачи управления (SICPRO 09): VIII международная конференция, 26-30 января, 2009 г.: труды конференции. - М: ИПУ РАН, 2009. ? С. 1529-1549. - 1 электрон. опт. диск (CD-ROM): 12 см. - Систем. требования: Pentium-266; 32 Mb RAM; CD-ROM Windows 98/2000/NT/XP. - имя контейнера: procdngs. - имя файла: 1529.

Размещено на Allbest.ru

...