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

МИНИСТЕРСТВО

ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

(Технический университет)

Кафедра математического обеспечения систем обработки информации и управления

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

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

Москва 2005

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, заполненную буквами алфавита в случайном порядке.