 |
|
Лабораторная работа 3
Многоалфавитные подстановки
В целях маскирования естественной частотной статистики исходного языка применяется многоалфавитная(полиалфавитная) подстановка, которая также бывает нескольких видов. В многоалфавитных подстановках для замены символов исходного текста используется не один, а несколько алфавитов. Обычно алфавиты для замены образованы из символов исходного алфавита, записанных в другом порядке.
Рассмотрим шифр Гронсфельда, представляющий собой модификацию шифра Цезаря. В качестве ключа используется последовательность цифр произвольной фиксированной длины. Каждая цифра этой последовательности записывается под одним символом открытого текста, причем если длина ключа меньше длины текста, ключ циклически повторяется. Шифротекст получают примерно так же, как в шифре Цезаря, но отсчитывают не третью букву по алфавиту (как в шифре Цезаря), а ту, которая смещена по алфавиту на соответствующую цифру ключа.
Зашифруем слово «информатика» ключом «123»:
М = ИНФОРМАТИКА
12312312312 К= 123
М' = ЙПЧПТПБОЛЛВ
Данный шифр (описанный Жюль Верном в романе «Жангада») относится к семейству многоалфавитных шифров (или шифров сложной замены). Мы видим, что одна и та же буква «и» превращается то в «й», то в «л» в зависимости от того, какая цифра ключа использовалась для шифрования, а буква «а» может быть зашифрована как «б» или «в». Более того, буква «п», встречающаяся в зашифрованном тексте три раза, каждый раз означает разные буквы.
Таким образом, хотя статистические особенности исходного текста и будут проявляться с цикличностью n, где n — длина ключа, при достаточно большом n (десять и более цифр, при том, что противнику эта длина неизвестна), таблицы частот дают гораздо большую погрешность, не говоря уже о том, что проверять предположения, восстанавливая фрагменты по смыслу, становится практически невозможным.
Главная слабость шифра Гронсфельда в том, что каждая буква зашифрованного текста отстоит от «своей» буквы открытого текста не более, чем на девять позиций в алфавите, а это дает противнику возможность легко проверять различные предположения.
Эта проблема исчезает в модификации шифра Гронсфельда, где в качестве ключа выступает не цифровая, а буквенная последовательность. Порядковый номер буквы открытого текста складывается с записанной под ней буквой ключа и получается порядковый номер буквы зашифрованного текста (который берется по модулю мощности алфавита, т.е. Г + Э = 4 + 31 = 35; 35 mod 33 = 2 = Б; Г + Э = Б):
Пример 1.
М = ИНФОРМАТИКА
ВАСЯВАСЯВАС К = ВАСЯ
М' = ЛОЖКУНТСЛЛТ
Механизм «сложения» исходного текста с ключом, представляющим собой цифровую или буквенную поседовательность, который мы наблюдали в шифрах Цезаря и Гронсфельда, используется и во многих других шифрах. Особенностью таких шифров является возможность восстановления ключа, если известны открытые и зашифрованный текст. Это делается операцией, обратной «сложению» — «вычитанием»[1].
Пример 2.
Открытый текст: "ЗАМЕНА".
Ключ: "КЛЮЧ"
| З | А | М | Е | Н | А |
| К | Л | Ю | Ч | К | Л |
С0 = 8 + 11 (mod 33) = 19 → Т
С1 = 1 + 12 (mod 33) = 13 → М
С2 = 13+ 31 (mod ЗЗ) = 11 → К
С3 = 6 + 24 (mod 33) = 30 → Э
С4 = 14+11 (mod 33) = 25 → Ш
С5 = 1 +12 (mod 33) = 13 → М.
Шифротекст: "ТМКЭШМ".
Примером многоалфавитной подстановки может служить также схема, основанная на использовании таблицы Вижинера. Этот метод, известный уже в XVI веке, был описан французом Блезом Вижинером в "Трактате о шифрах", вышедшем в 1585 году.
Для шифрования текста выбирают ключ, представляющий собой некоторое слово или набор символов исходного алфавита. В процессе шифрования под каждой буквой шифруемого текста записывают буквы ключа (ключ повторяют требуемое число раз), затем шифруемый текст по таблице шифрования (приложение 4) заменяют буквами, расположенными на пересечениях линий, соединяющих буквы текста первой строки таблицы и буквы ключа, находящейся под ней. Каждый из символов ключа используется для шифрования одного символа исходного сообщения. После использования всех символов ключа, они повторяются в том же порядке.
Например, под первой буквой исходного текста "М" записана буква "В" ключа. В таблице кодирования находим столбец, начинающийся с "М" и строку, начинающуюся с "В". На их пересечении располагается буква "О". Она и будет первым символом зашифрованного сообщения. Следующая буква исходного сообщения – "Е", символ ключа – тоже "Е". Находим пересечение строки, начинающейся с "Е", и столбца, начинающегося с "Е". Это будет буква "Л" – второй символ зашифрованного сообщения.
Рассмотрим на примере процесс расшифрования сообщения по методу Вижинера. Пусть имеется зашифрованное с помощью ключа ВЕСНА сообщение КЕКХТВОЭЦОТССВИЛ (пробелы при шифровании пропущены). Расшифровка текста выполняется в следующей последовательности:
· над буквами шифрованного текста сверху последовательно записывают буквы ключа, повторяя ключ требуемое число раз;
· в строке подматрицы таблицы Вижинера для каждой буквы ключа отыскивается буква, соответствующая знаку шифрованного текста. Находящаяся над ней буква первой строки и будет знаком расшифрованного текста;
Раскрыть шифр Вижинера, тем же способом, что и шифр одноалфавитной замены, невозможно, так как одни и те же символы открытого текста могут быть заменены различными символами зашифрованного текста. С другой стороны, различные буквы открытого текста могут быть заменены одинаковыми знаками зашифрованного текста.
Если ключ шифрования состоит из одного символа, то при шифровании будет использоваться одна строка таблицы Вижинера, следовательно, в этом случае мы получим моноалфавитную подстановку, а именно шифр Цезаря.
С целью повышения надежности шифрования текста можно использовать подряд два или более зашифрования по методу Вижинера с разными ключами (составной шифр Вижинера).
На практике кроме метода Вижинера использовались также различные модификации этого метода. Например, шифр Вижинера с перемешанным один раз алфавитом. В этом случае для расшифрования сообщения получателю необходимо кроме ключа знать порядок следования символов в таблице шифрования.
Еще одним примером метода многоалфавитной подстановки являетсяшифр с бегущим ключом или книжный шифр. В этом методе один текст используется в качестве ключа для шифрования другого текста. В эпоху "докомпьютерной" криптографии в качестве ключа для шифра с бегущим ключом выбирали какую-нибудь достаточно толстую книгу; от этого и произошло второе название этого шифра. Периодом в таком методе шифрования будет длина выбранного в качестве ключа произведения.
Методы многоалфавитной подстановки значительно труднее поддаются "ручному" криптоанализу. Для вскрытия методов многоалфавитной замены разработаны специальные, достаточно сложные алгоритмы. С использованием компьютера вскрытие метода многоалфавитной подстановки возможно достаточно быстро благодаря высокой скорости проводимых операций и расчетов.
Это интересно! Долгое время шифры Виженера и их модификации считались невзламываемыми. Политические деятели Франции XVI — XVII веков постоянно применяли эти шифры в своей переписке. Примечателен в этом отношении следующий абзац из мемуаров активного политического деятеля Фронды, парижского архиепископа кардинала де Реца, середина XVII века (Кардинал де Рец. Мемуары. М.: Наука, 1997. С. 581-582. (Литературные памятники)): "Мы с принцессой Пфальцской пользовались шифром, который прозвали непроницаемым, уверенные, что его нельзя прочесть, не зная слова, служащего к нему ключом. Мы полагались на него настолько безоглядно, что с его помощью не обинуясь сообщали друг другу самые важные и сокровенные тайны, доверяя их простым гонцам. Принц де Конде, у которого на службе состоял один из самых искусных в мире отгадчиков тайнописи — его, помнится, звали Мартен, - шесть недель продержал у себя в Брюсселе этот шифр и вернул мне его, признав, что Мартен подтвердил: прочитать его нельзя. " Лишь в 1863 году прусским офицером Ф.В. Касисским был найден простой способ поиска ключа для шифра Виженера.
Задание:
Задание 1. Используя ключ 314, расшифруйте сообщение, зашифрованное с помощью шифра Гронсфельда. Шифровка выглядит так: ФПИСЬИОССАХИЛФИУСС
(Ответ: «СОВЕРШЕННО СЕКРЕТНО»)
Задание 2. Выполните упражнения № 4, 5(стр.34-36 )