106
из блочного шифра, как было показано в Конструкции 3.29. Приведем ниже
замкнутое описание. Для шифрования в режиме счетчика, сначала выбирается
равномерное значение ctr∈{0, 1}n.
Затем, генерируется псевдослучайный поток путем вычисления yi := Fk (ctr + i),
где ctr and i считаются числами сложение выполняется по модулю 2n.
i-ый блок
шифртекста равен ci:= yi⊕mi, а IV снова посылается как часть шифртекста. См.
Рисунок 3.10. Заметим, что расшифровка снова не требует, чтобы F была обрати-
мой, или даже перестановкой. Так же как и в режиме ОСВ, еще одном режиме «с
поточными шифрами», сгенерированный поток может быть сокращен до длины
открытого текста, может быть применена предварительная обработка для генера-
ции псевдослучайного потока до того, как известно сообщение, а версия режима
счетчика с сохранением состояния является устойчивой.
В отличие от всех устойчивых режимах, обсуждаемых выше, режим счетчика
имеет преимущество, состоящее в том, что шифрование и расшифровка могут
происходить полностью параллельно, так как все блоки псевдослучайного потока
могут быть вычислены независимо друг от друга. В отличие от ОСВ, здесь также
можно расшифровать i-ый блок шифртекста, используя только одно вычисление
F. За счет этих характеристик режим счетчика является приемлемым выбором.
Режим счетчика также довольно легко анализировать:
ТЕОРЕМА 3.32 Если F псевдослучайная функция, то режим счетчика
устойчив против атак с выбором открытого текста.
ДОКАЗАТЕЛЬСТВО Используем тот же шаблон, что и для доказательства Те-
оремы 3.31: сначала заменим F случайной функцией и затем проанализируем полу-
ченную схему. Пусть Π = (Gen, Enc, Dec) — шифровальная схема (без сохранения
состояния) в режиме счетчика, и пусть Π˜= (G˜en, E˜nc, D˜ec) — шифровальная схе-
ма, идентичная Π, с единственным отличием в том, что вместо Fk используется дей-
ствительно случайная функция. То есть, G˜en(1n) выбирает равномерную функциюf
∈
Funcn, и E˜nc шифрует точто так же, как Enc только вместо Fk используется f .
(Снова, ни G˜en, ни E˜nc
не являются эффективными, но это не важно для определе-
ния эксперимента с Π˜.) Зафиксируем произвольного противника ppt A, и пусть q(n)
— полиномиальное максимальное значение числа запросов к шифровальному ораку-
лу, сделанных A(1n), а также максимальное число блоков в любом из этих запросов и
максимальное число блоков в m0 и m1. В качестве первой ступени доказательства, мы
утверждаем, что существует пренебрежимо малая функция negl ,
такая что
Это утверждение доказывается от обратного похожим образом, как и ана-
логичная ступень доказательства Теоремы 3.31, и предосталяется в качестве
упражнения читателю.
107
Затем мы утверждаем, что
Соединив это уравнение с Уравнением (3.12),
получаем
Так как q полиномиально,
пренебрежительно мало, что и следовало
доказать.
Теперь докажем Уравнение (3.13). Зафиксируем некоторое значение n для
параметра безопасности. Пусть
обозначает длину (в блоках) со-
общений m0, m1
выданных в эксперименте
, и пусть ctr* обозначает
начальное значение, использованное при генерации анализируемого шифртек-
ста. Аналогично, пусть Ai ≤ q(n) — длина (в блоках) i-го запроса к шифро-
вальному оракулу, сделанного A, и пусть ctri обозначает начальное значение,
использованное при ответе на запрос. Когда дается ответ на i-ый запрос у шиф-
ровальному оракулу f применяется в значениям ctri + 1, . . . , ctri + Ai.
Когда про-
исходит шифрование анализируемого шифртекста, f применяется к ctr* +1, . . .
, ctr* +A*, и i-ый блок шифртекста вычисляется путем объединения операцией
исключающего ИЛИ f (ctr* + i) с i-ым блоком сообщения. Есть два случая:
1. Не существуют такие i, j, j*≥1 (с j≤Ai j*≤A*), для которых ctri+j= ctr*+ j*:
В этом случае, значения f (ctr* + 1), . . . , f (ctr* + A*), используемые при шиф-
ровании анализируемого шифртекста, равномерно распределены и независимы
от остальной части эксперимента, так как f не применялась ни к одному из этих
аргументов при шифровании запросов противника к оракулу. Это означает, что
анализируемый шифртекст вычисляется путем применения операции исклю-
чающего ИЛИ к потоку равномерных битов и сообщению mb, то есть вероят-
ность того, что A выдаст br = b равна 1/2 (как в случае шифра Вермана).
2. Существуют i, j, j*≥1 (с j≤Ai иj*≤ A*), для которых ctri+j = ctr*+ j* : Мы назовем это
событие Overlap. В этом случае, A может потенциально определить, какое из его сообще-
ний было зашифрованно для получения анализируемого шифртекста, так как A может
вычислить значение f (ctri +j) = f (ctr*+j*) на основе ответа на его i-ый запрос к оракулу.
Проанализируем вероятность события Overlap . Вероятность максимальна,
если A* и каждый Ai максимально велики, так что предположим, что A*= Ai=
q(n) для всех i. Пусть Overlapi
обозначает событие, при котором последова-
тельность ctri+1, . . . , ctri+q(n) перекрывает последовательность ctr*+1, . . . ,
ctr*+q(n). Тогда Overlap — это событие, при котором Overlapi имеет место для
некоторого i. Так как существует максимум q(n) заросов к оракулу, граница объ-
единения (сравните Предположение А.7) дает
108
При фиксировании ctr*, событие Overlapi имеет место именно когда ctri
удослетворяет ctr*−q(n)+1≤ctri≤ ct*+q(n)−1.
Так как существует 2q(n) − 1 значений ctri, для которых имеет место Overlapi,
и ctri выбирается равномерно из {0, 1}n, мы
видим, что
Объединив это уравнение с Уравнением (3.14), получаем Pr[Overlap] < 2q(n)2/2n.
Учитывая приведенное выше, мы можем легко оценить вероятность успеха A:
Это доказывает Уравнение (3.13) и завершает данное доказательство.
Достарыңызбен бөлісу: