Languages

Математическое и программное обеспечение защиты информации



Мат. и информ. обеспечение экономической деятельности

Аннотация курсов программы

510200-ДНМ05
Теория сложности

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

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

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

Метод «разделяй и властвуй» для построения быстрых алгоритмов. Быстрые алгоритмы для умножения чисел и матриц.

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

Некоторые классы сложности. Определения классов P и NP. Примеры языков из NP, замкнутость класса P относительно полиномиального сведения. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач. Полиномиальный алгоритм для распознавания 2-выполнимости.

Задачи оптимизации. Жадный алгоритм для задачи о кратчайшем остовном дереве. Задачи коммивояжёра, её NP-трудность, теорема о приближённых алгоритмов для неё.

Курс читает профессор, д.ф.-м.н. Алексеев В.Б.

1-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - экзамен.

510213-СДМ01
Введение в криптографию

1. Основные понятия и задачи криптографии. Криптографические методы обеспечения информационной безопасности. Формальное определение шифра. (криптосистемы). Алгебраическая и вероятностная модели шифра. Симметрические и асимметрические шифры. Шифры простой замены и перестановки, криптосистемы РСА и Эль Гамаля. Табличное гаммирование. Понятие односторонней функции и односторонней функции с секретом.
2. Краткий исторический обзор развития криптографии. Шифры атбаш, Сцитала, табличка Энея, квадрат Полибия. Шифр Цезаря, шифровальный диск Альберти. Шифр простой биграмной замены де ла Порта.. Шифры Виженера, Ришелье, Наполеона. Шифр Вернама, дисковый шифратор «Энигма».
3. Блочные и поточные шифры. Математическая модель шифра замены. Атаки на шифр, стойкость шифра, совершенный шифр, теорема Шеннона, имитостойкость шифров. Режимы использования блочных шифров. Стандарты шифрования ГОСТ 28147-89 и DES.
4. Универсальные методы криптоанализа. Метод полного перебора. Аналитический метод. Метод «встреча по середине». Метод «разделяй и побеждай». Методы криптоанализа при неравновероятной гамме. Расстояние единственности, теоремы Шеннона. Перекрытие гаммы. Корреляционные атаки на поточные шифры. Криптоанализ шифра Виженера.
5. Статистические методы криптоанализа. Линейный и дифференциальный криптоанализ блочных шифров. Примеры атак на блочные шифры.
6. Криптографические протоколы. Протоколы аутентификации электронно-цифровой подписи (ЭЦП). Формальная модель протокола ЭЦП на основе односторонней функции. Понятие хэш-функции .. Методы построения хэш-функций.Элементарные свойства хэш-функций. Ключевые и бесключевые хэш-функции. Метод коллизий для хэш-функций.
7. Ключевые системы. Управление ключами. Предварительное распределение секретных ключей. Пересылка ключей. Протокол открытого распределения ключей. Ифраструктура открытых ключей. Центр сертификации открытых ключей. Система управления сертификатами. Федеральная ифраструктура открытых ключей.
8. Криптографические средства и методы защиты данных программного обеспечения. Основные требования обеспечения безопасности данных в программных системах. Средства и методы защиты. Ключевая система и ключевые носители. Контроль целостности программного обеспечения.

Курс читает к. ф.-м.н., доцент Применко Э.А.

1-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - экзамен.

510213-СДМ02
Комбинаторика

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

1. Основные понятия
1.1. Сочетания и перестановки с повторениями и без повторений. Биномиальные коэффициенты.
1.2. Принцип включения-исключения. Задача о беспорядках. Неравенства Бонферрони.
2. Производящие функции
2.1. Формальные степенные ряды и действия над ними.
2.2. Алгебраические и дифференциальные уравнения над кольцом формальных степенных рядов.
2.3. Производящие функции для известных последовательностей.
3. Тождества с биномиальными коэффициентами.
3.1. Рекуррентные соотношения.
3.2. Формулы обращения.
4. Примеры перечислительных задач.
4.1. Задача Андрэ.
4.2. Числа Каталана, Моргана. Числа и многочлены Белла.
4.3. Многочлены Гаусса.
5. Разбиение натуральных чисел.
5.1. Элементарная теория разбиений. Граф Феррера.
5.2. Вычисление функции разбиения.
5.3. Введение в общую теорию тождеств с разбиениями. Описание идеалов первого порядка.

Курс читает к. ф.-м.н. Ролдугин П. В.

1-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - зачет.

510213-СДМ03
Математическая теория информации

1. Информация и энтропия конечной вероятностной схемы.
Аксиомы А. Я. Хинчина и Д. К. Фаддеева. Теорема о единственности вида функции энтропии.
Теорема о связи энтропии объединённой вероятностной схемы АВ с энтропиями схем А и В, её составляющих, с использованием соответствующих неравенств и ее следствия.
Взаимная информация исходов, средней взаимной информации, собственной информации исхода, средней собственной информации.
Соотношения аддитивности информации. Теорема о невозрастании взаимной информации при сюрьективных отображениях схем.
Теорема о выпуклости средней взаимной информации. Привести соответствующую геометрическую интерпретацию. Сформулировать теорему о локальных экстремумах функции I(A; В).
2. Источники сообщений.
Математическая модель дискретного источника сообщений. Энтропия источника
Дискретного источника без памяти. Доказать первую теорему Шеннона для источников такого вида.
Вторая теорема Шеннона для источников без памяти и следствия из этой теоремы.
Марковский источника. Шаговая энтропия и энтропия на знак для марковского источника.
Первая теорема Шеннона для марковских источников.
Эргодический источник. Теорема Бирхгофа. Примеры эргодического и неэргодического источников.
Энтропия на знак и шаговая энтропия для эргодического источника.
Теорема Макмиллана.
3. Оптимальное кодирование.
Понятия теории "сжимающих кодов. Неравенство Крафта.
Алгоритмы кодирования Р. Фано и К. Шеннона.
Оптимальный код и его свойства.
Алгоритм Хафмана. Привести примеры построения оптимальных кодов. Алгоритм Хафмана для d-ичных алфавитов.
Теорема о верхней и нижней границах для средней длины кодового слова.
Теорема А. Я. Хинчина о нижней грани коэффициента сжатия кода.

Курс читает к.ф.-м.н. Духин А.А.

1-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - экзамен.

510213-СДМ04
Математические основы криптологии

1. Теоретико-числовые модели криптологии.
Алгоритм Евклида. Теорема о представлении НОД.
Основная теорема арифметики. Свойства простых делителей. Сравнения и их свойства. Алгоритм вычисления обратного элемента. Китайская теорема об остатках. Функции Эйлера и Мебиуса и их свойства. Обоснование криптосистемы РСА. Быстрое возведение в степень.
Квадратичные вычеты, символ Лежандра и его свойства..Алгоритмы решения сравнений второй степени.
Символ Якоби и его свойства. Числа Блюма и их свойства. Квадратичные вычеты и задача факторизации.
2. Теоретико-алгебраические модели криптологии
Группы, теорема Лагранжа. Циклическая группа, порядок элемента, число образующих, критерий для образующей. Основная теорема о конечной абелевой группе. Теоремы о мультипликативной циклической группе по модулю степени простого числа. Группа подстановок на конечном множестве. Кратная транзитивность и примитивность. Системы образующих симметрической и знакопеременной групп.
Кольцо, идеал, главный идеал. Кольцо многочленов над полем, теорема Безу, алгоритм Эвклида. Конечные поля и их строение. Теорема о примитивном элементе. Примитивный многочлен и его свойства, критерий примитивности многочлена. Алгоритмы вычисления дискретного логарифма в конечном поле. Криптосистема Эль Гамаля, протокол открытого распределения ключей Диффи-Хеллмана.
3. Эллиптические кривые над конечными полями.
Эллиптическая кривая над простым полем. Сложение точек эллиптической кривой . Теорема Постникова. Две теоремы о порядке группы точек эллиптической кривой для некоторых типов простых чисел. Теорема Хассе. Эллиптические кривые над полями характеристики два. Суперсингулярные и несуперсингулярные кривые и их свойства.
4. Математические модели порождения псевдослучайных последовательностей.
Линейные рекуррентные последовательности над конечным полем. Характеристический многочлен ЛРП, период, условие периодичности. Аннулирующий многочлен ЛРП, лемма о подпространстве ЛРП с данным характеристическим многочленом. Период суммы двух ЛРП с взаимно простыми характеристическими многочленами. Связь между периодом ЛРП и периодом ее характеристического многочлена. Построение ЛРП максимального периода..Регистры сдвига с одной обратной связью. Условие регулярности в поле вычетов по модулю два. Утверждение о возможности склеивания циклов. Автономный автомат, регулярность автономного автомата . Общие критерии регулярности автономного автомата. Критерии регулярности для случая кольца с единицей. Критерии регулярности преобразований над конечным полем. Теорема Скворцова, обобщенный критерий Хаффмана.
Линейный конгруэнтный метод. Критерий биективности многочлена по модулю степени простого числа. Критерий транзитивности линейной функции по модулю степени простого числа.

