SEWiki - Вклад участника [ru]

Криптографические протоколы 4MIT осень 2017

2017-12-26T12:55:42Z

Alra: /* Лекции */

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

== Лекции ==
'''Лекция 1'''.

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

'''Лекции 2 и 3'''. Симметричные криптосистемы. Потоковые шифры.

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

Слайды: [[Медиа:Лекция2-3.pdf]]

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

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

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

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

Режимы использования блочных шифров (“электронная кодовая книга”, режимы с зацеплением, режимы использования блочных шифров для получения поточных шифров).
Детерминированные и недерминированные алгоритмы шифрования. Влияние случайности на стойкость. Слабости блочных шифров.

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

'''Лекция 6 '''. Контроль целостности.

MAC. Определение, модель безопасности. Построение на базе Блоковых шифров: BCB-MAC, NMAC, PMAC.

'''Лекция 7 '''. Хэш-функции.

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

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

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

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

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

Схема шифрования ElGamal. Базовые задачи, допущение Диффи и Хелмана. Схема шифрования Меркла-Хелмана. Электронная цифровая подпись. Основные понятия, требования. Определение безопасности.

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

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

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

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

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

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

'''Лекция 12 '''. Протоколы цифровых денег и электронного голосования.

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

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

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

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

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

'''Лекция 13 '''. ПРОТОКОЛЫ ИДЕНТИФИКАЦИИ + личностная криптография.

Схема идентификации Schnorr – Shamir. Схема идентификации Feige – Fiat – Shamir. Инфраструктура открытых ключей и альтернативные подходы(ID-based распределенные системы).

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

'''Лекция 14 '''. Пост-квантовая криптография.

Понятия квантовых вычислений. Построение криптосистем на доказано сложных задачах. Линейные коды. Способы задания. Декодирование линейных кодов как «трудная» задача. Декодирование линейных кодов как «простая» задача. NP- полные задачи кодирования. Системы Макэлиса и Нидерайтора.

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

----

'''[[Вопросы по курсу]]''':[[Медиа:Вопросы по курсу_Криптографические протоколы.pdf]]

----

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

