Криптографические методы

Семестр I. Криптография с секретным ключом

Введение

история • коммуникации и угрозы • криптосистема

[лекция]

Классические криптосистемы

алфавит • шифр сдвига • аффинный шифр • шифр простой замены • шифр Хилла • шифр перестановки • шифр Виженера

[лекция]

Задачи криптоанализа

атаки • частотные атаки • криптоанализ шифра Виженера

[лекция]

Элементы теории Шеннона

модель противника • совершенная криптосистема • энтропия • расстояние единственности

Конечные поля

конечные поля • многочлены • поля из pⁿ  элементов • подгруппы • подгруппы • подполя и расширения полей • характеристика поля • лемма о степени суммы и разности • мультипликативная группа • функция "след"

[лекция]

Блочные криптосистемы

блочно-итерационные криптосистемы • представления довичных слов • 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) • трюк Шамира

[лекция]

Доказательства с нулевым разглашением

протокол Шнорра • протокол Шнорра на гомоморфизмах • шифрование ЭльГамаля • свойства протоколов ZKP • неинтерактивный протокол Шнорра

Протоколы ИОК

подписанные данные и сертификаты • управление сертификатами

Модификации протокола Диффи – Хеллмана

базовый протокол • протокол с сертификатами • протоколы MTI • защита от "чтения назад" • атака "малая подгруппа" • аутентификация • протокол MQV • протокол STS • протоколы PAKE 

[cm.pdf, 5.2 -- 5.8]

Протокол TLS

схема протокола • формирование общего ключа

Протоколы консенсуса

византийское соглашение • Bitcoin

Контроль знаний

Задачи по семестру I

[cm.pdf; 3.16]

Задачи по семестру II

[cm.pdf; 2.14, 4.7, 5.10]

Задачи повышенной трудности

[solved]

Слайды

pdf