Введение в современную криптографию
Псевдослучайные перестановки/Блочные шифры
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Псевдослучайные перестановки/Блочные шифры
Пусть Permn — это множество всех перестановок (т.е. взаимно-однозначных соответствий) над {0, 1}n. Как и ранее, мы рассматриваем любую f∈Permn как таблицу, но теперь мы добавили ограничение, что входные данные в любых двух различных строках таблицы должны различаться. Скажем, есть 2n раз- личных возможных выборов для данных первой строки таблицы; как только эта строка выбрана, у нас остается только 2n − 1 возможных выборов для второй строки, и так далее. Таким образом, мы видим, что размер Permn равен (2n)!. Пусть F — функция с ключом. Назовем F перестановкой с ключом, если Ain= Aout, и кроме того, для всех k∈Akey (n) функция Fk:{0, 1}Ain(n)→{0, 1}Ain(n) является взаимно однозначной (т.е. Fk является перестановкой). Назовем Ain блочной длиной функции F. Как и ранее, если не указано иначе, предполагается, что является сохра- няющей длину и, таким образом, Akey(n)=Ain(n)=n. Перестановка с ключом является эффективной, если существует алгоритм полиномиального времени для вычисления Fk(x) при заданных k и x, а также существует алгоритм полиномиального времени для вычисления F−1(y) при заданных k и y. То есть, Fk должна быть одновременно эффективно вычисляемой и эффективно обратимой при известной k. Определение того, что значит для еффективной перестановки с ключом F быть псевдослучайной перестановкой абсолютно аналогично Определению 3.25, с единственным отличием в том, что теперь Fk должна быть неотличима от равномерной перестановки ,а не от равномерной функции. Таким образом, мы задаем требование, что никакой эффективный алгоритм не может отли- чить доступ к Fk (для единообразного ключа k) от доступа к f (для однородной f∈Permn). Оказывается, что это всего лишь решение эстетического характера, так как, когда длина блока достаточно велика, произвольная пер естановка сама по себе неотличима от произвольной функции. Интуитивно, это происходит потому, что равномерная функция f выглядит идентично равномерной пере- становке, однако только в том случае, если не существует таких значений x и y, для которых f (x) = f (y), так как в этом случае эта функция не может быть перестановкой. Однако, вероятность найти такие значения x, y с помощью по- 93 линомиального числа запросов пренебрежимо мала. (Это следует из результа- тов Приложения А.4.) Предположение 3.27Если F — псевдослучайная перестановка и, к тому же, Ain(n) ≥ n, то F также является псевднопроизвольной функцией. Если F — это перестановка с ключом, то криптографические схемы, осно- ванные на F могут предполагать наличие честных участников для вычисления обратной функции F −1 в добавление к вычислению самой функции Fk . Это потенциально предполагает новые проблемы с безопасностью. В частности, в этом случае, возможно, необходимо ввести более сильное требование, а имен- но, что Fk должна быть неотличимой от равномерной перестановки даже если дистинктору дополнительно предосталяется оракульный доступ к обратной функции этой перестановки. Если F обладает этой характеристикой, то мы на- зовем ее сильной псевдослучайной перестановкой. ОПРЕДЕЛЕНИЕ 3.28 Пусть F:{0, 1}*×{0, 1}*→{0, 1}* будет эффективной, сохраняющей длину перестановкой с ключом. F является сильной псевдослучай- ной перестановкой, если для всех вероятностных полиномиальных дистинкто- ров D, существует пренебрежимо малая функция negl, такая что: где первая вероятность вычисляется над равномерно выбранными k∈ {0,1}n и произвольным D, а вторая вероятность вычисляется над равномерно выбран- ными f∈Permn и и произвольным D. Очевидным образом, любая сильная псевдослучайная перестановка является также псевдослучайной перестановкой. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|