Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА 3.18
- ДОКАЗАТЕЛЬСТВО
| РИСУНОК 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 является случайной строкой. Более подробно: жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|