Алгебра секретных систем.
Если имеются две секретные системы Т и R, их часто можно комбинировать различными способами для получения новой секретной системы S. Если T и R имеют одну и ту же область (пространство сообщений), то можно образовать своего рода "взвешенную сумму" S = рТ + qR, где p + q = 1. Эта операция состоит, во-первых, из предварительного выбора систем T или R с вероятностями p и q. Этот выбор является частью ключа S. После того, как этот выбор сделан, системы T или R применяются в соответствии с их определениями. Полный ключ S должен указывать, какая из систем T или R выбрана и с каким ключом используется выбранная система. Если Т состоит из отображений Т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 (право- и левосторонние дистрибутивные законы), а также справедливо равенство 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 соответствует возможности использования совершенно нового неизвестного шифра.
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (169)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |