Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
Простейшим представителем другого направления шифрования -перестановочных алгоритмов может служить перестановочный алгоритм шифрования с шагом в к букв. В рамках этого алгоритма буквами исходного текста поочередно заполняются клетки прямоугольника из к строк в порядке, указанном ниже на примере шифрования исходного текста "встреча у букиниста" (значение к принято здесь равным трем).
в р а - к и а с е - б и с -т ч у у н т -
и в качестве шифрограммы принимается последовательность букв "вра — киасе — бис — тчуунт -". Иными словами, используется правило "запись по столбцам - шифрограмма по строкам". Расшифровка шифрограммы осуществляется в обратном порядке "запись по строкам — исходный текст по столбцам", а именно, буквами шифрограммы поочередно заполняются клетки прямоугольника из т = М/к столбцов (М - число букв в шифрограмме), а исходный текст формируется поочередным чтением букв по столбцам.
Описанный только что алгоритм шифрования не обладает сколько-нибудь серьезным уровнем криптостойкости. Но здесь налицо основной принцип работы перестановочных алгоритмов - перестановка позиций, которые занимают буквы в исходных текстах. Путем усложнения правил перестановки в ряде случаев удается добиться достаточно высокого уровня крипстойкости. И тогда для взламывания криптосистемы приходится прибегать к более мощным средствам, например, с исполь-
73
ГЛАВА 5зованием значений вероятностей встречаемости различных пар букв, триад букв и т.д., с учетом даже позиций этих пар, триад в словах естественных языков.
Не вдаваясь в подробности анализа различных хитроумных решений в каждой конкретной криптосистеме, где могут сочетаться подстановочный и перестановочный принципы шифрования, отметим лишь, что основным инструментом их взлома является использование тех или иных проявлений избыточности текстов естественных языков.
В рассматриваемом смысле наиболее продуктивными оказались алгоритмы шифрования, которые в наибольшей степени защищены от средств взлома, базирующихся на использовании избыточности естественных языков. В этом плане большой научно-практический интерес представляют алгоритмы, являющиеся различными вариантами реализации криптосистемы, предложенной аббатом из Вюрцбурга Иоганном Тритемиусом [3]. Сущность системы заключается в использовании в качестве секретного ключа некоторой конечной последовательности букв. При работе с этой криптосистемой все символы, которые могут встречаться в передаваемых сообщениях, предварительно произвольным образом нумеруются. В частности, порядок нумерации может совпадать с алфавитным порядком. И тогда, если условиться, что, как и выше, в передаваемых сообщениях могут встречаться лишь 33 различных символа, то нумерация букв будет такой же, как и в рассмотренных выше примерах (V = 0, 'б' = 1, ...). Далее выбирается произвольная конечная последовательность букв в качестве секретного ключа шифрования. Обычно, чтобы легко было запоминать, в качестве таковой берется некоторый осмысленный текст или слово. Примем, например, что в качестве секретного ключа выбрано слово "аура", а передаче подлежит тот же текст "встреча у букиниста". Для шифрования этого текста под ним записывается секретный ключ, как это показано ниже:
ветреча-у-букиниста аурааурааурааурааур
и далее осуществляется побуквенное сложение этих строк по модулю 33. Например, результат сложения буквы 'в' с буквой 'а' определится как
('в' = 2) + ('а' = 0) = 2mod(33) = 2 = 'в'.
Аналогично определяется результат сложения
('ч' = 23) + ('у' = 19) = 42mod(33) = 9 = 'й\
Поступая таким образом, в качестве шифрограммы получим следующую последовательность букв:
вгбрейр-утсукыэисдр Чтобы отсюда восстановить исходный текст, получатель информации
74записывает под шифрограммой секретный ключ, как это показано ниже:
вгбрейр-утсукыэисдр
аурааурааурааурааур
и затем осуществляет побуквенное вычитание этих строк по модулю 33. Например, результат вычитания буквы 'р' от буквы 'б' определится как
('б' = 1) - ('р' = 16) = -15mod(33) = 18 = 'т .
Поступая таким образом, в качестве разницы двух строк получим исходный текст "встреча у букиниста".
Легко заметить,что взламывание алгоритма Тритемиуса путем использования избыточности языка значительно сложнее по сравнению с подстановочными и перестановочными алгоритмами. Вместе с тем, сам факт многократного повторения секретного ключа вкупе с тем, что секретный ключ имеет собственную избыточность, в ряде случаев приводит к тому, что алгоритм Тритемиуса в рассмотренном только что варианте его реализации все же удается взламывать. Чтобы полностью (или почти полностью) избавить криптограммы от избыточности, присущей естественным языкам, К. Шеннон рекомендует конфиденциальные тексты предварительно архивировать с помощью какого-либо из эффективных алгоритмов сжатия текстов (Фано, Хаффмэн, Шеннон) и уже архивированный текст подвергать шифрованию но схеме Тритемиуса, используя в качестве секретного ключа случайную последовательность символов алфавита данного естественного языка. При этом практически исключаются случаи взламывания, но такой алгоритм вряд ли можно признать приемлемым с практической точки зрения, поскольку при его использовании требуется посылать адресату не только шифрограмму, но и секретный ключ - случайную последовательность букв, длина которой в данном случае оказывается равной длине архивированного текста [3, 11].