Методические указания к лабораторным работам по курсу «Теория информациии и основы криптографии»

Национальный исследовательский университет
"Высшая школа экономики"

Московский институт электроники и математики

Кафедра кибернетики

Методические указания к лабораторным работам по курсу

«Теория информациии и основы криптографии»

Москва 2012

1.Цель работ.

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

2.Теоретические сведения.

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

Рассмотрим традиционные (классические) методы симметричного шифрования, отличающиеся простотой и наглядностью.

2.1.Табличные шифры перестановки

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

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

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

Пример. Зашифруем сообщение: «ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ» с помощью таблицы 5х7 и ключевого слова «ПЕЛИКАН»:

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

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

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

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

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

Пример магического квадрата и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО:

16	3	2	13	О	И	Р	М
5	10	11	8	Е	О	С	Ю
9	6	7	12	В	Т	А	Ь
4	15	14	1	Л	Г	О	П

Шифртекст, получаемый при считывании содержим правой таблицы по строкам, имеет вполне загадочный вид:

ОИРМ ЕОСЮ ВТАЬ ЛГОП

Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3х3 (если не учитывать его повороты). Количество магических квадратов 4х4 составляет уже 880, а количество магических квадратов 5х5 - около 250000.

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

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

Шифр Кардано. К шифрам перестановки относится и Шифр Кардано. В середине 16 века итальянским математиком Кардано была выдвинута идея использования части самого передаваемого открытого текста в качестве ключа и новый способ шифрования, получивший название «решетка Кардано».Для ее изготовления берется квадратный кусок картона в котором по специальным правилам прорезаются «окна». При шифровании решетка накладывалась на лист бумаги и открытый текст вписывался в окна. Затем решетка поворачивалась на 90 градусов и вновь вписывался текст, всего 4 раза.

Главное требование к «решетке Кардано» - при всех поворотах окна не должны попадать на одно и то же место бумаги.

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

Как математик, Кардано сумел вычислить количество квадратов-решеток (ключей) заданного размера NxN. Если N - четное число, то это количество равно . При N=10 оно имеет порядок десять в пятнадцатой степени.

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

2.2.Табличные шифры замены.

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

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

Шифрующие таблицы Трисемуса. В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием "Полиграфия". В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово. В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку.

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

Пример. Для русского алфавита шифрующая таблица может иметь размер 4x8. Выберем в качестве ключа слово БАНДЕРОЛЬ. Шифрующая таблица примет вид:

Б	А	Н	Д	Е	Р	О	Л
Ь	В	Г	Ж	3	И	И	К
М	П	С	Т	У	Ф	X	Ц
Ч	Ш	Щ	Ы	Ъ	Э	Ю	Я

При шифровании с помощью этой таблицы

сообщения В Ы Л Е Т А Е М П Я Т О Г О

получаем шифртекст П Д К З Ы В З Ч Ш Л Ы Й С Й

Шифр Уинстона. В 1854 г. англичанин Чарльз Уитстон разработал новый метод шифрования биграммами, который называют "двойным квадратом". Свое название этот шифр получил по аналогии с полибианским квадратом. В отличие от полибианского шифр "двойной квадрат" использует сразу две таблицы, размещенные по одной горизонтали, а шифрование идет биграммами (парами), как в шифре Плейфейра. Эти не столь сложные модификации привели к появлению на свет качественно новой криптографической системы ручного шифрования. Шифр "двойной квадрат" оказался очень надежным и удобным и применялся Германией даже в годы второй мировой войны.

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

Если обе буквы биграммы сообщения лежат в одной строке, то и буквы шифртекста берут из этой же строки. Первую букву биграммы шифртекста берут из левой таблицы в столбце, соответствующем второй букве биграммы сообщения. Вторая же буква биграммы шифртекста берется из правой таблицы в столбце, соответствующем первой букве биграммы сообщения.

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

Ж	Щ	Н	Ю	Р	И	Ч	Г	Я	Т
И	Т	Ь	Ц	Б	1	Ж	Ь	М	О
Я	М	Е	.	С	3	Ю	Р	В	Щ
В	Ы	П	Ч		Ц	:	П	Е	Л
:	Д	У	О	К	Ъ	А	Н	.	X
3	Э	Ф	Г	Ш	Э	К	С	Ш	Д
X	А	1	Л	Ъ	Б	Ф	У	Ы

Рис. Две таблицы со случайно расположенными символами русского алфавита для шифра "двойной квадрат

Предположим, что шифруется биграмма исходного текста ИЛ. Буква И находится в столбце 1 и строке 2 левой таблицы. Буква Л находится в столбце 5 и строке 4 правой таблицы. Это означает, что прямоугольник образован строками 2 и 4, а также столбцами 1 левой таблицы и 5 правой таблицы. Следовательно, в биграмму шифртекста входят буква О, расположенная в столбце 5 и строке 2 правой таблицы, и буква В, расположенная в столбце 1 и строке 4 левой таблицы, т.е. получаем биграмму шифртекста ОВ.

Если обе буквы биграммы сообщения лежат в одной строке, например ТО, то биграмма сообщения ТО превращается в биграмму шифртекста ЖБ. Аналогичным образом шифруются все биграммы сообщения:

Сообщение ПР ИЛ ЕТ АЮ _Ш ЕС ТО ГО

Шифртекст ПЕ ОВ ЩН ФМ ЕШ РФ БЖ ДЦ

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