6. Алгебра секретных систем

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

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

Если Т состоит из отображения с вероятностями из с вероятностями то система состоит из отображений с вероятностями соответственно.

Обобщая далее, можно образовать сумму нескольких систем

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

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

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

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

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

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

Таким образом, если ключей системы Т выбирается с вероятностями

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

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

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

Можно заметить, что такое умножение, вообще говоря, некоммутативно (т. е. не всегда хотя в частных случаях (таких, как подстановка и транспозиция) коммутативность имеет место.

Так как наше умножение представляет собой некоторую операцию, оно по определению ассоциативно, т. е. Кроме того, верны законы

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

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

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

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

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

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

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

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

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

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

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

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