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

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

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

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

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

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

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

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

Москва 2005

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

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

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

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

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

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

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

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

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

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

П

Е

Л

И

К

А

Н

А

Е

И

К

Л

Н

П

7

2

5

3

4

1

6

1

2

3

4

5

6

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 раза.

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

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

Как математик, Кардано сумел вычислить количество квадратов-решеток (ключей) заданного размера N xN. Если 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 левой таблицы, т.е. получаем биграмму шифртекста ОВ.

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

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

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

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

2.3. Шифры простой замены

В шифре простой замены каждый символ исходного текста заменяется символами и того же алфавита одинаково на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.

Под подстановкой множества М мы подразу­меваем взаимно однозначное отображение этого множества на себя

p: М® М

т. е. сопоставление p каждому элементу m из М некоторого образа p(m ), причем каждый элемент из М является образом в точности одного элемента.

Ключом шифра является подстановка π в алфавите Zm, определяющая правило замены при шифровании буквы х открытого текста (представленной в виде целого числа, определяемого ее порядковым номером в алфавите) на букву π(х ) шифртекста:

π: х → π(х ).

Подстановка π является взаимно однозначным отображением из Zm на Zm .

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). При шифровании исходного текста каждая буква заменя­лась на другую букву того же алфавита путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использо­вал шифр замены при смещении К = 3. Например, послание Цезаря VENI VIDI VICI (в переводе на русский означает „Пришел, Увидел, Победил“), на­правленное его другу Аминтию после победы над понтийским ца­рем Фарнаком, сыном Митридата, выглядело бы в зашифрован­ном виде так:

YHQL YLGL YLFL

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

Рассматривая алфавит криптосистемы как множество целых Zm, мы можем записать функцию шифрования Еk для k =3 в шифре Цезаря как

Еk: x → (x + 3) mod m, „x ÎZm ,

где x — числовой код буквы открытого текста; x + 3 -числовой код соответствующей буквы шифртекста.

Шифр Цезаря с ключевым словом. Этот шифр также являет­ся одноалфавитным. Особенностью его является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки.

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

Пример. правило подстановки для k =3 и ключа «информация»:

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

Шифрованный текст: эюинформацябвгдежзйклоп...

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

2.4. Шифры сложной замены

Шифры сложной замены называют многоалфавитными, так как для шифрования каждого символа исходного сообщения применяют свой шифр простой замены. Многоалфавитная подстановка последова­тельно и циклически меняет используемые алфавиты. При r -алфавитной подстановке символ х0 исходного сообщения за­ме­няется символом из алфавита Во, символ х1 символом из алфави­та B1, и так далее, символ хr-1 заменяется символом из алфавита Br-1, символ хr заменяется символом снова из алфавита Во, и т.д.

Общая схема многоалфавитной подстановки (r =4):

Входной символ х0 х1 х2 х3 х4 х5 х6 х7 х8 х9

Алфавит подстановки B0 B1 B2 B3 B0 B1 B2 B3 B0 B1

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

Для многоалфавитной подстановки Ек ключ подстановки К представляет собой последовательность подстановок из некоторого множества P :

К = {(π0, π1, …, πn-1 ), πi Î P }, 1£ n < ¥

В случае блочного шифра эта подстановка шифрует п -грамму (блок) открытого текста

(х 0,х 1,х 2, …, хn-1 ) в п -грамму (y 0,y 1,y 2, …, yn‑1 ) шифртекста в соответствии с формулой:

yi = πi (х i ), 0 £ i < n, п = 1, 2, 3,… .

При n ®¥ мы приближаемся к теоретически стойкой одноразовой системе шифрования.

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

Диск Альберти. Многоалфавитные шифры замены предложил и ввел в практику криптографии Леон Батист Альберти, который также был известным архитектором и теоретиком искусства. Он же впервые выдвинул идею повторного шифрования, которая в виде идеи многократного шифрования лежит в основе всех современных шифров с секретным ключом. Кроме шифра многоалфа­витной замены, Альберти также подробно описал устройства для его реализации. Диск Альберти представляет собой систему из внешнего неподвижного и внутреннего подвижного дисков, на которые нанесены символы алфавита и цифры. На внешнем в алфавитном порядке, на внутреннем в произвольном. Ключом шифрования являются порядок букв на внутреннем диске и начальное положение внутреннего диска относительно внешнего. После шифрования слова внутренний диск сдвигался на один шаг. Количество алфавитов r в нем равно числу символов на диске.

Шифр Цезаря многоалфавитный. В отличие от простого шифра Цезаря, многоалфавит­ный или система шифрования Цезаря образуется множеством одноалфавитных подстановок, определяемых функциями шифрования Еk для различных значений ключа k, причем 0 £ k < m, где m -основание алфавита.

