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 устойчива
к АВОТ. Приведите полное доказательство своего решения.
Достарыңызбен бөлісу: