Подстановочный шифр

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Замещающий шифр»  -  новости  · газеты  · книги  · ученый  · JSTOR ( март 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В криптографии , A замещение шифр представляет собой способ шифрования , в котором блоки открытого текста заменяется шифротекстом , в соответствии с фиксированной системой; «единицы» могут быть отдельными буквами (наиболее распространенными), парами букв, тройками букв, смесями вышеперечисленного и так далее. Получатель расшифровывает текст, выполняя обратную замену.

Шифры замещения можно сравнить с шифрами транспонирования . В транспозиционном шифре единицы открытого текста переставляются в другом и обычно довольно сложном порядке, но сами единицы остаются неизменными. Напротив, в шифре замещения единицы открытого текста сохраняются в той же последовательности в зашифрованном тексте, но сами единицы изменяются.

Есть несколько различных типов подстановочного шифра. Если шифр работает с отдельными буквами, он называется шифром простой подстановки ; шифр, который работает с большими группами букв, называется полиграфическим . A моноалфавитных шифры используют фиксированное замещение по всему сообщению, в то время как полиалфавитный шифр использует ряд замен на различные позициях в сообщении, где блок из открытого текста отображаются на один из нескольких возможностей в шифротексте и наоборот.

Простая замена [ править ]

ROT13 - это шифр Цезаря , тип подстановочного шифра. В ROT13 алфавит вращается на 13 шагов.

Подстановку отдельных букв по отдельности - простую замену - можно продемонстрировать, выписав алфавит в определенном порядке, чтобы представить замену. Это называется алфавитом замещения . Шифровальный алфавит может быть сдвинут или инвертирован (создавая шифры Цезаря и Атбаша , соответственно) или зашифрован более сложным образом, и в этом случае он называется смешанным алфавитом или нарушенным алфавитом . Традиционно смешанные алфавиты можно создать, сначала написав ключевое слово, удалив в нем повторяющиеся буквы, а затем записав все оставшиеся буквы алфавита в обычном порядке.

Используя эту систему, ключевое слово « зебры » дает нам следующие алфавиты:

Сообщение

беги немедленно. нас открыли!

шифрует

SIAA ZQ LKBA. ВА ЗОА РФПБЛУАОАР!

Обычно зашифрованный текст записывается блоками фиксированной длины, без знаков препинания и пробелов; это делается для того, чтобы скрыть границы слов от открытого текста и избежать ошибок передачи. Эти блоки называются «группами», и иногда «количество групп» (то есть количество групп) задается в качестве дополнительной проверки. Часто используются пятибуквенные группы, начиная с того времени, когда сообщения передавались по телеграфу :

SIAAZ QLKBA VAZOA RFPBL UAOAR

Если длина сообщения не делится на пять, оно может быть дополнено в конце « нулями ». Это могут быть любые символы, которые расшифровываются до очевидной бессмыслицы, чтобы получатель мог легко их обнаружить и отбросить.

Алфавит зашифрованного текста иногда отличается от алфавита открытого текста; например, в шифровальном шифровании зашифрованный текст состоит из набора символов, полученных из сетки. Например:

Однако такие функции мало влияют на безопасность схемы - по крайней мере, любой набор странных символов может быть преобразован обратно в алфавит AZ и обработан как обычно.

В списках и каталогах для продавцов иногда используется очень простое шифрование, чтобы заменить числовые цифры буквами.

Пример: MAT будет использоваться для представления 120.

Безопасность простых подстановочных шифров [ править ]

Хотя традиционный метод ключевого слова для создания смешанного алфавита подстановки прост, серьезным недостатком является то, что последние буквы алфавита (которые в основном встречаются редко), как правило, остаются в конце. Более сильный способ построения смешанного алфавита - это генерировать алфавит замены полностью случайным образом.

Хотя число возможных алфавитов подстановки очень велико (26! ≈ 2 ^88,4 , или около 88 бит ), этот шифр не очень надежен и легко взламывается. При условии, что сообщение имеет разумную длину (см. Ниже), криптоаналитик может определить вероятное значение наиболее распространенных символов, проанализировав частотное распределение зашифрованного текста. Это позволяет формировать частичные слова, которые можно предварительно заполнить, постепенно расширяя (частичное) решение (см. Частотный анализ для демонстрации этого). В некоторых случаях основные слова также можно определить по образцу их букв; например, привлечь , костный, и слова с этими двумя в качестве корня - единственные распространенные английские слова с шаблоном ABBCADB . Многие люди решают такие шифры для развлечения, например, головоломки с криптограммами в газете.

Согласно единственности расстояния по - английски , 27,6 буквы шифртекста требуется взломать смешанный алфавит простой замены. На практике обычно требуется около 50 букв, хотя некоторые сообщения можно разбить меньшим числом, если обнаруживаются необычные шаблоны. В других случаях открытый текст может иметь почти ровное частотное распределение, и тогда криптоаналитику потребуются гораздо более длинные открытые тексты.

Номенклатор [ править ]

Один из распространенных когда-то вариантов шифра подстановки - это номенклатура . Названный в честь государственного должностного лица, объявившего титулы высокопоставленных гостей, этот шифр использует небольшую кодовую таблицу, содержащую таблицы замены букв, слогов и слов, иногда гомофонические, которые обычно преобразуют символы в числа. Первоначально часть кода была ограничена именами важных людей, отсюда и название шифра; в более поздние годы он включал также многие общеупотребительные слова и географические названия. Символы для целых слов ( кодовые слова в современном языке) и букв ( шифр в современном языке) не различались в зашифрованном тексте. Rossignols " Великий Cipherиспользовался Людовиком XIV во Франции .

Номенклатуры были стандартной пищей для дипломатической переписки, шпионажа и передовых политических заговоров с начала пятнадцатого века до конца восемнадцатого века; большинство заговорщиков были и остаются менее изощренными в криптографическом отношении. Хотя к середине XVI века криптоаналитики правительственной разведки систематически взламывали номенклатуру, а с 1467 года были доступны более совершенные системы, обычным ответом на криптоанализ было просто увеличить таблицы. К концу восемнадцатого века, когда система начала вымирать, у некоторых номенклаторов было 50 000 символов. ^{[ необходима цитата ]}

Тем не менее, не все номенклатуры были нарушены; Сегодня криптоанализ заархивированных зашифрованных текстов остается плодотворной областью исторических исследований .

Гомофоническая замена [ править ]

Ранняя попытка повысить сложность атак частотного анализа на шифры подстановки заключалась в том, чтобы замаскировать частоты букв открытого текста за счет омофонии . В этих шифрах буквы открытого текста соответствуют более чем одному символу зашифрованного текста. Обычно символам открытого текста с самой высокой частотой дается больше эквивалентов, чем буквам с меньшей частотой. Таким образом, распределение частот сглаживается, что затрудняет анализ.

Поскольку в алфавите зашифрованного текста потребуется более 26 символов, используются различные решения для изобретения более крупных алфавитов. Возможно, самым простым является использование числовой замены «алфавит». Другой метод состоит из простых вариаций существующего алфавита; прописные, строчные, перевернутые и т. д. Более художественно, хотя и не обязательно более надежно, некоторые гомофонические шифры использовали полностью изобретенные алфавиты фантастических символов.

В шифры Beale являются еще одним примером гомофонно шифра. Это история о захороненных сокровищах, описанная в 1819–1821 годах с помощью зашифрованного текста Декларации независимости. Здесь каждый символ зашифрованного текста был представлен числом. Число было определено путем взятия символа открытого текста и нахождения слова в Декларации независимости, начинающегося с этого символа, и использования числовой позиции этого слова в Декларации независимости в качестве зашифрованной формы этой буквы. Поскольку многие слова в Декларации независимости начинаются с одной и той же буквы, шифрованием этого символа может быть любое из чисел, связанных со словами в Декларации независимости, которые начинаются с этой буквы. Расшифровка зашифрованного текстового символа X (которое является числом) так же просто, как найти X-е слово Декларации независимости и использовать первую букву этого слова в качестве расшифрованного символа.

Другой гомофонический шифр был описан Шталем ^{[2] [3]} и был одной из первых ^{[ необходима цитата ]} попыток обеспечить компьютерную безопасность систем данных в компьютерах с помощью шифрования. Шталь сконструировал шифр таким образом, что количество омофонов для данного символа было пропорционально его частоте, что значительно усложняло частотный анализ.

Книга шифры и широко расставленная шахматная доска являются типами гомофонного шифра.

Франческо I Гонзага , герцог Мантуи , использовал самый ранний известный пример гомофонического шифра замещения в 1401 году для переписки с некой Симоной де Крема. ^{[4] [5]}

Полиалфавитная замена [ править ]

Работа Аль-Калкашанди (1355-1418), основанная на более ранней работе Ибн ад-Дурайхим (1312–1359), содержала первое опубликованное обсуждение замены и транспозиции шифров, а также первое описание полиалфавитного алфавита. шифр, в котором каждой букве открытого текста присвоено более одной замены. ^[6] Полиалфавитные шифры замещения были позже описаны в 1467 году Леоне Баттистой Альберти в форме дисков. Иоганн Тритемиус в своей книге « Стеганография» ( древнегреческое слово «скрытое письмо») представил теперь более стандартную форму таблицы.(см. ниже; около 1500 г., но опубликовано не так давно). Более сложная версия с использованием смешанных алфавитов была описана в 1563 году Джованни Баттиста делла Порта в его книге De Furtivis Literarum Notis ( латинское слово «О скрытых письмах»).

В полиалфавитном шифре используются несколько шифралфавитов. Для облегчения шифрования все алфавиты обычно записываются в большую таблицу , традиционно называемую таблицей . Размер таблицы обычно 26 × 26, так что доступно 26 полных алфавитов зашифрованного текста. Метод заполнения таблицы и выбора следующего алфавита определяет конкретный полиалфавитный шифр. Все такие шифры легче взломать, чем когда-либо считалось, поскольку алфавиты подстановки повторяются для достаточно больших открытых текстов.

Одним из самых популярных был Блез де Виженера . Впервые опубликованный в 1585 году, он считался нерушимым до 1863 года и на самом деле обычно назывался le chiffre unéchiffrable (по- французски «неразборчивый шифр»).

В шифре Виженера первая строка таблицы заполняется копией алфавита открытого текста, а последующие строки просто сдвигаются на одну позицию влево. (Такая простая таблица называется прямоугольной таблицей и математически соответствует сложению открытого текста и ключевых букв по модулю 26.) Затем ключевое слово используется для выбора того, какой алфавит зашифрованного текста использовать. Каждая буква ключевого слова используется по очереди, а затем они повторяются снова с начала. Таким образом, если ключевым словом является «CAT», первая буква открытого текста зашифровывается алфавитом «C», вторая - буквой «A», третья - буквой «T», четвертая - снова буквой «C» и так далее. На практике ключи Виженера часто были фразами длиной в несколько слов.

В 1863 году Фридрих Касиски опубликовал метод (возможно , обнаруженную тайно и независимо друг от друга до Крымской войны по Чарльза Бэббиджа ) , что позволило рассчитать длину ключевого слова в Vigenere зашифрованное сообщение. Как только это было сделано, буквы зашифрованного текста, которые были зашифрованы одним и тем же алфавитом, могли быть выделены и атакованы по отдельности как ряд полунезависимых простых замен, что усложнялось тем, что в пределах одного алфавита буквы были разделены и не образовывали полные слова, но упрощен тем фактом, что обычно использовалась tabula recta .

Таким образом, даже сегодня шифр типа Виженера теоретически должно быть трудно взломать, если в таблице используются смешанные алфавиты, если ключевое слово является случайным и если общая длина зашифрованного текста меньше, чем в 27,67 раз больше длины ключевого слова. ^[7] Эти требования редко понимаются на практике, поэтому безопасность зашифрованных сообщений Виженера обычно ниже, чем могла бы быть.

Другие известные полиалфавиты включают:

• Шифр Гронсфельда. Это идентично Vigenère, за исключением того, что используются только 10 алфавитов, поэтому «ключевое слово» является числовым.
• Beaufort шифра . Это практически то же самое, что и Vigenère, за исключением того, что прямая таблица заменяется обратной, математически эквивалентной зашифрованному тексту = ключ - открытый текст. Эта операция является самообратной , при этом одна и та же таблица используется как для шифрования, так и для дешифрования.
• Autokey шифра , который смешивает PLAINTEXT с ключом , чтобы избежать периодичности .
• Бегущий ключ шифрования , где ключ сделан очень долго, используя отрывок из книги или подобным текстом.

Современные поточные шифры также можно рассматривать с достаточно абстрактной точки зрения как форму полиалфавитного шифра, в котором все усилия были направлены на то, чтобы сделать ключевой поток как можно более длинным и непредсказуемым.

Полиграфическая подмена [ править ]

В шифре с полиграфической заменой буквы открытого текста заменяются большими группами вместо замены букв по отдельности. Первое преимущество состоит в том, что частотное распределение гораздо более плоское, чем у отдельных букв (хотя на самом деле не является плоским в реальных языках; например, «TH» гораздо более распространено, чем «XQ» в английском языке). Во-вторых, большее количество символов требует соответственно большего количества зашифрованного текста для продуктивного анализа частотности букв.

Для замены пары букв потребуется заменить алфавит длиной 676 символов ( ). В том же De Furtivis Literarum Notis, упомянутом выше, делла Порта фактически предложил такую ​​систему с таблицей 20 x 20 (для 20 букв итальянского / латинского алфавита, которые он использовал), заполненной 400 уникальными глифами . Однако система была непрактичной и, вероятно, фактически никогда не использовалась.${\ displaystyle 26 ^ {2}}$

Самым первым практическим диграфическим шифром (попарной заменой) был так называемый шифр Плейфэра , изобретенный сэром Чарльзом Уитстоном в 1854 году. В этом шифре сетка 5 x 5 заполнена буквами смешанного алфавита (две буквы, обычно I. и J, объединены). Затем симулируется диграфическая подстановка, принимая пары букв как два угла прямоугольника и используя два других угла в качестве зашифрованного текста ( диаграмму см. В основной статье Playfair cipher ). Специальные правила обрабатывают двойные буквы и пары, попадающие в одну строку или столбец. Playfair использовался в военных целях от англо-бурской войны до Второй мировой войны .

Несколько других практических ПОЛИГРАФИКА были введены в 1901 году Феликс Деластелл , в том числе бифидобактерий и четыре квадратных шифров (как digraphic) и TRIFID шифра (вероятно , первым практическим trigraphic).

Шифр Хилл , изобретенный в 1929 годе Лестер С. Хилл , является полиграфической заменой , которая может объединить гораздо большие группы букв одновременно с использованием линейной алгебры . Каждая буква рассматривается как цифра в базе 26 : A = 0, B = 1 и т. Д. (В варианте, 3 дополнительные символы добавляются , чтобы сделать базис простого числа .) Блок п букв затем рассматриваются как вектор из п измерений , и умноженный на апхпе матрицы , по модулю 26. Компоненты матрицы является ключом, и должна быть случайной при условии, что матрица обратима в${\ displaystyle \ mathbb {Z} _ {26} ^ {n}}$(для обеспечения возможности дешифрования). Механическая версия шифра Хилла размерности 6 была запатентована в 1929 году ^[8].

Шифр Хилла уязвим для атаки с использованием известного открытого текста, потому что он полностью линейен , поэтому он должен быть объединен с некоторым нелинейным шагом, чтобы отразить эту атаку. Комбинация более широких и более широких слабых, линейных диффузионных шагов, таких как шифр Хилла, с нелинейными шагами подстановки, в конечном итоге приводит к сети подстановки-перестановки (например, шифру Фейстеля ), поэтому можно - с этой крайней точки зрения - рассмотреть современные блочные шифры как разновидность полиграфической подстановки.

Шифры механической подстановки [ править ]

Примерно в период между Первой мировой войной и повсеместной доступностью компьютеров (для некоторых правительств это было примерно 1950-е или 1960-е годы; для других организаций это было десятилетие или более позже; для отдельных лиц это было не ранее 1975 года), механические реализации полиалфавитных шифров замещения широко использовались. Примерно в одно и то же время у нескольких изобретателей были похожие идеи, и роторные шифровальные машины были запатентованы четыре раза в 1919 году. Самой важной из полученных машин была Enigma , особенно в версиях, используемых немецкими военными примерно с 1930 года. Союзники также разработали и бывшие в употреблении роторные машины (например, SIGABA иTypex ).

Все они были похожи в том, что заменяемая буква была выбрана электрически из огромного количества возможных комбинаций, возникающих в результате вращения нескольких буквенных дисков. Поскольку один или несколько дисков вращались механически с каждой зашифрованной буквой открытого текста, количество используемых алфавитов было астрономическим. Тем не менее, ранние версии этой машины были ломкими. Уильям Ф. Фридман из армии США SIS рано обнаружили уязвимость в роторной машины Hebern в и GC & CS «s Dillwyn Knox решил версии Энигмы (те , без„коммутационной панели“) задолго до Второй мировой войныначалось. Трафик, защищенный практически всеми немецкими военными загадками, был нарушен криптоаналитиками союзников, в первую очередь в Блетчли-парке , начиная с варианта немецкой армии, использовавшегося в начале 1930-х годов. Эта версия была нарушена вдохновенными математическими открытиями Мариана Реевского из Польши .

Насколько общеизвестно, ни одно сообщение, защищенное машинами SIGABA и Typex, никогда не было сломано во время или почти в то время, когда эти системы находились в эксплуатации.

Одноразовый блокнот [ править ]

Один из типов шифра подстановки, одноразовый блокнот , является совершенно особенным. Он был изобретен в конце Первой мировой войны Гилбертом Вернамом и Джозефом Моборном в США. Клод Шеннон математически доказал ее неразрывность , вероятно, во время Второй мировой войны ; его работа была впервые опубликована в конце 1940-х годов. В наиболее распространенной реализации одноразовый блокнот можно назвать шифром подстановки только с необычной точки зрения; обычно буква открытого текста комбинируется (не заменяется) каким-либо образом (например, XOR ) с символом материала ключа в этой позиции.

Одноразовый блокнот в большинстве случаев непрактичен, так как требует, чтобы ключевой материал был такой же длины, как открытый текст, фактически случайным , использовался один раз и только один раз и держался в полной тайне от всех, кроме отправителя и предполагаемого получателя. Когда эти условия нарушаются, даже незначительно, одноразовый блокнот перестает быть небьющимся. В советских одноразовых блокнотах, отправленных из США на короткое время во время Второй мировой войны, использовался неслучайный ключевой материал. Американские криптоаналитики, начиная с конца 40-х годов, могли полностью или частично взламывать несколько тысяч сообщений из нескольких сотен тысяч. (См. Проект Venona )

В механическом исполнении, как и в случае с оборудованием Rockex , одноразовый блокнот использовался для сообщений, отправляемых по горячей линии Москва - Вашингтон, созданной после кубинского ракетного кризиса .

Подмена в современной криптографии [ править ]

Замещающие шифры, о которых говорилось выше, особенно старые ручные шифры, написанные карандашом и бумагой, больше не используются серьезно. Однако криптографическая концепция замещения сохраняется и сегодня. С достаточно абстрактной точки зрения современные битовые блочные шифры (например, DES или AES ) можно рассматривать как шифры замещения на чрезвычайно большом двоичном алфавите. Кроме того, блочные шифры часто включают в себя меньшие таблицы подстановки, называемые S-блоками . См. Также сеть замещения-перестановки .

Подстановочные шифры в популярной культуре [ править ]

• Шерлок Холмс взламывает подстановочный шифр в « Приключении танцующих мужчин ». Там шифр оставался нерасшифрованным годами, если не десятилетиями; не из-за сложности, а потому, что никто не подозревал, что это код , а считал это детскими каракулями.
• Язык Аль Бхед в Final Fantasy X на самом деле является шифром замены, хотя он произносится фонетически (т.е. «you» на английском языке переводится как «oui» в Al Bhed, но произносится так же, как «oui» на французском языке. ).
• В минбарском алфавите «с от Вавилона 5 серии подмены шифр с английского языка.
• Язык в Starfox Adventures : Dinosaur Planet, на котором говорят местные заурианцы и Кристал , также является шифром замены английского алфавита .
• Телепрограмма « Футурама» содержала замещающий шифр, в котором все 26 букв были заменены символами и называлась «Чужой язык» . Это было довольно быстро расшифровано стойкими зрителями, показав рекламу "Slurm" со словом "Drink" как на простом английском, так и на иностранном языке, что дало ключ. Позже продюсеры создали второй инопланетный язык, который использовал комбинацию замещающих и математических шифров. После того, как английская буква инопланетного языка расшифрована, числовое значение этой буквы (от 0 для «A» до 25 для «Z» соответственно) затем добавляется (по модулю 26) к значению предыдущей буквы, показывающей фактическое предполагаемое значение. письмо.Эти сообщения можно увидеть в каждом эпизоде ​​сериала и последующих фильмах.
• В конце каждого эпизода 1 сезона мультсериала « Гравити Фолз» во время проверки кредита есть один из трех простых заменяющих шифров: Шифр Цезаря A -3 (намекает «3 буквы назад» в конце вступительной части) , шифр Атбаша или буквенно-цифровой простой шифр подстановки. Финал 1 сезона закодирует сообщение со всеми тремя. Во втором сезоне шифры Виженера используются вместо различных моноалфавитных шифров, каждый из которых использует ключ, спрятанный в его эпизоде.
• В серии « Артемис Фаул » Эоина Колфера есть три подстановочных шифра; Гномами, кентаврианами и этернейцами, которые проходят внизу страниц или где-то еще в книгах.
• В Bitterblue , третьем романе Кристин Кашор , подстановочные шифры служат важной формой кодированной коммуникации.
• В видеоигре BioShock Infinite 2013 года на протяжении всей игры спрятаны подстановочные шифры, в которых игрок должен найти кодовые книги, чтобы помочь расшифровать их и получить доступ к излишкам запасов.
• В аниме-адаптации «Дьявол по совместительству!» , язык Энте Исла, называемый Энтеан, использует шифр подстановки с алфавитом зашифрованного текста AZYXEWVTISRLPNOMQKJHUGFDCB , оставляя только A, E, I, O, U, L, N и Q в исходных положениях.

См. Также [ править ]

• Бан (единица) с таблицей Centiban
• Копиальный шифр
• Leet
• Шифр Виженера
• Темы в криптографии

Ссылки [ править ]

Внешние ссылки [ править ]

• quipqiup Автоматизированный инструмент для решения простых подстановочных шифров как с известными границами слов, так и без них.
• CrypTool Исчерпывающий бесплатный инструмент электронного обучения с открытым исходным кодом для выполнения и взлома шифров подстановки и многого другого.
• Приложение Substitution Cipher Toolkit, которое, помимо прочего, может автоматически расшифровывать тексты, зашифрованные с помощью шифра замены.
• SCB Cipher Solver Взломщик одноалфавитных шифров.
• Реализация моноалфавитного шифра для шифрования файла (язык C).
• Реализация подстановочного шифра с шифрами Цезаря и Атбаша (Java)
• Реализация простой замены онлайн (Flash)
• Реализация простой замены в Интернете для кода MAKEPROFIT (сценарий CGI: ввод в URL, чтение вывода на веб-странице)
• Моноалфавитная подстановка, взламывающая моноалфавитную систему шифрования с использованием известной атаки открытого текста
• http://cryptoclub.math.uic.edu/substitutioncipher/sub2.htm