Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Индекс общего обозначения Общие обозначения
| Подсказка: Используйте ключ длиной n2 и, используя гибридный
аргумент, докажите, что ваша конструкция безопасна. Докажите, что двухраундовая сеть Фейстеля, использующая псевдослучайные раундовые функции (как в выражении (7.15)), не является псевдослучайной. Докажите, что трехраундовая сеть Фейстеля, использующая псевдослучайные раундовые функции (как в выражении (7.16)), не является строго псевдослучайной. Подсказка: Это значительно труднее, чем в предыдущем упраж- нении. Используйте отличительный признак, который делает два за- проса к перестановке, и один запрос к ее инверсии. Рассмотрим ключевую перестановку F * , определенную с помощью F* k (x) = FeistelFk ,Fk ,Fk (x). (Обратите внимание, что в каждом раунде используется тот же самый ключ). Покажите, что F* не является псевдослучайной. Пусть tt – псевдослучайный генератор с коэффициентом расширения A(n) = n + 1. Докажите, что tt является односторонней функцией. Пусть X , Y, Z – вероятностный ансамбль. Докажите, что если X ≡ Y и Y ≡ Z, то X ≡ Z. Докажите теорему 7.32. Пусть X = {Xn}n∈N и Y = {Yn}n∈N – вычислительно неразличимые вероятност- ные ансамбли. Докажите, что для любого вероятностного полиномиально-временно- го алгоритма A, ансамбли {A(Xn}n∈N и {A(Yn}n∈N вычислительно неразличимы. 307 Индекс общего обозначения Общие обозначения: • := называется детерминированным присвоением • Если S – множество, то x ← S обозначает, что x выбирается равномерно из S • Если A – случайный алгоритм, то y ← A(x) обозначает действующий A на входе x, с равномерной случайной лентой , и назначающий выход для y. Мы пишем y := A(x; r), чтобы обозначить действующий A на входе x , использую- щий случайную ленту r , и назначающий выход для y • ٨ обозначает логическое умножение (оператор И (AND)) • V обозначает логическое отрицание (оператор ИЛИ (OR)) • ⊕ обозначает исключающее ИЛИ (оператор XOR); этот оператор может быть применен к отдельным битам или целым строкам (в последнем случае оператор XOR действует поразрядно) • {0, 1}n это множество всех битовых строк длиной n • {0, 1}≤n то множество всех битовых строк длиной не более n • {0, 1}* множество конечных битовых строк • 0n (соотв., 1n) обозначает строку, составленную из n нулей (соотв., n единиц) • ||x|| обозначает длину двоичного представления (положительного) целого числа x, записанного вместе с ведущим битом 1. Обратите внимание, что log x < ||x|| ≤ log x + 1 • |x| обозначает длину двоичной строки x (у которой могут быть ведущие нули), или абсолютное значение действительного числа x • O(•), Θ(•), Ω(•), ω(•) см. приложение A.2 • 0x обозначает, что эти числа представлены в шестнадцатеричном коде • x||y однозначную конкатенацию строк x и y («однозначная» означает, что x and y могут быть восстановлены из x||y) • Pr[X] обозначает вероятность события X • log x обозначает логарифм x по основанию 2 жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|