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

7. Чистые и смешанные шифры

Некоторые типы шифров, такие как простая подстановка, транспозиция с данным периодом, система Виженера с данным периодом,

Рис. 4.
\begin{center} \parbox{25mm}{\begin{center}\sffamily Остаточные классы соо... ...nter}{\ttfamily\sffamily Чистая система}\end{center}\end{minipage} \end{center}

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

\begin{displaymath}pS+qT,\end{displaymath}

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

Причина однородности таких систем лежит в групповом свойстве: заметим, что в приведенных выше примерах однородных шифров произведение $ T_iT_j$ любых двух отображений из множества равно третьему отображению $ T_k$ из этого же множества. С другой стороны, $ T_iS_j$ не равно какому-нибудь отображению для шифра

\begin{displaymath}pS+qT,\end{displaymath}

который содержит только подстановки и транспозиции, но не их произведения.

Было бы можно, таким образом, определить ``чистый'' шифр как шифр, в котором $ Т_j$ образуют группу. Однако это было бы слишком сильным ограничением, так как тогда потребовалось бы, чтобы пространство $ Е$ совпадало с пространством $ М$, т.е. чтобы система была эндоморфной. Дробная транспозиция так же однородна, как и обычная транспозиция, но она не эндоморфна. Подходящим является следующее определение: шифр $ Т$ является чистым, если для каждых $ Т_i, T_j, Т_k$ имеется такое $ T_s$, что

\begin{displaymath}T_iT_j^{-1}T_k = T_s,\end{displaymath}

и все ключи равновероятны. В противном случае шифр является смешанным. Шифры на рис. 2 являются смешанными, а на рис. 4 -- чистыми, если только все ключи равновероятны.


Теорема 1.   В чистом шифре операции $ Т_i^{-1} Т_j$, отображающие пространство сообщений в себя, образуют группу, порядок которой равен $ m$ -- числу различных ключей.


Так как

\begin{displaymath}T_j^{-1}T_kT_k^{-1}T_j=I,\end{displaymath}

то каждый элемент имеет обратный. Ассоциативный закон верен, так как это операции, а групповое свойство следует из того, что

\begin{displaymath}T_i^{-1}T_jT_k^{-1}T_l =T_s^{-1}T_kT_k^{-1}T_l=T_s^{-1}T_l,\end{displaymath}

где предполагалось, что $ T_i^{-1}T_j=T_s^{-1}T_k$ для некоторого $ s$.

Операция $ Т_i^{-1} Т_j$ означает шифрование сообщения с помощью ключа $ j$ с последующим дешифрованием с помощью ключа $ i$, что приводит нас назад к пространству сообщений. Если система $ Т$ эндоморфна, т.е. $ Т_i$ отображают пространство $ \Omega_M$ в само себя (что имеет место для большинства шифров, в которых и пространство сообщений, и пространство криптограмм состоит из последовательностей букв), и если $ T_i$ образуют группу и равновероятны, то $ Т$ -- чистый шифр, так как

\begin{displaymath}T_iT_j^{-1}T_k=T_iT_r=T_s.\end{displaymath}


Теорема 2.   Произведение двух чистых коммутирующих шифров является чистым шифром.


Если $ Т$ и $ R$ коммутируют, то $ T_iR_j = R_lT_m$ для любых $ i,j $ при соответствующих $ l,m$. Тогда

\begin{displaymath}T_iR_j(T_kR_l)^{-1}T_mR_n= T_iR_jR_l^{-1}T_k^{-1}T_mR_n= R_uR_v^{-1}R_w T_rT_s^{-1}T_t=R_hT_g. \end{displaymath}

Условие коммутирования не является, однако, необходимым для того, чтобы произведение было чистым шифром.

Система, состоящая из одного ключа, т.е. из единственной определенной операции $ T_1$, является чистым шифром, т.е. при единственном возможном выборе индексов имеем

\begin{displaymath}T_1T_1^{-1}T_1=T_1. \end{displaymath}

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

Исследование примера, приведенного на рис. 4, вскрывает некоторые свойства чистого шифра. Сообщения распадаются на определенные подмножества, которые мы будем называть остаточными классами, и возможные криптограммы также распадаются на соответствующие им остаточные классы. От каждого сообщения в любом классе к каждой криптограмме в соответствующем классе имеется не менее одной линии и нет линий между несоответствующими классами. Число сообщений в классе является делителем полного числа ключей. Число ``параллельных'' линий от сообщения $ М$ к криптограмме в соответствующем классе равно числу ключей, деленному на число сообщений в классе, содержащем это сообщение (или криптограмму).

В приложении2) показывается, что это верно для чистых шифров и в общем случае. Резюмируя сказанное, мы имеем


Теорема 3.   В чистой системе сообщения можно разделить на множество ``остаточных классов'' $ C_1,\dots,C_s$, а криптограммы -- на соответствующее множество остаточных классов $ C'_1,\dots,C'_s$. Эти классы будут иметь следующие свойства:

1. Остаточные классы сообщений взаимно исключают друг друга и содержат все возможные сообщения. Аналогичное утверждение верно и для остаточных классов криптограмм.

2. Если зашифровать любое сообщение из класса $ C_i $ с помощью любого ключа, то получится криптограмма из класса $ C'_i $. Дешифрирование любой криптограммы из класса $ C'_i $ с помощью любого ключа приводит к сообщению из класса $ C_i $.

3. Число сообщений в классе $ C_i $, скажем, $ \varphi_i$, равно числу криптограмм в классе $ C'_i $ и является делителем $ k$ -- числа ключей.

4. Каждое сообщение из класса $ C_i $ может быть зашифровано в каждую криптограмму из класса $ C'_i $ при помощи точно $ k/\varphi_i$ различных ключей. То же самое верно и для дешифрирования.


Смысл понятия чистый шифр (и причина для выбора такого термина) лежит в том, что в чистом шифре все ключи являются по существу одинаковыми. Какой бы ключ ни использовался для заданного сообщения, апостериорные вероятности всех сообщений будут теми же самыми. Чтобы показать это, заметим, что два различных ключа, примененных к одному сообщению, дадут в результате две криптограммы из одного остаточного класса, скажем $ C'_i $. Поэтому эти две криптограммы могут быть расшифрованы с помощью $ k/\ph_i$ ключей в каждое из сообщений в классе $ C_i $ и больше ни в какие возможные сообщения. Так как все ключи равновероятны, то апостериорные вероятности различных сообщений равны

\begin{displaymath}P_E(M)=\frac{P(M)\cdot P_M(E)}{P(E)}= \frac{P(M)\cdot P_M(E)}{\Sigma_M P(M) P_M(E)}=\frac{P(M)}{P(C_i)}, \end{displaymath}

где $ М$ -- сообщение из класса $ C_i $, $ Е$ -- криптограмма из класса $ C'_i $ и сумма берется по всем $ М$ из класса $ C_i $. Если $ Е$ и $ М$ не принадлежат соответствующим остаточным классам, то $ P_Е(М) = 0$.

Аналогично можно показать, что набор апостериорных вероятностей различных ключей всегда одинаков, но эти вероятности ставятся в соответствие ключам лишь после того, как уже использован некоторый ключ. При изменении частного ключа это множество чисел $ P_Е(К)$ подвергается перестановке. Иными словами, имеем:


Теорема 4.   В чистой системе апостериорные вероятности различных сообщений $ P_E(M)$ не зависят от выбора ключа. Апостериорные вероятности ключей $ P_Е(К)$ образуют один и тот же набор величин, но подвергаются перестановке в результате различных выборов ключа.


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

В качестве примера чистого шифра может служить простая подстановка с равновероятными ключами. Остаточный класс, соответствующий данной криптограмме $ Е$, является множеством всех криптограмм, которые могут быть получены из $ Е$ с помощью операций $ T_jT_k^{-1}Е$. В рассматриваемом случае операция $ T_jT_k^{-1} $ сама является подстановкой и поэтому любая подстановка переводит криптограмму $ Е$ в другой член того же самого остаточного класса; таким образом, если криптограмма представляет собой
\begin{align*} &Е =XCPPGCFQ,&&\\ \intertext{то} &E_1 = RDHHGDSN,&&\\ &E_2 = ABCCDBEF&& \text{и т. д.} \end{align*}
принадлежат к тому же остаточному классу. В этом случае очевидно, что криптограммы по существу эквивалентны. Все существенное в простой подстановке со случайным ключом заключено в характере повторения букв, в то время как сами буквы являются несущественной маскировкой. В действительности можно бы полностью обойтись без них, указав характер повторений букв в $ Е$ следующим образом:

\epsfbox{shannon.6}



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

В шифре типа Цезаря имеют значение только первые разности криптограммы по модулю 26. Две криптограммы с теми же самыми разностями ($ \Delta e_i$) принадлежат к одному остаточному классу. Этот шифр можно раскрыть путем простого процесса выписывания двадцати шести сообщений из этого остаточного класса и выбора того из них, которое имеет смысл.

Шифр Виженера с периодом $ d$ со случайным ключом представляет собой другой пример чистого шифра. Здесь остаточный класс сообщений состоит из всех последовательностей с теми же первыми разностями, что и у криптограммы для букв, отстоящих на расстояние $ d$. Для $ d = 3$ остаточный класс определяется с помощью равенств

\begin{displaymath} \begin{array}{rcl} m_1-m_4&=&e_1-e_4\\ m_2-m_5&=&e_2-e_5\\... ...\ \multicolumn{3}{c}{\dots\quad\dots\quad\dots} \end{array} \end{displaymath}

где $ Е=e_1e_2\dots$ -- криптограмма, а $ m_1m_2\dots$ является любым сообщением $ М$ в соответствующем остаточном классе.

В транспозиции с периодом $ d$ со случайным ключом остаточный класс состоит из всех способов расстановок символов криптограммы, в которых никакое $ e_i$ не выдвигается из своего блока длины $ d$ и любые два $ e_i$ с расстоянием $ d$ остаются на таком же расстоянии. Это используется для раскрытия шифра следующим образом: криптограмма записывается в виде последовательных блоков длины $ d$ один под другим, как показано ниже (для $ d = 5$)

\begin{displaymath}\begin{matrix} e_1&e_2&e_3&e_4&e_5\\ e_6&e_7&e_8&e_9&e_{10}\\ e_{11}&e_{12}&\hdotsfor{3}\\ \hdotsfor{5} \end{matrix} \end{displaymath}

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

Теорема 5.   Если шифр $ Т$ -- чистый, то $ T_iT_j^{-1}T=T$, где $ T_i, T_j $ -- любые два отображения из $ Т$. Обратно, если это выполняется для любых принадлежащих шифру $ T_i, T_j $, то шифр $ Т$ является чистым.

Первая часть этой теоремы следует, очевидно, из определения чистого шифра. Чтобы доказать вторую часть, заметим сначала, что если $ Т_iТ_j^{-1}Т = Т$, то $ Т_iТ_j^{-1} T_s$ является отображением из $ Т$. Остается показать, что все ключи равновероятны. Имеем $ Т =\sum_{s}^{}p_s T_s$ и

\begin{displaymath} \sum_{s}^{}p_sТ_iТ_j^{-1}T_s= \sum_{s}^{}p_sT_s. \end{displaymath}

Слагаемое в стоящей слева сумме с $ s =j$ дает $ p_jT_i $. Единственным слагаемым с $ T_i$ в правой части является $ р_iТ_i$. Так как все коэффициенты неотрицательны, то отсюда следует, что

\begin{displaymath}p_j\leq p_i.\end{displaymath}

То же самое рассуждение остается справедливым, если $ i$ и $ j$ поменять местами. Следовательно,

\begin{displaymath}p_i = p_j\end{displaymath}

и $ T$ -- чистый шифр. Таким образом, условие $ Т_iТ_j^{-1}Т = Т$ можно было бы использовать в качестве другого определения чистого шифра.

Next: 8. Подобные системы Up: Часть I. МАТЕМАТИЧЕСКАЯ СТРУКТУРА СЕКРЕТНЫХ Previous: 6. Алгебра секретных систем Contents: Содержание

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