Леонид Черняк – Криптовойна 1933-1945 (страница 13)
Замена и перестановка, два метода шифрования
Почти разнообразие эмпирических приемов традиционной криптографии, использующей алфавитную письменность, в конечном счете сводится всего к двум – к более распространенному методу замены символов и к менее популярному методу перестановки символов. Замена или перестановка и ничего более, к тому же основная идея каждого из них тривиально проста. В первом случае в открытом тексте символы того алфавита, на котором он написан, заменяются символами из другого алфавита, составленного из тех же символов, но иначе упорядоченных. Во втором случае шифрование сводится к перестановке местами символов внутри открытого текста. Помимо алфавитных есть шифры для языков с иероглифической письменностью, таких как японский и китайский, есть стеганография и еще некоторые экзотические шифры. Известны и другие подходы к шифрованию, не связанные с заменой и перестановкой. Они не связаны с содержанием этой книги, поэтому вот лишь названия некоторых: «Миланский ключ», Номенклатор, Великий Шифр Россиньоля, Книжный шифр. За каждым шифром кроется увлекательная история, они хорошо и подробно описаны.
Алгоритмы шифрования заменой и перестановкой относятся к симметричным (symmetric-key algorithm), где и шифрование, и дешифрование выполняется одним и тем же ключом. Впрочем, иного прежде и не мыслилось, неологизм «симметричное шифрование» возник как реакция на появление современного асимметричного шифрования, для противопоставления старого новому. Невольно вспоминается господин Журден из «Мещанина во дворянстве» Мольера, открывший для себя: «Честное слово, я и не подозревал, что вот уже более сорока лет говорю прозой. Большое вам спасибо, что сказали». Такие термины лингвисты называют ретронимами, они служат для обозначения чего-то старого, ранее известного от нового схожего. Общий ключ симметричного алгоритма должен сохраняться в тайне обеими сторонами. Ключ шифрования выбирается сторонами до начала обмена сообщениями.
Достоинство метода замены в возможности его механизации без особых сложностей, поэтому он стал основой для всех шифромашин, созданных в первой половине прошлого века, о них мы будем долго говорить ниже.
Однако для полноты картины все же следует упомянуть и о методе перестановки. Шифрование им напоминает перетасовку карт, но не случайную, а следуя заданному правилу – ключу. В процессе шифрования перестановкой в открытом тексте единичные символы, а возможно и пары или тройки по заданному ключу меняются местами. Шифрование перестановкой не слишком популярно, но его первое применение можно обнаружить в простейших устройствах, созданных в IV веке до н. э. полководцем Энеем Тактиком, в них шифрование осуществлялось прошивкой шнурком диска или линейки с отверстиями, эти инструменты вошли в историю под его именем диска Энея или линейки Энея.
Из древности известны примеры шифрования перестановкой – анаграммы. Анаграмма, по-гречески «перестановка букв». Известны анаграммы Галилея и Ньютона, которыми великие ученые шифровали свои открытия. Возможны шифры двух вариантов – с простой или со сложной перестановкой. Простую перестановку еще называют маршрутной, потому что в процессе шифрования символы открытого текста записывают не последовательно, а разбрасываются по прямоугольной матрице в заданном порядке, называемом маршрутом, маршрут – это ключ, получатель, обладая им, можно пройти по матрице тем же маршрутом, что и отправитель и восстановить открытый текст. Сложная перестановка предполагает какой-то более изощренный метод маршрутизации. Из сложных наибольшую известность получил шифр Rail fence cipher, названный так, потому что маршрут напоминает ограждение из продольных брусьев, какими огораживают пастбища.
Метод перестановки механизировать сложно, приспособлений, упрощающих работы с ним, совсем мало, но они известны с древности. Один из них скитала, она представляет собой цилиндр, на который наматывается кожаная полоска примерно так, как на рукоять теннисной ракетки. Шифрование состоит в том, что вдоль оси цилиндра построчно поперек полосок записывался текст, затем полоска разматывалась и порядок букв терялся. Ключом является диаметр цилиндра, у получающего должен быть такой же цилиндр, как у отправителя. Широко известно как скиталу использовали спартанцы в войне с Афинами. В качестве инструмента криптоаналитика для расшифровки сообщения, подготовленного посредством скиталы, можно использовать конус и подбором найти диаметр.
Еще одно приспособление для упрощения перестановки называют поворотной решеткой, его придумал в 1550 году итальянский математик Джероламо Кардано. Эта решетка многократно описана в популярных книгах для юношества, например, у Перельмана и Гарднера. В моем детстве их вырезали из бумаги в клеточку и использовали в качестве развлечения при переписке с одноклассниками на скучных уроках.
Метод замены гораздо популярнее перестановки. Знакомый всем тривиальный пример шифрования заменой описан в знаменитом рассказе «Пляшущие человечки» Конана Дойла, здесь ключ есть ничто иное, как правило, по которому осуществляется подстановка символов из одного алфавита или символами другого алфавита.
Шифрования заменой отличается двумя фундаментальными свойствами, которые сохраняются вне зависимости от конкретной реализации, будь то тривиальной ручной или сложной машинный:
Сохранение идентичности. Трансформацию открытого текста в зашифрованный заменой можно сравнить с пластической операцией, ее действие ограничено изменением внешнего вида текста, но оно не затрагивает его идентичность. В данном случае термин идентичность, естественно, понимается в узком специфическим смысле, всего лишь как набор тех или иных признаков, присущих данному тексту, делающий его уникальным, отличным от остальных текстов. Такими отличительными признаками могут быть часто употребляемые слова, сокращения, установившаяся структура всего текста или его фрагментов. При замене символа на символ текст меняет свое внешнее представление, но то, что мы назвали идентичностью, остается неизменным. Если применить к нему те или иные аналитические приемы, то эти признаки идентичности можно выявить и использовать для дешифровки. «Врожденным дефектом» шифра замены издавна пользовались криптоаналитики, но только Алан Тьюринг и его коллеги смогли систематизировать поиск этих признаков, они назвали их crib, словом чрезвычайно многозначным, один их его смыслов «подсказка». Хотя идея использования подсказок не нова, но только дешифровщики в Блетчли-Парке смогли поставить эту работу на «промышленные рельсы» с использованием криптоаналитических машин.
Симметричность ключа. Симметрию понимают как правило попарного соответствия, сохраняющееся при преобразовании текст в обоих направлениях – от открытого к зашифрованному и в обратном. Симметрия способствовала успеху криптомашин, сама криптомашина является ключом, поэтому одна и та же машина может быть использована как при передаче сообщений, так и при приеме. В приложении к криптомашинам используется термин скремблирование. Скремблер (от scramble – шифровать, перемешивать) – это устройство или алгоритм, выполняющие обратимое преобразование. Обратимый процесс скремблирования позволяет восстановить исходное сообщение, применив обратный алгоритм.
Моноалфавитные шифры
Шифры замены делятся на два класса – на моноалфавитные и на полиалфавитные. В простых моноалфавитных шифрах каждому символу открытого текста ставится в соответствие всего один единственный фиксированный символ из другого, иначе упорядоченного алфавита, поэтому, независимо от того, где и сколько раз некий символ встречается в открытом тексте, в зашифрованном тексте ему будет соответствовать всегда один и тот же заменяющий его символ. Существует несколько алгоритмов для выбора заменяющего символа из шифрующего алфавита. Например, аддитивный шифр Цезаря, в нем ключом дистанция, отделяющая заменяющий символ от исходного. В латинском алфавите она в пределах от 1 до 26 и сохраняется постоянной для всех букв открытого текста. Позиция замещающего символа определяется суммированием. Название пошло от Светония, в «Жизни двенадцати цезарей» он написал, что Гай Юлий Цезарь использовал этот шифр для военных сообщений. Во времена Цезаря шифр был безопасен, если учесть, что большинство его врагов были неграмотны.
В более сложном мультипликативном шифре для вычисления позиции заменяющего символа в шифрующем алфавите используется не сложение, как в шифре Цезаря, а умножение. Есть еще аффинный шифр, в данном случае аффинный значит средний или соседний, он объединяет свойства аддитивного и мультипликативного шифров. Еще, наконец, полиграммный шифр подстановки, где заменяется не один символ, а целая группа.
Наши современники широко узнали о многоалфавитном шифре Атбаш из книги Дэна Брауна «Код да Винчи» и фильму по ней. Его название происходит от четырех букв алфавита древнееврейского языка – первой, последней, второй и предпоследней, то есть Алеф, Тау, Бет и Шин. Скорее всего Атбаш был изобретен иудейской сектой повстанцев ессеев, разрабатывавших методы тайнописи. Однако есть и иные мнения относительно происхождение Атбаша, не связанные с ессеями. Независимо от того, кто прав, его в IV веке унаследовала христианская секта гностиков, далее они передали его катарам, христианскому движению, распространившемуся в западной Европе в XII и XIII веках, затем Атбаш перенял орден Тамплиеров. Атбаш использовался почти 2000 лет, с 500 года до н. э. до того, как орден Тамплиеров перестал существовать в XIV веке.