1) D. Boneh and V. Shoup. A Graduate Course in Applied Cryptography. [https://crypto.stanford.edu/~dabo/courses/OnlineCrypto/]

2) ван Тилборг. Основы криптологии. [http://bwbooks.net/books/kriptologiya/tilborg-xka/2006/files/osnovikriptologiyi2006.pdf]

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.'''
Оценить теоретически количество зашифрованного текста (в символах) для успешного частотного криптоанализа и подтвердить результаты экспериментально, если известно, что открытый текст – это осмысленный текст на русском языке и была использована следующая система шифрования:

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

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

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

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

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

Необходимо:

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

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

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

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

'''Задание 3.'''

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

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

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

----

Занятие 2. Потоковые шифры

'''Задача 1.'''

Рассмотреть генератор псевдослучайной последовательности. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем <math> x_0= x^2 mod M</math>. <math>x_0</math> называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется <math> x_{n+1}= x_{n}^2 mod M</math>. Результатом n-го шага является бит чётности числа <math>х_{n+1}</math>, то есть сумма по модулю 2 единиц в двоичном представлении элемента.

Для данного генератора оценить статистические свойства при помощи следующих тестов:

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

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

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

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

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

Построить для генератора профиль линейной сложности (+5 баллов)

'''Задача 2.'''

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

Является ли данный генератор G предсказуемым для какого-либо i∈{0,n-1}?

'''Задача 3.'''

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

'''Задача 4.'''

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

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

<math> Adv_{SS} [A,E] ≤ 2Adv_{PRG} [B,G]</math>

-----

Занятие 3. Блоковые шифры.

'''Задача 1.'''

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

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

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

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

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

'''Задача 2.'''

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

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

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

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

-----

Занятие 4. MAC и хэш-функции.

'''Задача 1.'''

Рассмотрим MAC Картера-Вегмана (Carter-‐Wegman MAC) <math>I_{CW}=(S_{CW},V_{CW})</math>, который строится на основе стойкого одноразового MAC I=(S,V) и стойкой PRF функции F(k,m).
Проверочное значение tag формируется по правилу:
<math>tag=S_{CW} ((k_1,k_2 ),m)=(r,F(k_1,r) \ XOR \ S(k_2,m)),r <-R- \left\{ 0,1 \right\} ^n )</math>

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

'''Задача 2.'''

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

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

'''Задача 3.'''

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

''Итоговое задание''

В предложенной статье: разобрать протокол постановки подписи,
построить пример или реализовать исходный протокол, предложить требуемую модификация протокола,
привести доказательство стойкости нового протокола.

Варианты задания можно выбрать самостоятельно.

'''Вариант 1.'''
Статья: [[Медиа:TS_RSA_shoup.pdf]]

Дополнить процедурой выдачи новой проекции ключа без дилера.

'''Вариант 2.'''
Статья: [[Медиа:TS_RSA1.pdf]]

Дополнить процедурой выдачи новой проекции ключа без дилера.

'''Вариант 3.'''
Статья: [[Медиа:TS_RSA2.pdf]]

Дополнить процедурой обновления проекций участников без замены общего секрета.

'''Вариант 4.'''
Статья: [[Медиа:TS_RSA3.pdf]]

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

'''Вариант 5.'''
Статья: [[Медиа:gost-34.10-2012.pdf]]

Предложить пороговую схему k из n реализации российского стандарта ЭЦП.

Файл:Вопросы по курсу Криптографические протоколы.pdf

2017-12-26T12:42:27Z

Alra:

Файл:Лекция14.pdf

2017-12-26T12:42:04Z

Alra:

Файл:Лекция13.pdf

2017-12-26T12:41:45Z

Alra:

Файл:Лекция12c.pdf

2017-12-26T12:41:26Z

Alra:

Файл:Лекция12b.pdf

2017-12-26T12:41:00Z

Alra:

Файл:Лекция12a.pdf

2017-12-26T12:37:37Z

Alra:

Файл:Лекция11.pdf

2017-12-26T12:12:17Z

Alra:

Файл:Лекция10.pdf

2017-12-26T12:11:54Z

Alra:

Криптографические протоколы 4MIT осень 2017

2017-12-13T10:38:12Z

Alra: /* Лекции */

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

== Лекции ==
'''Лекция 1'''.

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

'''Лекции 2 и 3'''. Симметричные криптосистемы. Потоковые шифры.

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

Слайды: [[Медиа:Лекция2-3.pdf]]

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

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

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

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

Режимы использования блочных шифров (“электронная кодовая книга”, режимы с зацеплением, режимы использования блочных шифров для получения поточных шифров).
Детерминированные и недерминированные алгоритмы шифрования. Влияние случайности на стойкость. Слабости блочных шифров.

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

'''Лекция 6 '''. Контроль целостности.

MAC. Определение, модель безопасности. Построение на базе Блоковых шифров: BCB-MAC, NMAC, PMAC.

'''Лекция 7 '''. Хэш-функции.

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

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

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

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

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

Схема шифрования ElGamal. Базовые задачи, допущение Диффи и Хелмана. Схема шифрования Меркла-Хелмана. Электронная цифровая подпись. Основные понятия, требования. Определение безопасности.

----

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

1) D. Boneh and V. Shoup. A Graduate Course in Applied Cryptography. [https://crypto.stanford.edu/~dabo/courses/OnlineCrypto/]

2) ван Тилборг. Основы криптологии. [http://bwbooks.net/books/kriptologiya/tilborg-xka/2006/files/osnovikriptologiyi2006.pdf]

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.'''
Оценить теоретически количество зашифрованного текста (в символах) для успешного частотного криптоанализа и подтвердить результаты экспериментально, если известно, что открытый текст – это осмысленный текст на русском языке и была использована следующая система шифрования:

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

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

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

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

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

Необходимо:

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

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

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

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

'''Задание 3.'''

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

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

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

----

Занятие 2. Потоковые шифры

'''Задача 1.'''

Рассмотреть генератор псевдослучайной последовательности. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем <math> x_0= x^2 mod M</math>. <math>x_0</math> называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется <math> x_{n+1}= x_{n}^2 mod M</math>. Результатом n-го шага является бит чётности числа <math>х_{n+1}</math>, то есть сумма по модулю 2 единиц в двоичном представлении элемента.

Для данного генератора оценить статистические свойства при помощи следующих тестов:

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

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

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

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

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

Построить для генератора профиль линейной сложности (+5 баллов)

'''Задача 2.'''

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

Является ли данный генератор G предсказуемым для какого-либо i∈{0,n-1}?

'''Задача 3.'''

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

'''Задача 4.'''

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

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

<math> Adv_{SS} [A,E] ≤ 2Adv_{PRG} [B,G]</math>

-----

Занятие 3. Блоковые шифры.

'''Задача 1.'''

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

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

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

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

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

'''Задача 2.'''

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

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

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

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

-----

Занятие 4. MAC и хэш-функции.

'''Задача 1.'''

Рассмотрим MAC Картера-Вегмана (Carter-‐Wegman MAC) <math>I_{CW}=(S_{CW},V_{CW})</math>, который строится на основе стойкого одноразового MAC I=(S,V) и стойкой PRF функции F(k,m).
Проверочное значение tag формируется по правилу:
<math>tag=S_{CW} ((k_1,k_2 ),m)=(r,F(k_1,r) \ XOR \ S(k_2,m)),r <-R- \left\{ 0,1 \right\} ^n )</math>

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