Курс читает к. ф.-м.н., доцент Применко Э.А.

3-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - зачет

510213-СДМ05
Теоретические основы компьютерной безопасности

1. Технология построения защищенных компьютерных систем. Бизнес процессы и информационная поддержка. Противники, ущербы, угрозы, уязвимости. Политика безопасности. Риски. Аксиома безопасности как защиты доступа.
2. Классификация (категорирование) информации. Доказательство непротиворечивости, полноты. Задание функций автоматического категорирования.
3. Дискреционная политика безопасности. Неустойчивость к атакам с помощью «троянского коня». Сложность задачи контроля распространения прав в дискреционной политике. Модель take-grant.
4. Ролевая модель политики безопасности. Теорема о связи ролевой модели и дискреционной политики.
5. Простейшие информационные потоки. Многоуровневая политика безопасности (MLS). Устойчивость MLS к атакам с помощью троянского коня. Условия сохранение безопасного состояния при функционировании системы с многоуровневой политикой безопасности. Модель Белла-Лападулла. BST теорема. Модель LOW WATER MARK.
6. Сложные информационные потоки. Скрытые каналы. Примеры выполнения политики безопасности и нарушения безопасности с помощью скрытых каналов. Невидимость нарушения системой защиты.
7. Модель невлияния. Теоремы о сохранении безопасного состояния в автоматной модели невлияния. Невидимость верхнего уровня относительно нижнего уровня. Примеры.
8. Пример нарушения невидимости при выполнении условий невлияния.
9. Модель изолированной программной среды.
10. Распределенные системы. Критические системы. Обоснование нового базового набора требований по безопасности для больших распределенных систем. Угрозы в распределенных системах. Простейшие модели безопасных распределенных систем (с доказательством)
11. Механизмы защиты.
12. Архитектурная реализация многоуровневой политики безопасности. Доказательство безопасности для потоков в общем виде.

Курс читает д.ф.-м.н., профессор Грушо А.А.

2-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - зачет

510213-СДМ06
Теория кодирования

I. Коды, исправляющие ошибки.
Понятие линейного кода, его порождающая и проверочная матрицы. Минимальное кодовое расстояние. Обнаружение и исправление ошибок. Систематические коды.
Границы для параметров кодов. Совершенные и эквидистантные коды.
Декодирование линейных кодов с использованием стандартного расположения, модифицированный метод с использованием синдромов. Метод последовательного декодирования.
Код Хемминга и его свойства. Порождающая матрица кода Хемминга.
Методы построения новых кодов из заданных.
Тождества Мак-Уильямс.
Коды Адамара и матрицы Адамара, коды Рида-Маллера.
Неприводимые многочлены над конечными полями. Циклические коды, порождающая и проверочная матрицы, порождающий и проверочный многочлены. Алгебраическое строение циклических кодов.
Определение кода Боуза-Чоудхури-Хоквингема с параметром d. Теорема о кодовом расстоянии БЧХ-кода. Построение кодов, исправляющих заданное число ошибок.

II. Дискретные каналы связи без памяти и связанные с ними теоремы кодирования.
Задание дискретного канала связи без памяти (ДКБП) и его пропускной способности. Вычисление пропускной способности каналов связи, симметричных по входу, симметричных. Теорема о вероятностном распределении, максимизирующем взаимную информацию между входом и выходом канала.
Итеративный алгоритм нахождения пропускной способности дискретного канала связи без памяти. Нахождение пропускной способности канала в случае невырожденной матрицы переходных вероятностей.
Прямая и обратная теоремы Шеннона для двоичного симметричного канала.
Теорема кодирования для дискретного источника без памяти. Обратная теорема кодирования Вольфовица.

