1Классическая криптография и классический криптоанализ

Чумаков Александр Современный Гуманитарный Университет

Введение

Развитие Интернета приводит к появлению ряда серьезных проблем связанных с обеспечением безопасности информационных систем. Не так давно компьютеры работали независимо друг от друга, причем связь между ними либо отсутствовала, либо была очень слабой, а самое страшное, что могло произойти,- разрушение системы на одной отдельно взятой машине. В начале 90-х информационная безопасность интересовала лишь небольшое число людей – сотрудников специальных служб. Объединение большого числа компьютеров в большие информационные сети, с одной стороны, расширило возможности придачи информации, управлении ее потоками, расширило перспективы управлении бизнесом, с другой стороны, информация в объединенных информационных системах стала более уязвима. Информация обладает ценностью, а значит люди, прилагают усилия для ее добывания. Квалификация людей пытающихся получить доступ к приватной информации все время растет. Об уровне данной проблемы говорит и тот факт, что корпорация MICROSOFT в 2003 году остановило разработку своих продуктов на несколько месяцев, и прошла к обучению своих сотрудников. Почти все сотрудники прослушали от 80 до 100 часов лекций по предметам связанным с информационной безопасностью.

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

2Способы шифрования в античные времена.

2.1Шифр “скитала”.

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

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


Н	А	С	Т
У	П	А	И
Т	Е

Рис.1. Шифр "скитала"
писать по кольцу не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст.

Сообщение НАСТУПАЙТЕ при размещении его по окружности стержня по три буквы дает шифртекст

НУТАПЕСА_ТЙ

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

2.2Полибианский квадрат.

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

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

λ	ε	υ	ω	γ
ρ	ζ	δ	σ	ο
μ	η	β	ξ	τ
ψ	π	θ	α	Χ
χ	ν		φ	ι

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

ταυροσ

получается шифртекст

Χφδμτξ

Концепция полибианского квадрата оказалась плодотворной и нашла применение в криптосистемах последующего времени.

2.3Код Цезаря.

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).

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

Таблица 1

Одноалфавитная подстановка (K=3, m=26)

A→D	J→M	S→V
В→Е	K→N	T→W
C→F	L→0	U→X
D→G	М→Р	V→Y
Е→Н	N→Q	W→Z
F→I	0→R	X→A
G→J	P→S	Y→B
H→K	Q→T	Z→C
1→L	R→U

Например, послание Цезаря

VENI V1DI VICI

(в переводе на русский означает "Пришел, Увидел, Победил"), направленное его другу Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так:

YHQL YLGL YLFL
Достоинством системы шифрования Цезаря является простота шифрования и расшифрования. К недостаткам системы Цезаря следует отнести следующие:

• подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления различных букв исходного открытого текста;

• сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значения К изменяются только начальные позиции такой последовательности;

• число возможных ключей К мало;

• шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифртексте.

Криптоаналитическая атака против системы одноалфавитной замены начинается с подсчета частот появления символов:

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

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

3Способы шифрования в средние века.

3.1Шифрующие таблицы.

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

В качестве ключа в шифрующих таблицах используются:

• размер таблицы;

• слово или фраза, задающие перестановку;

• особенности структуры таблицы.

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

ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ

записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. 3.

После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам. Если шифртекст записывать

Т	Н	П	В	Е	Г	Л
Е	А	Р	А	Д	О	Н
Р	Т	И	Е	Ь	В	О
М	О	Б	Т	М	П	Ч
И	Р	Ы	С	О	О	Ь

Рис. 3. Заполнение таблицы из 5 строк и 7 столбцов

группами по гять букв, получается такое шифрованное сообщение:

ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ

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

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

Применим в качестве ключа, например, слово ПЕЛИКАН,

а текст сообщения возьмем из предыдущего примера. На рис. 4 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица - заполнению после перестановки.

П	Е	Л	И	К	А	Н
7	2	5	3	4	1	6
Т	Н	П	В	Е	Г	Л
Е	А	Р	А	Д	О	Н
Р	Т	И	Е	Ь	В	О
М	О	Б	Т	М	П	Ч
И	Р	Ы	С	О	О	Ь

А	Е	И	К	Л	Н	П
1	2	3	4	5	6	7
Г	Н	В	Е	П	Л	Т
О	А	А	Д	Р	Н	Е
В	Т	Е	Ь	И	О	Р
П	О	Т	М	Б	Ч	М
О	Р	С	О	Ы	Ь	И

Ключ

До перестановки После перестановки

Рис. 4. Таблицы, заполненные ключевым словом и текстом сообщения
В верхней строке левой таблицы записан ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе встретились одинаковые буквы, они бы были пронумерованы слева направо. В правой таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа.

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

ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ
Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным.

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

ТЮАЕ ООГМ РЛИП ОЬСВ
Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно)

	4	1	3	2
3	П	Р	И	Л
1	Е	Т	А	Ю
4	В	О	С	Ь
2	М	О	Г	О

	1	2	3	4
3	Р	Л	И	П
1	Т	Ю	А	Е
4	О	Ь	С	В
2	О	О	Г	М,

	1	2	3	4
1	Т	Ю	А	Е
2	О	О	Г	М
3	Р	Л	И	П
4	О	Ь	С	В

Исходная таблица Перестановка столбцов Перестановка строк

Рис. 5. Пример выполнения шифрования методом двойной перестановки

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

• для таблицы 3х3 36 вариантов;

• для таблицы 4х4 576 вариантов;

• для таблицы 5х5 14400 вариантов.

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

следующая страница >>