Криптографические протоколы весна 2020 — различия между версиями

Материал из CSC Wiki
Перейти к:навигация, поиск
(Домашние задания)
(Домашние задания)
Строка 51: Строка 51:
 
Задача 1.
 
Задача 1.
  
Рассмотреть генератор псевдослучайной последовательности. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем {\displaystyle x_0= x^2 mod M}. {\displaystyle x_0} называется стартовым числом генератора.
+
Рассмотреть генератор псевдослучайной последовательности. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем <math> x_0= x^2 mod M </math>. <math> x_0 </math> называется стартовым числом генератора.
  
На каждом n-м шаге работы генератора вычисляется {\displaystyle x_{n+1}= x_{n}^2 mod M}. Результатом n-го шага является бит чётности числа {\displaystyle х_{n+1}}, то есть сумма по модулю 2 единиц в двоичном представлении элемента.
+
На каждом n-м шаге работы генератора вычисляется <math> x_{n+1}= x_{n}^2 mod M </math>. Результатом n-го шага является бит чётности числа <math> х_{n+1} </math>, то есть сумма по модулю 2 единиц в двоичном представлении элемента.
  
 
Для данного генератора оценить статистические свойства при помощи следующих тестов:
 
Для данного генератора оценить статистические свойства при помощи следующих тестов:
Строка 76: Строка 76:
 
Задача 3.
 
Задача 3.
  
Пусть {\displaystyle G:K->{0,1}^n} криптографически стойкий псевдослучайный генератор (PRG), тогда потоковый шифр, основанный на нем, будет семантически стойким.
+
Пусть <math> G:K->{0,1}^n</math> криптографически стойкий псевдослучайный генератор (PRG), тогда потоковый шифр, основанный на нем, будет семантически стойким.
  
 
Чтобы подтвердить это утверждение докажите, что для любого атакующего шифр алгоритма A, существует алгоритм B для функции G, такой что:
 
Чтобы подтвердить это утверждение докажите, что для любого атакующего шифр алгоритма A, существует алгоритм B для функции G, такой что:
  
{\displaystyle Adv_{SS} [A,E] ≤ 2Adv_{PRG} [B,G]}
+
<math> Adv_{SS} [A,E] ≤ 2Adv_{PRG} [B,G] </math>
  
 
'''Занятие 3. Блоковые шифры.'''
 
'''Занятие 3. Блоковые шифры.'''
Строка 101: Строка 101:
 
Пусть заданы множества X={0,1} и K={0,1}.
 
Пусть заданы множества X={0,1} и K={0,1}.
  
Определим псевдослучайную перестановку PRP следующим образом: {\displaystyle E(k,x) = x \ XOR \ k }.
+
Определим псевдослучайную перестановку PRP следующим образом: <math>  E(k,x) = x \ XOR \ k </math>.
  
 
Будет ли эта перестановка криптографически стойкой PRP?
 
Будет ли эта перестановка криптографически стойкой PRP?
  
 
Будет ли предложенная функция псевдослучайной функцией PRF?
 
Будет ли предложенная функция псевдослучайной функцией PRF?

Версия 17:48, 22 января 2020

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

Лекции

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

Задание 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, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое с М. Вычисляем . называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется . Результатом n-го шага является бит чётности числа Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («<p>Во время обработки HTTP-запроса обнаружена проблема: 400 Bad Request </p>») от сервера «https://mathoid-beta.wmflabs.org»:): х_{n+1} , то есть сумма по модулю 2 единиц в двоичном представлении элемента.

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

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

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

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

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

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

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


Задача 2.

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

Задача 3.

Пусть криптографически стойкий псевдослучайный генератор (PRG), тогда потоковый шифр, основанный на нем, будет семантически стойким.

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

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («<p>Во время обработки HTTP-запроса обнаружена проблема: 400 Bad Request </p>») от сервера «https://mathoid-beta.wmflabs.org»:): Adv_{SS} [A,E] ≤ 2Adv_{PRG} [B,G]


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

Задача 1.

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

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

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

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

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


Задача 2.

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

Определим псевдослучайную перестановку PRP следующим образом: .

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

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