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

164
кажите, что t должен быть суперлогарифмическим или эквивалентно, что если 
t(n) = O(log n), тогда Π не может быть защищенным MAC.
Подсказка: Рассмотрите возможность случайного угадывания верного тега .
4.2 Рассмотрите расширение определения защищенной аутентификации со-
общений, при которой злоумышленник обеспечен обеими оракулами, Mac и Vrfy.
(a) Предоставьте формальное объяснение защиты для данного случая.
(b) Предположим, что Π является детерминированным MAC, использующим 
каноническую проверку, которая соответвтует Определению 4.2. Докажите, что 
Π также соответствует вашему определению из части (a).
4.3 Предположим, что имеют место защищенные MAC. Дайте конструкцию 
MAC, который защищенный согласно Определению 4.2, но незащищенный 
в случае, если злоумышленник дополнительно имеет доступ к оракулу Vrfy 
(сравните с предыдущим упражнением).
4.4 Докажите Предположение 4.4.
4.5 Предположим, что имеют место защищенные MAC. Докажите, что имеет 
место MAC, который защищен (по Определению 4.2), но не строго защищен 
(по Определению 4.3). 
4.6 Рассмотрите следующий MAC для сообщений длиной A(n) = 2n − 2 с 
использованием псевдослучайной функции F : При вводе сообщение m0||m1
(при |m0| = |m1| = n − 1) и ключ k ∈ {0, 1}n, алгоритм Mac выводит t = Fk 
(0||m0) || Fk (1||m1). Алгоритм Vrfy определяется естесственнм путем. Защищен 
ли (Gen, Mac, Vrfy)? Докажите свой ответ.
4.7 Пусть F — псевдослучайная функция. Покажите, что каждый из следующих 
MAC является незащищенным, даже если используется для аутентификации со-
общений фиксированной длины. (В каждом случае Gen выводит универсальный 
k ∈ {0, 1}n. Пусть (i) обозначает n/2-битное шифрование целого числаi.)
(a) Чтобы аутентифицировать сообщение m = m1, . . . , mA , в котором mi ∈ {0, 
1}n, вычислите t := Fk (m1) ⊕ • • • ⊕ Fk (mA ).
(b) Чтобы аутентифицировать сообщение m = m1, . . . , mA, в котором mi ∈ {0, 
1}n/2, вычислите t := Fk ((1)»m1) ⊕ • • • ⊕ Fk ((A)»mA ).
(c) Чтобы аутентифицировать сообщение m = m1, . . . , mA, в котором mi ∈{0, 
1}n/2, подберите универсальный r ← {0, 1}n, вычислите t := Fk (r) ⊕ Fk ((1)||m1) 
⊕
• • • ⊕ Fk ((A)||mA ), и пусть тег будет (r, t).
4.8 Пусть F будет псевдослучайной функцией. Покажите, что следующий 
MAC для сообщений длиной 2n является незащищенным: Gen выводит k ∈ {0, 
1}n. Чтобы аутентифицировать сообщение m1||m2 с |m1| = |m2| = n, вычислите 
тег Fk (m1) || Fk (Fk (m2)).

165
4.9 Давая любой детерминированный MAC (Mac, Vrfy), мы можем наблюдать 
Mac в качестве ключевой функции. В обеих Конструкциях, 4.5 и 4.11, Mac явля-
ется псевдослучайно функцией. Дайте конструкцию защищенного, детермини-
рованного MAC, в котором Mac не является псевдослучайно функцией. 
4.10 Является ли Конструкция 4.5 достаточно надежной при реализации с 
использованием слабой псевдослучайной функции (сравните с Упр ажнением 
3.26)? Объ ясните.
4.11 Докажите, что Конструкция 4.7 является надежной , даже е сли злоумыш-
ленник дополнительно имеет доступ к оракулу Vrfy (сравните с Упражнением 4.2). 
4.12 Докажите, что Конструкция 4.7 является надежной , если она изменяется 
следующим образом: Установите ti := Fk (r»b»i»mi), где b является одиночным би-
том, таким, что b = 0 во всех блоках, кроме последнего, и b = 1 в последнем блоке. 
(Предположим для простоты, что длина всех сообщений, подлежащих аутентифи-
кации, всегда целое число кратное n/2 − 1.) Какое преимущество такого изменения?
4.13 Мы выясним, что случится, если конструкция базового CBC-MAC ис-
пользуется с сообщениями различной длины.
(a) Скажем, отправитель и получатель не договорились о длине сообщений 
заранее (и поэтому Vrfy (m, t) = 1 iff t =? Mac (m), независимо от длины m), но 
отправитель проверяет подлинность только сообщений длиной 2n. Покажите, 
что злоумышленник может подделать верный тег на сообщении длиной 4n.
(b) Скажем, получатель получает 3-блочные сообщения (поэтому Vrfyk (m, t) 
=1 только, если m имеет длину 3n и t =? Mack (m)), но о тправитель аутенти-
фицирует сообщения любой длины кратной n. Покажите, что злоумышленник 
может подделать верный тег на новое сообщение.
4.14 Докажите, что следующие изменения базового CBC-MA не дают защи-
щенный MAC (даже для сообщений фиксированной дины):
(a) Mac выводит все блоки t1, . . . , tA, а не просто tA . (Проверка только лишь 
подтверждает правильность tA.)
(b) Случайный начальный блок используется каждый раз при аутентифика-
ции сообщения. То есть подберите универсальный t0 ∈ {0, 1}n, запустите ба-
щовый CBC-MAC над «сообщением» t0, m1, . . . , mA и выведите тег (t0, tA ). 
Проверка произведена естественным путем. 
4.15 Покажите, что, присоединяя длину сообщения к концу сообщения перед 
применением базового CBC-MAC, не приводит к защищенности MAC для со-
общений проивольной длины. 
4.16 Покажите, что шифрование для сообщений произвольной длины, опи-
санное в Разделе 4.4.2 является безпрефиксным.

166
4.17 Рассмотрите следующее шифрование, обрабатывающее сообщения дли-
ной меньшей, чем n • 2n: Мы шифруем строку m ∈ {0, 1}*, для начала добавляя 
столько нулей, сколько нужно, чтобы получить дину получившейся строки m 
отличной от нуля и кратной n. Затем мы добавляем число blocks к m (эквива-
лентно, добавляем целое число |m |/n), зашифрованное как n-битная строка. 
Покажите, что такое это шифрование не явля ется безпрефиксным. 
4.18 Докажите, что следующие изменения базового CBC-MAC дают защищен-
ный MAC для сообщений произвольной длины (для простоты, предположим, что 
длина всех сообщений кратная длине блока). Mack (m) сначала обпределяет kA 
= Fk (A), где A - это длина m. В таком случае, тег определяется с использованием 
CBC-MAC с ключом kA . Проверка произведена естественным путем.
4.19 Пусть F будет ключевой функцией, которая является защищенным (де-
терминированным) MAC для сообщений длиной n. (Обратите внимание, что F 
не обязательно быть псевдослучайной перестановкой.) Покажите, что базовый 
CBC-MAC не обязательно является защищенным MAC (даже для сообщений 
фиксированной длины) в случае реализации с F.
4.20 Покажите, что Конструкция 4.7 является строго защищенной.
4.21 Покажите, что Конструкция 4.18 может быть не защищенной от атак на 
основе подобранного шифротекста, если она реализована с помощью защи-
щенного MAC, которые не является строго защищенным.
4.22 Докажите, что Конструкция 4.18 не поддается подделке, если реализова-
на при помощи любой схемы шифрования (даже не защищенной от атак на ос-
нове подобранного открытого текста) и любого защищенного MAC (даже если 
MAC не является строго защищенным).
4.23 Рассмотрите усиленную версию невозможности подделки (Определение 
4.16), где A предоставлен доступ к оракулу шифрования.
(a) Напишите формальное определение для этой версии невозможности подделки.
(b) Докажите, что Конструкция 4.18 соответствует этому боле сильному опре-
делению, если ΠM является строго защищенным MAC.
(c) Покажите обратным примером, что Конструкция 4.18 не должна соответ-
ствовать этому более сильному определению, если ΠM является защищенным 
MAC, но не строго защищенным. (Сравните с предыдущим упражнением.)
4.24 Докажите, что подход «аутентификация, затем шифрование», реализо-
ванный при помощи любой схемы шифрования, защищенной от атак на осно-
ве подобранного открытого текста, и любого защищенного MAC, дает схему 
шифрования, защищенную от атак на основе подобранного открытого текста, 
которую невозможно подделать.