'''Задача 2.'''

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

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

'''Задача 3.'''

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

''Итоговое задание''

В предложенной статье: разобрать протокол постановки подписи,
построить пример или реализовать исходный протокол, предложить требуемую модификация протокола,
привести доказательство стойкости нового протокола.

Варианты задания можно выбрать самостоятельно.

'''Вариант 1.'''
Статья: [[Медиа:TS_RSA_shoup.pdf]]

Дополнить процедурой выдачи новой проекции ключа без дилера.

'''Вариант 2.'''
Статья: [[Медиа:TS_RSA1.pdf]]

Дополнить процедурой выдачи новой проекции ключа без дилера.

'''Вариант 3.'''
Статья: [[Медиа:TS_RSA2.pdf]]

Дополнить процедурой обновления проекций участников без замены общего секрета.

'''Вариант 4.'''
Статья: [[Медиа:TS_RSA3.pdf]]

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

'''Вариант 5.'''
Статья: [[Медиа:gost-34.10-2012.pdf]]

Предложить пороговую схему k из n реализации российского стандарта ЭЦП.

Файл:TS RSA3.pdf

2017-12-05T13:05:57Z

Alra: J. Kong, P. Zerfos, H. Luo, S. Lu, and L. Zhang. "Providing Robust and Ubiquitous Security Support for MANET"

J. Kong, P. Zerfos, H. Luo, S. Lu, and L. Zhang. "Providing Robust and Ubiquitous Security Support for MANET"

Криптографические протоколы 4MIT осень 2017

2017-12-05T13:04:34Z

Alra: /* Практика */

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

== Лекции ==
'''Лекция 1'''.

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

'''Лекции 2 и 3'''. Симметричные криптосистемы. Потоковые шифры.

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

Слайды: [[Медиа:Лекция2-3.pdf]]

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

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

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

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

Режимы использования блочных шифров (“электронная кодовая книга”, режимы с зацеплением, режимы использования блочных шифров для получения поточных шифров).
Детерминированные и недерминированные алгоритмы шифрования. Влияние случайности на стойкость. Слабости блочных шифров.

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

'''Лекция 6 '''. Контроль целостности.

MAC. Определение, модель безопасности. Построение на базе Блоковых шифров: BCB-MAC, NMAC, PMAC.

'''Лекция 7 '''. Хэш-функции.

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

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

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

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

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

Схема шифрования ElGamal. Базовые задачи, допущение Диффи и Хелмана. Схема шифрования Меркла-Хелмана. Электронная цифровая подпись. Основные понятия, требования. Определение безопасности.

== Практика ==
Занятие 1. Исторические шифры и частотный криптоанализ.

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

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

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

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

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

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

Необходимо:

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

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

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

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

'''Задание 3.'''

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

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

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

----

Занятие 2. Потоковые шифры

'''Задача 1.'''

