Шифр замены, одноалфавитные и многоалфавитные замены.

Одноалфавитный шифр замены, или моноалфавитный шифр, -это

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

символом шифротекста. Уязвимы к частотному анализу. Пример - шифр цезаря.

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

Примеры шифров замены: Шифрующие таблицы Трисемуса.

Способ задания: создается таблица (для русского языка 4х8). Ключевое слово вписывалось в таблицу по строкам, а повторяющиеся буквы отбрасывались, далее таблица до заполнялась не вошедшими в неё буквами алфавита по порядку.

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

Пример: ключ "весной тепло"

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

Сообщение " Встречайте " даёт шифровку " лбзщаямжза "

Такой шифр называется монограммным.

Шифр Плейфера:

Способ задания: создается таблица (для русского языка 4х8). Ключевое слово вписывалось в таблицу по строкам, а повторяющиеся буквы отбрасывались, далее таблица до заполнялась не вошедшими в неё буквами алфавита по порядку.

Правила шифрования:

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

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

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

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

Пример:

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

ве->сн; вл->лк; вб->лс.

Такой шифр называется биграммным.

К полиалфавитным можно отнести Таблицы Виженера.

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

Человек, посылающий сообщение, записывает ключевое слово («ЛЕМОН») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

ЛЕМОНЛЕМОН

Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.

Исходный текст: АВТОМОБИЛЬ

Ключ: ЛЕМОНЛЕМОН

Зашифрованный текст: ЛЗЮЬЩЩЖФЩЙ

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

Если буквы А-Я соответствуют числам 0-31, то шифрование Виженера можно записать в виде формулы:

С_i ≡(P_i + K_i) mod 32

Расшифровка: P_i ≡ (C_i – K_i +32) mod 32.

Вопросы криптоанализа простейших шифров замены.

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

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

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

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

2. Выявление шифробозначений, заменяющих гласные и согласные буквы.

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

Если длина текста достаточно велика, то найденные на этапе 1 частоты окажутся близкими к табулированным значениям частот знаков. Проведенная на этом этапе работа служит основанием для выдвижения гипотез о значениях шифрвеличин, соответ­ствующих данным шифробозначениям. При этом учитывается, что каждая буква имеет группу предпочтительных связей, которые составляют ее наиболее характерную особенность. Как правило, такие гипотезы подтверждаются не полностью. Хорошим критерием при этом является "читаемость" восстанавливаемого открытого текста. Выделение шифробозначений, отвечающих гласным и согласным, основано на характерных свойствах этих букв. Добавим к ним следующие соображения: если шифробозначение часто встречается, равномерно располага­ется по шифртексту, в отдельных местах чередуется через 1, 2 или 3 знака, сочетается сосредними и редкими шифробозначениями, то это дает основания полагать, что такое шифробозначение скрывает гласную букву. Удвоение гласных в открытом тексте происходит реже, чем согласных. Если некоторое шифробозначение признано гласной, то буква, часто сочетающаяся с ней, скорее всего согласная. В открытом тексте чрезвычайно редко встречаются три и более подряд идущие гласные. Четыре и более подряд идущие согласные также редки. Важно учитывать также процентное со­отношение чисел гласных и согласных в открытом тексте.

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

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

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

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

Дата добавления: 2015-12-01