Криптографические протоколы | Computer Science клуб при ПОМИ РАН

Язык курса: русский

Краткое описание курса:
Курс посвящён конкретным криптографическим протоколам и примитивам: RSA, эллиптической криптографии, разделению секрета, доказательствам с неразглашением. Мы также поговорим об алгоритмах взлома этих примитивов — разложения чисел на множители и дискретного логарифмирования.

1. Введение. Предмет и история криптографии. Криптографические атаки. Криптографические примитивы: хеш–функции, протоколы с секретным и открытым ключом.: Слайды (pdf). Версия для печати (pdf). Видео: tube, mp4.
2. Криптография с закрытым ключом. Поточные шифры: линейные сдвиговые регистры, линейная сложность функций, нелинейные сдвиговые регистры. Блочные шифры: ECB, CBC, CFB, OFB. Коды аутентификации сообщений (MAC, message authenticity code). Реализация криптографии с закрытым ключом через хеш–функции.: Слайды (pdf). Версия для печати (pdf). Видео: tube, mp4.
3. Криптография с открытым ключом I. Основы теории чисел: алгоритм Евклида, квадратичные вычеты, символ Лежандра. Эквивалентность вычисления квадратного корня по модулю N и разложения N на множители. Криптосистема RSA. Порождение простых чисел, тест Миллера–Рабина. RSA problem. Атаки на RSA. Криптосистема Рабина: стойкость, эквивалентная разложению числа на множители.: Слайды (pdf). Версия для печати (pdf). Видео: tube, mp4.
4. Криптография с открытым ключом II. Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–трудность задачи декодирования. Криптосистема МакЭлиса. Задача subset sum, супервозрастающие последовательности. Криптосистема Меркле–Хеллмана.: Слайды (pdf). Версия для печати (pdf). Видео: tube, mp4.
5. Решётки в криптографии. Основы теории решёток: базис, определитель, задача поиска кратчайшего вектора (SVP). Ортогонализация Грама–Шмидта. LLL–редуцированные базисы и оценка на размер rратчайшего вектора. Алгоритм LLL. Его применения в криптоанализе: решение subset sum низкой плотности, поиск корней многочленов и атака на RSA с маленькой экспонентой. Криптографические примитивы, основанные на решётках: конструкция семейства хеш–функций Ajtai и идея доказательства стойкости, конструкция криптосистемы Ajtai–Dwork.: Слайды (pdf). Версия для печати (pdf). Видео: tube, mp4.
6. Протоколы согласования ключа. Введение. Протокол Диффи–Хеллмана. Типы протоколов и атак, желаемые свойства. Протоколы: простой key transport, AKEP, протокол Шамира. Протоколы с сервером: протокол Отвея–Рииса, Kerberos. Протоколы с цифровой подписью: протокол Нидхэма–Шрёдера, алгоритм X.509. Классические атаки на протоколы согласования ключа. Распределение ключей: нижняя оценка, конструкция Блома. Разделение секрета: схема Блэкли, схема Шамира.: Слайды (pdf). Версия для печати (pdf). Видео: tube, mp4.
7. Разложение чисел на множители. Введение: метод Ферма. Метод Крайчика. Гладкие числа. Оценка сложности метода Крайчика на базе обобщения теоремы Мертенса. Решето Эратосфена для поиска гладких чисел. Квадратичное решето. Оценка сложности. Сложность решения линейной системы.: Слайды (pdf). Версия для печати (pdf). Видео: tube, mp4.
8. Задача дискретного логарифма I. Введение. Методы со сложностью O(sqrt(n)). Baby-step-giant–step. rho–метод Полларда. Алгоритмы поиска цикла: алгоритм Флойда и алгоритм Брента. Метод кенгуру: lambda–метод Полларда. Метод index calculus: первая и вторая фазы.: Слайды (pdf). Версия для печати (pdf).
9. Задача дискретного логарифма II. Метод index calculus: третья фаза и оценка сложности. Сложность решения линейной системы: алгоритм Видеманна. Идея решета числового поля. Метод Шупа сведения дискретного логарифма к задаче поиска кратчайших векторов в решётке.: Слайды (pdf). Версия для печати (pdf).
10. Доказательства с неразглашением. Пещера Али–Бабы и Усама бен–Али. Определения: доказательства, системы доказательств. Изоморфизм и неизоморфизм графов. Как определить доказательства с неразглашением.: Слайды (pdf). Версия для печати (pdf).
11. Доказательства с неразглашением II. Протокол с неразглашением для NISO. Доказательство неразглашения: симулятор, black box vs. доступ к коду. Oblivious transfer: протокол Рабина, 1–2–OT протокол, их эквивалентность. Секретное вычисление функции. Бросание монетки в колодец. Покер по телефону.: Слайды (pdf). Версия для печати (pdf).