Модель криптозащищенной ТКС

Определим ряд исходных положений дальнейшего анализа. Во-первых, будем рассматривать защищенные ТКС, в которых смысл передаваемого сообщения скрывается при помощи шифра, кода, но само существование сообщения не скрывается и предполагается, что противник обладает любым специальным оборудованием, необходимым для перехвата и записи переданных сигналов[8]. Во-вторых, ограничимся случаем дискретной информации, то есть положим, что сообщение, которое должно быть зашифровано, состоит из последовательных дискретных символов, каждый из которых выбран из некоторого конечного множества. Эти символы могут быть буквами или словами некоторого языка, амплитудными уровнями «квантованной» речи или видеосигнала, но главный акцент будет сделан на случае букв.

Далее следует ввести удовлетворительную идеализацию и определить математически приемлемым способом, что будет пониматься под криптозащищенной (далее по тексту – защищенной) системой. Схематическая структура защищенной системы показана на рис. 3.

Рис. 3. Схема защищенной телекоммуникационной системы

На передающем конце имеются два источника информации – источник сообщений и источник ключей. Источник ключей отбирает конкретный ключ среди всех возможных ключей данной системы. Этот ключ передается некоторым способом на приемный конец, причем предполагается, что его нельзя перехватить[9] (например, ключ передается посыльным). Источник сообщений формирует некоторое сообщение (незашифрованное), которое затем зашифровывается, и готовая криптограмма передается на приемный конец, причем криптограмма может быть перехвачена (например, пересылается по радио). На приемном конце шифровальщик с помощью ключа по криптограмме восстанавливает исходное сообщение. Очевидно, шифровальщик на передающем конце выполняет некоторую функциональную операцию. Если M – сообщение, K – ключ и E – зашифрованное сообщение (криптограмма), то имеем

E = f(M, K), (23)

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

E = T_iM. (24)

Отображение T_i примененное к сообщению M, дает криптограмму E. Индекс i соответствует конкретному используемому ключу. Вообще мы будем предполагать, что имеется лишь конечное число возможных ключей, каждому из которых соответствует вероятность p_i. Таким образом, источник ключей является статистическим процессом, или устройством, которое выбирает одно из множества отображений T₁,..., T_m с вероятностями p₁,..., p_m соответственно. Будем также предполагать, что число возможных сообщений конечно и эти сообщения M₁,..., M_n имеют априорные вероятности q₁,..., q_n. Например, возможными сообщениями могли бы быть всевозможные последовательности букв некоторого языка, включающих по N букв каждая, а соответствующими вероятностями тогда были бы относительные частоты появления таких последовательностей в тексте на соответствующем языке.

Должна иметься возможность восстанавливать M на приемном конце, когда известны E и K. Поэтому отображение T_i, из нашего семейства должно иметь единственное обратное отображение T_i^–1, так что T_iT_i^–1 = I, где I – тождественное отображение. Таким образом:

M = T_i^–1E. (25)

Во всяком случае, это обратное отображение T_i^–1 должно существовать и быть единственным для каждого E, которое может быть получено из M с помощью ключа i. Приходим, таким образом, к следующему определению: защищенная система есть семейство однозначно обратимых отображений T_i множества возможных сообщений во множество криптограмм, при этом отображение T_i имеет вероятность p_i. Обратно, любое множество объектов такого типа будет называться защищенной системой. Множество возможных сообщений для удобства будет называться «пространством сообщений», а множество возможных криптограмм – «пространством криптограмм». Две защищенные системы совпадают, если они образованы одним и тем же множеством отображений T_i и одинаковыми пространствами сообщений и криптограмм, причем вероятности ключей в этих системах также совпадают. Защищенную систему можно представлять себе как некоторую машину с одним или более переключающими устройствами. Последовательность букв (сообщение) поступает на вход машины, а на выходе ее получается другая последовательность. Конкретное положение переключающих устройств соответствует конкретному используемому ключу. Для выбора ключа из множества возможных ключей должны быть заданы некоторые статистические методы.

