Раздел второй

1. Исторические шифры.

1) Шифр Цезаря и шифр Августа.

Текст на латинском языке изменялся за счет замены каждой буквы на третью от нее в алфавите (шифр Цезаря) или на следующую в алфавите (шифр Августа). Замена была циклической, т.е. последние буквы алфавита заменялись первыми. Это пример шифров простой замены, при которой алфавит открытых текста инъективно отображается в алфавит закрытых текстов. Ключом к шифру является величина «сдвига». Ввиду незначительной величины ключевого пространства такой шифр легко вскрывается прямой атакой. Приведем пример. Открытый текст «CAESAR» по указанному правилу Цезаря преобразуется в шифртекст «FDHVDU».

2) Шифр Сцитала (Scitale).

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

3) Квадрат Полибия (древняя Греция)

В квадрат , строки и столбцы которого пронумерованы от 1 до 5, вписывались буквы латинского или греческого алфавитов по одной в каждую клетку. Латинские буквы i и j записывались в одну клетку. Шифрование производилось заменой каждой буквы открытого текста парой чисел – координат этой буквы в указанном квадрате. Это тоже шифр простой замены, но алфавит открытых текстов отличается от алфавита закрытых. Ключом является порядок размещения букв в квадрате. Ключевое пространство весьма обширно и оценивается величиной 25! (Сравним с числом 25 в шифрах Цезаря-Августа). Приведем пример. Зададим ключ в виде:

	1	2	3	4	5
1	A	B	C	D	E
2	F	G	H	I,J	K
3	L	M	N	O	P
4	Q	R	S	T	U
5	V	W	X	Y	Z

Тогда открытый текст «REMEMBER» преобразуется в шифртекст «4215321532121542».

4) Шифр четырех квадратов.

Латинский алфавит, из которого изъята буква j, записывается в квадрат в произвольном порядке. Составляются четыре таких квадрата, вообще говоря, различных. Квадраты записываются в матрицу так, чтобы строки и столбцы их были выровнены и составляли единое целое. Открытый текст разбивается на биграммы, т.е. пары букв. Каждая биграмма открытого текста заменяется иной биграммой по следующему правилу. Первая буква заменяемой биграммы ищется в левом верхнем квадрате, а вторая – в правом нижнем. Отмеченные буквы задают в матрице алфавитов две противоположные вершины прямоугольника. Замещающие буквы находят в вершинах этого прямоугольника соответственно в правом верхнем и левом нижнем квадрате. Этот шифр является биграммным шифром замены. Ключом служат указанные квадраты алфавитов. Объем ключевого пространства оценивается величиной . Рассмотрим пример со следующим ключом:

K	I	N	G	D		V	Q	E	O	K
O	M	A	B	C		W	R	F	M	I
E	F	H	L	P		X	S	H	A	N
Q	R	S	T	U		Y	T	L	B	G
V	W	X	Y	Z		Z	U	P	C	D
Z	Y	X	W	V		D	C	P	U	Z
U	T	S	R	Q		G	B	L	T	Y
P	L	H	F	E		N	A	H	S	X
C	B	A	M	O		I	M	F	R	W
D	G	N	I	K		K	O	E	Q	V

Расшифруйте закрытый текст «MOPWTIOMFXNS».

5) Шифр Кардано.

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

Для k = 2 зашифруем фразу: «ПО ПРОЧТЕНИИ СЖЕЧЬ». В соответствии с алгоритмом шифрования лишаем текст пробелов и вписываем буквы в имеющиеся прорези, изображенные жирными линиями. Получим до первого поворота

			П
		О
П
	Р

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

Ж	О	Н	П
Ч	Е	О	И
П	И	Т	Ч
С	Р	Ь	Е

Считывая текст построчно, разобьем его на блоки: «ЖОНПЧЕОИ ПИТЧСРЬЕ».

6) Шифр ADFGVX.

Немецкий военный шифр времен первой мировой войны, представляющий собой композицию двух шифров: билитеральной замены и матричного шифра обхо-да. Тридцать шесть символов открытого текста (26 латинских букв и 10 цифр) запи-сываются в матрицу , строки и столбцы которой, как в квадрате Полибия, про-нумерованы буквами, вынесенными в заголовок. Открытый текст на латинице, который лишается пробелов и знаков препинания, но может содержать цифры, преобразуется билитеральной заменой, т.е. каждый символ текста заменяется парой буквенных координат. Затем полученный текст подвергается повторному шифрованию, при котором он выписывается под заранее задуманным словом-лозунгом буква под буквой так, что в результате образуется матрица текста, число столбцов которой совпадает с числом букв лозунга. Столбцы матрицы затем переставляются в порядке следования букв лозунга при их размещении в стандартном алфавите латиницы. После этого текст из матрицы считывается построчно сверху вниз и разбивается на m-граммы. Композиция двух шифров в данном случае усложняет криптоанализ закрытых текстов и увеличивает ключевое пространство. Ключ состоит из исходного шифровального квадрата и слова-лозунга.

