Шифры замены

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

ЛАБОРАТОРНАЯ РАБОТА 1

Тема: Шифры замены

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

- шифра Цезаря;

- лозунгового шифра;

- полибианского квадрата;

- шифрующей системы Трисемуса;

- шифра Виженера. шифр замена кодирование текст

Цель работы: проанализировать эффективности кодов при блочном кодировании на примере некоторого осмысленного текстового документа.

Порядок выполнения работы

При составлении щифртекста использовать таблицу числовых эквивалентов букв русского алфавита. Мощность алфавита.

Размер шифрующей таблицы: 4х5 (или 4х6) зависит от количества символов в тексте.

Ключ 1: имя или первые 5 букв имени (если его длина больше 5), взятые в обратном порядке.

Ключ 2: первые 4 букв отчества, взятые в обратном порядке.

Содержание отчета

Отчет должен состоять из следующих частей:

* введение

* постановка задачи

* основная часть

* заключение

* приложение

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

Теоретическая часть

Сущность шифрования методом замены заключается в следующем. Пусть шифруются сообщения на русском языке и замене подлежит каждая буква этих сообщений. Тогда, букве А исходного алфавита сопоставляется некоторое множество символов (шифрозамен) МА, Б - МБ, …, Я - МЯ. Шифрозамены выбираются таким образом, чтобы любые два множества (МI и МJ, i ? j) не содержали одинаковых элементов (МI ? МJ = Ш ).

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

Рис.2. Таблица шифрозамен

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

Так как множества МА, МБ, ..., МЯ попарно не пересекаются, то по каждому символу шифрограммы можно однозначно определить, какому множеству он принадлежит, и, следовательно, какую букву открытого сообщения он заменяет. Поэтому расшифрование возможно и открытое сообщение определяется единственным образом.

Метод замены часто реализуется многими пользователями при работе на компьютере. Если по забывчивости не переключить на клавиатуре набор символов с латиницы на кириллицу, то вместо букв русского алфавита при вводе текста будут печататься буквы латинского алфавита («шифрозамены»).

Шифры замены можно разделить на следующие подклассы:

- шифры однозначной замены (моноалфавитные, простые подстановочные). Количество шифрозамен для каждого символа исходного алфавита равно 1 (| Мi | = 1 для одного символа);

- полиграммные шифры. Аналогичен предыдущему за исключением того, что шифрозамене соответствует сразу блок символов исходного сообщения (| Мi | = 1 для блока символов);

- омофонические шифры (однозвучные, многозначной замены). Количество шифрозамен для отдельных символов исходного алфавита больше 1 (| Мi | ? 1 для одного символа);

- полиалфавитные шифры (многоалфавитные). Состоит из нескольких шифров однозначной замены. Выбор варианта алфавита для зашифрования одного символа зависит от особенностей метода шифрования (|Мi | > 1 для одного символа).

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

I. Шифры однозначной замены.

Максимальное количество ключей для любого шифра этого вида не превышает n!, где n - количество символов в алфавите. С увеличением числа n значение n! растет очень быстро (1! = 1, 5! = 120, 10! = 3628800, 15! = 1307674368000). При больших n для приближенного вычисления n! можно воспользоваться формулой Стирлинга

(3)

Шифр Цезаря. Данный шифр был придуман Гаем Юлием Цезарем и использовался им в своей переписке (1 век до н.э.). Применительно к русскому языку суть его состоит в следующем. Выписывается исходный алфавит (А, Б, ..., Я), затем под ним выписывается тот же алфавит, но с циклическим сдвигом на 3 буквы влево.

Рис.3. Таблица шифрозамен для шифра Цезаря

При зашифровке буква А заменяется буквой Г, Б - на Д и т. д. Так, например, исходное сообщение «АБРАМОВ» после шифрования будет выглядеть «ГДУГПСЕ». Получатель сообщения «ГДУГПСЕ» ищет эти буквы в нижней строке и по буквам над ними восстанавливает исходное сообщение «АБРАМОВ».

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

Лозунговый шифр. Для данного шифра построение таблицы шифрозамен основано на лозунге (ключе) - легко запоминаемом слове. Вторая строка таблицы шифрозамен заполняется сначала словом-лозунгом (причем повторяющиеся буквы отбрасываются), а затем остальными буквами, не вошедшие в слово-лозунг, в алфавитном порядке. Например, если выбрано слово-лозунг «ДЯДИНА», то таблица имеет следующий вид.

