- •230105.65 – Программное обеспечение вычислительной техники и автоматизированных систем
- •Оглавление
- •Модель сетевой безопасности .Классификация сетевых атак
- •I. Пассивная атака
- •II. Активная атака
- •Создание ложного потока (фальсификация)
- •Сервисы безопасности
- •2 Классическая задача криптографии. Угрозы со стороны злоумышленника и участников процесса информационного взаимодействия.
- •3 Шифры замены и перестановки. Моно- и многоалфавитные подстановки. Шифры Цезаря, Виженера, Вернама. Методы дешифрования.
- •Перестановочные шифры Простой столбцевой перестановочный шифр
- •Перестановочный шифр с ключевым словом
- •Подстановочные шифры
- •Шифр Цезаря
- •Шифр Цезаря с ключевым словом
- •Шифр Вернама
- •Шифр Виженера
- •Шифр Виженера с перемешанным один раз алфавитом.
- •Шифр c автоключом
- •Методы анализа многоалфавитных систем
- •3.2 Классификация методов дешифрования. Модель предполагаемого противника. Правила Керкхоффа.
- •3.3 Совершенная секретность по Шеннону. Примеры совершенно секретных систем. Шифр Вернама. Понятие об управлении ключами.
- •Поточные шифры
- •Алгоритм des Принципы разработки
- •Шифрование. Начальная перестановка
- •Последовательность преобразований отдельного раунда
- •Создание подключей
- •Дешифрование
- •Проблемы des
- •5 Алгоритм гост 28147
- •Алгоритм гост 28147-89 - Режим гаммирования
- •6 Стандарт криптографической защиты 21 века (aes). Алгоритмы Rijndael т rc6. Математические понятия, лежащие в основе алгоритма Rijndael. Структура шифра. Алгоритм Rijndael
- •Поле gf(28)
- •Полиномы с коэффициентами из gf
- •Обоснование разработки
- •Спецификация алгоритма
- •Состояние, ключ шифрования и число раундов
- •Преобразование раунда
- •Создание ключей раунда
- •Алгоритм шифрования
- •Преимущества алгоритма
- •Расширения. Различная длина блока и ключа шифрования
- •7 Теория сложности вычислений. Классификация алгоритмов.
- •2. Сложность алгоритмов.
- •3. Сложность задач.
- •8 Алгоритм rsa. Математическая модель алгоритма. Стойкость алгоритма.
- •Описание алгоритма
- •Вычислительные аспекты
- •Шифрование/дешифрование
- •Создание ключей
- •9 Криптосистема Эль-Гамаля.
- •9 Электронная подпись. Варианты электронной подписи на основе алгоритмов rsa и Эль-Гамаля. Электpонная подпись на основе алгоpитма rsa
- •Простые хэш-функции
- •"Парадокс дня рождения"
- •Использование цепочки зашифрованных блоков
- •Обобщенная модель электронной цифровой подписи. Схема Диффи-Хеллмана, схема Эль-Гамаля. Общая схема цифровой подписи
- •Цифровая подпись на основе алгоритма rsa
- •Подход dss
- •Протоколы аутентификации
- •Взаимная аутентификация
- •Использование шифрования с открытым ключом
- •Односторонняя аутентификация
- •Виды протоколов.
- •Вскрытие "человек в середине"
- •Протокол "держась за руки" (Interlock protocol)
- •13 Сертификация ключей с помощью цифровых подписей. Разделение секрета. Метки времени. Пример протокола защиты базы данных. Обмен ключами с помощью цифровых подписей
- •Метки времени
- •Типовые методы криптоанализа классических алгоритмов .Метод встречи посередине .
- •15 Криптосистемы на эллиптических кривых. Математические понятия
- •Аналог алгоритма Диффи-Хеллмана обмена ключами
- •Алгоритм цифровой подписи на основе эллиптических кривых ecdsa
- •Шифрование/дешифрование с использованием эллиптических кривых
- •Литература
2. Сложность алгоритмов.
При оценке сложности алгоритма учитывается работа алгоритма на всех выходах или крайняя оценка – “в наихудшем случае”. Обычно вычислительная сложность характеризуется О (“О большое”), таким образом временная сложность не зависит от реализации.
Классификация алгоритмов, при рамере входных данных n :
Постоянные – сложность не зависит от n : O(1);
Линейные – сложность : О(n);
Полиномиальные – сложность : O(nm), где m это константа;
Экспоненциальные – сложность : O(tf(n)), где t константа большая 1, а f(n) – полиномиальная функция;
Суперполиномиальные– сложность : O(сf(n)), где с константа, а f(n) – функция возрастающая быстрее постоянной, но медленнее линейной;
3. Сложность задач.
Как отличить простые задачи от сложных?
Простые задачи (решаемые) – задачи, решаемые за полиномиальное время (например решение СЛУ в рациональных числах)
Сложные задачи (трудные, не решаемые) – задачи, которые не решаются за полиномиальное время, либо алгоритм решения за полиномиальное время не найден.
Помимо этого, существуют принципиально неразрешимые задачи, доказано А.Тьюрингом.
Сложность задач не определяется по сложности наилучшего алгоритма, ее решающего. Для оценки сложности вводится классификация по сложности функций, вычисление которых возможно при задаваемых ограничениях на потребляемые ресурсы:
a. Класс P – класс задач, которые можно решить за полиномиальное время.
b. Класс NP – класс задач, которые можно решить за полиномиальное время только на недетерминированной Машине Тьюринга: в отличии от обычной МТ может делать предположения. Это задачи у которых есть ответ, найти который трудно, но проверить можно за полиномиальное время.
Замечание: Ясно, что P входит NP, но вот проверить, что (P <> NP) или (P = NP) до сих пор не удалось. Это одна из важнейших проблем XXI века.
c. Класс NP-полных задач – класс задач, не менее сложных, чем любая NP задача. Т.е. решив такие задачи за полиномиальное время можно доказать (P = NP). К этому классу относится задача выполнимости - Задано логическое выражение. Существует ли набор правильных значений, на которых данное выражение будет истиной?(Пока не доказано.)
d. Класс PSPACE – класс задач, которые могут быть решены в полиномиальном пространстве, но не обязательно за полиномиальное время.
e. Класс PSPACE-полных задач – класс задач, которые обладают следующим свойством: если любая из них NP, то PSPACE=NP, и если любая из них является P проблемой, то PSPACE=NP.
f. Класс EXPTIME – класс задач, которые решаются за экспоненциальное время.
g. Класс EXPTIME-полных задач - класс задач, которые не решаются за детерминированное полиномиальное время. Известно, что P<>EXPTIME.
8 Алгоритм rsa. Математическая модель алгоритма. Стойкость алгоритма.
Алгоритм RSA
Диффи и Хеллман определили новый подход к шифрованию, что вызвало к жизни разработку алгоритмов шифрования, удовлетворяющих требованиям систем с открытым ключом. Одним из первых результатов был алгоритм, разработанный в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.
Алгоритм основан на использовании того факта, что задача факторизации является трудной, т.е. легко перемножить два числа, в то время как не существует полиномиального алгоритма нахождения простых сомножителей большого числа.
Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n.