167
4.25 Пусть F будет строго псевдослучайной перестановкой, определите сле-
дующую схему шифрования фиксированной длины: При вообще сообщения 
m ∈ {0, 1}n/2 и ключа k ∈ {0, 1}n, алгоритм Enc подбирает универсальный r ∈ 
{0, 1}n/2 и вычисляет c := Fk (m||r). (См. Упражнение 3.18.) Докажите, что эта 
схема является защищенной от атак на основе подобранного шифротекста, но 
не является схемой аутентифицированного шифрования.
4.26 Покажите схему шифрования с закрытым ключем, защищенную от атак 
на основа подобранного открытого текста, которую невозможно подделать, но 
которая не явялется защищенной от атак на основе подобранного шифротекста.
4.27 Зафиксируйте A > 0 и простое число p. Пусть K = Z p A+1, M = ZA и T = 
Zp. Определимp h : K × M → T как
hk0 ,k1,...,kA (m1, . . . , mA ) = [k0 + ∑i kimi mod p] . .
Докажите, что h является строго универсальным.
4.28 Зафиксируйте A, n > 0. Пусть K = {0, 1}A×n × {0, 1}A (интегрированный 
как булевое значение A × n матрица A-бесконечномерный вектор), пусть M = {0, 1}n, 
и пусть T = {0, 1}A. определите h : K × M → T как hK,v (m) = K • m ⊕v, где все опе-
рации выполняются по модулю 2. Докажите, что h является строго универсальным.
4.29 Матрица Теплица K это матрица, в которой Ki,j = Ki−1,j−1, где i, j > 1; то 
есть значения вдоль любой диагонали равны. Поэтому матрица Теплица A × n 
(для A > n) имеет форму
Пусть K = T A×n × {0, 1}A (где T A×n означает набор матриц Теплица A × n), пусть M 
= {0, 1}n и пусть T = {0, 1}A. Определите h : K × M → T как hK,v (m) = K • m ⊕ v, где все 
операции выполняются по модулю 2. Докажите, что h является строго универсальным.
Какое здесь преимущество в сравнении с конструкцией в предыдущем упражнении?
4.30 Определите правильно понятие двухразового ε-защищенного MAC, а 
также дайте конструкцию, отвечающую вашему определению.
4.31 Пусть {hn:Kn×{0,1}0•n→{0,1}n}n N будет таким, что hn будет строго уни-
версальным для всех n, и пусть F будет псевдослучайной функцией. (Где K∈Kn 
мы запишем hK(•) вместо hn,K (•).) Рассмотрите следующий MAC: Gen(1n) под-
бирает универсальный K∈Kn и k∈{0,1}n и выводит (K, k). Чтобы аутентифици-
ровать сообщение m ∈ {0,1}10•n, подберите универсальный r ∈ {0, 1}n и выведи-
те (r,hK (m) ⊕ Fk (r)). Проверка произведена естественным путем. Докажите, что 
это дает (вычислительно) защищенный MAC для сообщений длиной 10n.

168

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

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