В соответствии с этой системой буква x ÎZm открытого текста преобразуется в букву y ÎZm шифртекста согласно следующему правилу:

Еk: y = (x + k ) mod m,

где x — числовой код буквы открытого текста; y -числовой код соответствующей буквы шифртекста.

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

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

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

Сообщение

В

О

С

Т

О

Ч

Н

Ы

Й

Э

К

С

П

Р

Е

С

С

Ключ

2

7

1

8

2

7

1

8

2

7

1

8

2

7

1

8

2

Шифртекст

Д

Х

Т

Ь

Р

Ю

О

Г

Л

Д

Л

Щ

С

Ч

Ж

Щ

У

Чтобы зашифровать первую букву сообщения В, исполь­зуя первую цифру ключа 2, нужно отсчитать вторую по порядку букву от В, получается первая буква шифртекста Д.

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

Система шифрования Вижинера впервые была опубликована в 1586 г. и является одной из старейших и наиболее известных многоалфавитных систем. Свое название она получила по имени француз­ского дипломата XVI века Блеза Вижинера.

Этот шифр многоалфавитной замены можно описать таблицей шифрования, называемой таблицей (квадратом) Вижинера. Размер таблицы Вижинера равен длине алфавита. Первая строка имеет цифровой ключ «0» и заполняется всеми символами по алфавиту, вторая имеет цифровой ключ «1» и заполняется теми же символами, сдвинутыми вправо на один символ по кругу, и далее. k ‑ая имеет цифровой ключ «к-1 » и заполняется теми же символами, сдвинутыми вправо на (к-1 ) символ по кругу.

Приведем фрагмент таблицы Вижинера для русского алфавита.

а

б

в

г

д

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

а

б

в

г

д

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

1

б

в

г

д

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

ы

2

в

г

д

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

ы

ъ

3

г

д

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

ы

ъ

э

4

д

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

ы

ъ

э

ю

5

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

ы

ъ

э

ю

я

6

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ь

ы

ъ

э

ю

я

а

Таблица Вижинера используется для зашифрования и расшифрования. Она имеет два входа:

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

— крайний левый столбец ключа.

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

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

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

Выпишем исходное сообщение в строку и запишем под ним ключе­вое слово с повторением. В третью строку выпишем шифртекст.

Сообщение П Р И Л Е Т А Ю С Е Д Ь М О Г О

Ключ АМ Б Р О З И Я А М Б Р О З И Я

Шифртекст П Ъ Й Ы УЩИ Э С С Е К Ь Х Л Н

Шифры Вижинера с коротким периодическим ключом используются и в наши дни в системах шифрования, от которых не требуется высокая криптостойкость. Так, например они использо­вались в программе-архиваторе ARJ в программе Word версии 6.

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

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

π =( π0, π1, …, πr-1 ),

Функция шифрования Вижинера Еπ: х → y преобразует

открытый текст х =(х ,х 1 ,х 2 , …, хn-1 ) в шифртекст y = (y ,y 1 ,y 2 , …, yn-1 )

согласно правилу:

y = (y ,y 1 ,y 2 , …, yn-1 ) = (π0(х0 ), π1 (х1 ), …, πn-1 (х n-1 )), где πi =π(i mod r ) .

2.5. Шифры, основанные на аналитических преобразованиях.

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

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

Определим в такой системе преобразование Еa,b: Zm → Zm :

Еa,b (x ) = ax+b mod m ,

где в качестве ключа k =(a, b )используется пара целых чисел, удовлетворяющих условиям

0 £ a,b < m, и НОД(а,m )=1.

В данном преобразовании буква, соответствующая числу x в открытом тексте, заменяется на букву шифртекста, соответствующую числовому значению y =(ax +b ) mod m (например m =26 в латинском алфавите).

Следует заметить, что преобразование Еa,b (x ) является взаимно однозначным отображением на множестве Zm только в том случае, если НОД(а ,m )=1, т.е. а и m должны быть взаимно простыми числами.

Это условие взаимной простоты необходимо для обеспечения инъективнос­ти отображения Еa,b (x ) = ax+b mod m. Если оно не выполняется, возможна ситуация, когда две разные буквы отображаются в одну (возникает неоднозначность расшифрования), а некоторые буквы отсутствуют в шифртексте, так как никакие буквы в них не отображаются.

Достоинством аффинной системы является удобное управление ключами — ключи шифрования и расшифрования представляются в компактной форме в виде пары чисел (а, b ). По сравнению с простой системой шифрования Цезаря, количество возможных ключей значительно больше и алфавитный порядок слов при шифровании не сохраняется.

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

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

Алгебраический метод, обобщающий аффинную подста­новку Цезаря для шифрования n -грамм, был сформулирован Лестером С.Хиллом .

Шифрование ведется путем выполнения умножения вектора на матрицу. Матрица является ключом шифрования. Открытый текст разбивается на n -граммы — блоки длинойn, равной размерности матрицы и каждая n -грамма х = (х 0,х 1,х 2, …, хn-1 ) рассматривается как вектор.

Ключевая матрица Т размером п хп видаТ ={ti ,j }, i,j = 0,1, … ,n - 1 задает отображение, являющееся линейным преобразованием:

Т: Zm,n → Zm,n, Т: х → у; у=Тх, где .

Для расшифрования шифртекста необходимо выполнить обратное преобразование:

х = Т -1у .

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

Т Т -1 = Т -1Т = I, где I — единичная матрица.

Доказано, что для этого необходимо, чтобы определитель матрицы det Т, не делился на любое простое р, которое делитm .

2.6. Шифры гаммирования.

Гамма шифра — это псевдослучайная последовательность, выработанная по заданному алгоритму для шифрования открытых данных и дешифрования зашифрованных данных. Под гаммированием понимают процесс наложения по оп­ределенному закону гаммы шифра на открытые данные, он может выполняться как в режиме блочного, так и потоковового шифрования. Он является типичным и наиболее про­стым примером реализации абсолютно стойкого шифра (при использовании бесконечного ключап =¥).

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

Следует отметить, что при блочном шифровании открытые данные разбивают на блоки Т0(i ) одинаковой длины, обычно по 64 бита. Гамма шифра вырабатывается в виде последовательности блоков γi аналогичной длины.

Уравнение зашифрования можно записать в виде

ci = γi Å mi, i =1,…,M ,

где ci — i -ый блок шифртекста; γi — i -ый блок гаммы шифра; mi -i -ый блок открытого текста; М — количество блоков открытого текста.

Процесс дешифрования сводится к повторной генерации гаммы шифра и наложению этой гаммы на зашифрованные дан­ные. Уравнение расшифрования имеет вид

mi = γi Å ci, i =1,…,M ,

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

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

γi+1 = (а γi + b ) modm ,

где а и b — константы, γ0 — исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений а и b. Необходимо выбирать числа a и b такие, чтобы период был максимальным. Как показано Д. Кнутом, это возможно тогда и только тогда, когда b — нечетное и взаимно простое с m, и величина а mod 4 = 1. По другим рекомендациям b — взаимно простое с m, и а нечетное.

Шифр Вернама является частным случаем шифрования гаммированием для двоичного алфавита (при значении модуля m =2).

Конкретная версия этого шифра, предложенная в 1926 году сотрудни­ком фирмы AT&T Вернамом, использует двоичное представление символов исходного текста. Каждая буква исходного текста в алфавите, расширенном некоторыми дополнительными знаками, сначала переводилась с использованием телеграфного кода Бодо в пятибитовый символ. То есть алфавит криптосистемы представляет собой множество Z32 всех пятибитовых последовательностей.

Ключ k =(k 0,k 1 ,...,k к-1 ), где “ki Î Z32 записывался на бумажной ленте. При шифровании ключ добавлялся к исходному тексту суммированием по модулю 2.

В общем случае система шифрования Вернама осуществляет побитовое сложение п -битового от­крытого текста и п -битового ключа:

yi = xi Åki, i=1,…,n

Здесь х1 х2 … xп — открытый текст, k1 k2 … kп — ключ, y1 y2 … yп — ши­фрованный текст.

Расшифрование состоит в сложении по модулю 2 симво­лов у шифртекста с той же последовательностью ключей k :

y Å k =x Å k Å k = x .

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

2.7. Анализ стойкости криптосистем

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

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

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

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

— количество всех возможных ключей;

— среднее время, необходимое для кpиптоанализа.

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

Для этого рекомендуется использовать один из двух простейших мето­дов вскрытия шифра

1. Статистическую атаку.

2. Силовую атаку.

Рассмотрим в чем они состоят.

Криптоаналитическая статистическая атака

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

— определяется число появлений каждой буквы в шифртексте.

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

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

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

Силовая атака

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

Алгоритм криптоанализа заключается в следующем: определяется множество всех возможных ключей шифрования для данной криптосистемы и для каждого ключа выполняются шаги:

— Дешифрование известного шифртекста на этом ключе;

— Анализ «осмысленности» полученного предполагаемого открытого текста, например путем поиска соответствующих слов в словаре возможных сообщений;

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

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

3. Задания

3.1. Лабораторная работа №1