Курс читает доцент к.ф.-м.н. Духин А.А.

2-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - зачет

510213-СДМ07
Защита информационных процессов в компьютерных системах

1. Технология построения защищенных компьютерных систем. Бизнес процессы и информационная поддержка. Противники, ущербы, угрозы, уязвимости. Политика безопасности. Риски. Защита доступа как Аксиома безопасности. Атака как основное понятие компьютерной безопасности. Некоторые характеристики атак.
2. Иерархическая декомпозиция компьютерных систем, систем межкомпьютерной связи, баз данных, распределенных систем.
3. Внутри компьютерные связи, возможности недекларированных возможностей процессоров. О возможности существования «невидимых» для защиты агентов в процессоре (выполнение условий невлияния).
4. Невидимость для защиты агентов на уровне ОС (выполнение условий невлияния).
5. Теоремы о возможности создания сети агентов, невидимых для средств защиты.
6. Враждебные многоагентные системы. Возможность невидимо для средств защиты атаковать приложения. Атаки на LDAP.
7. Проблема взаимодействия агентов с внешней средой. Межсетевые экраны. IPsec.
8. Атаки на защищенные сегменты VPN с помощью скрытых каналов.
9. Построение стеганографических каналов, использующих особенности IP.
10. Методы встраивания враждебного ПО в КС.
11. Анонимные вычисления, как защита вычислений во враждебной среде.
12. Архитектурные методы защиты.

Курс читает д. ф.-м.н., профессор Грушо А.А.

3-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - экзамен

510213-СДМ08
Криптопротоколы

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

Курс читает к. ф.-м.н., доцент Применко Э.А.

3-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - экзамен

510213-СДМ09
Программно-аппаратная защита информации

Курс читает к. ф.-м.н., доцент Попов В.О.

4-ой семестр.
Трудоемкость курса - 4 академических часа в неделю, лекции.
Форма контроля - зачет

510213-СДМ10
Булевы функции в кодировании и криптографии

Общие сведения. Схемы аутентификации. Возможные угрозы. Классификация систем аутентификации.

Математические основы теории аутентификации. Основные комбинаторные структуры и их свойства. Элементы теории игр. Энтропия вероятностной схемы и ее свойства.

Коды аутентификации и их параметры.
Основные параметры и классификация А-кодов. Пример безусловно стойкого А-кода. Теоретико-игровой подход в выборе стратегий защиты и нападения. Примеры вычисления оптимальных стратегий для А-кодов.

Энтропийные границы параметров А-кодов.
Оценки вероятностей успеха имитации и подмены. Совершенные А-коды. Атака обмана порядка r.

Комбинаторные границы параметров А-кодов. Комбинаторные границы вероятности успеха обмана. Комбинаторные границы числа правил кодирования А-кодов. Экстремальные А-коды. Комбинаторные свойства экстремальных А-кодов. Симметричные экстремальные А-коды. А-коды с равномерным по сообщениям распределением вероятностей. А-коды, стойкие к атаке обмана порядка r. А-коды, оптимальные по ключу.

Кратно-совершенные А-коды. Общие результаты. Декартовы кратно-совершенные А-коды. Декартовы А-коды и MDS-коды. Декартовы А-коды на основе обобщенных многоугольников. А-коды с достижимыми комбинаторными и энтропийными оценками параметров.

А-коды с аутентификатором (Ā-коды). Определения и примеры. Комбинаторные границы параметров. Конструкции Ā-кодов с достижимыми нижними оценками параметров. Характеризация Ā-кодов. Примеры реализаций А-кодов.

Курс читает к. ф.-м.н., доцент Зубов А.Ю.

4-ой семестр.
Трудоемкость курса - 2 академических часа в неделю, лекции.
Форма контроля - зачет

510213-ДНМ06
510213-СДМ12
Дисциплина по выбору студента

Дискретные функции в кодировании и криптографии. Часть 2
Динамические системы и криптография
Основы комбинаторики
Правовые основы информационной безопасности
Информационное общество и информационная безопасность. Философско-социологические аспекты безопасности
Вычислительные методы теории чисел
Методы криптоанализа схем с открытым ключом
Методы теории кодирования в криптографии
Проектирование и разработка защищенных приложений
Математическая криптография