Вероятностно-статистические модели сообщений и их энтропийные свойства

     Для сообщения длиной n число различных  ключей, которые расшифруют шифротекст сообщения в какой-то осмысленный  открытый текст на языке оригинального  открытого текста (например, английском), определяется следующей формулой:

     2^{H(K)- nR} – 1

     Шеннон  определил расстояние уникальности, U, называемое также точкой уникальности, как такое приближенное количество шифротекста, для которого сумма  реальной информации (энтропия) в соответствующем открытом тексте плюс энтропия ключа шифрования равняется числу используемых битов шифротекста.

     Затем он показал, что имеет смысл считать, что шифротексты, которые длиннее  расстояния уникальности, можно расшифровать только одним осмысленным способом. Шифротексты, которые заметно короче расстояния уникальности, скорее всего, можно расшифровать несколькими способами, каждый из которых может быть правилен, и таким образом обеспечить безопасность, поставив противника перед выбором правильного открытого текста.

     Для большинства симметричных криптосистем расстояние уникальности определяется как энтропия криптосистемы деленная на избыточность языка.

     U = H(К)/R

     Расстояние  уникальности является не точным, а  вероятностным значением. Оно позволяет  оценить минимальное количество шифротекста, при вскрытии которого грубой силой имеется, вероятно, только один разумный способ дешифрирования. Обычно чем больше расстояние уникальности, тем лучше криптосистема. Для DES с 56-битовым ключом и англоязычного сообщения, записанного символами ASCII, расстояние уникальности приблизительно равно 8.2 символа ASCII или 66 бит. В таблице 2 приведены расстояния уникальности для различных длин ключа.

     Расстояние  уникальности измеряет не количество криптотекста, нужного для криптоанализа, а количество криптотекста, необходимое  для единственности результата криптоанализа. Криптосистема может быть вычислительно  неуязвима, даже если теоретически ее возможно взломать, используя малое количество шифротекста.

     Расстояние  уникальности пропорционально избыточности. Если избыточность стремится к нулю, даже тривиальный шифр может не поддаться  вскрытию с использованием только шифротекста. В таблице 2 приведены расстояния уникальности текстов с различной длиной ключа

Таблица 2 - Расстояния уникальности текста ASCII, зашифрованного алгоритмами с различной  длиной ключа

 

     Шеннон  определил криптосистему с бесконечным  расстоянием уникальности, как обладающую идеальной тайной. Обратите внимание, что идеальная криптосистема  не обязательно является совершенной, хотя совершенная криптосистема  обязательно будет и идеальной. Если криптосистема обладает идеальной тайной, то даже при успешном криптоанализе останется некоторая неопределенность, является ли восстановленный открытый текст реальным открытым текстом.

     Хотя  эти понятия имеют большое  теоретическое значение, реальный криптоанализ использует их достаточно редко. Расстояние уникальности гарантирует ненадежность системы, если оно слишком мало, но его высокое значение не гарантирует безопасности. Несколько практических алгоритмов абсолютно не поддаются анализу, поведение параметров теории информации могло бы способствовать взлому некоторых шифрованных сообщений. Однако, подобные соображения теории информации иногда полезны, например, для определения в конкретном алгоритме рекомендуемого интервала изменения ключей. Криптоаналитики также используют ряд тестов не базе статистики и теории информации, чтобы выбирать наиболее перспективные направления анализа. К сожалению, большинство литературы по применению теории информации в криптоанализе остается секретной, включая основополагающую работу Алана Тьюринга (Alan Turing), написанную в 1940. 
2. Совершенная секретность 

     На основе вероятностных характеристик Клод Шеннон предложил определение совершенной секретности сообщений.

     Предположим, что имеется конечное число возможных сообщений M₁,…,M_n с априорными вероятностями P(M₁),…,P(M_n) и что эти сообщения преобразуются в возможные криптограммы E₁,…,E_m, так что E = T_iM. После того как шифровальщик противника перехватил некоторую криптограмму E, он может вычислить, по крайней мере в принципе, апостериорные вероятности различных сообщений P_E(M). Естественно определить совершенную секретность с помощью следующего условия: для всех E апостериорные вероятности равны априорным вероятностям, независимо от величины этих последних. В этом случае перехват сообщения не дает шифровальщику противника никакой информации. Теперь он не может корректировать никакие свои действия в зависимости от информации, содержащейся в криптограмме, так как все вероятности, относящиеся к содержанию криптограммы, не изменяются.

С другой стороны, если это условие равенства  вероятностей не выполнено, то имеются  такие случаи, в которых для  определенного ключа и определенных выборов сообщений апостериорные  вероятности противника отличаются от априорных. А это в свою очередь может повлиять на выбор противником своих действий и, таким образом, совершенной секретности не получится. Следовательно, приведенное определение неизбежным образом следует из нашего интуитивного представления о совершенной секретности. Необходимое и достаточное условие для того, чтобы система была совершенно секретной, можно записать в следующем виде. По теореме Байеса

, где

     P(M) – априорная вероятность сообщения  M;

     P_M(E) – условная вероятность криптограммы E при условии, что выбрано сообщение M, т.е. сумма вероятностей всех тех ключей, которые переводят сообщение M в криптограмму E;

     P(E) – вероятность получения криптограммы E;

     P_E(M) – апостериорная вероятность сообщения M при условии, что перехвачена криптограмма E.

     Для совершенной секретности системы  величины P_E(M) и P(M) должны быть равны для всех E и M. Следовательно, должно быть выполнено одно из равенств: или P(M) = 0 [это решение должно быть отброшено, так как требуется, чтобы равенство осуществлялось при любых значениях P(M)], или же

     P_M(E) = P(E)

     для любых M и E. Наоборот, если P_M(E) = P(E), то

     P_E(M) = P(M),

     и система совершенно секретна. Таким  образом, можно сформулировать следующую  теорему: Необходимое и достаточное  условие для совершенной секретности состоит в том, что P_M(E) = P(E) для всех M и E, т.е. P_M(E) не должно зависеть от M.

     Другими словами, полная вероятность всех ключей, переводящих сообщение M_i в данную криптограмму E, равна полной вероятности всех ключей, переводящих сообщение M_j в ту же самую криптограмму E для всех M_i, M_j и E. Далее, должно существовать по крайней мере столько же криптограмм E, сколько и сообщений M, так как для фиксированного i отображение T_i дает взаимно-однозначное соответствие между всеми M и некоторыми из E. Для совершенно секретных систем для каждого из этих E и любого M P_M(E) = P(E) → 0. Следовательно, найдется по крайней мере один ключ, отображающий данное M в любое из E. Но все ключи, отображающие фиксированное M в различные E, должны быть различными, и поэтому число различных ключей не меньше числа сообщений M.

     Как показывает следующий пример, можно  получить совершенную секретность, когда число сообщений точно  равно числу ключей. Пусть Mi занумерованы числами от 1 до n, так же как и E_i, и пусть используются n ключей. Тогда

     T_iM_j = E_s,

     где s = i + j (mod n). В этом случае оказывается справедливым равенство P_E(M) = 1/n = P(E) и система является совершенно секретной. Один пример такой системы показан на рисунке 1.

     где

     s = i + j - 1(mod 5)

     

     Рисунок 1. Совершенная система

     Совершенно  секретные системы, в которых  число криптограмм равно числу  сообщений, а также числу ключей, характеризуются следующими двумя  свойствами:

1. каждое M связывается с каждым E только одной линией;
2. все ключи равновероятны.

     Таким образом, матричное представление такой системы является «латинским квадратом». В «Математической теории связи» показано, что количественно информацию удобно измерять с помощью энтропии. Если имеется некоторая совокупность возможностей с вероятностями p₁,…,p_n, то энтропия дается выражением

      .

     Секретная система включает в себя два статистических выбора: выбор сообщения и выбор  ключа. Можно измерять количество информации, создаваемой при выборе сообщения, через H(M)

      ,

     где суммирование выполняется по всем возможным  сообщениям. Аналогично, неопределенность, связанная с выбором ключа, дается выражением

      .

     В совершенно секретных системах описанного выше типа количество информации в сообщении равно самое большее log n (эта величина достигается для равновероятных сообщений). Эта информация может быть скрыта полностью лишь тогда, когда неопределенность ключа не меньше log n. Это является первым примером общего принципа, который будет часто встречаться ниже: существует предел, которого нельзя превзойти при заданной неопределенности ключа – количество неопределенности, которое может быть введено в решение, не может быть больше, чем неопределенность ключа.

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

     Предположим далее, что для шифрования и дешифрирования сообщения длины L_M  требуется только определенная длина ключа L_K. Пусть логарифм числа букв в алфавите сообщений будет R_M, а такой же логарифм для ключа – R_K. Тогда из рассуждений для конечного случая, очевидно, следует, что для совершенной секретности требуется, чтобы выполнялось неравенство

     R_ML_M <= R_KL_K.

     Такой вид совершенной секретности  реализован в системе Вернама. Эти выводы делаются в предположении, что априорные вероятности сообщений неизвестны или произвольны. В этом случае ключ, требуемый для того, чтобы имела место совершенная секретность, зависит от полного числа возможных сообщений. Можно было бы ожидать, что если в пространстве сообщений имеются фиксированные известные статистические связи, так что имеется определенная скорость создания сообщений R в смысле, принятом в «Математической теории связи», то необходимый объем ключа можно было бы снизить в среднем в R/R_M раз, и это действительно верно. В самом деле, сообщение можно пропустить через преобразователь, который устраняет избыточность и уменьшает среднюю длину сообщения как раз во столько раз. Затем к результату можно применить шифр Вернама. Очевидно, что объем ключа, используемого на букву сообщения, статистически уменьшается на множитель R/R_M, и в этом случае источник ключа и источник сообщений в точности согласован – один бит ключа полностью скрывает один бит информации сообщения.

     С помощью методов, использованных в «Математической теории связи», легко также показать, что это лучшее, чего можно достигнуть. Совершенно секретные системы могут применяться и на практике, их можно использовать или в том случае, когда полной секретности придается чрезвычайно большое значение, например, для кодирования документов высших военных инстанций управления, или же в случаях, где число возможных сообщений мало. Так, беря крайний пример, когда имеются в виду только два сообщения – «да» или «нет», – можно, конечно, использовать совершенно секретную систему со следующей таблицей (3) отображений: