Клод Шеннон. Теория связи в секретных системах. Примеры секретных систем.


На домашнюю страничку Титульный лист Предыдущий раздел Следующий раздел

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

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

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

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

М = m1m2m3m4...,

где m1,m2,... - последовательные буквы, переходит в

E = e1e2e3e4... = f(m1)f(m2)f(m3)f(m4)...,

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

XGUACDTBFHRSLMQVYZWIEJOKNP.

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

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

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

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

m1m2m3m4m5m6m7m8m9m10...

переходит в

m2m3m1m5m4m7m8m6m10m9...

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

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

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

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

ei = mi+ki (mod 26),

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

Сообщение NO WI ST HE
Повторяемый ключ GAHG AHGA
Криптограмма TODO SANE

Шифр Виженера с периодом 1 называется шифром Цезаря. Он представляет собой простую подстановку, в которой каждая буква сообщения М сдвигается вперед на фиксированное число мест по алфавиту. Это число и является ключом; оно может быть любым от 0 до 25. Так называемый шифр Бофора (Beaufort) и видоизмененный шифр Бофора подобны шифру Виженера. В них сообщения зашифровываются с помощью равенств

ei = ki - mi (mod 26)

и

ei = mi - ki (mod 26)

соответственно. Шифр Бофора с периодом 1 называется обратным шифром Цезаря.

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

ei = mi + ki + li + ... + si (mod 26),

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

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

ei = mi + ki (mod 26),

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

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

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

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

Такой шифр представляет собой простую подстановку с последующим применением шифра Виженера

ei = f(mi) + ki,

mi = f -1(ei - ki).

"Обратным" к такому шифру является шифр Виженера с последующей простой подстановкой

ei = g(mi + ki),

mi = g-1(ei) - ki.

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

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

[здесь формула], i = 1,...,n.

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

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

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

L Z Q C P
AGNOU
RDMIF
KYHVS
XBTEW

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

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

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

m1m2m3m4m5m6...

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

f(m1)f(m2)f(m3)f(m4)f(m5)f(m6)...

и т.д.

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

Шифр типа Виженера, в котором или само сообщение или результирующая криптограмма используются в качестве "ключа", называется шифром с автоключом. Шифрование начинается с помощью "первичного ключа" (который является настоящим ключом в нашем смысле) и продолжается с помощью сообщения или криптограммы, смещенной на длину первичного ключа, как в указанном ниже примере, где первичным ключом является набор букв COMET. В качестве "ключа" используется сообщение:

Сообщение SEN DSU PPL IES ...
Ключ COMET SENDS UP...
Криптограмма USZHL MTCOA YH...

Если в качестве "ключа" использовать криптограмму, то получится

Сообщение SEN DSU PPL IES ...
Ключ COMET USZHL OH...
Криптограмма USZHL OHOST TS...

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

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

01 234
0 LZQCP
1 AGNOU
2 RDMIF
3 KYHVS
4 XBTEW

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

Коды.

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

На домашнюю страничку Титульный лист Предыдущий раздел Следующий раздел


[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 09.03.01. (c) 2001 Андрей Винокуров.