Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Пример 3.15
Определим tt(s) выводить s вместе с , таким образом, коэффициент расширения tt составляет A(n) = n + 1. Выходные данные tt можно легко от- личить от однородных. Рассмотрим следующий эффективный дистинктор D: на входе строка w, на выходе 1 тогда и только тогда, когда конечный бит w равносилен операции исключающего ИЛИ всех предшествующих битов w. Поскольку эта харак- теристика верна для всех строк, выведенных tt, имеем Pr[D(tt(s)) = 1] = 1. С другой стороны, если w является равномерной, последний бит w является рав- номерным, и тогда Pr[D(w)=1]=1/2. Количество |1/2 − 1| является постоянным, не пренебрежимо малым, и, таким образом, данный tt не является генератором псевдослучайных чисел. (Обратите внимание, что D не всегда «корректен», по- скольку иногда выводит 1 даже когда задана равномерная строка. Это не меняет того факта, что D является хорошим дистинктором.) ♦ Обсуждение. Распределение выходных данных генератора псевдослучайных чи- сел tt далеко от равномерного. Рассмотрим для наглядности случай, когда A(n)=2n и тогда tt удваивает длин входных данных. При равномерном распределении по {0, 1}2n, каждая из 22n возможных строк выбирается с вероятностью ровно 2−2n. Для сравнения рассмотрим распределение вывода tt (когда tt запущен по начальному чис- лу). Когда tt получает входные данные длиной n, число различных строк в диапазоне tt составляет максимум 2n. Относительное количество строк длиной 2n, находящихся в диапазоне tt, таким образом, составляет максимум 2n/22n = 2−n, и мы видим, что по- давляющая часть строк длиной 2n не встречаются в виде выходных данных tt. В частности, это означает, что легко отличить случайные строки от псев- дослучайных, заданных неограниченное число раз. Пусть tt останется тем, что указано выше, и рассмотрим экспоненциально-временной дистинктор D, работающий следующим образом: D(w) выводит 1 тогда и только тогда, когда существует s ∈ {0, 1}n, такое что tt(s) = w. (Это вычисление осуществляется в экспоненциальном времени путем тщательной обработки tt(s) для каждого s ∈ {0, 1}n. Напомним, что по принципу Керкгоффса характеристика tt известна D.) Теперь, если w была выведена tt, тогда D выводит 1 с вероятностью 1. Напро- тив, если w равномерно распределена по {0, 1}2n, тогда вероятность существо- 74 вания s при tt(s) = w составляет максимум 2−n, и тогда D выводит в этом случае 1 с вероятностью максимум 2−n. Таким образом, Pr[D(r) = 1] − Pr[D(tt(s)) = 1]. ≥ 1 − 2−n, являющееся большим. Это еще один пример атаки методом перебора, кото- рый не противоречит псевдослучайности tt, поскольку атака не эффективна. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|