Криптографические протоколы 3 модуль 2019

Материал из CSC Wiki
Перейти к:навигация, поиск

Преподаватель: Афанасьева Александра

Лекции

Лекция 1.

Основные понятия криптографии. Предмет и задачи. Определение шифра, понятие стойкости, предположения об исходных условиях криптоанализа, симметричные и асимметричные криптосистемы, криптографические протоколы. История криптографии. Принцип Керкгоффса. Понятие абсолютной стойкости или теоретико-информационной стойкости.

Медиа:Лекция1.pdf

Лекция 2.

Симметричные криптосистемы. Потоковые шифры 1. Одноразовый блокнот. Понятие псевдослучайности. Требования к потоковым шифрам: Постулаты Голомба, профиль линейной сложности. Статистические тесты. Методы построения больших периодов в поточных шифрах.

Медиа:Лекция2.pdf

Лекция 3.

Симметричные криптосистемы. Потоковые шифры 2.Нелинейные генераторы. Атаки на потоковые шифры. Понятие псевдослучайного генератора (PRG) и его криптографическая стойкость. Семантическая стойкости криптосистемы.

Медиа:Лекция 3.pdf

Лекция 4.

Симметричные криптосистемы. Блоковые шифры 1.

Определение блокового шифра. Требования к блоковым шифрам. Различие понятий PRP и PRF. Определение стойкости. Способы построение блоковых шифров: подстановки, перестановки, сети Фейстеля. Алгоритм DES.

Слайды: Медиа:Лекция_4.pdf

Лекция 5.

Симметричные криптосистемы. Блоковые шифры 2.

Режимы использования блочных шифров (“электронная кодовая книга”, режимы с зацеплением, режимы использования блочных шифров для получения поточных шифров). Детерминированные и недерминированные алгоритмы шифрования. Влияние случайности на стойкость. Слабости блочных шифров. Контроль целостности. MAC. Определение, модель безопасности. Построение на базе Блоковых шифров: BCB-MAC, NMAC, PMAC.

Слайды: Медиа:Лекция_5.pdf

Лекция 6.

Стойкость к колизиям. Требования к хэш-функциям. Парадокс ДР. Примеры хэш-функций. HMAC. CCA модель атак и аутентифицированное шифрование. Способы построения AE. Стандарты.

Слайды: Медиа:Лекция_6.pdf

Лекция 7 . Основные алгоритмы с открытым ключом 1.

Схема RSA. Атаки на RSA. Базовые задачи, допущение Диффи и Хелмана. Возможность реализации систем на мультипликативной группе точек эллиптических кривых.Схема шифрования Меркла-Хелмана.

Слайды: Медиа:Лекция_8.pdf

Лекция 8 . Управление ключами 1.

Попарные ключи. Использование мастер-ключей. Система Диффи и Хелмана. Человек посередине. Протоколы обмена ключами. С сервером, без сервера. Известные атаки на протоколы обмена ключами.

Слайды: Медиа:Лекция10.pdf

Лекция 9 . Управление ключами 2.

K-надежные схемы распределения ключей. Протоколы разделения секрета. Пороговая криптография.

Слайды: Медиа:Лекция11.pdf

Лекция 10 . Протоколы электронного голосования.

Протоколы электронного голосования. Криптографическая реализация. Слепая подпись. Требования безопасности. Доказательства с нулевым разглашением. Примеры систем.

Слайды: Медиа:Лекция12.pdf

Слайды: Медиа:Лекция12a.pdf

Слайды: Медиа:Лекция12b.pdf



Вопросы по курсу

Медиа:Вопросы по курсу.pdf


Список литературы

1) D. Boneh and V. Shoup. A Graduate Course in Applied Cryptography. [1]

2) ван Тилборг. Основы криптологии. [2]

3) Van Tilborg Henk C.A., Jajodia Sushil (Eds.) Encyclopedia of Cryptography and Security.

4) Menezes A.J., Van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography.

5) Б. Шнайер. Прикладная криптография.


Домашнее задание

Задание 1.

Задача 1.[4 балла]

Оценить теоретически количество зашифрованного текста (в символах) для успешного частотного криптоанализа и подтвердить результаты экспериментально, если известно, что открытый текст – это осмысленный текст на русском языке и была использована следующая система шифрования:

1) Шифр Цезаря;

2) Аффинный шифр;

3) Шифр Вижинера с известной длиной ключа (показать зависимость от длины ключа);

4) Шифр Вижинера с неизвестной длиной ключа (показать зависимость от длины ключа).


Задача 2.[4 балла]

Простым перестановочным шифром зашифрован некий текст, при этом известно, что в качестве открытого текста использован палиндром, в котором все пробелы и знаки препинания опущены. В результате шифрования получен следующий текст: МТИССЛАИЛПНАОЛМУИЛОПИТУ

Необходимо:

1) Расшифровать текст,

2) Оценить, насколько можно уменьшить сложность перебора, используя информацию об исходном сообщении;

