Метод простой подстановки

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

Пример 1. Пусть исходным является русский алфавит. Составим таблицу соответствия, используя служебные символы, знаки препинания и знаки арифметических действий из таблицы ASCII- кодов в качестве кодового алфавита:

Тогда сообщение ИНФОРМАТИКА будет закодировано как }=_”~|!:}]!.

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

Можно рассчитать частоту каждого символа s – f_S:

f_S = m_S / M,

где m_S – количество символов S в сообщениях.

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

Пример 2. Пусть есть закодированное сообщение из примера 1: }=_”~|!:}]!. Известно, что до кодирования оно было составлено из букв русского алфавита. Требуется декодировать его, используя в качестве представительной выборки закодированных русскоязычных текстов настоящее учебное пособие, предварительно выполнив все замены русских букв символами из таблицы соответствия примера 1.

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

Так определим, что общее число символов М в учебном пособии на момент подготовки данного примера составляет 275979.

Определяем, сколько раз встречаются интересующие нас символы из закодированного сообщения - m_s:

Это позволяет рассчитать частоты символов f_s по приведенной выше формуле:

Сопоставим полученные данные с приведенной выше таблицей частот символов. Наиболее близкие по значению символы для полученных частот показаны ниже:

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

Если построить все возможные сочетания символов из указанных множеств, там будет, в частности и сочетание вида И Н * О Р * А Т И * А, где знак * означает любой символ из соответствующего, определенного выше, множества исходных символов (в случае * декодирование, очевидно, выполнено неверно). Если предъявить полученную строку человеку или автомату, способному распознать русское слово, зашифрованное сообщение можно считать декодированным.

Очевидно, декодирование также возможно при известной таблице соответствия.

Метод Вижинера

Разрушить статистические зависимости в закодированных сообщениях и тем самым повысить надежность кодирования можно с помощью метода Вижинера. Алгоритм применения этого метода приведен ниже:

1) символы исходного алфавита нумеруются, начиная с нуля, например:

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Получают таблицу соответствия;

2) задаются ключом кодирования – словом в исходном алфавите, например, АСУ;

3) выписывают сообщение, подлежащее кодированию, например, пусть это будет сообщение ИНФОРМАТИКА, и выполняют следующие шаги:

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

И Н Ф О Р М А Т И К А

8 12 19 13 15 11 0 17 8 9 0

б) под сообщением выписывают ключевое слово, а под символами ключа выписывают их порядковые номера из таблицы соответствия:

А С У А С У А С У А С

0 16 18 0 16 18 0 16 18 0 16

в) порядковые номера символов складываются по модулю, равному числу символов исходного алфавита (в нашем случае – 31):

8 28 6 13 0 29 0 2 26 9 16

Сложение по модулю (обозначается ⊕) выполняется без переноса единицы переноса в старший разряд. Так мы получили при сложении по модулю 31, например, чисел 17 и 16 (сумма равна 33, что на 2 превышает модуль 31) значение 2;

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

И Ь Ж О А Ъ А В Ю К С.

Очевидно, что статистика не поможет декодировать это сообщение, поскольку повторяются совсем не те символы, что в исходном сообщении.

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

Пример 1. Декодировать сообщение И Ь Ж О А Ъ А В Ю К С, задавшись ключом АСУ и зная таблицу соответствия.

Решение:

а) выписываем под закодированным сообщением порядковые номера символов из таблицы соответствия (см. выше):

И Ь Ж О А Ъ А В Ю К С

8 28 6 13 0 29 0 2 26 9 16

б) выписываем под сообщением ключ с порядковыми номерами символов:

А С У А С У А С У А С

0 16 18 0 16 18 0 16 18 0 16

в) вычитаем с учетом модуля 31 из чисел в закодированном сообщении числа для ключа:

8 12 19 13 15 11 0 17 8 9 0

г) преобразуем числа в символы по таблице соответствия:

И Н Ф О Р М А Т И К А

При декодировании возникла сложность в получении кодов символов Т, Ф, Р. В самом деле, при вычитании из 2 числа 16 получалось –14. Тогда к 2 прибавили модуль 31, получили 33 и уже из 33 вычли 16. Получили 17 – порядковый номер символа Т. Аналогично поступили и с символами Ф и Р.

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