Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 48

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 42 43 44 45 46 47 < 48 > 49 50 51 52 53 54 .. 126 >> Следующая


\X\<\Y\<\K\. (20)

Доказательство. Первое неравенство, очевидно, имеет место для любого шифра. Если шифр — совершенный, то для любых х є X, у е Y найдется ключ к є К, такой, что

Ek(X) = у. В самом деле, в противном случае, согласно (15),

176
Надежность шифров

мы бы имели р(у/х) = 0, а тогда и, согласно (18), P(Xjy)-O. Согласно (19), вероятность рх(х) также оказывается равной нулю, вопреки нашей договоренности о том, ЧТО Px (х) > 0 для любого X є X .

Отсюда следует также, что для любого х є X выполняется равенство {Ек (х), к є К} = Y и, следовательно,

|у| < IК\. Утверждение доказано.

В большинстве случаев применяемые на практике шифры обладают свойством X = Y. Следуя К. Шеннону, назовем такие шифры эндоморфными. К. Шеннону удалось полностью описать эндоморфные совершенные шифры с минимально возможным числом ключей. Согласно (20), это минимально

возможное число ключей \к\ равно |к|. В несколько более

общей форме теорема формулируется следующим образом.

Теорема (К. Шеннон). Пусть Yb — шифр, для которого \Х\ = |Г| = |^Г|. Тогда шифр Yb — совершенный тогда и только тогда, когда выполняются два условия:

1) для любых х є X, у є Y существует единственный

ключ к є К, для которого Ek (х) = у;

2) распределение вероятностей P(K) — равномерное,

то есть для любого ключа рк (к) = —

Доказательство. Пусть шифр Ъв —совершенный. Согласно доказательству утверждения 1,

177
/лава 7

Поэтому из неравенства Ф к2 следует неравенство Ekx (х) Ф Ek^ (х) для любого х є X . Это доказывает необходимость условия 1).

Пусть .Ar = . Зафиксируем произвольный эле-

мент ysY и занумеруем ключи так, чтобы Ejii(Xl) = у,

і = ItN. Тогда

(х / а = РІу!х,)'Pxix,) = Pk(K) Px(Xi)

Pr (У) Pr (У)

Так как Yb — совершенный шифр, то P(XiIy) = рх (*/) . Отсюда и из (21) получаем равенство pK(kt) = ру(у) Для

любого і = I9N , которое доказывает необходимость условия 2).

Пусть условия 1) и 2) выполнены. Тогда, пользуясь для фиксированного элемента у є Y введенной выше нумерацией ключей, имеем цепочку равенств:

Ру(у)= YjP х(х,)-Pk(K). = =77’

(X1JO (ycni))N N

Ек,(х,)=У

из которой

( I ) = РЛКРОМ = ( }

Py (у) (У“2»

Достаточность условий теоремы также доказана.

Обратим внимание на то, что таблица зашифрования шифра, удовлетворяющего условиям теоремы Шеннона, согласно условию 1) этой теоремы, является латинским квадратом. Поэтому в случае, когда X = Y = K = Zn, по сути дела, шифры табличного гаммирования со случайными равно-178
Надежность шифров

вероятными ключами, и только они являются единственными совершенными шифрами.

V /к X, Xn
К Екх(х і) Екх (xN )

kN Екы Oi) ... EkN (xn)

Подчеркнем также, что не только указанные шифры являются совершенными. В качестве примера можно указать следующий не эндоморфный совершенный шифр.

Пример

X = (X05X1), Y = {У0,У\,У2}, К = {k0,kbk2},

Ekl (Xj) = Ут, т = 0' + У)niod3, рк(к() = 1/3,/ = 0,2.

Теорема Шеннона может быть обобщена и для некоторых других криптоатак. Например, в статье [God90] такое обобщение проводится для криптоатак на основе нескольких шифртекстов, полученных на одном ключе, а также для криптоатак на основе ряда открытых и соответствующих им шифрованных текстов, образованных с помощью одного ключа.

Практическая стойкость шифров

В своей работе [ШенбЗ] К. Шеннон, помимо исследований по теоретической стойкости, рассматривал также вопрос о практической стойкости шифров. Он рассуждал следующим образом (рассматривая, как и ранее, криптоатаку на основе одного шифртекста на шифр, не являющийся совершенным).

179
І лава 7

После того как объем перехвата (у ) превзойдет расстояние единственности (естественно, предполагается, что для рассматриваемого шифра оно существует!), обычно будет сущесгвовать единственное решение (х или к ) криптограммы. Задача дешифрования и состоит в нахождении этого единственного решения, имеющего высокую вероятность (р(х/у) или р(к/у)). До того как объем перехвата достигнет расстояния единственности, задача состоит в нахождении всех решений, имеющих большую вероятность (по сравнению с остальными решениями), и, конечно, в определении вероятностей этих решений.

Несмотря на то, что эти решения можно в принципе найти, поочередно перебирая, например, все ключи при расшифровании, для различных шифров нужно будет затратить для этого весьма различающиеся объемы работы. Средний объем работы W(N), необходимый для определения ключа по криптограмме, состоящей из N букв, измеренный в удобных элементарных операциях, К. Шеннон предложил назвать рабочей характеристикой шифра. Это среднее значение берется по всем сообщениям и всем ключам с соответствующими им вероятностями. Функция W(N) характеризует средние затраты (временные и материальные), необходимые для практического дешифрования криптограммы. Подобную характеристику можно рассматривать не только для одной конкретной криптоатаки, но и для других постановок задач криптоанализа.

Рис. 20

180
Надежность шифров

К. Шеннон привел рабочую характеристику шифра простой замены, сопоставив ее с неопределенностью шифра по открытому тексту (как функцией длины сообщения). Пунктирная линия кривой на рис. 20 относится к области, где имеется несколько возможных решений. По мере увеличения объема перехвата количество необходимой работы быстро уменьшается, стремясь к некоторому асимптотическому значению, которое достигается, когда дополнительные данные уже не уменьшают работы.
Предыдущая << 1 .. 42 43 44 45 46 47 < 48 > 49 50 51 52 53 54 .. 126 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed