Криптографические методы
Семестр I. Криптография с секретным ключом
Введение
история • коммуникации и угрозы • криптосистема
[лекция]
Классические криптосистемы
алфавит • шифр сдвига • аффинный шифр • шифр простой замены • шифр Хилла • шифр перестановки • шифр Виженера
[лекция]
Задачи криптоанализа
атаки • частотные атаки • криптоанализ шифра Виженера
[лекция]
Элементы теории Шеннона
модель противника • совершенная криптосистема • энтропия • расстояние единственности
Конечные поля
конечные поля • многочлены • поля из pn элементов • подгруппы • подгруппы • подполя и расширения полей • характеристика поля • лемма о степени суммы и разности • мультипликативная группа • функция "след"
[лекция]
Блочные криптосистемы
блочно-итерационные криптосистемы • представления довичных слов • SP-криптосистемы • τ-инволютивные подстановки • криптосистемы Фейстеля
[cm.pdf, 3.1, 3.3, 3.4, 3.6, 3.8, 3.9]
AES
AES • инверсные S-блоки • стратегия "широкого следа"
[лекция]
Атака "грубой силой"
базовая атака • простые соотношения • баланс "время – память"
[лекция]
Разностная атака
разностная атака • криптосистема G • разностная атака на криптосистему G
[лекция]
Режимы шифрования
режим простой замены • режимы шифрования • имитозащита
[лекция]
Поточные криптосистемы
поточные криптосистемы • конечные автоматы • РСЛОС • РСЛОС и функция "след"
[лекция]
Свойства л.р.л.
период л.р.п. • порядок многочлена • постулаты Голомба
[лекция]
Усложнение л.р.л.
минимальный многочлен • генераторы на базе РСЛОС • линейная сложность
[лекция; слайды: A5/1 vs A5/2]
Семестр II. Криптография с открытым ключом
Протокол Диффи – Хеллмана
головоломки Меркля • протокол Диффи – Хеллмана • "противник посередине" • реализация протокола
[лекция; слайды]
Элементы теории сложности
вычислительные задачи • машина Тьюринга • разрешимые и неразрешимые задачи • ресурсы • вероятностные машины • алгоритмы Лас-Вегас и Монте-Карло • сложностные классы • язык PRIMES
[cm.pdf, 2.1 – 2.10; слайды]
Односторонние функции
односторонние функции • функции с лазейкой • шифрование с открытым ключом • системы ЭЦП • сертификаты открытых ключей
[cm.pdf, 2.11 – 2.13; слайды]
Инфраструктура открытых ключей
инфраструктура открытых ключей • инфраструктура РБ
[лекция; слайды]
RSA
криптосистема RSA • RSA и факторизация • арифметика больших чисел • алгоритм Евклида • расширенный алгоритм Евклида • возведение в степень • китайская система сравнений • оптимизация RSA
[лекция1; лекция2; слайды]
Генерация простых
генерация простых • распределение простых • тест Ферма • тест Рабина – Миллера • построение простых
[лекция; слайды]
Функции хэширования
определение и использование • задачи криптоанализа • блочно-итерационные функции • конструкция Дамгарда
[cm.pdf, 4.1 – 4.4; слайды; функция хэширования СТБ 34.101.31]
Атака "дней рождения"
базовая атака • модифицированная атака • алгоритм Брента
[cm.pdf, 4.5 – 4.6; слайды]
ЭЦП
ЭЦП ЭльГамаля • стойкость ЭЦП ЭльГамаля • модификации ЭЦП ЭльГамаля • метод Монтгомери • ЭЦП Шнорра • СТБ 1176.2-99
[лекция; слайды; СТБ 1176.2; СТБ 34.101.45]
Факторизация
задача факторизации • алгоритм p – 1 • ρ-метод • выбор модуля RSA
[лекция; слайды]
Дискретное логарифмирование
метод больших-малых шагов • ρ-метод • метод Поллига – Хеллмана • λ-метод
[лекция; слайды]
Субэкспоненциальные методы факторизации и логарифмирования
метод Диксона • квадратичное решето • индекс-метод
[лекция]
Семестр III. Криптографические протоколы
Эллиптические кривые в криптографии
эллиптические кривые • дискриминант • сложение точек • группа точек ЭК • задача дискретного логарифмирования на ЭК
[лекция]
Реализация арифметики эллиптических кривых
кратная точка • специальные простые • умножение и возведение в квадрат столбиком • умножение Карацубы – Офмана • проективные координаты • аддитивные цепочки • цепочки Брауэра • аддитивно-субтрактивные цепочки • оптимальная знаковая форма (NAF) • трюк Шамира
[лекция]
ЭЦП и сертификаты
ЭЦП Шнорра на ЭК • подписанные данные и сертификаты • управление сертификатами
Модификации протокола Диффи – Хеллмана
базовый протокол • протокол с сертификатами • протоколы MTI • защита от "чтения назад" • атака "малая подгруппа" • аутентификация • протокол MQV • протокол STS
[cm.pdf, 5.2 -- 5.8]
Протокол TLS
схема протокола • формирование общего ключа
Доказательства с нулевым разглашением
протокол Шнорра • доказательства с нулевым разглашением • протокол Шнорра на гомоморфизмах • шифрование ЭльГамаля
Протоколы консенсуса
византийское соглашение • Bitcoin
Контроль знаний
Задачи по семестру I
[cm.pdf; 3.16]
Задачи по семестру II
[cm.pdf; 2.14, 4.7, 5.10]
Задачи повышенной трудности
[solved]
Слайды
pdf
