Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 7. Чистые и смешанные Up: Часть I. МАТЕМАТИЧЕСКАЯ СТРУКТУРА СЕКРЕТНЫХ Previous: 5. Оценка секретных систем Contents: Содержание


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

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

\begin{displaymath} S=pT+qR, \end{displaymath}

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

Если $ Т$ состоит из отображений $ T_1,\dots, T_m$ с вероятностями $ p_1,\dots$ $ \dots, p_m$, а $ R$ -- из $ R_1,\dots,R_k$ с вероятностями $ q_1,\dots,q_k$, то система $ S =\linebreak = рТ + qR$ состоит из отображений $ T_1,\dots,T_m, R_1,\dots,R_k$ с вероятностями $ pp_1,\dots$ $ \dots,pp_m, qq_1,\dots,qq_k$ соответственно.

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

\begin{displaymath} S=p_1T+p_2R+\dots+p_mU, \quad \sum_{}^{}p_i=1. \end{displaymath}

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

\begin{displaymath} Т = p_1T_1 + p_2Т_2 + \dots + p_mT_m, \end{displaymath}

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

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

\begin{displaymath} S=RT. \end{displaymath}

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

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

\epsfbox{shannon.3}

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

\begin{displaymath}p_1,p_2,\dots, p_m,\end{displaymath}

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

\begin{displaymath}p'_1,p'_2,\dots, p'_n,\end{displaymath}

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

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

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

\begin{displaymath}р(р'Т + q'R) + qS =рр'Т + pq'R + qS\end{displaymath}

(взвешенный ассоциативный закон для сложения);
\begin{gather*} T(pR+qS)=pTR+qTS\\ (pR + qS) Т = pRT + qST \end{gather*}
(право- и левосторонние дистрибутивные законы), а также справедливо равенство

\begin{displaymath}p_1T + p_2Т + p_3R = (p_1+р_2)Т+ p_3R.\end{displaymath}

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

\begin{displaymath}R_iR_j\ne R_jR_i,\end{displaymath}

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

\begin{displaymath}RR=V\end{displaymath}

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

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

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

\begin{displaymath}ТТ=Т,\end{displaymath}

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

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


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


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

\begin{displaymath} Т=р_1A+р_2B+ \dots+p_rS+p'X, \quad \sum_{}^{} p_i=1, \end{displaymath}

где $ A, В, \dots, S$ в данном случае -- известные типы шифров с их априорными вероятностями $ p_i $, а $ р'Х$ соответствует возможности использования совершенно нового неизвестного шифра.

Next: 7. Чистые и смешанные Up: Часть I. МАТЕМАТИЧЕСКАЯ СТРУКТУРА СЕКРЕТНЫХ Previous: 5. Оценка секретных систем Contents: Содержание

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100