Рассмотрим пример. Пусть таблица билитеральной замены имеет вид:

	A	D	F	G	V	X
A	C	O	8	X	F	4
D	M	K	3	A	Z	9
F	N	W	L	0	J	D
G	5	S	I	Y	H	U
V	P	1	V	B	6	R
X	E	Q	7	T	2	G

Зашифруем следующую фразу «DON’T PUT IT OFF TILL TOMORROW». Тогда промежуточный шифртекст выглядит так:

«FXADFAXGVAGXXGGFXGADAVAVXGGFFFFFXGADDAADVXVXADFD».

Пусть слово-лозунг есть «GARDEN». Теперь применим к полученному тексту матричный шифр обхода:

4 1 6 2 3 5

G A R D E N

F X A D F A

X G V A G X

X G G F X G

A D A V A V

X G G F F F

F F X G A D

D A A D V X

V X A D F D

Теперь, считывая столбцы полученной матрицы в соответствии со старшинством букв лозунга и разбивая текст на блоки, получаем окончательно шифртекст:

«XGGDG FAXDA FVFGD DFGXA FAVFF XXAXF DVAXG VFDXD AVGAG XAA».

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

2. Частотный метод.

Шифры простой замены (так называют инъективные отображения множества заменяемых символов во множество замещающих) позволяют (при условии, что перехваченный шифртекст имеет достаточно большую длину) применить способ криптоанализа, который основан на учете частоты встречаемости символов алфавита естественных языков, для которых имеются соответствующие частотные таблицы. Существуют и более обширные таблицы частот биграмм и даже триграмм. В соответствии с такого рода данными криптоаналитик противника, подсчитывая частоты встречаемости символов в перехваченном шифртексте, может высказывать правдоподобные гипотезы о том, какие символы были заменены символами шифртекста. Такой подход весьма успешно работает, особенно для универсальных текстов большой длины. Рассматриваются поначалу те символы, которые встречаются наиболее часто. Если гипотеза не подтверждается, то переходят к следующим символам частотной таблицы имеющих наибольшую частоту из оставшихся. В русскоязычных текстах, например, наиболее часто встречающимся символом является символ пробела, а наиболее редкой буквой является «ф». Таким образом, шифр Полибия и шифр четырех квадратов могут быть вскрыты частотным методом.

Вернемся к историческим шифрам.

7) Шифр Б. де Виженера.

Полиалфавитный шифр, т.е. шифр замены, при котором замещающий символ зависит от места в открытом тексте, на котором стоит заменяемый символ. Шифрующая таблица Виженера представляет собой в случае латиницы квадрат , который заполнен буквами алфавита так, что каждая строка сдвинута на одну позицию вперед по отношению к предыдущей. При этом последние буквы приписываются спереди в соответствующем порядке. Таким образом, формально используются 26 алфавитов. Ключом служит некоторое слово на латинице, которое приписывается некоторое количество раз под открытым текстом, который предварительно лишен пробелов и знаков препинания и представляет собой единую строку. Строка закрытого текста получается по следующему правилу: для замены буквы открытого текста ее ищут в верхней строке таблицы Виженера, а стоящую под ней букву ключа – в левом столбце таблицы; замещающей буквой является та, что стоит на пересечении строки и столбца, в которых стоят заменяемая буква и соответствующая буква ключа. Текст, полученный таким образом, далее может быть разбит на m-граммы. Заметим, что это один из вариантов шифра Виженера. Ясно, что в этом случае одна и та же буква может заменяться разными в зависимости от попадания в пару с какой-либо ключевой буквой. Приведем пример. Имеется открытый текст:

“CHAUCER MET A YOUNG LADY AT COURT NAMED PHILIPPA”

Выберем ключевое слово:

“SHERIDAN”

Получим шифртекст:

CHAUCERMETAYOUNGLADYATCOURT NAMEDPH I LI PPA

SHE RI DANSHE RI DANS HER I DANSHE R IDANSHERI DAN

-------------------------------------------------------------------------------------

UOELKHRZWAEPWXNTDHHP IWCBMYXEI P EQHOMCQSPN

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

СELUP

HTARH

AADTI

UYYNL

COAAI

EUTMP

RNCEP

MGODA

Каждая из этих последовательностей преобразуется данным ключом по правилу сдвига по mod 26 на соответственно 18, 7, 4, 17, 8, 3, 0, 13 позиций. Поэтому, разбивая шифртекст на такие подпоследовательности, можно для достаточно длинного текста при помощи обычного частотного анализа найти величины этих сдвигов. Остается проблема определения длины ключа. Для этого пытаются найти в шифртексте одинаковые биграммы и триграммы (т.е. буквосочетания из двух и трех букв). Предполагая, что они порождены одинаковыми биграммами и триграммами открытого текста, делают вывод, что величина расстояния между двумя одинаковыми k-граммами кратна длине ключа. Это позволяет сократить количество вариантов перебора.

8) Шифр Г. Вернама (одноразовый блокнот)

