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

Общая информация
ЛекторС. И. Николенко
Семестросень 2009
Дата начала20.09.2009
Количество пар11
Язык курсарусский
Видеоhttp://video.yandex.ru/users/pdmicsclub/collection/3/
Аннотация Курс посвящён конкретным криптографическим протоколам и примитивам: RSA, эллиптической криптографии, разделению секрета, доказательствам с неразглашением. Мы также поговорим об алгоритмах взлома этих примитивов — разложения чисел на множители и дискретного логарифмирования.
Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Введение
(18.08.2010 - 01:45)

Предмет и история криптографии. Криптографические атаки. Криптографические примитивы: хеш–функции, протоколы с секретным и открытым ключом. http://video.yandex.ru/users/pdmicsclub/view/11/?cauthor=pdmicsclub&cid=3
2. Криптография с закрытым ключом
(18.08.2010 - 01:45)

Поточные шифры: линейные сдвиговые регистры, линейная сложность функций, нелинейные сдвиговые регистры. Блочные шифры: ECB, CBC, CFB, OFB. Коды аутентификации сообщений (MAC, message authenticity code). Реализация криптографии с закрытым ключом через хеш–функции. http://video.yandex.ru/users/pdmicsclub/view/10/?cauthor=pdmicsclub&cid=3
3. Криптография с открытым ключом I
(18.08.2010 - 01:45)

Основы теории чисел: алгоритм Евклида, квадратичные вычеты, символ Лежандра. Эквивалентность вычисления квадратного корня по модулю N и разложения N на множители. Криптосистема RSA. Порождение простых чисел, тест Миллера–Рабина. RSA problem. Атаки на RSA. Криптосистема Рабина: стойкость, эквивалентная разложению числа на множители. http://video.yandex.ru/users/pdmicsclub/view/9/?cauthor=pdmicsclub&cid=3
4. Криптография с открытым ключом II
(18.08.2010 - 02:00)

Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–трудность задачи декодирования. Криптосистема МакЭлиса. Задача subset sum, супервозрастающие последовательности. Криптосистема Меркле–Хеллмана. http://video.yandex.ru/users/pdmicsclub/view/6/?cauthor=pdmicsclub&cid=3
5. Решётки в криптографии
(18.08.2010 - 02:00)

Основы теории решёток: базис, определитель, задача поиска кратчайшего вектора (SVP). Ортогонализация Грама–Шмидта. LLL–редуцированные базисы и оценка на размер rратчайшего вектора. Алгоритм LLL. Его применения в криптоанализе: решение subset sum низкой плотности, поиск корней многочленов и атака на RSA с маленькой экспонентой. Криптографические примитивы, основанные на решётках: конструкция семейства хеш–функций Ajtai и идея доказательства стойкости, конструкция криптосистемы Ajtai–Dwork. http://video.yandex.ru/users/pdmicsclub/view/15/
6. Протоколы согласования ключа
(18.08.2010 - 02:00)

Введение. Протокол Диффи–Хеллмана. Типы протоколов и атак, желаемые свойства. Протоколы: простой key transport, AKEP, протокол Шамира. Протоколы с сервером: протокол Отвея–Рииса, Kerberos. Протоколы с цифровой подписью: протокол Нидхэма–Шрёдера, алгоритм X.509. Классические атаки на протоколы согласования ключа. Распределение ключей: нижняя оценка, конструкция Блома. Разделение секрета: схема Блэкли, схема Шамира. http://video.yandex.ru/users/pdmicsclub/view/34/
7. Разложение чисел на множители
(18.08.2010 - 02:00)

Введение: метод Ферма. Метод Крайчика. Гладкие числа. Оценка сложности метода Крайчика на базе обобщения теоремы Мертенса. Решето Эратосфена для поиска гладких чисел. Квадратичное решето. Оценка сложности. Сложность решения линейной системы. http://video.yandex.ru/users/pdmicsclub/view/53/
8. Задача дискретного логарифма I
(18.08.2010 - 02:00)

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

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

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

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