ЛАБОРАТОРНАЯ РАБОТА № 1. ШИФРЫ ЗАМЕНЫ

Сущность шифрования методом замены заключается в следующем [2]. Пусть шифруются сообщения на русском языке и замене подлежит каждая буква этих сообщений. Тогда, для буквы А исходного алфавита строится некоторое множество символов (шифрозамен) М_А, для Б – М_Б, …, для Я – М_Я. Шифрозамены выбираютсятаким образом, чтобы любые два множества (М_I и М_J, i ¹ j) не содержали одинаковых элементов (М_I Ç М_J = Æ).

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

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

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

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

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

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

- шифры многозначной замены (многоалфавитные). Количество шифрозамен для отдельных символов исходного алфавита больше 1 (½М_i½≥1).

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

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

. (3)

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

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

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

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

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

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

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

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

Каждая буква открытого сообщения заменяется буквой, расположенной ниже в том же столбце. Если буква находится на последней строке таблицы, то для ее шифрования берут самую верхнюю букву столбца. Например, если исходное сообщение «АБРАМОВ», то шифрограмма – «УФВУЭЬТ».

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

Шифрование выполняется как и в предыдущем шифре (исходное сообщение «АБРАМОВ», зашифрованное – «ИЙЪИХШК»).

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

Таблица 1

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

Буква (символ)	Вероят- ность	Буква	Вероят- ность	Буква	Вероят- Ность	Буква	Вероят- ность
Пробел	0.146	Р	0.042	Я	0.017	Ж	0.007
О	0.094	Л	0.039	З	0.016	Ш	0.006
Е	0.071	В	0.038	Ы	0.015	Ц, Ю	0.005
А	0.069	К	0.029	Г	0.014	Щ	0.004
И	0.064	М	0.027	Ь, Б	0.013	Ф	0.003
Н	0.057	П	0.026	Ч	0.012	Э	0.002
Т	0.054	Д	0.024	Й	0.010	Ъ	0.001
С	0.046	У	0.023	Х	0.008

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

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

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

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

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

Система омофонов. Число шифрозамен для каждого символа берется пропорциональным вероятности его появления в открытых текстах. Так, если ориентироваться на табл.1, то число шифрозамен для буквы О должно составлять 94, для буквы Е – 71 и т.д. При этом каждая шифрозамена должна состоять из 3 цифр и их общее количество равно 1000. На рис.7 представлен фрагмент таблицы шифрозамен.

№ п/п

Пробел

…

Рис.7. Фрагмент таблицы шифрозамен для системы омофонов

При шифровании символ исходного сообщения заменяется на любую шифрозамену из своего столбца. Если символ встречается повторно, то, как правило, используют разные шифрозамены. Например, исходное сообщение «АБРАМОВ» после шифрования будет выглядеть «357 990 374 678 037 828 175».

Система шифрования Виженера. Шифр описан в 1585 г. французом Блезом де Виженером в «Трактате о шифрах». Этот шифр задается квадратной таблицей, со стороной равной n, где n – количество символов в алфавите. В первой строке матрицы записываются буквы в порядке их очередности в алфавите, во второй – та же последовательность букв, но с циклическим сдвигом на одну позицию влево, в третьей – с циклическим сдвигом на две позиции влево и т.д.

…

⁶О

…

¹Д

⁷Ж

…

³Ф

…

⁴И

…

⁵Щ

…

²А

…

Рис.8. Фрагмент таблицы шифрозамен для системы шифрования Виженера

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

Например, исходное сообщение «АБРАМОВ», ключ – «ДЯДИНА», шифрограмма – «ДАФИЩОЖ» (числами на рис.8 показаны символы, попавшие в шифрограмму).

⇐ Предыдущая 123 4 5 6 7 Следующая ⇒