В криптографии шифр замены — это метод шифрования , при котором единицы открытого текста заменяются зашифрованным текстом определенным образом с помощью ключа; «единицами» могут быть отдельные буквы (наиболее распространенные), пары букв, тройки букв, смеси вышеперечисленных и т. д. Получатель расшифровывает текст, выполняя процесс обратной замены для извлечения исходного сообщения.
Шифры замены можно сравнить с шифрами перестановки . В транспозиционном шифре единицы открытого текста переставляются в другом и обычно довольно сложном порядке, но сами единицы остаются неизменными. Напротив, в шифре замены единицы открытого текста сохраняются в той же последовательности в зашифрованном тексте, но сами единицы изменяются.
Существует множество различных типов шифра замены. Если шифр работает с отдельными буквами, его называют шифром простой замены ; шифр, который работает с большими группами букв, называется полиграфическим . Одноалфавитный шифр использует фиксированную замену во всем сообщении, тогда как полиалфавитный шифр использует ряд замен в разных позициях сообщения, где единица открытого текста сопоставляется с одной из нескольких возможностей в зашифрованном тексте и наоборот.
Первое опубликованное описание того, как взломать простые шифры замены, было дано Аль-Кинди в «Рукописи по расшифровке криптографических сообщений», написанной около 850 г. н.э. Описанный им метод теперь известен как частотный анализ .
Замену отдельных букв по отдельности — простую замену — можно продемонстрировать, выписав алфавит в некотором порядке, представляющем замену. Это называется алфавитом замены . Шифралфавит может быть сдвинут или перевернут (создавая шифры Цезаря и Атбаша соответственно) или зашифрован более сложным способом, и в этом случае его называют смешанным алфавитом или ненормальным алфавитом . Традиционно смешанные алфавиты можно создать, сначала выписав ключевое слово, удалив из него повторяющиеся буквы, а затем написав все оставшиеся буквы алфавита в обычном порядке.
Используя эту систему, ключевое слово « зебры » дает нам следующие алфавиты:
Сообщение
сразу бежать. нас обнаружили!
шифрует в
СИАА ZQ LKBA. ВА ЗОА RFPBLUAOAR!
Обычно зашифрованный текст записывается блоками фиксированной длины без знаков препинания и пробелов; это делается для того, чтобы скрыть границы слов от открытого текста и избежать ошибок передачи. Эти блоки называются «группами», и иногда в качестве дополнительной проверки задается «счетчик групп» (т. е. количество групп). Часто используются пятибуквенные группы, датируемые тем временем, когда сообщения передавались по телеграфу :
СИААЗ КЛКБА ВАЗОА РФПБЛ УАОАР
Если длина сообщения не делится на пять, оно может быть дополнено в конце нулями . Это могут быть любые символы, которые расшифровываются до явной ерунды, чтобы получатель мог их легко обнаружить и отбросить.
Алфавит зашифрованного текста иногда отличается от алфавита открытого текста; например, в шифре pigpen зашифрованный текст состоит из набора символов, полученных из сетки. Например:
Однако такие функции мало влияют на безопасность схемы — по крайней мере, любой набор странных символов можно переписать обратно в алфавит AZ и обращаться с ним как обычно.
В списках и каталогах для продавцов иногда используется очень простое шифрование для замены цифровых цифр буквами.
Пример: MAT будет использоваться для обозначения 120.
Хотя традиционный метод ключевых слов для создания алфавита смешанной замены прост, его серьезным недостатком является то, что последние буквы алфавита (в основном низкочастотные) имеют тенденцию оставаться в конце. Более сильный способ создания смешанного алфавита — генерировать алфавит замены совершенно случайным образом.
Хотя число возможных алфавитов замены очень велико (26! ≈ 2 88,4 или около 88 бит ), этот шифр не очень стойкий и легко взламывается. При условии, что сообщение имеет разумную длину (см. ниже), криптоаналитик может вывести вероятное значение наиболее распространенных символов, анализируя распределение частот зашифрованного текста. Это позволяет формировать частичные слова, которые можно предварительно заполнить, постепенно расширяя (частичное) решение ( демонстрацию этого см. в частотном анализе ). В некоторых случаях основные слова также можно определить по рисунку их букв; например, «attract », «osseous » и слова с этими двумя корнями являются единственными распространенными английскими словами с образцом ABBCADB . Многие люди решают такие шифры для развлечения, например, криптограммные головоломки в газете.
Согласно расстоянию уникальности английского языка , для взлома простой замены смешанного алфавита требуется 27,6 букв зашифрованного текста. На практике обычно требуется около 50 букв, хотя некоторые сообщения могут быть разбиты на меньшее количество, если обнаружены необычные шаблоны. В других случаях можно сделать так, чтобы открытый текст имел почти ровное частотное распределение, и тогда криптоаналитику потребуются гораздо более длинные открытые тексты.
Одним из некогда распространенных вариантов шифра замены является номенклатор . Названный в честь государственного чиновника, объявившего титулы приезжих высокопоставленных лиц, этот шифр использует небольшой кодовый лист, содержащий таблицы замены букв, слогов и слов, иногда гомофонные, которые обычно преобразуют символы в числа. Первоначально часть кода ограничивалась именами важных людей, отсюда и название шифра; в последующие годы он также охватывал множество общих слов и географических названий. В зашифрованном тексте не различались символы целых слов ( кодовых слов в современном языке) и букв ( шифр в современном языке). Одним из них был «Великий шифр Россиньоля » , использовавшийся французским Людовиком XIV .
Номенклаторы были стандартным средством дипломатической переписки, шпионажа и продвинутых политических заговоров с начала пятнадцатого века до конца восемнадцатого века; большинство заговорщиков были и остаются менее изощренными в криптографическом отношении. Хотя криптоаналитики правительственной разведки систематически взламывали номенклатуры к середине шестнадцатого века, а более совершенные системы были доступны с 1467 года, обычной реакцией на криптоанализ было просто увеличение размеров таблиц. К концу восемнадцатого века, когда система начала отмирать, у некоторых номенклатур было 50 000 символов. [ нужна цитата ]
Тем не менее не все номенклаторы были сломаны; Сегодня криптоанализ архивных зашифрованных текстов остается плодотворной областью исторических исследований .
Первой попыткой повысить сложность атак частотного анализа на шифры замены была маскировка частот букв открытого текста с помощью гомофонии . В этих шифрах буквы открытого текста сопоставляются более чем с одним символом зашифрованного текста. Обычно наиболее часто встречающимся символам открытого текста присваивается больше эквивалентов, чем более низкочастотным буквам. Таким образом, частотное распределение выравнивается, что усложняет анализ.
Поскольку в алфавите зашифрованного текста потребуется более 26 символов, используются различные решения для создания более крупных алфавитов. Возможно, самым простым является использование числовой замены «алфавит». Другой метод состоит из простых вариаций существующего алфавита; прописные, строчные, перевернутые и т. д. Более художественно, хотя и не обязательно более надежно, некоторые гомофонические шифры использовали полностью изобретенные алфавиты причудливых символов.
Книжный шифр — это разновидность гомофонного шифра, одним из примеров являются шифры Била . Это история о зарытом сокровище, описанная в 1819–1821 годах с использованием зашифрованного текста, связанного с Декларацией независимости. Здесь каждый символ зашифрованного текста был представлен числом. Число определялось путем взятия символа открытого текста и поиска слова в Декларации независимости, которое начиналось с этого символа, и использования числовой позиции этого слова в Декларации независимости в качестве зашифрованной формы этой буквы. Поскольку многие слова в Декларации независимости начинаются с одной и той же буквы, шифрованием этого символа может быть любое число, связанное со словами в Декларации независимости, начинающимися с этой буквы. Расшифровать зашифрованный текстовый символ X (который является числом) так же просто, как найти X-е слово Декларации независимости и использовать первую букву этого слова в качестве расшифрованного символа.
Другой гомофонный шифр был описан Шталем [2] [3] и был одной из первых попыток обеспечить компьютерную безопасность систем данных в компьютерах посредством шифрования . Шталь построил шифр таким образом, чтобы количество омофонов для данного символа было пропорционально частоте символа, что значительно усложнило частотный анализ.
Франческо I Гонзага , герцог Мантуи , использовал самый ранний известный пример шифра гомофонной замены в 1401 году для переписки с некой Симоной де Крема. [4] [5]
Мария, королева Шотландии , находясь в заточении у Елизаветы I, в течение лет с 1578 по 1584 годы использовала гомофонные шифры с дополнительным шифрованием с использованием номенклатора для частых префиксов, суффиксов и имен собственных при общении со своими союзниками, включая Мишеля де Кастельно . [6]
Работа Аль-Калкашанди (1355–1418), основанная на более ранней работе Ибн ад-Дурайхима (1312–1359), содержала первое опубликованное обсуждение замены и транспонирования шифров, а также первое описание полиалфавитной системы шифров. шифр, в котором каждой букве открытого текста назначается более одного заменителя. [7] Многоалфавитные шифры замены были позже описаны в 1467 году Леоне Баттистой Альберти в форме дисков. Иоганн Тритемий в своей книге «Стеганография» ( на древнегреческом языке означает «скрытое письмо») представил теперь более стандартную форму таблицы ( см. ниже; около 1500 г., но опубликовано гораздо позже). Более сложная версия с использованием смешанных алфавитов была описана в 1563 году Джованни Баттистой делла Порта в его книге De Furtivis Literarum Notis ( с латыни «О скрытых символах в письменной форме»).
В полиалфавитном шифре используется несколько шифралфавитов. Для облегчения шифрования все алфавиты обычно записываются в большую таблицу , традиционно называемую tableau . Размер таблицы обычно составляет 26×26, так что доступно 26 полных алфавитов зашифрованного текста. Метод заполнения таблицы и выбора следующего алфавита определяет конкретный полиалфавитный шифр. Все такие шифры взломать легче, чем считалось ранее, поскольку алфавиты замены повторяются для достаточно больших открытых текстов.
Одним из самых популярных было произведение Блеза де Виженера . Впервые опубликованный в 1585 году, он считался невзламываемым до 1863 года, и его действительно часто называли le chiffre indéchiffrable ( по -французски «нерасшифрованный шифр»).
В шифре Виженера первая строка таблицы заполняется копией алфавита открытого текста, а последующие строки просто сдвигаются на одну позицию влево. (Такая простая таблица называется прямой таблицей и математически соответствует сложению открытого текста и ключевых букв по модулю 26.) Затем используется ключевое слово, чтобы выбрать, какой алфавит зашифрованного текста использовать. Каждая буква ключевого слова используется по очереди, а затем снова повторяется с начала. Таким образом, если ключевым словом является «CAT», первая буква открытого текста зашифровывается буквой «C», вторая — буквой «А», третья — буквой «Т», четвертая — снова буквой «С» и так далее. На практике ключи Виженера часто представляли собой фразы длиной в несколько слов.
В 1863 году Фридрих Касиски опубликовал метод (вероятно, открытый тайно и независимо перед Крымской войной Чарльзом Бэббиджем ), который позволил вычислить длину ключевого слова в зашифрованном сообщении Виженера. Как только это было сделано, буквы зашифрованного текста, которые были зашифрованы одним и тем же алфавитом, можно было выделить и атаковать отдельно как ряд полунезависимых простых замен, что осложнялось тем, что внутри одного алфавита буквы были разделены и не образовывали полных слов. но упрощено тем фактом, что обычно использовалась прямая таблица .
Таким образом, даже сегодня шифр типа Виженера теоретически должно быть трудно взломать, если в таблице используются смешанные алфавиты, если ключевое слово случайное и если общая длина зашифрованного текста менее чем в 27,67 раза превышает длину ключевого слова. [8] Эти требования редко понимаются на практике, и поэтому безопасность зашифрованных сообщений Виженера обычно ниже, чем могла бы быть.
Другие известные полиалфавиты включают:
Современные потоковые шифры также можно рассматривать, с достаточно абстрактной точки зрения, как форму полиалфавитного шифра, в котором все усилия направлены на то, чтобы сделать ключевой поток как можно более длинным и непредсказуемым.
В шифре полиграфической замены буквы открытого текста заменяются большими группами, а не заменяются буквами по отдельности. Первое преимущество состоит в том, что распределение частот гораздо более плоское, чем у отдельных букв (хотя в реальных языках оно не является на самом деле плоским; например, «TH» встречается гораздо чаще, чем «XQ» в английском языке). Во-вторых, большее количество символов требует соответственно большего зашифрованного текста для продуктивного анализа частоты букв.
Для замены пар букв потребуется алфавит замены длиной 676 символов ( ). В том же De Furtivis Literarum Notis , упомянутом выше, делла Порта фактически предложил такую систему с таблицей 20 x 20 (для 20 букв итальянского/латинского алфавита, которую он использовал), заполненной 400 уникальными глифами . Однако система была непрактичной и, вероятно, никогда фактически не использовалась.
Самым ранним практическим диграфическим шифром (парной заменой) был так называемый шифр Плейфэра , изобретенный сэром Чарльзом Уитстоном в 1854 году. В этом шифре сетка 5х5 заполняется буквами смешанного алфавита (две буквы, обычно I). и J объединены). Затем моделируется диграфическая замена, принимая пары букв как два угла прямоугольника и используя два других угла в качестве зашифрованного текста ( диаграмму см. в основной статье о шифрах Playfair ). Специальные правила обрабатывают двойные буквы и пары, находящиеся в одной строке или столбце. Playfair использовался в военных целях от англо-бурской войны до Второй мировой войны .
Несколько других практических полиграфических методов были представлены в 1901 году Феликсом Деластелем , включая двураздельные и четырехугольные шифры (оба диграфические), а также тройной шифр (вероятно, первый практический триграфический шифр).
Шифр Хилла , изобретенный в 1929 году Лестером С. Хиллом , представляет собой полиграфическую замену, которая позволяет одновременно объединять гораздо большие группы букв с использованием линейной алгебры . Каждая буква рассматривается как цифра по основанию 26 : A = 0, B = 1 и так далее. (В другом варианте добавляются 3 дополнительных символа, чтобы сделать базис простым .) Затем блок из n букв рассматривается как вектор n измерений и умножается на матрицу anxn по модулю 26. Компоненты матрицы являются ключом, и должен быть случайным при условии, что матрица обратима (чтобы обеспечить возможность дешифрования). Механическая версия шифра Хилла размерности 6 была запатентована в 1929 году. [9]
Шифр Хилла уязвим для атаки с известным открытым текстом, поскольку он полностью линеен , поэтому для отражения этой атаки его необходимо объединить с некоторым нелинейным шагом. Комбинация все более и более широких слабых линейных диффузионных шагов, таких как шифр Хилла, с шагами нелинейной замены, в конечном итоге приводит к сети замены-перестановки (например, шифру Фейстеля ), поэтому можно - с этой крайней точки зрения - рассмотреть современные блочные шифры как разновидность полиграфического замещения.
Между Первой мировой войной и широким распространением компьютеров (для некоторых правительств это было примерно в 1950-х или 1960-х годах; для других организаций это было десятилетие или более позже; для отдельных лиц это было не ранее 1975 года), механическая реализация шифров полиалфавитной замены широко использовались. Примерно в одно и то же время у нескольких изобретателей были схожие идеи, и роторные шифровальные машины были запатентованы четыре раза в 1919 году. Наиболее важной из получившихся машин была « Энигма» , особенно в версиях, используемых немецкой армией примерно с 1930 года . Союзники также разработали и бывшие в употреблении роторные машины (например, SIGABA и Typex ).
Все они были похожи тем, что заменяемая буква выбиралась электрически из огромного количества возможных комбинаций, возникающих в результате вращения нескольких буквенных дисков. Поскольку один или несколько дисков вращались механически при зашифровке каждой буквы открытого текста, количество используемых алфавитов было астрономическим. Тем не менее ранние версии этих машин были хрупкими. Уильям Ф. Фридман из SIS армии США рано обнаружил уязвимости в роторной машине Хеберна , а Дилвин Нокс из GC&CS решил версии машины Enigma (без «коммутационной панели») задолго до начала Второй мировой войны . Трафик, защищенный практически всеми немецкими военными «Энигмами», был взломан криптоаналитиками союзников, особенно в Блетчли-парке , начиная с варианта немецкой армии, использовавшегося в начале 1930-х годов. Эта версия была опровергнута вдохновенным математическим прозрением Мариана Реевского из Польши .
Насколько общеизвестно, ни одно сообщение, защищенное машинами SIGABA и Typex , никогда не было взломано в то время или около того времени, когда эти системы находились в эксплуатации.
Один тип шифра замены — одноразовый блокнот — уникален. Его изобрели ближе к концу Первой мировой войны Гилберт Вернам и Жозеф Моборн в США. Его неразрушимость была математически доказана Клодом Шенноном , вероятно, во время Второй мировой войны ; его работа была впервые опубликована в конце 1940-х годов. В наиболее распространенной реализации одноразовый блокнот можно назвать шифром замены только с необычной точки зрения; обычно буква открытого текста каким-либо образом комбинируется (не заменяется) (например, XOR ) с ключевым символом материала в этой позиции.
Одноразовый блокнот в большинстве случаев непрактичен, поскольку требует, чтобы ключевой материал был такой же длины, как и открытый текст, фактически случайным , использовался один и только один раз и хранился в полной тайне от всех, кроме отправителя и предполагаемого получателя. При нарушении этих условий, даже незначительном, одноразовый блокнот уже не является нерушимым. В советских одноразовых сообщениях, отправленных из США на короткое время во время Второй мировой войны, использовался неслучайный ключевой материал. Криптоаналитики США, начиная с конца 40-х годов, смогли полностью или частично взломать несколько тысяч сообщений из нескольких сотен тысяч. (См. проект Венона )
В механической реализации, подобно оборудованию Rockex , одноразовый блокнот использовался для сообщений, отправляемых на горячую линию Москва - Вашингтон , созданную после Карибского кризиса .
Шифры замены, описанные выше, особенно старые ручные шифры с карандашом и бумагой, больше не используются серьезно. Однако криптографическая концепция замещения сохраняется и сегодня. С абстрактной точки зрения современные бит-ориентированные блочные шифры (например, DES или AES ) можно рассматривать как шифры замены в большом двоичном алфавите. Кроме того, блочные шифры часто включают в себя меньшие таблицы подстановки, называемые S-блоками . См. также сеть подстановки-перестановки .
