Смекни!
smekni.com

Теория связи в секретных системах (стр. 5 из 5)

Если Т состоит из отображений Т1,...,Тm с вероятностями p1,...,pm, a R - из R1,...,Rk с вероятностями q1,...,qk, то система S = рТ + qR состоит из отображений Т1,...,Тm,R1,...,Rk с вероятностями pp1,...,ppm,qq1,...,qqk соответственно. Обобщая далее, можно образовать сумму нескольких систем

S = p1Т + p2R + ... + pmU,

pi = 1.

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

T = p1Т1 + p2T2 + ... + pmTm,

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

Второй способ комбинирования двух секретных систем заключается в образовании "произведения", как показано схематически на рис. 3.

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

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

S = RT.

Ключ системы S состоит как из ключа системы T, так и из ключа системы R, причем предполагается, что эти ключи выбираются соответственно их первоначальным вероятностям и независимо. Таким образом, если m ключей системы T выбирается с вероятностями

p1,p2,...,pm,

а n ключей системы R имеют вероятности

p'1,p'2,...,p'n,

то система S имеет самое большее mn ключей с вероятностями pip'j. Во многих случаях некоторые из отображений RiTj будут одинаковыми и могут быть сгруппированы вместе, а их вероятности при этом сложатся.

Произведение шифров используется часто: например, после подстановки применяют перестановку или после перестановки - код Виженера, или же применяют код к тексту и зашифровывают результат с помощью подстановки, перестановки, дробным шифром и т.д.

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

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

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

T(pR + qS) = pTR + qTS
(pR + qS)T = pRT + qST

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

p1T + p2T + p3R = (p1 + p2)T + p3R.

Следует подчеркнуть, что эти операции комбинирования сложения и умножения применяются к секретным системам в целом. Произведение двух систем TR не следует смешивать с произведением отображений в системах TiRj, которое также часто используется в настоящей работе. Первое является секретной системой, т.е. множеством отображений с соответствующими вероятностями; второе является фиксированным отображением. Далее, в то время как сумма двух систем pR + qT является системой, сумма двух отображений не определена. Системы T и R могут коммутировать, в то время как конкретные Rj и Ti не коммутируют. Например, если R - система Бофора данного периода, все ключи которой равновероятны, то, вообще говоря,

RiRj

RjRi,

но, конечно, произведение RR не зависит от порядка сомножителей; действительно

RR = V

является системой Виженера того же самого периода со случайным ключом. С другой стороны, если отдельные отображения Ti и Rj двух систем T и R коммутируют, то и системы коммутируют.

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

Секретная система T, произведение которой на саму себя равно T, т.е. такая, что

TT = T,

будет называться идемпотентной. Например, простая подстановка, транспозиция с периодом p, система Виженера с периодом p (все с равновероятными ключами) являются идемпотентными.

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

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

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

T = p1A + p2B + ... + prS + p'X,

pi = 1,

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