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



Pdf көрінісі
бет55/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   51   52   53   54   55   56   57   58   ...   249
Криптография Катц

РИСУНОК 3.2: Шифрование с псевдослучайным генератором.
тремя алгоритмами: алгоритмом генерации ключей Gen, алгоритмом шиф-
рования Enc и алгоритмом расшифрования Dec. Алгоритм генерации ключей 
самый обычный: Gen(1n) просто выводит унифицированный ключ k длиной n. 
Шифрование осуществляется с применением tt к ключу (который служит на-
чальным числом) с целью получения набора данных, к которым вместе с откры-
тым текстом будет применяться операция исключающего ИЛИ. Для восстанов-
ления сообщения алгоритм расшифрования применяет tt к ключу и использует 
операцию XOR к получившейся последовательности и шифртексту. Система 
формально описана в конструкции 3.17. В разделе 3.6.1, мы описываем, как по-
точные шифры используются для реализации этой системы на практике.
Система шифрования с закрытым ключом, опирающаяся на любой псевдос-
лучайный генератор.
КОНСТРУКЦИЯ 3.17
Пусть tt - псевдослучайный генератор с кооффициентом расширения А. Опре-
делим систему шифрования с закрытым ключом для сообщений длинны А сле-
дующим образом:
• Gen: на входе 1n выбрать равномерный k∈{0.1}n и вывести его в качестве ключа
• Dec: на входе ключ k∈{0.1}n и шифротекст m∈{0.1}A(n) , на выходе c: 
G(k)⊕m
• Dec: на входе ключ k∈{0.1}n и шифротекст c∈{0.1}A(n) , на выходе
m: G(k)⊕c
ТЕОРЕМА 3.18 Если tt является псевдослучайным генератором, тогда 
Конструкция 3.17 является системой шифрования с закрытым ключом фик-
сированной длины, обладающей неразличимым шифрованием при наличии под-
слушивающей стороны.


79
ДОКАЗАТЕЛЬСТВО Пусть Π обозначает конструкцию 3.17. Покажем, что 
Π соответствует определению 3.8: покажем, что для любого вероятностного по-
линомиально-временного противника A существует такая пренебрежимо малая 
функция negl, что
Интуиция подсказывает, что если П использует равномерную последователь-
ность вместо псевдослучайной последовательности tt(k), тогда получившаяся си-
стема должна быть идентична системе шифрования Вернама, и A не должен быть 
в состоянии правильно угадать, какое сообщение было зашифровано, с вероятно-
стью выше, чем 1/2. Таким образом, если уравнение (3.2) не верно, тогда A должен в 
неявной форме различать выходные данные tt и по-настоящему случайные строки.
Мы явным образом докажем это методом от противного, именно, показав, как ис-
пользовать A для конструирования эффективного дистинктора D, такой что способ-
ность D различать выходные данные tt и равномерную строку будет напрямую свя-
зана со способностью A определять, какое именно сообщение было зашифровано 
системой Π. Надежность tt тогда подразумевает надежность Π.
Пусть A - это произвольный ppt противник. Мы конструируем дистинктор D, 
который на входе берет строку w и целью которого является определить, была 
ли строка w выбрана равномерно (т. е. w - это «случайная строка») или w была 
сгенерирована с помощью унифицированного k и вычислена w := tt(k) (т. е. w 
- это «псевдослучайная строка»). Мы конструируем D так, чтобы имитировал 
эксперимент с подслушивающей стороной для A, как описано ниже, и наблю-
дал, добьется A успеха или нет. Если A справляется, тогда D угадывает, что w 
должна быть псевдослучайной строкой, а если A не справляется, тогда D угады-
вает, что w является случайной строкой. Более подробно:


Достарыңызбен бөлісу:
1   ...   51   52   53   54   55   56   57   58   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет