Современная прикладная криптография (стр. 11 )

C = M K =

при случайном равновероятном выборе секретного ключа (P(K)=)получаем для любых C и M очевидное равенство

(P(C/M)=),

из которого следует, что тексты M и C статистически независимы.

Помимо неудобств, связанных с большим объемом ключа, совершенно секретные системы, как отметил Рюппель (Rueppel) в [40], могут быть дешифрованы при известном открытом тексте (Known plaintext attack). Кроме того, чрезмерно предположение о противнике с неограниченными вычислительными мощностями, да и сама информация может иметь ограниченную временную ценность.

Поэтому Шеннон, помимо теоретической стойкости криптосистем, рассматривал и практическую стойкость. Для этого он ввел так называемую рабочую характеристику w(n) - среднее количество работы (измеренное в удобных единицах), требуемое для нахождения ключа на основе знания n знаков шифртекста с помощью наилучшего криптоаналитического алгоритма. Обычно криптосистемы оценивают с помощью достигнутой оценки рабочей характеристики при использовании наилучшего из известных методов дешифрования. Криптосистемы называются практически стойкими, если они не могут быть вскрыты в течение реального времени ( const ) всеми общедоступными методами. Хотя Шеннон исходил из анализа криптосистем лишь по шифртексту, определение подразумевает все типы анализа.

При построении криптосистем на практике используют именно понятие практической безопасности. Однако при этом следует иметь в виду, что не все методы дешифрования, известные противнику, известны и создателю криптосистемы. Таким образом, квалификация создателя играет исключительно важную роль. Кроме того, новые исследования, возможно, могут открыть новые методы, которые сделают криптосистему практически нестойкой. Поэтому очень важно периодически проводить контрольные исследования уже созданных систем на основе вновь полученных результатов и разработанных методов.

Важным понятием при изучении стойкости несовершенных шифров (криптосистем) является введенное Шенноном понятие расстояния единственности (unicity distance) шифра (криптосистемы). Оно определяется как наименьшее число знаков шифртекста, необходимое для однозначного определения ключа, то есть когда неопределенность H(K|c) при известном шифртексте данной длины равна (близка) нулю. (Величина Н(К]с) - key equivocation - иногда переводится как "ненадежность ключа"). Системы, которые не обладают совершенной секретностью, но, тем не менее, не вскрываемы, так как не дают достаточной информации в шифртексте для однозначного определения ключа, называются "идеально секретными" (ideal secrecy). У идеально секретных систем неопределенность H(K|C) не достигает нуля ни при какой длине шифртекста. Для "строго идеальных систем" выполняется соотношение H(K|C) = M(k). По определению, для величины H(K|c) имеем соотношение

Н(К|с) = - P(K|c) P(K|c)

где Р(K|c) - вероятность того, что данный ключ к использовался при получении данного шифртекста C. Большинство криптосистем слишком сложны, чтобы для них можно было определить все вероятности Р(K|с), встречающиеся в последнем соотношении. Тем не менее, Шеннон показал, что возможно оценить H(K|с), используя так называемую модель случайного шифра (random cipher model), для которого при любых K и C из соответствующих пространств, значение является независимой случайной величиной, равномерно распределенной на пространстве всех открытых текстов (в действительности полной независимости быть не может, так как при и любом k в силу однозначности зашифрования).

Пусть, для простоты изложения, мощности алфавитов открытого и шифрованного текстов равны L. Тогда существует = последовательностей длин n, где N = N (absolute rate of language). Например, при L=26 ( английский язык ) R = . Эти последовательностей разбиваются на два множества: множество из осмысленных текстов длины N и множество из - бессмысленных текстов. Здесь r (rate of the language) обозначает энтропию источника сообщений на один знак, то есть величину H(m)/N. Например, для английского языка при больших значениях n величина r заключена в границах I бит/буква и 1.5 бит/буква. Предполагается, что все осмысленные тексты имеют одинаковую вероятность . тогда как все бессмысленные - нулевую вероятность. Также естественно считать, что все ключей одинаково вероятны (P(K)= ) для использования, H(K) энтропия ключа (число битов в ключе).

Если шифртекст с = получен при каких-то истинных значениях k и m, то криптоаналитик противника может принять ложный ключ k за истинный в следующих двух случаях

с =

или с = ,

при том же или другом осмысленном тексте . Так как каждый открытый текст одинаково вероятен, то вероятность получить осмысленный открытый текст при случайно выбранном для расшифрования ключе из множества (-1) ложных ключей равна 2, где величина D= (N-r) называется избыточностью языка (redundency of the language). Таким образом, число ложных решений можно оценить величиной

(.

Отсюда видно, что число ложных решений равно нулю(единице), а значит, и неопределимость H(K|с) ключа тоже равна нулю при h(k)-dn=o или при n=n(k)/d. Величина N(k)/D является оценкой для расстояния единственности.

В качестве примеров, можно посчитать расстояние единственности для широко известных криптосистем Hagelin H-209, DES и SKIPJACK, у которых величина H(к) равна 131, 56 и 80 бит соответственно. Приняв для английского языка D=3,2, получим значения расстояния единственности соответственно в 40.9; 17,5; 25 букв.

Из отношения h(k)/d для расстояния единственности можно сделать некоторые выводы. Во-первых, если при любом n число возможных ключей так же велико, как число осмысленных открытых текстов, то

H(K)=-=rN

и если h(k)-dn = (r-D)N 0, то система является теоретически невскрываемой. Подобный принцип лежит в основе шифра Вернама (one-tine pad).

Во-вторых, при фиксированном размере ключа H(к) и нулевой избыточности языка D = R-r, расстояние единственности равно бесконечности, и криптоаналитик никогда не сможет раскрыть криптосистему, даже если число ключей много меньше числа осмысленных открытых текстов, и совершенная секретность не имеет места. Действительно, для любого шифртекста с все тексты при всех ключах к будут восприниматься криптоаналитиком как осмысленные открытые тексты. На основании этих рассуждений Шеннон предложил устранять избыточность открытого текста перед зашифрованием. Этого можно достичь, например, с помощью специального кодирования. Так, можно использовать архиваторы текстов перед зашифрованием.

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

В дальнейшем идеи Шеннона были развиты в работах Хеллмана, Джилберта, Мак Вильямса и Слоэна [68].

1.4. Теория сложности и криптология

Стойкость криптосистем определяется вычислительной сложностью (coeputatlonal complexity) алгоритмов, применяемых криптоаналитиками для дешифрования этих систем.