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

4. Примеры секретных систем

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

1. Шифр простой подстановки.

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

Таким образом, сообщение

\begin{displaymath}M=m_1m_2m_3m_4\dots,\end{displaymath}

где $ m_1, m_2, \dots$ -- последовательные буквы, переходит в

\begin{displaymath}Е = e_1e_2e_3e_4\dots = f(m_1) f(m_2) f (m_3) f (m_4) \dots,\end{displaymath}

причем функция $ f(m)$ имеет обратную функцию. Ключ является просто перестановкой алфавита (если буквы заменяются на буквы), например,

\begin{displaymath}XGUACDTBFHRSLMQVYZWIEJOKNP.\end{displaymath}

Первая буква -- $ Х$ заменяет букву $ A$, $ G$ заменяет $ В$ и т.д.

2. Транспозиция с фиксированным периодом $ d$.

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

Таким образом, для $ d = 5$ в качестве перестановки можно взять 23154. Это будет означать, что

\begin{displaymath}m_1m_2m_3m_4m_5m_6m_7m_8m_9m_{10}\dots\end{displaymath}

переходит в

\begin{displaymath}m_2m_3m_1m_5m_4m_7m_8m_6m_{10}m_9\dots .\end{displaymath}

Последовательное применение двух или более транспозиций будет называться составной транспозицией. Если периоды этих транспозиций $ d_1$, ..., $ d_s$, то, очевидно, в результате получится транспозиция периода $ d$, где $ d$ -- наименьшее общее кратное $ d_1,\dots, d_s$.

3. Шифр Виженера и его варианты.

В шифре Виженера ключ задается набором из $ d$ букв. Такие наборы подписываются с повторением под сообщением и полученные две последовательности складываются по модулю 26 (каждая буква рассматриваемого алфавита нумеруется от $ A= 0$ до $ Z = 25$).

Таким образом,

\begin{displaymath} l_i=m_i+k_i\pmod {26}, \end{displaymath}

где $ k_i$ -- буква ключа, полученная сокращением числа $ i$ по модулю $ d$. Например, с помощью ключа $ GAH$ получаем

Сообщение $ N$ $ О$ $ W$ $ I$ $ S$ $ Т$ $ Н$ $ Е$
Повторяемый ключ $ G$ $ A$ $ Н$ $ G$ $ А$ $ Н$ $ G$ $ А$
Криптограмма $ T$ $ O$ $ D$ $ O$ $ S$ $ A$ $ N$ $ E$

Шифр Виженера с периодом 1 называется шифром Цезаря. Он представляет собой простую подстановку, в которой каждая буква сообщения $ М$ сдвигается вперед на фиксированное число мест по алфавиту. Это число и является ключом; оно может быть любым от 0 до 25. Так называемый шифр Бофора (Beaufort) и видоизмененный шифр Бофора подобны шифру Виженера. В них сообщения зашифровываются с помощью равенств
\begin{align*} &l_i = k_i -m_i \pmod {26} \mbox{ и}\\ &l_i = m_i - k_i \pmod {26} \end{align*}
соответственно. Шифр Бофора с периодом 1 называется обратным шифром Цезаря.

Повторное применение двух или более шифров Виженера будет называться составным шифром Виженера. Он имеет уравнение

\begin{displaymath}l_i=m_i+k_i+l_i+\dots+s_i\pmod {26},\end{displaymath}

где $ k_i,l_i,\dots, s_i$ вообще говоря, имеют различные периоды. Период их суммы $ k_i+l_i+\dots+s_i$, как и в составной транспозиции, будет наименьшим общим кратным отдельных периодов.

Если используется шифр Виженера с неограниченным неповторяющимся ключом, то мы имеем шифр Вернама, в котором

\begin{displaymath}l_i = m_i + k_i \pmod {26}\end{displaymath}

и $ k_i$ выбираются случайно и независимо среди чисел 0, 1, ..., 25. Если ключом служит текст, имеющий смысл, то имеем шифр ``бегущего ключа''.

4. Диграммная, триграммная и $ n$-граммная подстановки.

Вместо подстановки одной буквы можно использовать подстановку диграмм, триграмм и т.д. Для диграммной подстановки в общем виде требуется ключ, состоящий из перестановок $ 26^2$ диграмм. Он может быть представлен с помощью таблицы, в которой ряд соответствует первой букве диграммы, а столбец -- второй букве, причем клетки таблицы заполнены заменяющими символами (обычно также диграммами).

5. Шифр Виженера с перемешанным один раз алфавитом.

Такой шифр представляет собой простую подстановку с последующим применением шифра Виженера
\begin{gather*} l_i=f(m_i)+k_i,\\ m_i=f^{-1}(l_i-k_i). \end{gather*}

``Обратным'' к такому шифру является шифр Виженера с последующей простой подстановкой
\begin{gather*} l_i=g(m_i+k_i),\\ m_i=g^{-1}(l_i)-k_i. \end{gather*}

