П о с ы л а ю _ к г _ в з р ы в ч а т к и.

Если кто не догадался, то каждая буква здесь была заменена на ее предшественницу в алфавите ("о" вместо "п", "н" вместо "o", "p" вместо "c", "к" вместо "л", "я" вместо "а" и т.п.).

Подобные шифры широко использовались в древности, достоверно известно, что Ю.Цезарь применял шифр замены со сдвигом на три буквы вперед при шифровании. Метод дешифрования шифра подстановки описан у Конан-Дойля в рассказе "Пляшущие человечки": достаточно сначала догадаться хотя бы об одном слове - появляются несколько известных букв, подставляя их в зашифрованный текст, можно угадать другие слова и узнать новые буквы и т.д.

Более формальный подход к дешифрованию основан на использовании средней частоты появления букв в текстах. Впервые похожий метод был предложен в конце 15-го века (итальянский математик Леон Баттиста Альберти) и использовал свойство неравномерности встречаемости разных букв алфавита. Позднее были определены средние частоты использования букв языка в текстах. Некоторые из них приведены в таблице 1.1.

Таблица 1.1. Буквы высокой частоты использования (%)

Английский язык	Е (12,9) Т (9,7) А (8,0) I(7,5) N (7,0) R (7,0)
Немецкий язык	E(19,2) N (10,2) I (8,2) S (7,0) R (7,0) T (5,9)
Русский язык	O (11,0) И (8,9) Е (8,3) А (7,9) Н (6,9) Т (6,0)

Теперь, имея шифртексты, можно было провести в них частотный анализ использования символов и на его основе получить (при неограниченном количестве шифрсообщений) точные значения всех букв. Но так как материала, как правило, не очень много, то частотный анализ дает приблизительные результаты, поэтому можно лишь с высокой долей вероятности предположить буквенное значение самых частоупотребимых символов, а далее - необходимо подставлять их в шифртексты и пытаться угадывать слова, однако результаты появляются достаточно быстро. Увлекательно на эту тему повествовал Эдгар По в своем «Золотом жуке».

На слабость шифров однозначной замены обратили внимание еще в 15-м веке. Случайные догадки - кто и кому пишет, названия городов и селений, часто употребляемые слова, вроде предлогов, - могли привести к почти мгновенному раскрытию шифра. Попытки модификации основывались на многозначной замене букв открытого текста с использованием ключевойпоследовательности (ключевого слова или ключа).

В наиболее чистом виде этот подход можно изложить так. Пусть мы хотим получить 10 вариантов (0, 1, ..., 9) замены каждой буквы исходного текста (в таблице 1.2 вариант замены определяет величину сдвига по алфавиту).

Придумаем ключевую последовательность из цифр 0...9 произвольной длины (например, 190 277 321 856 403). Для открытого текста надпишем над буквами цифры ключа (периодически) и выполним зашифрование, выбирая вариант замены по цифре ключа. Хорошо видно, что одни и те же буквы заменяются по разному, а разные буквы могут быть представлены одинаково:

1 9 0 2 7 7 3 2 1 8 5 6 4 0 3 1 9 0 2 7 7 3 2 1 8 5 6 ...

Н а ш а _ Т а н я _ г р о м к о _ п л а ч е т , у р о н и л а ...

О й ш в _ щ з р б _ д ш у т о о _ т м к ч з щ

, ы у р о р р ж ...

Таблица 1.2

Таблица вариантов замены

Вариант Буква
А	а	б	в	г	д	е	ж	з	и	й
Б	б	в	г	д	е	ж	з	и	й	к
В	в	г	д	е	ж	з	и	й	к	л
…	…	…	…	…	…	…	…	…	…	…
Я	я	а	б	в	г	д	е	ж	з	и

Идея фактически была предложена в 16-м веке французским дипломатом Блезом де Вижинером. Вместо цифр им использовались буквы, и ключевая последовательность представляла собой слово.

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

На основе алгоритма многозначной замены были разработаны и нашли широкое применение (особенно во время второй мировой войны) дисковые шифровальные машины. Сконструированные на принципах, используемых в арифмометрах, шифрмашины содержали 6-10 дисков на общей оси, которые могли дискретно поворачиваться один относительно другого, создавая на каждом такте уникальное сочетание из всех возможных сочетаний угловых положений.

Принцип работы дисков был одновременно открыт четырьмя изобретателями из разных стран (американец - 1918 г., голландец - 1919 г., швед - 1919г., немец Артур Шербиус - 1927 г.). Именно он сконструировал энигму (в переводе с немецкого – «загадка»).

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

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

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

- еженедельно устанавливается новый набор рабочих дисков;

- ежедневно устанавливается новый порядок дисков на оси;

- для каждого нового сообщения некоторому получателю в течении дня устанавливается новое начальное угловое положение дисков.

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

Оригинальный вариант алгоритма многозначной замены был предложен в 1917 году американским инженером Г.С.Вернамом. Он предназначался для шифрования текстов, представленных в двоичном (телеграфном) коде (код Бодо). Главным элементом был секретный (двоичный) ключ, цифры которого как бы надписывались над исходным кодом, а шифрсообщение (также в двоичном коде) формировалось применением операции «исключающее ИЛИ» (сложение по модулю два) к двоичным цифрам исходного текста и ключа. Как было установлено значительно позднее (доказал К.Шеннон), стойкость шифра Г.С. Вернама очень высока, если длина ключа не меньше длины сообщения (практически нераскрываемый шифр). Казалось бы проблема решена, но здесь имеются трудности с ключами (их качество, хранение, уничтожение, транспортировка). На каждом этапе существует угроза их безопасности. Поэтому этот метод используют в исключительных случаях.

Шифры перестановки

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

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

П	л	к	з	ч	и
о	а	Г	р	а	#
с	ю	-	ы	т	#
ы	-	В	в	к	#

Рис.1.2.Шифр табличной перестановки

Открытый текст: Посылаю _ кг _ взрывчатки###.

Шифрсообщение:Плкзчиоагра#сю_ыт#ы_ввк#.

‘#’ - произвольные символы

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

Другой вариант - кодирование перестановкой по группам символов, используя некоторые зигзагообразные шаблоны, например, как показано на рисунке 1.3. Стоит записать

1 7 9 3 5 11

8 6 2 10 12 4

Рис.1.3. Зигзагообразный шифр перестановки

Открытый текст: Посылаю_кг_взрывчатки###

Шифрсообщение:Пюксл_ывгоа_ зтиыч#в##рак

_______________ _____________

группа 1 группа2

‘#’- произвольные символы.

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

Использовались и более сложные (ручные) системы, также групповые. Например, в квадрате (рис.1.4), состоящем из 4 малых квадратов с определенной нумерацией клеток, вырезают 4 клетки под разными номерами. Квадрат кладется в начальное положение («1» - вверху) и в отверстия (слева направо/сверху вниз) вписываются буквы открытого сообщения. Затем квадрат поворачивается против часовой стрелки на 90 градусов («2» - вверху) и также вписываются следующие буквы, потом повторяем процесс для положения «3» и «4». Если остаются свободные клетки - они заполняются произвольными символами. Шифрсообщение получают, считав по столбцам или по строкам последовательность записанных в прямоугольнике букв.

1
4	2 4 1 3	1 2 3 4
	4 3 2 1	3 1 4 2
3

1 2 3 4

П О		П о	л	П о г	К Л	зП о г	р к лы
Ы	с	а ы ю	с	А ы ю	С в	а в ы ю	С В

Посылаю_кг_взрывчатки

ЗоаыПгвюрлсвкы_ _ …

группа_1 группа_2

Рис.1.4. Шифровальный квадрат

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

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

⇐ Предыдущая 123 4 5 Следующая ⇒