Рис.4. Таблица шифрозамен для лозунгового шифра

При шифровании исходного сообщения «АБРАМОВ» по приведенному выше ключу шифрограмма будет выглядеть «ДЯПДКМИ».

В качестве лозунга рекомендуется выбирать фразу, в которой содержаться конечные буквы алфавита. В общем случае, количество вариантов нижней строки (применительно к русскому языку) составляет 33! (? 1035).

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

Шифруемая буква заменяется на координаты квадрата (строка-столбец), в котором она записана. Например, если исходное сообщение «АБРАМОВ», то шифрограмма - «11 12 36 11 32 34 13». В Древней Греции сообщения передавались с помощью оптического телеграфа (с помощью факелов). Для каждой буквы сообщения в начале поднималось количество факелов, соответствующее номеру строки буквы, а затем номеру столбца.

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

Рис.5. Таблица шифрозамен для Рис.6. Таблица шифрозамен

полибианского квадрата для шифра Трисемуса

Каждая буква открытого сообщения заменяется буквой, расположенной под ней в том же столбце. Если буква находится в последней строке таблицы, то для ее шифрования берут самую верхнюю букву столбца. Например, исходное сообщение «АБРАМОВ», зашифрованное - «ИЙЪИХШК».

Одним из существенных недостатков шифров однозначной замены является их легкаявскрываемость. При вскрытии шифрограмм используются различные приемы, которые даже при отсутствии мощных вычислительных средств позволяют добиться положительного результата. Один из таких приемов базируется на том, что в шифрограммах остается информация о частоте встречаемости букв исходного текста. Если в открытом сообщении часто встречается какая-либо буква, то в шифрованном сообщении также часто будет встречаться соответствующий ей символ. Еще в 1412 году Шихаба ал-Калкашанди в своем труде «Субх ал-Ааша» привел таблицу частоты появления арабских букв в тексте на основе анализа текста Корана. Для разных языков мира существуют подобные таблицы. Так, например, для русского языка такая таблица выглядит следующим образом [7].

Таблица 1. Вероятности появления букв русского языка в текстах*

*) В таблице приведены оценки вероятностей появления букв русского языка и пробела, полученные на основе анализа научно-технических и художественных текстов общим объемом более 1000000 символов.

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

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

II. Полиграммные шифры.

Полиграммные шифры замены - шифры, которые шифруют сразу группы (блоки) символов.

Шифр Playfair (англ. «Честная игра»). Был изобретен в 1854 г. Чарльзом Уитстоном, но назван именем лорда ЛайонаПлейфера, который внедрил данный шифр в государственные службы Великобритании. Он использовался англичанами в Первой мировой войне. Шифр предусматривает шифрование пар символов (биграмм). Таким образом, этот шифр более устойчив к взлому по сравнению с шифром простой замены, так как затрудняется частотный анализ. Он может быть проведен, но не для 26 возможных символов (латинский алфавит), а для 26 х 26 = 676 возможных биграмм. Анализ частоты биграмм возможен, но является значительно более трудным и требует намного большего объема зашифрованного текста.

Для шифрования сообщения необходимо разбить его на биграммы (группы из двух символов), при этом, если в биграмме встретятся два одинаковых символа, то между ними добавляется заранее оговоренный вспомогательный символ (в оригинале - X, для русского алфавита - Я). Например, «зашифрованное сообщение» становится «за ши фров ан но есоЯ об ще ни еЯ». Для формирования ключевой таблицы выбирается лозунг и далее она заполняется по правилам шифрующей системы Трисемуса. Например, лозунг «ДЯДИНА»

Рис.7. Ключевая таблица для шифра Playfair

Затем, руководствуясь следующими правилами, выполняется зашифровывание пар символов исходного текста:

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

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

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

Пример шифрования.

- биграмма «за» формирует прямоугольник - заменяется на «жб»;

- биграмма «ши» находятся в одном столбце - заменяется на «юе»;

- биграмма «фр» находятся в одной строке - заменяется на «хс»;

- биграмма «ов» формирует прямоугольник - заменяется на «йж»;

- биграмма «ан» находятся в одной строке - заменяется на «ба»;

- биграмма «но» формирует прямоугольник - заменяется на «ам»;

- биграмма «ес» формирует прямоугольник - заменяется на «гт»;

- биграмма «оя» формирует прямоугольник - заменяется на «ка»;

- биграмма «об» формирует прямоугольник - заменяется на «па»;

- биграмма «ще» формирует прямоугольник - заменяется на «шё»;

- биграмма «ни» формирует прямоугольник - заменяется на «ан»;

- биграмма «ея» формирует прямоугольник - заменяется на «ги».

Шифрограмма - «жбюехсйж ба амгт ка па шё ан ги».

Для расшифровки необходимо использовать инверсию этих правил, откидывая символы Я (или Х), если они не несут смысла в исходном сообщении.

III. Омофонические шифры.

Другое направление повышения стойкости шифров замены состоит в том, чтобы каждое множество шифрообозначений Мi содержало более одного элемента. При использовании такого шифра одну и ту же букву (если она встречается несколько раз в сообщении) заменяют на разные шифрозамены из Мi. Это позволяет скрыть истинную частоту встречаемости букв открытого сообщения.

Система омофонов. В 1401 г. Симеоне де Крема стал использовать таблицы омофонов для сокрытия частоты появления гласных букв в тексте при помощи более чем одной шифрозамены. Такие шифры позже стали называться шифрами многозначной замены или омофонами1. Они получили развитие в XV веке. В книге «Трактат о шифрах» Леона Баттисты Альберти (итальянский ученый, архитектор, теоретик искусства, секретарь папы Климентия XII), опубликованной в 1466 г., приводится описание шифра замены, в котором каждой букве ставится в соответствие несколько эквивалентов, число которых пропорционально частоте встречаемости буквы в открытом тексте.

Книжный шифр. Заметным вкладом греческого ученого Энея Тактика в криптографию является предложенный им так называемый книжный шифр, описанный в сочинении «Об обороне укреплённых мест». Эней предложил прокалывать малозаметные дырки в книге или в другом документе над буквами секретного сообщения. Интересно отметить, что в первой мировой войне германские шпионы использовали аналогичный шифр, заменив дырки на точки, наносимые симпатическими черниламина буквы газетного текста.

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

IV. Полиалфавитные шифры.

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

Диск Альберти. В «Трактате о шифрах» Альберти приводит также первое точное описание многоалфавитного шифра на основе шифровального диска.

Рис.9. Диск Альберти

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

Таблица Трисемуса. Одним из шифров, придуманных немецким аббатом Трисемусом, стал многоалфавитный шифр, основанный на так называемой «таблице Трисемуса» - таблице со стороной равнойn, где n - количество символов в алфавите. В первой строке матрицы записываются буквы в порядке их очередности в алфавите, во второй - та же последовательность букв, но с циклическим сдвигом на одну позицию влево, в третьей - с циклическим сдвигом на две позиции влево и т.д. (см. рис. 10).

Здесь первая строка является одновременно и строкой букв открытого текста. Первая буква текста шифруется по первой строке, вторая буква по второй и так далее после использования последней строки вновь возвращаются к первой. Так сообщение «АБРАМОВ» приобретет вид «АВТГРУИ».

Система шифрования Виженера. В 1586 г. французский дипломат БлезВиженер представил перед комиссией Генриха III описание простого, но довольно стойкого шифра, в основе которого лежит таблица Трисемуса.

Перед шифрованием выбирается ключ из символов алфавита. Сама процедура шифрования заключается в следующем. По i-ому символу открытого сообщения в первой строке определяется столбец, а по i-ому символу ключа в крайнем левом столбце - строка. На пересечении строки и столбца будет находиться i-ый символ, помещаемый в шифрограмму. Если длина ключа меньше сообщения, то он используется повторно. Например, исходное сообщение «АБРАМОВ», ключ - «ДЯДИНА», шифрограмма - «ДАФИЩОЖ».

Справедливости ради, следует отметить, что авторство данного шифра принадлежит итальянцу Джованни Батиста Беллазо, который описал его в 1553 г. История «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания». Беллазо предложил называть секретное слово или фразу паролем (ит. password; фр. parole - слово).

Рис.10. Таблица Трисемуса

1Омофоны (греч. homos - одинаковый и phone - звук) - слова, которые звучат одинаково, но пишутся по-разному и имеют разное значение.

Размещено на Allbest.ru