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

117
кажите, что ваше определение эквивалентно Определению 3.25.
Рассмотрим функцию с ключом F : Для параметра безопасности n, ключ — 
это матрица A логических значений размера n × n и n-битный вектор логиче-
ских значений b. Дайте определение FA,b : {0, 1}n → {0, 1}n by FA,b(x) Ax 
+ b, где все операции производятся по модулю 2. Продемонстрируйте, что F не 
является всевдослучайной функцией .
Докажите, что если F — псевдослучайная функция, сохраняющая длину, то 
tt(s) F (1)||F (2)|| • • • ||F (A) — псевдослучайный генератор с коэффициентом 
расширения A • n.
Определите понятия абсолютной стойкости при атаке с выбором открытого 
текста, изменив Определение 3.22. Продемонстрируйте, что определение не мо-
жет быть завершено.
Докажите Предположение 3.27.
Подсказка: Используйте результаты Приложения А.4.
Предположим существование псевдослучайных перестановок. Покажите, 
что существует функция F r , которая является псевдослучайной перестановкой, 
но не является строгой псевдослучайной перестановкой.
Подсказка: Постройте F r , такую что F r (k) = 0|k|.
Пусть F — псевдослучайная перестановка. Определим шифровальную схему 
с фиксированной длиной (Enc, Dec) следующим образов: На входе m ∈ {0, 1}n/2
и ключ k ∈ {0, 1}n, алгоритм Enc выбирает единообразную последовательностьr 
∈
{0, 1}n/2 длины n/2 и вычисляет c := Fk (r||m).
Покажите расшифровку и докажите, что эта схема устойчива к АВОТ для со-
общений длины n/2. (Если вы хотите действительно сложное задание, докажите, 
что эта схема устойчива к АВШ, если F — строгая псевдослучайная перестановка.)
Пусть F — псевдослучайная функция и tt — псевдослучайный генератор с
коэффициентом расширения A(n) = n + 1. Для каждой из следующий схем шиф-
рования укажите, обладает ли схема неразличимыми шифрованиями в присут-
ствии перехватчика и устойчива ли она к АВОТ. (В каждом случае общедоступ-
ным ключом является единообразный k ∈ {0, 1}n.) Поясните свой ответ.
(a) Для шифрования m ∈ {0, 1}n+1, выбрать идинообразную r ∈ {0, 1}n и вы-
дать шифртекст (r, tt(r) ⊕ m).
(b) Для шифрования m ∈ {0, 1}n, выдать шифртекст m ⊕ Fk (0n).
(c) Для шифрования m ∈ {0, 1}2n, анализировать m как m1»m2 с |m1| = |m2|, 
затем выбрать единообразную r ∈ {0, 1}n и послать (r, m1 ⊕Fk(r), m2 ⊕Fk(r+1)).
Рассмотрим версию шифрования в режиме СШВ с сохранением состояния, 

118
где отправитель просто увеличивает IV на 1 каждый раз, когда шифруется со-
общение (вместо того, чтобы произвольно выбирать IV каждый раз). Покажите, 
что полученная схема не устойчива к АВОТ.
Каков эффект однобитной ошибки в шифртексте при использовании режи-
мов СШВ, ОСВ и режима счетчика?
Каков эффект произведет пропущенный блок шифртекста (т.е. если переда-
ваемый шифртекст c1, c2, c3, . . . получен как c1, c3, . . .) при использовании 
режимов СШВ, ОСВ и режима счетчика ?
Представим, что для шифрования сообщения 1024-битной длины используется 
шифрование в режиме СШВ используется с блочным шифром, имеющим 256-бит-
ный ключ и 128-битную длину блока. Какова длина полученного шифртекста?
Предоставьте подробности доказательства от обратного для Уравнения (3.12).
Пусть F — псевдослучайная функция, такая что для k ∈ {0, 1}n функция Fk
отображает Ain(n)-битные входные данные на Aout(n)-битные выходные данные.
(a) Рассмотрим применение шифрования в режиме счетчика с помощью F . Для 
каких функций Ain, Aout полученная схема шифрования устойчива к АВОТ?
(b) Рассмотрим применение шифрования в режиме счетчика с помощью F , 
но только для сообщений фиксированной длины A(n) (которое является целым 
кратным Aout(n)). Для каких Ain, Aout, A эта схема имеет неразличимые шиф-
рования в присутствии перехватчика?
Для любой функции g : {0, 1}n → {0, 1}n, определим g$(•) как вероят-
ностн ый оракул, который на входе 1n, выбирает единообразную r ∈ {0, 1}n
и возвращает (r, g(r)). Функция с ключом F является слабой псевдослучайной 
функцией для всех ppt алгоритмов D, существует пренебрежимо малая функ-
ция negl, такая что:
где k ∈ {0, 1}n и f ∈ Funcn выбраны равномерно.
(a) Докажите, что если F псевдослучайна, то она слабо псевдослучайна.
(b) Пусть F r — псевдослучайная функция. Определим
Докажите, что F слабо псевдослучайна, но не псевдослучайна.
(c) Обязательно ли шифрование в режиме счетчика, использующее слабо 
псевдослучайную функцию, является учтойчивым в АВОТ? Обязательно ли 
оно имеет неразличимые шифрования в присутствии перехватчика? Докажите 

119
свои ответы.
(d) Докажите, что Конструкция 3.30 устойчива к АВОТ, если F — слабо 
псевдослучайная функция.
Пусть F будет псевдослучайной перестановкой. Рассмотрим режим, при кото-
ром выбирается единнобразное значение ctr ∈ {0, 1}n, и i-ый блок шифртекста 
ci вычисляется как ci := Fk (ctr + i + mi). Покажите, что эта схема не имеет нераз-
личимых шифрований в присутствии перехватчика.
Покажите, что режимы СШВ, ОСВ и режим счетчика не производят схем, 
устойчивых в АВШ (независимо от F ). 
Пусть Π1 = (Enc1, Dec1) и Π2 = (Enc2, Dec2) — две шифровальных схемы, 
для которых известно, что по крайней мере одна из них устойчива к АВОТ (но 
мы не знаем, кака именно). Покажите, как построить шифровальную схему Π, 
которая точно устойчива к АВОТ, если по крайней мере Π1 или Π2 устойчива 
к АВОТ. Приведите полное доказательство своего решения.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: