Основы построения и эксплуатации защищенных телекоммуникационных систем

3. Число сообщений в классе  С_i, скажем n_i, равно числу криптограмм в классе С_i' и является делителем k – числа ключей.

4. Каждое сообщение из класса  С_i, может быть зашифровано в каждую криптограмму из класса С_i' при помощи точно k/n_i различных ключей. То же самое верно и для расшифрования.

Смысл понятия чистый шифр (и причина  для выбора такого термина) лежит  в том, что в чистом шифре все  ключи являются по существу одинаковыми. Какой бы ключ ни использовался для заданного сообщения, апостериорные вероятности всех сообщений будут теми же самыми. Чтобы показать это, заметим, что два различных ключа, примененных к одному сообщению, дадут в результате две криптограммы из одного остаточного класса, скажем С_i'. Поэтому эти две криптограммы могут быть расшифрованы с помощью k/n_i ключей в каждое из сообщений в классе С_i, и больше ни в какие возможные сообщения. Так как все ключи равновероятны, то апостериорные вероятности различных сообщений равны

 

,    (37)

 

где M – сообщение из класса С_i, E – криптограмма из класса С_i' и сумма берется по всем M из класса Сi. Если E и M не принадлежат соответствующим остаточным классам, то P_E(M) = 0.

Аналогично можно показать, что  набор апостериорных вероятностей различных ключей всегда одинаков, но эти вероятности ставятся в соответствие ключам лишь после того, как уже использован некоторый ключ. При изменении частного ключа это множество чисел P_E(M) подвергается перестановке. Иными словами, в чистой системе апостериорные вероятности различных сообщений P_E(M) не зависят от выбора ключа. Апостериорные вероятности ключей P_E(K) образуют один и тот же набор величин, но подвергаются перестановке в результате различных выборов ключа.

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

В качестве примера чистого шифра  может служить простая подстановка  с равновероятными ключами. Остаточный класс, соответствующий данной криптограмме E, является множеством всех криптограмм, которые могут быть получены из E с помощью операций T_jT_k^–1E. В рассматриваемом случае операция T_jT_k^–1 сама является подстановкой и поэтому любая подстановка переводит криптограмму E в другой член того же самого остаточного класса; таким образом, если криптограмма представляет собой Е = XCPPGCFQ, то Е₁ = RDHHGDSN, Е₂ = ABCCDBEF и так далее, принадлежат к тому же остаточному классу. В этом случае очевидно, что криптограммы по существу эквивалентны. Все существенное в простой подстановке со случайным ключом заключено в характере повторения букв, в то время как сами буквы являются несущественной маскировкой. В действительности можно бы полностью обойтись без них, указав характер повторений букв в E следующим образом (рис. 7).

 

 

Рис. 7. Характер повторений букв для  простой подстановки

 

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

На основе изложенного выше можно  заключить, что если шифр T – чистый, то T_iT_j^–1T = T, где T_i ,T_j – любые два отображения из T. Обратно, если это выполняется для любых принадлежащих шифру T_i ,T_j, то шифр T является чистым.

Для дальнейшего изложения потребуется  ввести еще одно определение. Две  секретные системы R и S будем называть подобными, если существует отображение A, имеющее обратное A^–1, такое, что

 

R = AS.     (38)

 

Это означает, что шифрование с  помощью R даст то же, что шифрование с помощью S с последующим применением  отображения А. Если использовать запись R ~ S для обозначения того, что R подобно S, то, очевидно, из R ~ S следует S ~ R. Кроме того, из R ~ S и S ~ T следует, что R ~ T и, наконец, R ~ R. Резюмируя вышеизложенное, можно сказать, что подобие систем является соотношением эквивалентности.

Криптографический смысл подобия состоит в том, что если R ~ S, то R и S эквивалентны с точки зрения дешифрования. Действительно, если шифровальщик противника перехватывает криптограмму из системы S, он может перевести ее в криптограмму из системы R простым применением к ней отображения A. Обратно, криптограмма из системы R переводится в криптограмму из системы S с помощью A^–1. Если R и S применяются к одному и тому же пространству сообщений или языку, то имеется взаимно однозначное соответствие между получающимися криптограммами. Соответствующие друг другу криптограммы дают одинаковое апостериорное распределение вероятностей для всех сообщений.

Если имеется некоторый способ раскрытия системы R, то любая система S, подобная R, может быть раскрыта после  приведения ее к R с помощью операции A. Этот способ часто используется на практике.

2.3. Теоретическая  оценка криптозащищенности ТКС

 

Рассмотрим теперь вопросы, связанные  с «теоретической защищенностью» систем. Насколько устойчива некоторая  система, если шифровальщик противника не ограничен временем и обладает всеми необходимыми средствами для анализа криптограмм? Имеет ли криптограмма единственное решение (даже если для нахождения этого решения может потребоваться такой объем работ, что его практически нельзя будет выполнить), а если нет, то сколько она имеет приемлемых решений? Какой объем текста, зашифрованного в данной системе, нужно перехватить для того, чтобы решение стало единственным? Существуют ли защищенные системы, в которых вообще нельзя найти единственного решения независимо от того, каков объем перехваченного зашифрованного текста? Существуют ли защищенные системы, в которых противник не получает никакой информации, сколько бы он ни перехватывал зашифрованного текста?

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

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

 

,     (39)

 

где 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)      (40)

 

для всех 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.

Как показывает следующий пример, можно получить совершенную секретность, когда число сообщений точно равно числу ключей. Пусть M_i занумерованы числами от 1 до n, так же как и E_i, и пусть используются n ключей. Тогда T_iM_j = E_s, где s = i + j (mod n). В этом случае оказывается справедливым равенство P_E(M) = 1/n = P(E) и система является совершенно защищенной (рис. 8).

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

 

E=-∑p_ilog(p_i).     (41)

 

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

 

H(M) = -∑P(M)logP(M),    (42)

 

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

 

H(K) = -∑P(K)logP(K).    (43)

 

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

 

 

Рис. 8. Совершенно защищенная система

 

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

 

R_ML_M ≤ R_KL_K.     (44)

 

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

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

Предположим теперь, что для английского  текста используется шифр простой подстановки и что перехвачено определенное число, скажем N, букв зашифрованного текста. Если N достаточно велико, скажем более 50, то почти всегда существует единственное решение шифра, т.е. единственная последовательность, имеющая смысл на английском языке, в которую переводится перехваченный материал с помощью простой подстановки. Для меньших N шансы на неединственность решения увеличиваются; для N = 15, вообще говоря, будет существовать некоторое число подходящих отрывков осмысленного английского текста, в то время как для N = 8 окажется подходящей значительная часть (порядка 1/8) всех возможных значащих английских последовательностей такой длины, так как из восьми букв редко повторится больше чем одна. При N = 1, очевидно, возможна любая буква и апостериорная вероятность любой буквы будет равна ее априорной вероятности. Для одной буквы система является совершенно секретной.

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

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

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