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

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

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

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

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

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

«Информационная беопасность и защита информации»

Москва 2005

Цель работ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p: М® М

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

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

π: х → π(х).

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

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

YHQL YLGL YLFL

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

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

Е _k: x → (x + 3) mod m, " x Î Z_m,

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

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

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

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

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

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

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

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

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

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

Входной символ х₀х₁х₂х₃х₄х₅х₆х₇х₈х₉

Алфавит подстановки B₀B₁B₂B₃B₀B₁B₂B₃ B₀B₁

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

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

К = {(π ₀, π ₁, …, π _n-1), π _i Î P }, 1£ n < ¥

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

(х _0, х _1, х _{2, …,} х_n-1) в п -грамму (y _0, y _1, y _{2, …,} y_n‑1) шифртекста в соответствии с формулой:

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

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

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

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

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

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

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

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

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

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

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

Сообщение

Ключ

Шифртекст

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

π =(π ₀, π ₁, …, π _r-1),

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

открытый текст х =(х₀ _, х₁ _, х₂ _{, …,} х_n-1) в шифртекст y = (y₀ _, y₁ _, y₂ _{, …,} y_n-1)

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

y = (y₀ _, y₁ _, y₂ _{, …,} y_n-1) = (π₀(х₀), π₁(х₁), …, π _n-1 (х_n-1)), где π _i =π₍ _i _mod _r ₎.

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

Поиск по сайту