Рассмотреть генератор псевдослучайной последовательности. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем <math> x_0= x^2 mod M</math>. <math>x_0</math> называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется <math> x_{n+1}= x_{n}^2 mod M</math>. Результатом n-го шага является бит чётности числа <math>х_{n+1}</math>, то есть сумма по модулю 2 единиц в двоичном представлении элемента.

Для данного генератора оценить статистические свойства при помощи следующих тестов:

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

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

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

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

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

Построить для генератора профиль линейной сложности (+5 баллов)

'''Задача 2.'''

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

Является ли данный генератор G предсказуемым для какого-либо i∈{0,n-1}?

'''Задача 3.'''

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

'''Задача 4.'''

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

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

<math> Adv_{SS} [A,E] ≤ 2Adv_{PRG} [B,G]</math>

-----

Занятие 3. Блоковые шифры.

'''Задача 1.'''

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

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

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

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

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

'''Задача 2.'''

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

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

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

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

-----

Занятие 4. MAC и хэш-функции.

'''Задача 1.'''

Рассмотрим MAC Картера-Вегмана (Carter-‐Wegman MAC) <math>I_{CW}=(S_{CW},V_{CW})</math>, который строится на основе стойкого одноразового MAC I=(S,V) и стойкой PRF функции F(k,m).
Проверочное значение tag формируется по правилу:
<math>tag=S_{CW} ((k_1,k_2 ),m)=(r,F(k_1,r) \ XOR \ S(k_2,m)),r <-R- \left\{ 0,1 \right\} ^n )</math>

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

'''Задача 2.'''

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

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

'''Задача 3.'''

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

''Итоговое задание''

В предложенной статье: разобрать протокол постановки подписи,
построить пример или реализовать исходный протокол, предложить требуемую модификация протокола,
привести доказательство стойкости нового протокола.

Варианты задания можно выбрать самостоятельно.

'''Вариант 1.'''
Статья: [[Медиа:TS_RSA_shoup.pdf]]

Дополнить процедурой выдачи новой проекции ключа без дилера.

'''Вариант 2.'''
Статья: [[Медиа:TS_RSA1.pdf]]

Дополнить процедурой выдачи новой проекции ключа без дилера.

'''Вариант 3.'''
Статья: [[Медиа:TS_RSA2.pdf]]

Дополнить процедурой обновления проекций участников без замены общего секрета.

'''Вариант 4.'''
Статья: [[Медиа:TS_RSA3.pdf]]

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

'''Вариант 5.'''
Статья: [[Медиа:gost-34.10-2012.pdf]]

Предложить пороговую схему k из n реализации российского стандарта ЭЦП.

Файл:TS RSA2.pdf

2017-12-05T10:41:17Z

Alra: А.Д. Фомин. "Распределенная подпись RSA"

А.Д. Фомин. "Распределенная подпись RSA"

Файл:Gost-34.10-2012.pdf

2017-12-05T10:32:28Z

Alra: Российский стандарт ЭЦП

Российский стандарт ЭЦП

Файл:Robust Threshold Dss Signatures.pdf

2017-12-05T10:30:35Z

Alra: Rosario Gennaro "Robust Threshold DSS Signatures"

Rosario Gennaro "Robust Threshold DSS Signatures"

Файл:TS RSA1.pdf

2017-12-05T10:28:54Z

Alra: Rosario Gennaro, Shai Halevi, Hugo Krawczyk, Tal Rabin. "Threshold RSA for Dynamic and Ad-Hoc Groups"

Rosario Gennaro, Shai Halevi, Hugo Krawczyk, Tal Rabin. "Threshold RSA for Dynamic and Ad-Hoc Groups"

Файл:TS RSA shoup.pdf

2017-12-05T10:27:04Z

Alra: V. Shoup. "Practical Threshold Signatures"

V. Shoup. "Practical Threshold Signatures"

Файл:Лекция7.pdf

2017-11-20T14:11:59Z

Alra:

Криптографические протоколы 4MIT осень 2017

2017-11-20T14:11:16Z

Alra:

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

== Лекции ==
'''Лекция 1'''.

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