6. Матричная система

Имеется один метод подстановки $ n$-грамм, который заключается в применении к последовательным $ n$-граммам некоторой матрицы, имеющей обратную. Предполагается, что буквы занумерованы от 0 до 25 и рассматриваются как элементы некоторого алгебраического кольца. Если к $ n$-грамме сообщения применить матрицу $ a_{ij}$, то получится $ n$-грамма криптограммы

\begin{displaymath} l_i=\sum_{j=1}^{n}a_{ij}m_j, \qquad i=1,\dots, n. \end{displaymath}

Матрица $ a_{ij}$ является ключом, и расшифровка выполняется с помощью обратной матрицы. Обратная матрица будет существовать тогда и только тогда, когда определитель $ \vertа_{ij} \vert$ имеет обратный элемент в нашем кольце.

7. Шифр Плэйфер

Этот шифр является частным видом диграммной подстановки, которая производится с помощью перемешанного алфавита из 25 букв, записанных в виде квадрата $ 5\times5$. (Буква $ J$ часто опускается при криптографической работе, так как она редко встречается, и в тех случаях, когда она встречается, ее можно заменить буквой $ I$). Предположим, что ключевой квадрат записывается следующим образом:

\begin{displaymath}\begin{array}{ccccc} L& Z& Q& С& Р \\ A& G& N& О& U \\ R& D& M& I& F \\ К& Y& Н& V& S \\ Х& В& Т& Е& W. \end{array} \end{displaymath}

В этом случае диграмма $ AC$, например, заменяется на пару букв, расположенных в противоположных углах прямоугольника, определяемого буквами $ A$ и $ C$, т.е. на $ LO$, причем $ L$ взята первой, так как она выше $ A$. Если буквы диграммы расположены на одной горизонтали, то используются стоящие справа от них буквы. Таким образом, $ RI$ заменяется на $ DF$, $ RF$ заменяется на $ DR$. Если буквы расположены на одной вертикали, то используются буквы, стоящие под ними. Таким образом, $ PS$ заменяется на $ UW$. Если обе буквы диграммы совпадают, то можно использовать для их разделения нуль или же одну из букв опустить и т.п.

8. Перемешивание алфавита с помощью многократной подстановки.

В этом шифре используются последовательно $ d$ простых подстановок. Так, если $ d = 4$, то

\begin{displaymath}m_1m_2m_3m_4m_5m_6\dots\end{displaymath}

заменяется на

\begin{displaymath}f_1(m_1)f_2(m_2)f_3(m_3)f_4(m_4)f_1(m_5)f_2(m_6)\dots\end{displaymath}

и т.д.

9. Шифр с автоключом.

Шифр типа Виженера, в котором или само сообщение или результирующая криптограмма используются в качестве ``ключа'', называется шифром с автоключом. Шифрование начинается с помощью ``первичного ключа'' (который является настоящим ключом в нашем смысле) и продолжается с помощью сообщения или криптограммы, смещенной на длину первичного ключа, как в указанном ниже примере, где первичным ключом является набор букв $ COMET$. В качестве ``ключа'' используется сообщение:
Сообщение $ S$ $ E$ $ N$ $ D$ $ S$ $ U$ $ P$ $ P$ $ L$ $ I$ $ E$ $ S$ $ \dots$
Ключ $ C$ $ O$ $ M$ $ E$ $ T$ $ S$ $ E$ $ N$ $ D$ $ S$ $ U$ $ P$ $ \dots$
Криптограмма $ U$ $ S$ $ Z$ $ H$ $ L$ $ M$ $ T$ $ C$ $ O$ $ A$ $ Y$ $ H$ $ \dots$


Если в качестве ``ключа'' использовать криптограмму, то получится1)
Сообщение $ S$ $ E$ $ N$ $ D$ $ S$ $ U$ $ P$ $ P$ $ L$ $ I$ $ E$ $ S$ $ \dots$
Ключ $ C$ $ O$ $ M$ $ E$ $ T$ $ U$ $ S$ $ Z$ $ H$ $ L$ $ O$ $ Н$ $ \dots$
Криптограмма $ U$ $ S$ $ Z$ $ H$ $ L$ $ O$ $ H$ $ O$ $ S$ $ T$ $ T$ $ S$ $ \dots$


10. Дробные шифры.

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

\begin{displaymath} \begin{array}{cccccc} & 0& 1& 2& 3& 4\\ 0& L& Z& Q& С& Р\... ... M& I& F\\ 3& К& Y& H& V& S\\ 4& X& В& Т& Е& W \end{array} \end{displaymath}

Например, букве $ В$ соответствует ``число'' 41. После того как полученный ряд чисел подвергнут некоторой перестановке, его можно снова разбить на пары чисел и перейти к буквам.

11. Коды.

В кодах слова (или иногда слоги) заменяются группами букв. Иногда затем применяется шифр того или иного вида.

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

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