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

Для того чтобы нашу проблему можно было рассмотреть математически, предположим, что противнику известна используемая система. Иными словами, он знает семейство отображений 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.