Обратимые конечные автоматы с входной памятью

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

Введение
1. Проблемы защиты информации в компьютерных системах
2. Исследовательская часть 12
2.1. Конечные автоматы преобразователи 12
2.1.1. Введение 12
2.1.2. Конечные автоматы 13
2.2. Восстановление входной последовательности конечного автомата 15
2.2.1. Задача о числе прообразов и запреты конечных автоматов 15
2.2.2. Обратимость конечных автоматов 16
2.3. Нелинейный фильтр с входной памятью 17
2.3.1. Введение 17
2.3.2. Нелинейный фильтрующий генератор 18
2.3.3. Бинарный фильтр с выходной памятью 19
2.3.4. Криптосистемы с открытым ключом 20
2.4. Восстановление входной последовательности нелинейного фильтра с входной памятью для случая функции без запретов. 21
2.4.1. Запреты булевых функций 21
2.4.2. Восстановление входных последовательностей 24
2.5. Поиск обратного автомата 25
2.5.1.Алгоритм построения обратного автомата 25
2.5.2. Алгоритм вычисления задержки 29
2.5.3. Пример вычисления обратного автомата 32
3. Конструкторская часть 36
3.1. Разработка общей структуры ПО 38
3.2. Разработка пользовательского интерфейса 39
3.2.1. Ввод исходных данных 40
3.2.2. Отображение результатов работы 41
3.2.3. Механизм сохранения результатов работы 41
3.3. Основные этапы производства программных продуктов 42
3.4. Методы проектирования программных систем 43
4. Технологическая часть 46
4.1. Выбор языка реализации 46
4.2. Формат хранения данных в оперативной памяти 47
4.3. Оптимизация вычислений 47
4.3.1. Оптимизация при программировании 47
4.3.2. Возможность дальнейшей оптимизации 48
5. ОРГАНИЗАЦИОННО-ПРАВОЕ ОБЕСПЕЧЕНИЕ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ 50
5.1. ГОСУДАРСТВЕННАЯ ТАЙНА 50
5.2. Коммерческая тайна 51
5.3. Авторские права на разработанное ПО 52
5.3.1. Авторское право на программы для ЭВМ 52
5.3.2. Права автора 57
5.3.3. Права работодателя 60
5.3.4. Права пользователя 62
5.3.5. Выводы 64
5.4. Особенности применения закона «О правовой охране программ для ЭВМ и баз данных» 65
5.5. Использование разработанного ПО и Российское законодательство в области средств защиты информации 66
5.6. Заключение 68
6. Экономическая часть 70
6.1. Введение 70
6.2. Определение структуры (этапов) работ 70
6.3. Построение сетевого графика 72
6.4. Построение диаграммы Гантта 74
6.5. Анализ структуры затрат проекта 74
6.6. Выводы 78
7. Заключение 79
8. Литература 80
9. Приложения 81
9.1. Приложение 1. Оценка быстродействия генерируемого машинного кода. 81
9.2. Приложение 2. Руководство пользователя 85
9.2.1. Введение 85
9.2.2. Требования к системе 85
9.2.3. Работа с программой 85
9.2.3.1. Главное окно приложения 85
9.2.3.2. Результаты выполнения расчётов 88
9.2.3.3. Окно моделирования работы НФВП 91
9.2.3.4. Окно моделирования работы обратного автомата

Конечный автомат над двоичным входным/выходным алфавитом является общепринятой моделью для описания и исследования работы целого ряда симметричных криптосистем, в том числе систем поточного шифрования и, в последнее время, криптосистем с открытым ключом. Одной из разновидностей конечного автомата является так называемый нелинейный фильтр с входной памятью (НФВП).
Целью дипломного проектирования является изучение возможностей получения по известному выходу заданного обратимого НФВП соответствующей входной последовательности и построения автомата, обратного заданному НФВП. Для этого предполагается осуществить разработку и создание специализированного программного обеспечения, предназначенного для построения конечного автомата специального вида, восстанавливающего для заданного НФВП входную последовательность по известной выходной.
Задачи дипломного проектирования:
• разработать алгоритм вычисления максимальной величины задержки, с которой может быть восстановлена произвольная входная последовательность;
• разработать алгоритм построения конечного автомата, восстанавливающего для заданного НФВП входную последовательность по известной выходной;
• разработать интерфейс пользователя;
• разработать и реализовать программное обеспечение в виде отдельного приложения.