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

Санкт-Петербург, весна 2015

Описание

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

Преподаватели

Список лекций

Введение в криптографические примитивы

Введение. Предмет и история криптографии. Виды криптографических атак. Чем вообще занимается криптография сегодня? Виды криптографических примитивов: хеш-функции, протоколы с закрытым ключом, протоколы с открытым ключом. Другие задачи криптографии.

Протоколы с секретным ключом

Криптография с секретным ключом. Как использовать один и тот же ключ много раз? Блочные шифры: ECB, CBC, CFB, OFB. Имитовставки.

Поточные шифры, сдвиговые регистры и реконструкция рациональных функций

Поточные шифры: линейные сдвиговые регистры, линейная сложность функций, нелинейные сдвиговые регистры. Алгоритм Евклида для многочленов. Реконструкция рациональных функций. Обучение линейных сдвиговых регистров. Коды Рида-Соломона.

Основы теории чисел

Вспоминаем теорию чисел: арифметика по модулю, вычеты, символ Лежандра. Задача извлечения корня по модулю. Задача дискретного логарифма.

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

Криптосистемы с открытым ключом: RSA. Атаки на RSA. Криптосистемы Рабина, Эль-Гамаля, Мак-Элиса, Меркле-Хеллмана.

Протоколы согласования ключа

Криптография с открытым ключом: протоколы согласования ключа. Протокол Диффи-Хеллмана. AKEP, протокол Шамира, протокол Отвея-Рииса, Kerberos, протокол Нидхема-Шрёдера, X.509. Атаки на протоколы согласования ключа.

Разложение чисел на множители

Метод Ферма. Метод Крайчика. Гладкие числа. Оценка сложности метода Крайчика на базе обобщения теоремы Мертенса. Решето Эратосфена для поиска гладких чисел. Квадратичное решето. Оценка сложности. Сложность решения линейной системы.

Задача дискретного логарифма

Методы со сложностью O(sqrt(n)): baby-step-giant–step, rho–метод Полларда. Алгоритмы поиска цикла: алгоритм Флойда и алгоритм Брента. Метод кенгуру: lambda–метод Полларда. Метод index calculus. Оценка сложности метода index calculus.

Эллиптические кривые

Основные определения. Сингулярные и несингулярные кривые, проективная плоскость и проективные кривые. Числа пересечения, теорема Безу.

Источник: J.S. Milne, Elliptic Curves.

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

Групповой закон на эллиптических кривых. Алгоритм Ленстры (ECM) на эллиптических кривых. Вычисления на эллиптических кривых, криптографические протоколы на них.

Источник: J.S. Milne, Elliptic Curves.

Квантовые вычисления

Что квантовый компьютер может сделать лучше, чем классический? Алгоритм Дойча-Йожи. Алгоритм Шора: чем это страшно для криптографии.

Некоммутативная криптография

Некоммутативная криптография: протокол Ко-Ли, протокол Аншель-Аншеля-Голдфельда. Группа кос и криптография в группе кос.