Тема: симметричные криптосистемы.

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

1. Разработать алгоритмы шифрования и дешифрования блока (потока) открытого текста заданной длины из алфавита Zn на заданном ключе с помощью метода, указанного в варианте(Если это позволяет алгоритм, длину блока взять кратной 8 бит).

2. Определить алфавит криптосистемы (открытого текста и шифртекста). Если алфавит не задан в варианте, выбрать его самостоятельно, так, чтобы он включал в себя символы используемого в примере открытого текста. Например, русский, английский, ASCII. Поставить символам исходного алфавита в соответствие символы из алфавита Zn (n – основание алфавита).

3. Написать программу генерации случайных ключей шифра, оценить размерность ключевого пространства.

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

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

6. Провести тестирование программ

— на коротких тестовых примерах.

— на текстах в несколько страниц

3.2. Лабораторная работа №2

Тема: криптоанализ симметричных криптосистем.

Провести эксперимент по определению практической стойкости, алгоритма, разработанного в лабораторной работе №1.

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

— анализа статистических свойств шифртекста (частот появления букв).

— силовую атаку (полный перебор ключей).

— другие (если есть более эффективные)

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

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

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

Построить графики зависимости времени криптоанализа от параметров ал­горитма шифрования (длины или других параметров ключа, размера шифр­текста или др., в зависимости от алгоритмов шифрования и криптоанализа).

В результате эксперимента определить параметры алгоритма шифрования (размер передаваемого текста, размер и характеристи­ки ключа, объем ключевого пространства и другие параметры алгоритма шифрования), необходимые для практической криптостойкости разработанного в лабораторной работе №1 алгоритма ширования.

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

4. Варианты

Основные варианты:

Вариант 1. Шифрующие таблицы с числовым ключом

Вариант 2. Шифр Гронсфельда с ключевым словом

Вариант 3. Алгоритм, реализующий идею «диска Альберти» для русского алфавита

Вариант 4. Шифр Цезаря с ключевым словом

Вариант 5. Шифрующие таблицы с перестановкой по ключу –размеру таблицы.

Вариант 6. Полибианский квадрат для русского алфавита.

Вариант 7. Шифр Гронсфельда с числовым ключом

Вариант 8. Шифр Кардано без поворотов.

Вариант 9. Шифр Плейфера

Вариант 10. Шифрующие таблицы с ключевым словом

Вариант 11. Шифр Цезаря многоалфавитный

Вариант 12. Шифр гаммирования с линейным конгруэнтным генератором ключей

Вариант 13. Аффинная система подстановок Цезаря

Вариант 14. Шифр Вижинера с числовым ключом

Вариант 15. Шифр Хилла для 3-грамм

Вариант 16. Шифрующие таблицы Трисемуса

Вариант 17. Шифр Вернама.

Вариант 18. Алгоритм, реализующий идею «диска Альберти» для английского алфавита

Вариант 19. Шифр Вижинера с ключевым словом

Вариант 20. Шифр гаммирования с генератором ключей на основе датчика случайных чисел

Вариант 21. Полибианский квадрат для английского алфавита.

Вариант 22. Шифрующие таблицы с двойной перестановкой по ключевому слову.

Вариант 23. Шифр Уинстона

Вариант 24. Шифрующие таблицы с двойной перестановкой по числовому ключу.

Дополнительные варианты ( повышенной сложности ) :

Вариант 25. Магические квадраты

Вариант 26. Шифр Кардано с поворотами.

5. Приложение .

Приложение 1: Таблица вероятностей букв в русских текстах.

буква	пробел	о	е илиё	а	и	н	т	с	р	в	л
вер-ть	0,175	0,090	0,072	0,062	0,062	0,053	0,053	0,045	0,040	0,038	0,035
буква	к	м	д	п	у	я	з	ы	б
вер-ть	0,028	0,026	0,025	0,023	0,021	0,018	0,016	0,016	0,014	0,014	0,013
буква	ъ или ь	г	х	ж	ш	ю	ц	щ	э	ф
вер-ть	0,012	0,010	0,009	0,007	0,006	0,006	0,004	0,003	0,003	0,002

Приложение 2. Таблица вероятностей букв в английских текстах.

буква	пр-л	е	t	а	о	n	i	s	r
вер-ть	0,185	0,097	0,076	0,064	0,062	0,057	0,056	0,052	0,047
буква	h	l	d	с	u	p	f	м	w
вер-ть	0,04	0,031	0,028	0,025	0,018	0,018	0,018	0,017	0,016
буква	y	в	g	v	к	q	x	j	z
вер-ть	0,015	0,013	0,013	0,007	0,039	0,002	0,002	0,001	0,001