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

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) и завершает данное доказательство.

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

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