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



Pdf көрінісі
бет50/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   46   47   48   49   50   51   52   53   ...   249
Криптография Катц

Пример 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 не является генератором 
псевдослучайных чисел. (Обратите внимание, что не всегда «корректен», по-
скольку иногда выводит 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, поскольку атака не эффективна.


Достарыңызбен бөлісу:
1   ...   46   47   48   49   50   51   52   53   ...   249




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

    Басты бет