Криптология: подстановочно-перестановочный шифр и его применение
В Л С
Щ О Ы С И Е Т
Е Н М Н Т Е А
после перестановки
В верхней строке ее записан ключ, а номера под ключом определены по
естественному порядку соответствующих букв ключа в алфавите. Если в ключе
встретились бы одинаковые буквы, они бы нумеровались слева направо.
Получается шифровка: СНЯНН БОЯЕТ ЕООЕЕ ПНЯВЛ СЩОЫС ИЕТЕН МНТЕА. Для
дополнительной скрытности можно повторно шифровать сообщение, которое уже
было зашифровано. Этот способ известен под названием двойная перестановка.
Для этого размер второй таблицы подбирают так, чтобы длины ее строк и
столбцов были другие, чем в первой таблице. Лучше всего, если они будут
взаимно простыми. Кроме того, в первой таблице можно переставлять столбцы,
а во второй строки. Наконец, можно заполнять таблицу зигзагом, змейкой, по
спирали или каким-то другим способом. Такие способы заполнения таблицы если
и не усиливают стойкость шифра, то делают процесс шифрования гораздо более
занимательным.
Кроме одиночных перестановок использовались еще двойные
перестановки столбцов и строк таблицы с сообщением. При этом перестановки
определялись отдельно для столбцов и отдельно для строк. В таблицу
вписывался текст, и переставлялись столбцы, а потом строки. При расшифровке
порядок перестановок был обратный. Насколько просто выполнялось это
шифрование, показывает следующий пример:
2 4 1 3
4 П P И Е
1 3 Ж A Ю
2 Ш Е С
3 Т О Г О
исходная
таблица
1 2 3 4
4 И П Е Р
1 A 3 Ю Ж
2 Е С Ш
3 Г Т О О
перестановка
столбцов
1 2 3 4
1 A 3 Ю Ж
2 Е С Ш
3 Г Т О О
4 И П Е Р
перестановка
строк
Получается шифровка АЗЮЖЕ СШГТООИПЕР. Ключом к этому шифру служат
номера столбцов 2413 и номера строк 4123 исходной таблицы. Число вариантов
двойной перестановки тоже велико: для таблицы 3х3 их 36, для 4х 4 их 576, а
для 5 х 5 их уже 14400. Однако двойная перестановка очень слабый вид шифра,
легко читаемый при любом размере таблицы шифрования.
Выдающимся английским философом и изобретателем Роджером Бэконом,
предвосхитившим многие позднейшие открытия (наиболее значительное из его
изобретений - очки, которые он предложил в 1268 году), был найден состав
черного пороха. Так почему же традиционно считают его изобретателем
Бертольда Шварца, по преданиям казненного императором Венцеславом на
пороховой бочке? Карамзин по этому поводу писал: "Нет сомнения, что и монах
Рогер Бакон за 100 лет до Бертольда Шварца умел составлять порох: ибо ясно
говорит в своем творении de nulitate Magiae о свойстве и силе оного". Дело
в том, что средневековые ученые, сделав открытие, отнюдь не всегда спешили
его опубликовать в письмах коллегам, как это было тогда принято при
отсутствии периодических научных изданий. Нередко ту часть открытия,
которую теперь называют know how, они шифровали анаграммой, переставляя
буквы сообщения по известному только им ключу. Например, названия древней и
современной столиц Японии в русском написании тоже представляют собой
анаграмму: КИОТО - ТОКИО.
В упомянутом труде Бэкона состав пороха был приведен в виде
зашифрованной анаграммы, которую до появления сверхбыстродействующих ЭВМ не
удавалось вскрыть, и слава открытия поэтому приписывалась Шварцу. Гораздо
более сложная проблема возникает с приписываемым Галилео Галилею открытием
спутников Юпитера. Долгое время приведенная им анаграмма читалась так:
"Высочайшую планету двойною наблюдал", но в 1960-х годах с применением
компьютеров при расшифровке был получен иной вариант прочтения: "Привет
вам, близнецы, Марса порождение!" Конечно, открытие Фобоса и Деймоса на
слабеньком телескопе за два с половиной столетия до американца Асафа Холла
- событие мало реальное, но кто знает? Описал же Свифт в "Путешествиях
Гулливера" спутники Марса за полтораста лет до астрономов с поразительной
точностью! Может быть Свифт знал результаты Галилея, которые сейчас
неизвестны? Шифры перестановки чрезвычайно коварны в том смысле, что могут
дать несколько вариантов осмысленного прочтения, если не знать точного
значения ключа.
Какие же шифры применялись еще средневековыми учеными? На известной
гравюре Дюрера "Меланхолия" позади грустящего ангела изображен магический
квадрат, заполненный цифрами. Магическими квадратами называются квадратные
таблицы со вписанными в их клетки последовательными натуральными числами от
1, которые дают в сумме по каждому столбцу, каждой строке и каждой
диагонали одно и то же число. Подобные квадраты широко применялись для
вписывания шифруемого текста по приведенной в них нумерации. Если потом
выписать содержимое таблицы по строкам, то получалась шифровка
перестановкой букв. Считалось, что созданные с их помощью шифровки охраняет
не только ключ, но и магическая сила. Вот пример магического квадрата и его
шифровки:
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1
О И Р Т
З Ш Е Ю
Ж А С
Е Г О П
Полученная из ПРИЕЗЖАЮ ШЕСТОГО, шифровка ОИРТЗШЕЮ ЖАСЕГОП
представляется довольно основательной. На первый взгляд кажется, будто
магических квадратов очень мало. Тем не менее их число очень быстро
возрастает с увеличением размера квадрата. Так, существует лишь один
магический квадрат размером 3 х 3, если не принимать во внимание его
повороты. Магических квадратов 4 х 4 насчитывается уже 880, а число
магических квадратов размером 5 х 5 около 250000. Поэтому магические
квадраты больших размеров могли быть хорошей основой для надежной системы
шифрования того времени, потому что ручной перебор всех вариантов ключа для
этого шифра был немыслим.
Широкое развитие торговли в средние века потребовало специфических
шифров, предельно простых и удобных, которыми могли бы пользоваться купцы
для передачи, например, даты приезда или цены товара. Это были простые
шифры замены цифр на буквы, основанные на ключевом слове. Собственно, это
коды, а не шифры - вспомните обозначение месяцев на банках консервов, но
код, примененный единожды с неизвестной таблицей кодирования, схож по
свойствам с шифром. Торговцы заранее договаривались использовать общее
ключевое слово, буквы которого соответствовали бы цифрам. Например, для
ключа РЕСПУБЛИКА цифра 0 означает букву Р, цифра 1 означает Е, 2 - С, 3-Н и
так далее. Поэтому, получив от корреспондента сообщение, ПРИБЫВАЮ ЕЛРПАС,
они его читали, как ПРИБЫВАЮ 16/03/92. Простота и удобство этой системы
шифрования позволили ей дожить до начала этого века без всяких изменений.
Другой шифр, обычно называемый шифром Гронсфельда, состоит в
модификации шифра Цезаря числовым ключом. Для этого под сообщением пишут
ключ. Если ключ короче сообщения, то его повторяют циклически. Шифровку
получают будто в шифре Цезаря, но отсчитывая необязательно только третью
букву по алфавиту, а ту, которая сдвинута на соответствующую цифру ключа.
Так, применяя в качестве ключа группу из трех начальных цифр числа "пи", а
именно 314, получаем шифровку:
сообщение СОВЕРШЕННО СЕКРЕТНО
ключ 3143143143143143143
шифровка ФПЖИСЬИОССАХИЛФИУСС
Чтобы зашифровать первую букву сообщения С используя первую цифру ключа
3, отсчитывается третья по порядку от С в алфавите буква С-Т-У-Ф и
получается буква шифровки Ф. Разновидность этого шифра была применена в
резидентном англо-русском словаре, составленном студентами МВТУ, и взломка
его доставила слушателям лекций по программированию не меньше удовольствия,
чем разгадывание кроссворда. Шифр Гронсфелвда имеет массу модификаций,
претендующих на его улучшение, от курьезных, вроде записи текста шифровки
буквами другого алфавита, до нешуточных, как двойное шифрование разными
ключами. Кроме этих шифров, зачастую использовался шифр простой замены,
заключающийся в замене каждой буквы сообщения на соответствующую ей букву
шифра. Такой шифр, популярный среди школьников, является простым кодом и
вскрытие его возможно при длине шифровки всего в 20-30 букв, а при длинах
текста свыше 100 символов представляет собой очень простую, но весьма
увлекательную задачу приведенную ниже. А сейчас рассмотрим рождение шифра
сложной замены, шифры сложной замены называют многоалфавитными, так как для
шифрования каждого символа исходного сообщения применяется свой шифр
простой замены. Шифр Гронсфельда тоже многоалфавитный шифр (в нем 10
вариантов замены), который используется по сей день.
Архитекторы и исследователи Италии эпохи Возрождения считают, что один
из самых важных этапов ренессансной архитектуры связан с именем Леона
Батиста Альберти, написавшем десять книг о зодчестве, построившим палаццо
Ручеллаи, церковь Иль Джезу и ряд других замечательных произведений
зодчества средневековой Италии. Будучи теоретиком искусства, он обобщил
опыт гуманистической науки в изучении античного наследия, написав ряд
трактатов: "О статуе", "О живописи", "О зодчестве". С другой стороны,
криптологи всего мира почитают его отцом своей науки. Главным достижением
Альберти в криптологии было изобретение многоалфавитной замены, сделавших
шифровку очень устойчивой к вскрытию. Кроме самого шифра он еще подробно
описал устройства из вращаю
| |  скачать работу |
Криптология: подстановочно-перестановочный шифр и его применение |