3) При программной реализации минимизировать количество возвращаемых вариантов ответа.

4) Позволяет ли успешный криптоанализ данного сообщения раскрыть ключ шифрования?


Задача 3.[2 балла]

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

Э рсдх ыъсг, фрьыя сяы тцорт срэдт
Юрь нфурсау уцир нэръ, мрьыя
Нрусиъ рнмясяэуцэяуц нурэрт,
Нурэрт оячолжяуц ьрорыя.

1) Расшифровать текст,

2) Позволяет ли успешный криптоанализ данного сообщения раскрыть ключ шифрования?


Задание 2 (Лекции 2-3)

Задача 1. [6 баллов]

Рассмотреть генератор псевдослучайной последовательности. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем x_0=x^2 mod M. x_0 называется стартовым числом генератора. На каждом n-м шаге работы генератора вычисляется x_n=x_(n-1)^2 mod M . Результатом n-го шага является бит чётности числа x_n , то есть сумма по модулю 2 единиц в двоичном представлении элемента. Для данного генератора оценить статистические свойства при помощи следующих тестов:

1) (monobit test) равно ли количество нулей и единиц;

2) (two-bit test) равно ли количество 00, 01, 10 и 11;

3) (poker test) равно ли количество разных последовательностей длины m;

4) (runs test) подходящее ли количество последовательностей идущих подряд нулей и единиц той или иной длины;

5) (autocorrelation test) одинаковая ли автокорреляция на разных сдвигах;

6) Построить для генератора профиль линейной сложности


Задача 2. [2 баллов]

Пусть G:K→{0,1}^n псевдослучайный генератор, про который известно, что для него по значениям последних n/2 бит можно построить первые n/2 бит. Является ли данный генератор G предсказуемым для какого-либо i∈{0,n-1}?


Задача 3. [3 баллов]

Доказать, что одноразовый блокнот является семантически стойким алгоритмом шифрования.


Задача 4. [6 баллов]

Пусть G:K→{0,1}^n криптографически стойкий псевдослучайный генератор (PRG), тогда потоковый шифр, основанный на нем, будет семантически стойким.

Чтобы подтвердить это утверждение докажите, что для любого атакующего шифр алгоритма A, существует алгоритм B для функции G, такой что:

Adv_SS[A,E] ≤ 2Adv_PRG[B,G]


Оценка Критерии выставления оценки

«Отлично»(8-10) Решено задач на 12 или более баллов

«Хорошо»(6-7) Решено задач на 9-11,5 баллов

«Удовлетворительно»(4-5) Решено задач на 5-8 баллов

«Неудовлетворительно» (0-2) Решено задач на менее чем 5 баллов


Задание 3 (Лекции 4-5)


Задача 1. [1,5 балла]

Рассмотрим MAC Картера-Вегмана (Carter-­‐Wegman MAC) I_CW=(S_CW,V_CW), который строится на основе стойкого одноразового MAC I=(S,V) и стойкой PRF функции F(k,m). Проверочное значение tag формируется по правилу:

tag=S_CW ((k_1,k_2 ),m)=(r,F(k_1,r) XOR S(k_2,m)), r<--{0,1}^n )

Построить функцию верификации для проверки сообщения V_CW (m,tag).


Задача 2. [5 баллов]

Предложить хэш-функцию, стойкую к коллизиям h(H,m), на основе стойкого блокового шифра E:K×{0,1}^n ->{0,1}^n. Предложенная хэш-функция должна отображать

h:({0,1}^n) x ({0,1}^n) →{0,1}^n.

Какое максимальное количество различных конструкций с данными свойствами вы можете предложить?


Задача 3. [3 балла]

Будет ли стойкой к коллизиям хэш-функция, на основе стойкого блокового шифра E: K×{0,1}^n -→{0,1}^n, следующего вида: h(H,m) = E(m,H) XOR m?

Ответ обосновать.


Задача 4. [2 балла]

Оценить во сколько раз увеличится длина передаваемого сообщения в 1 байт, если оно зашифровано:

алгоритмом шифрования АES в режиме CBC со случайным IV.

алгоритмом шифрования АES в режиме CTR.

алгоритмом шифрования АES в режиме OFB со случайным IV.

алгоритмом шифрования 3DES в режиме CBC со случайным IV.


Задача 5. [3 балла]

Пусть заданы множества X={0,1} и K={0,1}.

Определим псевдослучайную перестановку PRP следующим образом: E(k,x) = x XOR k.

Будет ли эта перестановка криптографически стойкой? Будет ли предложенная функция псевдослучайной функцией PRF?


Критерии оценивания и шкала оценки

Оценка Критерии выставления оценки

«Отлично»(8-10) Решено задач на 12 или более баллов

«Хорошо»(6-7) Решено задач на 9-11,5 баллов

«Удовлетворительно»(4-5) Решено задач на 4-8 баллов

«Неудовлетворительно» (0-2) Решено задач на менее чем 4 баллов