Этот шифр представляет собой реализацию абсолютно стойкого шифра по К. Шеннону. Оцифрованный текст, записанный в двоичной системе счисления, представляет единую строку. Ключ есть строка битов, длина которой совпадает с длиной строки открытого текста, выбирается случайным образом из ключевого пространства с равномерным распределением вероятностей появления. Строка ключа складывается по модулю 2 со строкой открытого текста, в результате чего появляется закрытый текст сообщения, Для расшифровки достаточно повторно прибавить к полученной строке ключ. Ключ должен быть использован только один раз для конкретного сообщения и после применения уничтожен. К недостаткам такой системы шифрования относят: во-первых, большую возможную длину ключа, что может оказаться весьма неудобным, а во-вторых, необходимость в абсолютно надежном канале снабжения переписывающихся сторон такими ключами.

9) Аффинные шифры.

Общая идея таких шифров состоит в том, что рабочим алфавитом открытых и закрытых текстов является кольцо Z , где n – число символов алфавита естественного языка (речь идет о европейских языках). Таким образом, все вычисления производятся по модулю n. Если k – порядок шифра, то при генерировании ключей выбирают обратимую матрицу над кольцом Z и столбец над тем же кольцом размера . Пусть это будет матрица А и столбец S.

Открытый текст разбивается на k-граммы и оцифровывается (т.е. описывается через символы кольца Z ). Обозначив k-грамму открытого текста через Х, а соответствующий шифртекст через Y, процедуру шифрования можно описать так:

.

Результатом шифрования является набор образов вида Y.

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

.

Открытый текст представляет из себя набор прообразов вида X.

В случае, когда S = 0, говорят о линейном шифре, а если А = 0, – о шифре сдвига.

Ключевое пространство для линейного шифра k-го порядка совпадает с множеством обратимых матриц k-го порядка над Z . Это количество оценивается значением обобщенной функции Эйлера:

,

где .

Этот вид шифра оказывается нестойким против атаки с выбором открытого текста. Действительно, достаточно получить шифртексты для k (где k – порядок шифра) единичных столбцов в линейном случае, т.е. для

, ,

где 1 расположена на i-м месте, и дополнительно еще один шифртекст для

в случае аффинного шифра. Знание таких шифртекстов позволяет легко получить ключ зашифрования и, значит, ключ расшифрования.

При атаке с шифртекстом для k = 1 и k = 2 применим частотный метод (простой или с учетом частот биграмм). В случае атаки с известным открытым текстом можно существенно уменьшить количество вариантов перебора. Когда k = 2, аффинный шифр поддается частотному анализу как и любой биграммный шифр. Приведем пример. Пусть задан открытый текст:

«WALTER SCOTT IS THE CREATOR OF THE ENGLISH HISTORICAL NOVEL»

Применим аффинный шифр второго порядка, для чего зададим матрицу второго по-рядка А и вектор сдвига В:

А = , В = .

Далее следует разбить текст на биграммы ( если число символов оказывается нечет-ным, добавляем букву «J») и перевести его в цифровую запись, заменяя буквы и пробел номерами от 0 до 26. Получим представление открытого текста в виде:

«2200 1119 0417 2618 0214 1919 2608 1826 1907 0426 0217 0400 1914 1726 1405 2619

0704 2604 1306 1108 1807 2607 0818 1914 1708 0200 1126 1314 2104 1109».

Представляя теперь цифровую запись каждой биграммы в виде двумерного столбца,

умножаем полученное на матрицу А слева и прибавляем к результату столбец В. В итоге получаем цифровую запись шифртекста (напомним, что все вычисления производятся по mod 27):

«1409 2416 1215 1610 2319 1018 2307 1905 1309 0315 0201 0518 0003 1425 1122 1813

0124 1522 0818 0210 0802 2104 0719 0003 0525 2204 1110 2415 1714 0413».

Остается записать криптограмму в исходном алфавите:

«OJYQMPQKXTKSXHTFNJDPCBFSADOZLWSNBYPWISCKICVEHTADFZWELKYPROEN».

В случае атаки с известным открытым текстом предположим, что шифрующий алгоритм преобразует столбцы Х = (3 , 11) , Х = (8, 23) , Х = (9,1) соответст-венно в Y = (22, 17) , Y = (17, 7) , Y = (20, 12) . Вычитая из равенства Y = АХ + B (для i = 1,2) равенство Y = AX + B, получаем систему

А = ,

А = .

Иначе, получается матричное равенство

А = .

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

А = ,

можно получить линейные соотношения, доставляемые указанным уравнением, которые существенно сокращают возможный перебор вариантов (придется решать систему четырех линейных уравнений с четырьмя неизвестными над кольцом Z ). Напомним, что необходимым и достаточным условием обратимости матрицы D над кольцом Z является обратимость det D по mod n. Легко видеть, что в примере мат-рица справа имеет определитель, равный 13 (mod 27), 13 = 25 ( mod 27). Потому, используя обычный алгоритм нахождения обратной матрицы, получим, что

= .

Теперь можно найти и матрицу А:

А = = (mod 27).

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

A = , С = .

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