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

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

Ниже приведена программа курса и ссылки на файлы презентаций (некоторые пункты программы не однозначно соответствуют лекциям). Некоторые лекции также снабжены видеозаписью; видеозаписи были сделаны во время чтения курса в Computer Science Club при ПОМИ РАН

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. Эллиптические кривые. Основные определения: приводимые и неприводимые кривые, рациональные точки, сингулярные и несингулярные точки. Теория результантов. Числа пересечений. Проективная плоскость и проективные кривые. Теорема Безу. Групповой закон на эллиптических кривых (с наброском доказательства ассоциативности). Уравнение Вейерштрасса, основные формы. Теорема Хассе, групповая структура (без док-ва). Координаты Якоби и Чудновского. Быстрое умножение точки на скаляр, NAF (non-adjacent form).

6. Решётки в криптографии. Основы теории решёток: базис, определитель, задача поиска кратчайшего вектора (SVP). Ортогонализация Грама-Шмидта. LLL-редуцированные базисы и оценка на размер rратчайшего вектора. Алгоритм LLL. Его применения в криптоанализе: решение subset sum низкой плотности, поиск корней многочленов и атака на RSA с маленькой экспонентой. Криптографические примитивы, основанные на решётках: конструкция семейства хеш-функций Ajtai и идея доказательства стойкости, конструкция криптосистемы Ajtai-Dwork.

Слайды (pdf). Версия для печати (pdf).   Видео: tube, mp4.

7. Протоколы согласования ключа. Введение. Протокол Диффи-Хеллмана. Типы протоколов и атак, желаемые свойства. Протоколы: простой key transport, AKEP, протокол Шамира. Протоколы с сервером: протокол Отвея-Рииса, Kerberos. Протоколы с цифровой подписью: протокол Нидхэма-Шрёдера, алгоритм X.509. Классические атаки на протоколы согласования ключа. Распределение ключей: нижняя оценка, конструкция Блома. Разделение секрета: схема Блэкли, схема Шамира.

Слайды (pdf). Версия для печати (pdf).   Видео: tube, mp4.

8. Разложение чисел на множители. Введение: метод Ферма. Метод Крайчика. Гладкие числа. Оценка сложности метода Крайчика на базе обобщения теоремы Мертенса. Решето Эратосфена для поиска гладких чисел. Квадратичное решето. Оценка сложности. Метод Ленстры (алгоритм ECM) разложения чисел при помощи эллиптических кривых.

Слайды (pdf). Версия для печати (pdf).   Видео: tube, mp4.

9. Задача дискретного логарифма I. Введение. Методы со сложностью O(sqrt(n)). Baby-step-giant-step. rho-метод Полларда. Алгоритмы поиска цикла: алгоритм Флойда и алгоритм Брента. Метод кенгуру: lambda-метод Полларда. Метод index calculus: первая и вторая фазы.

Слайды (pdf). Версия для печати (pdf).

10. Задача дискретного логарифма II. Метод index calculus: третья фаза и оценка сложности. Сложность решения линейной системы: алгоритм Видеманна. Идея решета числового поля. Метод Шупа сведения дискретного логарифма к задаче поиска кратчайших векторов в решётке.

Слайды (pdf). Версия для печати (pdf).

11. Доказательства с неразглашением. Пещера Али-Бабы и Усама бен-Али. Определения: доказательства, системы доказательств. Изоморфизм и неизоморфизм графов. Как определить доказательства с неразглашением.

Слайды (pdf). Версия для печати (pdf).

12. Доказательства с неразглашением II. Протокол с неразглашением для NISO. Доказательство неразглашения: симулятор, black box vs. доступ к коду. Oblivious transfer: протокол Рабина, 1-2-OT протокол, их эквивалентность. Секретное вычисление функции. Бросание монетки в колодец. Покер по телефону.

Слайды (pdf). Версия для печати (pdf).

13. Квантовые вычисления и криптография. Квантовые вычисления. Квантовые состояния, кубиты, запутанные состояния, измерения. Запутывание, интерференция и параллелизм. Задача Deutsch-Jozsa. Задача Саймона. Квнтовое преобразование Фурье. Алгоритм Шора: поиск периода. Алгоритм Шора для поиска дискретного логарифма.

Слайды (pdf). Версия для печати (pdf).

14. Некоммутативная криптография. Вычислительные задачи на группах: задача равенства слов, задача сопряжённости, поисковые версии. Желаемые свойства базовой группы. Некоммутативные протоколы согласования ключей, основанные на коммутирующих подгруппах. Протокол Аншель-Аншеля-Гольдфельда. Атаки, основанные на длине. Атаки линейной алгеброй. Неудачная версия протокола Штикеля.

Слайды (pdf). Версия для печати (pdf).

15. Расцвет и упадок криптографии в группе кос. Группа кос: определение, представление Артина, простые косы, положительные косы и порядок на них, фундаментальная коса в представлении Артина, нормальная форма, band generators, нормальная форма в них, подгруппы LBn и RBn. Представление Бурау, обобщённое (окрашенное) представление Бурау, представление Лоуренса–Краммера. Протоколы на группе кос, задача BDHP. Атаки: атака, основанная на длине, атака на сопряжение посредством summit sets, атака линейной алгеброй.

Слайды (pdf). Версия для печати (pdf).