'''Лекции 2 и 3'''. Симметричные криптосистемы. Потоковые шифры.

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

Слайды: [[Медиа:Лекция2-3.pdf]]

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

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

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

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

Режимы использования блочных шифров (“электронная кодовая книга”, режимы с зацеплением, режимы использования блочных шифров для получения поточных шифров).
Детерминированные и недерминированные алгоритмы шифрования. Влияние случайности на стойкость. Слабости блочных шифров.

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

'''Лекция 6 '''. Контроль целостности.

MAC. Определение, модель безопасности. Построение на базе Блоковых шифров: BCB-MAC, NMAC, PMAC.

'''Лекция 7 '''. Хэш-функции.

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

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

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

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

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

Схема шифрования ElGamal. Базовые задачи, допущение Диффи и Хелмана. Схема шифрования Меркла-Хелмана. Электронная цифровая подпись. Основные понятия, требования. Определение безопасности.

== Практика ==
Занятие 1. Исторические шифры и частотный криптоанализ.

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

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

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

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

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

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

Необходимо:

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

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

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

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

'''Задание 3.'''

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

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

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

----

Занятие 2. Потоковые шифры

'''Задача 1.'''

Рассмотреть генератор псевдослучайной последовательности. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем <math> x_0= x^2 mod M</math>. <math>x_0</math> называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется <math> x_{n+1}= x_{n}^2 mod M</math>. Результатом n-го шага является бит чётности числа <math>х_{n+1}</math>, то есть сумма по модулю 2 единиц в двоичном представлении элемента.

Для данного генератора оценить статистические свойства при помощи следующих тестов:

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

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

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

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

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

Построить для генератора профиль линейной сложности (+5 баллов)

'''Задача 2.'''

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

Является ли данный генератор G предсказуемым для какого-либо i∈{0,n-1}?

'''Задача 3.'''

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

'''Задача 4.'''

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

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

<math> Adv_{SS} [A,E] ≤ 2Adv_{PRG} [B,G]</math>

-----

Занятие 3. Блоковые шифры.

'''Задача 1.'''

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

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

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

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

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

'''Задача 2.'''

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

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

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

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

-----

Занятие 4. MAC и хэш-функции.

'''Задача 1.'''

Рассмотрим MAC Картера-Вегмана (Carter-‐Wegman MAC) <math>I_{CW}=(S_{CW},V_{CW})</math>, который строится на основе стойкого одноразового MAC I=(S,V) и стойкой PRF функции F(k,m).
Проверочное значение tag формируется по правилу:
<math>tag=S_{CW} ((k_1,k_2 ),m)=(r,F(k_1,r) \ XOR \ S(k_2,m)),r <-R- \left\{ 0,1 \right\} ^n )</math>

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

'''Задача 2.'''

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

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

'''Задача 3.'''

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

Криптографические протоколы 4MIT осень 2017

2017-11-01T15:10:45Z

Alra: /* Практика */

Файл:Лекция5.pdf

2017-11-01T13:37:11Z

Alra:

Криптографические протоколы 4MIT осень 2017

2017-11-01T13:31:00Z

Alra: /* Лекции */

Криптографические протоколы 4MIT осень 2017

2017-10-06T07:11:07Z

Alra: /* Лекции */

Файл:Лекция4.pdf

2017-10-06T07:06:09Z

Alra:

Криптографические протоколы 4MIT осень 2017

2017-10-06T07:05:09Z

Alra: /* Практика */

Криптографические протоколы 4MIT осень 2017

2017-10-02T10:21:51Z

Alra: /* Лекции */

Файл:Лекция2-3.pdf

2017-10-02T10:19:10Z

Alra: Слайды к лекциям 2 и 3

Слайды к лекциям 2 и 3

Криптографические протоколы 4MIT осень 2017

2017-10-02T10:17:34Z

Alra: /* Лекции */

Криптографические протоколы 4MIT осень 2017

2017-09-11T09:43:43Z

Alra: /* Практика */

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

== Лекции ==

== Практика ==
Занятие 1. Исторические шифры и частотный криптоанализ.

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

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

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

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

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

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

Необходимо:

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

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

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

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

'''Задание 3.'''

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

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

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