Шифр подстано́вки — это метод шифрования, в котором элементы исходного открытого текста заменяются зашифрованным текстом в соответствии с некоторым правилом. Элементами текста могут быть отдельные символы (самый распространённый случай), пары букв, тройки букв, комбинирование этих случаев и так далее. В классической криптографии различают четыре типа шифра подстановки: Одноалфавитный шифр подстановки (например, шифр простой замены, шифр Цезаря) — шифр, при котором каждый символ открытого текста заменяется на некоторый, фиксированный при данном ключе символ того же алфавита. Однозвучный шифр подстановки (например, книжный шифр) похож на одноалфавитный, за исключением того, что символ открытого текста может быть заменён одним из нескольких возможных символов. Полиграммный шифр подстановки заменяет не один символ, а целую группу. Пример: шифр Плейфера. Полиалфавитный шифр подстановки состоит из нескольких шифров простой замены. Примеры: шифр Виженера, шифр Бофора, одноразовый блокнот. В качестве альтернативы шифрам подстановки можно рассматривать перестановочные шифры. В них, элементы текста переставляются в ином от исходного порядке, а сами элементы остаются неизменными. Напротив, в шифрах подстановки, элементы текста не меняют свою последовательность, а изменяются сами.
История
Использование шифров подстановки берет свое начало в Месопотамии. С целью сокрытия информации о рецепте производства глазури для гончарных изделий автор заменял часть слов на цифры и клинописные знаки. Римский император Гай Юлий Цезарь при написании секретных сообщений смещал каждую букву алфавита на 3 позиции. Данный вид шифров подстановки впоследствии назвали его именем, шифр Цезаря. Другой не менее известный шифр античности, Атбаш, применялся в Библии для создания скрытых посланий. Каждая буква слова заменялась её зеркальным отражением в алфавите .
Одним из первых шифровальных устройств принято считать линейку Энея, при использовании которой длинная нить продевалась через прорезь, а затем через проделанные в линейке отверстия. Рядом с отверстиями располагались соответствующие им буквы. На нити завязывался узелок в месте прохождения её через отверстие. Таким образом осуществлялась замена текста послания на последовательность расстояний между узелками. Данное устройство было изобретено древнегреческим полководцем Энеем Тактиком в IV веке до н. э.
С началом использования частотного анализа для вскрытия моноалфавитных шифров в IX веке, появилась необходимость в изменении частотности появления символов обычного текста. С этой целью стал применяться однозвучный шифр подстановки, сутью которого было сопоставление нескольких заменяющих символов одной букве пропорционально частотности появление этой буквы в различных текстах. Секретарь антипапы Клемёнтия VII Габриель де Лавинда в XV веке впервые использует омофоны для обеспечения приблизительно одинаковой частотности гласных букв. Спустя 65 лет Леон Баттиста Альберти подробно описывает однозвучный шифр подстановки в своей книге «Трактат о шифрах». Основной проблемой распространения омофонической замены была необходимость использования расширенного алфавита для зашифровки сообщений.
Этого недостатка были лишены полиалфавитные шифры, первый из которых был описан немецким монахом Иоганном Тритемием. Согласно методу, описанному в его трактате «Полиграфия» очередная буква заменялась символом из собственного шифралфавита, при этом каждый следующий алфавит получался из предыдущего с помощью сдвига на одну букву. Особенную популярность получил полиалфавитный шифр, описанный Блезом де Виженером в 1585 году. В качестве ключа к шифру использовалось произвольное слово. Соответствующий данному слову набор шифралфавитов определялся из таблицы Виженера.
В 1854 году английским физиком Чарльзом Уитстоном публикуется полиграммный шифр, впоследствии названный именем лорда Лайона Плейфера. Данный шифр осуществляет замену пар букв (биграмм) на одиночные символы, что значительно увеличивает его криптостойкость к частотному анализу.
С появлением ЭВМ полиалфавитные и полиграммные шифры отошли на второй план, а на смену им пришли новые более надежные блочные шифры.
Шифры простой замены
В шифрах простой замены замена производится только над одним-единственным символом. Для наглядной демонстрации шифра простой замены достаточно выписать под заданным алфавитом тот же алфавит, но в другом порядке или, например, со смещением. Записанный таким образом алфавит называют алфавитом замены.
Примеры шифров простой замены
Атбаш
Шифр простой замены, использованный для еврейского алфавита и получивший оттуда своё название. Шифрование происходит заменой первой буквы алфавита на последнюю, второй на предпоследнюю (алеф (первая буква) заменяется на тав (последнюю), бет (вторая) заменяется на шин (предпоследняя); из этих сочетаний шифр и получил своё название). Шифр Атбаш для английского алфавита:
Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Алфавит замены: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
Шифр Цезаря
Шифр Цезаря — один из древнейших шифров. При шифровании каждая буква заменяется другой, отстоящей от нее в алфавите на фиксированное число позиций. Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки. Естественным развитием шифра Цезаря стал шифр Виженера. Шифрование с использованием ключа :
Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Алфавит замены: E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
Современным примером шифра Цезаря является ROT13. Он сдвигает каждый символ английского алфавита на 13 позиций. Используется в интернет-форумах, как средство для сокрытия спойлеров, основных мыслей, решений загадок и оскорбительных материалов от случайного взгляда.
Шифр с использованием кодового слова Шифр с использованием кодового слова является одним из самых простых как в реализации, так и в расшифровывании. Идея заключается в том, что выбирается кодовое слово, которое пишется впереди, затем выписываются остальные буквы алфавита в своем порядке. Шифр с использованием кодового слова WORD.
Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Алфавит замены: W O R D A B C E F G H I J K L M N P Q S T U V X Y Z
Как мы видим, при использовании короткого кодового слова мы получаем очень и очень простую замену. Мы можем использовать слово с повторяющимися буквами в качестве кодового слова, но только в том случае, если уберём из кодового слова лишние буквы, иначе это приведёт к неоднозначности расшифровки, то есть двум различным буквам исходного алфавита будет соответствовать одна и та же буква шифрованного текста.
Метод записи зашифрованных текстов По традиции, зашифрованный текст пишут блоками (другое название «группы») по 5 символов, не учитывая пунктуацию и пробелы. Это помогает избежать ошибок при передаче шифрованного сообщения и позволяет скрыть границы слов в исходном тексте. Блок содержит 6 символов, так как раньше их было удобно передавать по телеграфу.
Безопасность шифров простой замены Главный недостаток этого метода шифрования — это то, что последние буквы алфавита (которые имеют низкие коэффициенты при частотном анализе) имеют тенденцию оставаться в конце. Более защищённый способ построить алфавит замены состоит в том, чтобы выполнить колоночное перемещение (перемещение столбцов) в алфавите, используя ключевое слово, но это нечасто делается.
Несмотря на то, что число возможных ключей является очень большим (26! = 288.4), этот вид шифра может быть легко взломанным. При условии, что сообщение имеет достаточную длину (см. ниже), криптоаналитик может предположить значения некоторых самых распространённых букв исходя из анализа частотного распределения символов в зашифрованном тексте. Это позволяет формировать отдельные слова, которые могут быть предварительно использованы, для последующего получения более полного решения (см. частотный анализ). Согласно расстоянию уникальности английского языка 27.6 букв от зашифрованного текста должно быть достаточно, чтобы взломать шифр простой замены. На практике обычно достаточно около 50 символов для взлома, хотя некоторые шифротексты могут быть взломаны и с меньшим количеством символов, если найдены какие-либо нестандартные структуры. Но при равномерном распределении символов в тексте могут потребоваться куда более длинные шифротексты для взлома.
расстояние уникальности — термин, используемый в криптографии, обращающейся к длине оригинального шифротекста, которого должно быть достаточно для взлома шифра.
Омофоническая замена
Ранние попытки увеличить сложность частотного анализа шифротекстов состояли в том, чтобы замаскировать реальные частотности символов обычного текста с помощью омофонии. В этих шифрах буквы исходного алфавита соответствуют более чем одному символу из алфавита замены. Обычно символам исходного текста с наивысшей частотностью дают большее количество эквивалентов, чем более редким символам. Таким образом, распределение частотностей становится более равномерным, сильно затрудняя частотный анализ.
С тех пор, как для алфавита замены стало требоваться больше чем 26 символов, появилась необходимость в расширенных алфавитах. Одним из самых простых решений является замена алфавита на цифры. Другой метод состоит из простых изменений существующего алфавита: прописные буквы, строчные буквы, перевернутые символы и т. д. Более художественными, хотя не обязательно более надежными, будут омофонические шифры, которые используют полностью изобретённые (вымышленные) алфавиты (как например, шифр в книге «Золотой жук» Э. По, или «Рукопись Войнича». Впрочем, эти шифры не являются примерами омофонической замены).
Примеры омофонических шифров
Номенклатор Шифр, изданный средневековым чиновником, представляющий собой маленькую книгу с большими омофоническими таблицами замены. Первоначально шифр был ограничен именами важных людей того времени, отсюда и последовало название шифра; в более поздних изданиях этот шифр дополнился большим количеством распространённых слов и географических названий. На основе этого «номенклатора» был составлен Великий Шифр Россиньоля, использовавшийся королём Франции Людовиком XIV. И действительно, после того как этот шифр перестал использоваться, французские архивы были закрытыми ещё в течение нескольких сотен лет.
«Номенклаторы» были стандартом для дипломатической корреспонденции, шпионских сообщений и являлись основным средством антиполитической конспирации с начала XV до конца XVIII века. Хотя правительственные криптоаналитики систематически взламывали «номенклаторы» к середине шестнадцатого столетия. Обычным выходом из этой ситуации было увеличение объёмов таблиц. Но к концу восемнадцатого столетия, когда система начала выходить из употребления, некоторые «номенклаторы» имели до 50 000 символов. Однако не все «номенклаторы» были сломаны.
Великий Шифр Россиньоля
Антуан Россиньоль и его сын Бонавентур Россиньоль изобрели Великий Шифр, который использовал 587 различных чисел. Шифр был настолько силен, что в течение многих столетий никто не мог взломать его, пока это не сделал офицер французской армии, криптограф Этьен Базери в 1893 году на примере одного письма военного министра Лувуа королю Людовику XIV. Он понял, что каждое число кодировало не одну букву, а целый слог. Базери предположил, что последовательность 124-22-125-46-345 кодирует слово «les ennemis» (враги), и, отталкиваясь от этой информации, смог расшифровать весь текст.
Книжный шифр