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

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

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

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

, (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 вероятности некоторых сообщений возрастают, но для большинства сообщений они убывают до тех пор, пока не останется только одно сообщение, имеющее вероятность, близкую к единице, в то время как полная вероятность всех других близка к нулю.

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

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

Учитывая эти соображения, естественно использовать аналогичную применяемой в радиофизике и теории информации условную энтропию передаваемого сигнала при условии, что принятый сигнал известен, в качестве теоретической меры секретности, которая далее будет названа ненадежностью. Следует отметить, что имеются две основные ненадежности: ненадежность ключа и ненадежность сообщения. Они будут обозначаться через H_E(K) и H_E(M) соответственно. Их величины определяются соотношениями:

, (45)

, (46)

где E, M и K – криптограмма, сообщение и ключ; P(E, K) – вероятность ключа K и криптограммы E; P_E(K) – апостериорная вероятность ключа K, если перехвачена криптограмма E; P(E, M) и P_E(M) – аналогичные вероятности, но не для ключа, а для сообщения. Суммирование в H_E(K) проводится по всем возможным криптограммам определенной длины (скажем, N) и по всем возможным ключам. Для H_E(M) суммирование проводится по всем сообщениям и криптограммам длины N. Таким образом, H_E(K) и H_E(M) являются функциями от N – числа перехваченных букв. Это будет иногда указываться в обозначении так: H_E(K, N), H_E(M, N).

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

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

· ненадежность ключа Н_Е(K, N) — невозрастающая функция N[11];

· ненадежность первых А букв сообщения является невозрастающей функцией N: если перехвачено N букв, то ненадежность первых N букв сообщения меньше или равна ненадежности ключа;

· ненадежность сообщения для произведения криптозащищенных система S = TR не меньше ненадежности для одной системы R.

Рассмотрим теперь, что имеется «чистую» защищенную систему. Обозначим различные остаточные классы сообщений через C₁, C₂, …, C_r и соответствующие остаточные классы криптограмм через C₁', C₂', …, C_r'. Вероятности всех E из C_i одинаковы и равны

, (47)

где n_i – число различных сообщений в C_i. Таким образом, имеем:

. (48)

Учитывая, что

H_E(K) = H(K) + H(M) – H(E), (49)

с учетом (48) для чистого шифра имеем

. (50)

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

1. Пусть число возможных сообщений длины N есть T=2^RN, где R = log₂G, G – число букв алфавита. Предполагается, что число возможных криптограмм длины N также равно T.

2. Все возможные сообщения длины N можно разделить на две группы: группу с высокими и достаточно равномерными априорными вероятностями и группу с пренебрежимо малой полной вероятностью. Высоко вероятная группа будет содержать S = 2^RN сообщений, где R = H(M)/N, то есть R – энтропия источника сообщений на одну букву.

3. Операцию расшифрования можно представлять графически в виде ряда линий (как на рис. 5 и 7), идущих от каждого Е к различным M. Предположим, что имеется k равновероятных ключей, и что от каждого E будет отходить k линий. Предположим, что для случайного шифра линии от каждого E отходят к случайному набору возможных сообщений. Тогда случайный шифр будет представлять собой фактически целый ансамбль шифров и его ненадежность будет равна средней ненадежности этого ансамбля.

Ненадежность ключа определяется с помощью равенства

H_E(K) = Σ P(E) P_E(K) log P_E(K). (51)

Вероятность того, что от частного E к высоковероятной группе сообщений отходит ровно m линий, составляет

. (52)

Если перехвачена криптограмма, которой соответствует m таких линий, то ненадежность равна log(m). Вероятность такой криптограммы равна mT/Sk, так как она может быть создана из высоковероятных сообщений, каждое из которых имеет вероятность T/S с помощью одного из m ключей. Отсюда ненадежность равна

. (53)

Требуется найти простое приближенное выражение для H_E(K), когда k велико. Если для

величины m ее среднее значение μ = Sk / T много больше 1, то изменение log(m) в области тех m, для которых биномиальные слагаемые велики, будет малым и мы можем заменить log(m) на log(μ). Этот множитель можно вынести за знак суммы, которая даст значение m. Таким образом, при этом условии

, (54)

H_E(K) ≈ H(K) – DN, (55)

где D – избыточность на букву первоначального языка (D = D_N/N).

Если m мало по сравнению с k, то биномиальное распределение может быть приближенно пуассоновским:

, (56)

где λ = Sk/T. Отсюда

. (57)

Заменив m на m+1, получим:

. (58)

Это выражение можно использовать, когда λ близко к 1. Если же λ < < 1, то существенным является лишь первый член ряда. Отбрасывая другие, получим

H_E(K) ≈ e^-λ λ log2 ≈ λ log2 ≈ 2^-ND k log2. (59)

Итак, подводя итог вышесказанному, получаем, что H_E(K), рассматриваемая как функция от N – числа перехваченных букв – при N = 0 равна H(K). Далее она убывает линейно с наклоном –D до окрестности точки N = H(K)/D. После небольшой переходной области H_E(K) начинает убывать экспоненциально со временем «полураспада» 1/D, если D измеряется в битах на букву. Поведение H_E(K) показано на рис. 9 вместе с аппроксимирующими кривыми.

С помощью аналогичных рассуждений можно подсчитать ненадежность сообщения. Она равна H_E(M) = RN для RN < < H_E(K); H_E(M) = H_E(K) для RN > > H_E(K), H_E(M) = H_E(K) – f(N) для RN ~ H_E(K), где f(N) – функция, показанная на рис. 8, причем шкала N сжата в D/R раз. Таким образом, H_E(M) возрастает линейно с наклоном R до тех пор, пока она не пересечет линию H_E(K). После закругленного перехода она идет ниже кривой H_E(K).

Рис. 9. Ненадежность для случайного шифра

Видно, что кривые ненадежности стремятся к нулю довольно резко. Поэтому можно с достаточной определенностью говорить о точке, в которой решение становится единственным. Найденное при этом число букв мы будем называть расстоянием единственности. Для случайного шифра оно приблизительно равно H(K)/D.

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