Для того чтобы нашу проблему можно было рассмотреть математически, предположим, что противнику известна используемая система. Иными словами, он знает семейство отображений T_i и вероятности выбора различных ключей. Можно было бы, во-первых, возразить, что такое предположение нереалистично, так как шифровальщик противника часто не знает, какая система использовалась или чему равны рассматриваемые вероятности. На это возражение имеется два ответа. Наложенное ограничение слабее, чем кажется с первого взгляда, из-за широты нашего определения защищенной системы. Предположим, что шифровальщик перехватывает сообщение и не знает, какой конкретно шифр использовался. Он может считать, что сообщение зашифровано с помощью системы, в которой часть ключа является указанием того, какой из трех типов имеющихся ключей был использован, а следующая часть – конкретный ключ этого типа. Указанным трем различным возможностям шифровальщик приписывает вероятности, учитывая при этом все имеющиеся у него сведения об априорных вероятностях использования шифровальщиком противника соответствующих типов шифров.

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

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

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

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

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

Рис. 4. Линейная схема защищенной системы

Возможные сообщения представляются точками слева, а возможные криптограммы – точками справа. Если некоторый ключ, скажем, ключ 1, отображает сообщение M₂ в криптограмму Е₂, то M₂ и E₂ соединяются линией, обозначенной значком 1. Для каждого ключа из каждого сообщения должна выходить ровно одна линия. Если это же верно и для каждой криптограммы, скажем, что система является замкнутой.

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

Если имеются две защищенные системы Т и R, их часто можно комбинировать различными способами для получения новой защищенной системы S. Если T и R имеют одну и ту же область (пространство сообщений), то можно образовать своего рода «взвешенную сумму»

S = рТ + qR, (26)

где p + q = 1. Эта операция состоит, во-первых, из предварительного выбора систем T или R с вероятностями p и q. Этот выбор является частью ключа S. После того как этот выбор сделан, системы T или R применяются в соответствии с их определениями. Полный ключ S должен указывать, какая из систем T или R выбрана и с каким ключом используется выбранная система.

Если Т состоит из отображений Т₁,..., Т_m с вероятностями p₁,..., p_m, a R – из R₁,..., R_k с вероятностями q₁,..., q_k, то система S = рТ + qR состоит из отображений Т₁,..., Т_m, R₁,..., R_k с вероятностями pp₁,..., pp_m, qq₁,..., qq_k, соответственно. Обобщая далее, можно образовать сумму нескольких систем

S = p₁Т + p₂R +... + p_mU, ∑ p_i = 1. (27)

Заметим, что любая система T может быть записана как сумма фиксированных операций

T = p₁Т₁ + p₂T₂ +... + p_mT_m, (28)

где T_i – определенная операция шифрования в системе T, соответствующая выбору ключа i, причем вероятность такого выбора равна p_i.

Второй способ комбинирования двух криптозащищенных систем заключается в образовании «произведения», как показано схематически на рис. 5. Предположим, что T и R – такие две системы, что область определения (пространство языка) системы R может быть отождествлена с областью значения (пространством криптограмм) системы T. Тогда можно применить сначала систему T к нашему языку, а затем систему R к результату этой операции, что дает результирующую операцию S, которую запишем в виде произведения

S = RT. (29)

Ключ системы S состоит как из ключа системы T, так и из ключа системы R, причем предполагается, что эти ключи выбираются соответственно их первоначальным вероятностям и независимо. Таким образом, если m ключей системы T выбирается с вероятностями p₁, p₂,..., p_m, а n ключей системы R имеют вероятности p'₁, p'₂,..., p'_n, то система S имеет самое большее mn ключей с вероятностями p_ip'_j.

Рис. 5. Произведение двух систем S = RT

Во многих случаях некоторые из отображений R_iT_j будут одинаковыми и могут быть сгруппированы вместе, а их вероятности при этом сложатся. Можно заметить, что такое умножение, вообще говоря, некоммутативно (то есть не всегда RS = SR), хотя в частных случаях (таких, как подстановка и перестановка) коммутативность имеет место. Так как наше умножение представляет собой некоторую операцию, оно по определению ассоциативно, то есть R(ST) = (RS)T = RST. Кроме того, верны законы

p(p'T + q'R) + qS = pp'T + pq'R + qS, (30)

то есть взвешенный ассоциативный закон для сложения и

T(pR + qS) = pTR + qTS, (31)

(pR + qS)T = pRT + qST, (32)

то есть право- и левосторонние дистрибутивные законы, а также справедливо равенство

p₁T + p₂T + p₃R = (p₁ + p₂)T + p₃R. (33)

Системы, у которых пространства M и E можно отождествить (этот случай является очень частым, если последовательности букв преобразуются в последовательности букв), могут быть названы эндоморфными. Эндоморфная система T может быть возведена в степень Tⁿ. Защищенная система T, произведение которой на саму себя равно T, то есть такая, что TT = T, будет называться идемпотентной.

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

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

T = p₁A + p₂B +... + p_rS + p'X, ∑ p_i = 1, (34)

где A, B,..., S в данном случае – известные типы шифров с их априорными вероятностями p_i, а p'X соответствует возможности использования совершенно нового неизвестного шифра.

Некоторые типы шифров обладают некоторой однородностью по отношению к ключу. Каков бы ни был ключ, процессы зашифрования, расшифрования адресатом и дешифрования противником являются по существу теми же самыми. Причина однородности таких систем лежит в групповом свойстве: для однородных шифров произведение T_iT_j любых двух отображений из множества равно третьему отображению T_k из этого же множества. Более строго, шифр T является чистым, если для каждых T_i, T_j, T_k имеется такое T_s, что

T_iT_j^–1T_k = T_s (35)

и все ключи равновероятны. В противном случае шифр является смешанным. Шифры на рис. 3 являются чистыми (если только все ключи равновероятны).

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

Если T и R коммутируют, то T_iR_j = R_lT_m для любых i, j при соответствующих l, m. Тогда

T_iR_j(T_kR_l)^–1T_mR_n = T_iR_jR_l^–1T_k^–1T_mR_n = R_uR_v^–1R_wT_rT_s^–1T_t = R_hT_g. (36)

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

Система, состоящая из одного ключа, т.е. из единственной определенной операции T₁, является чистым шифром, то есть при единственном возможном выборе индексов имеем T₁T₁^–1T₁ = T₁. Таким образом, разложение шифра в сумму таких простых отображений представляет собой разложение в его сумму чистых шифров.

Рис. 6. Пример «чистой» системы

Исследование примера, приведенного на рис. 6, вскрывает некоторые свойства чистого шифра. Сообщения распадаются на определенные подмножества, которые мы будем называть остаточными классами, и возможные криптограммы также распадаются на соответствующие им остаточные классы. От каждого сообщения в любом классе к каждой криптограмме в соответствующем классе ведет не менее одной линии, и нет линий между несоответствующими классами. Число сообщений в классе является делителем полного числа ключей. Число «параллельных» линий от сообщения M к криптограмме в соответствующем классе равно числу ключей, деленному на число сообщений в классе, содержащем это сообщение (или криптограмму). Можно доказать, что это верно для чистых шифров и в общем случае.

В чистой системе сообщения можно разделить на множество «остаточных классов» С₁,..., С_s, а криптограммы – на соответствующее множество остаточных классов С₁',..., С_s'. Эти классы будут иметь следующие свойства.

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

2. Если зашифровать любое сообщение из класса С_i с помощью любого ключа, то получится криптограмма из класса С_i'. Расшифрование любой криптограммы из класса С_i' с помощью любого ключа приводит к сообщению из класса С_i.

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. Этот способ часто используется на практике.