Омофоническая замена

Шифрование методом омофонической замены известно с 15 века[2].

Симеоне де Крема в 1401 году впервые использовал таблицы омофонов для равномерной частотности гласных букв при помощи многозначной замены[3].

Леон Баттиста Альберти в своей книге «Трактат о шифрах», опубликованной в 1466 году, описал шифр замены, в котором одной букве сопоставляется несколько элементов[3].

Традиционные моноалфавитные шифры замены в семнадцатом веке всё ещё оставались актуальными для решения лёгких задач, таких как шифрование личной переписки для скрытия информации от слуг или защита своего дневника от жены или мужа. Моноалфавитная замена производит простую и быструю защиту информации от людей, несведущих в криптоанализе. Однако для более серьёзных целей такое шифрование уже не являлось безопасным, поэтому появилась необходимость поиска шифра, взломать который было бы сложнее, чем моноалфавитный шифр замены, но пользоваться которым было бы проще, чем полиалфавитным шифром замены. Было представлено несколько вариантов таких шифров, самым эффективным решением данной проблемы оказался омофонический шифр замены, или омофоническая замена[1].

Пусть ${\displaystyle i}$ — символ алфавита, который используется в открытом тексте. Для каждого ${\displaystyle i}$ составим множество символов ${\displaystyle M_{i}}$, таким образом, чтобы для различных символов ${\displaystyle i}$ и ${\displaystyle j}$ множества ${\displaystyle M_{i}}$ и ${\displaystyle M_{j}}$ не пересекались. Обычно элементами множества ${\displaystyle M_{i}}$ являются числа. При омофоническом шифровании, число замен для каждого символа берется пропорционально вероятности появления этого символа в открытом тексте. При шифровании замена для символа открытого текста выбирается либо случайным образом (генератор случайных чисел), либо определенным образом (например, по порядку). Чтобы запомнить буквы, которые чаще всего встречаются в текстах, используют комбинации букв «сеновалитр» и «tetrishonda» для русского и английского языков соответственно. Эти комбинации похожи на слова, а потому легко запоминаются[4].

(*) (В таблице представлены результаты частотного анализа художественных и научно-технических текстов общим объёмом более 1 млн символов. При этих же условиях вероятность «пробела» составляет 0,146.)

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

Пример такой таблицы представлен ниже.

Некоторые поля в таблице пусты, так как для каждого символа исходного алфавита количество замен различно. Например, по этому фрагменту можно зашифровать слово «ВЕРА». Каждую букву исходного сообщения, в данном случае слова, следует заменить на одну из шифрозамен в столбце этой буквы. Если буквы заменить такими шифрозаменами: «В»-${\displaystyle 325}$, «Е»-${\displaystyle 700}$, «Р»-${\displaystyle 865}$, «А»-${\displaystyle 906}$, тогда зашифрованное слово имеет вид числовой последовательности «${\displaystyle 325}$ ${\displaystyle 700}$ ${\displaystyle 865}$ ${\displaystyle 906}$»[4].

Шифрование омофонической заменой является простейшей защитой против криптоатак частотного анализа, так как при шифровании буквы исходного текста случайным образом выбирается одна из её замен. При таком методе шифрования элементы шифротекста появляются равновероятно, поэтому обычный подсчет частоты букв бесполезен для криптоаналитика. Однако частотный криптоанализ, основанный на подсчете пар, троек букв или слов будет более успешен. Например, артикль the является наиболее встречаемым в английском открытом тексте. Также, после буквы q встречается только одна буква — u. Таким образом, замечая некоторые комбинации символов, можно расшифровать часть текста, а затем, по полученным сведениям, восстановить оставшуюся часть[5][4].

В настоящее время современные компьютеры дешифруют тексты, зашифрованные омофонической заменой за считанные секунды[6].

Особенность данного метода состоит в том, что шифрозамены не повторяются. Это значит, что если у буквы «Ф» 3 шифрозамены, например, ${\displaystyle 100}$ , ${\displaystyle 477}$ и ${\displaystyle 906}$ , то шифрозамены ${\displaystyle 100}$ , ${\displaystyle 477}$ и ${\displaystyle 906}$ обозначают только букву «Ф»[7].

Омофонический шифр, возможно, и выглядит как многоалфавитный (полиалфавитный), так как каждая буква алфавита может быть зашифрована множеством способов, но, на самом деле, шифр омофонической замены является одним из видов одноалфавитного (моноалфавитного) шифра. Основная причина, почему омофонический шифр является моноалфавитным, заключается в том, что шифралфавит не меняется на протяжении всего процесса шифрования[7].

Шифр омофонической замены характеризуется двумя параметрами — длинной шифртекста ${\displaystyle N}$ и сложностью ${\displaystyle M=N/L}$, где ${\displaystyle L}$ — количество различных символов шифровального алфавита, использованных в данном шифртексте. Очевидно, что сложность ограничена ${\displaystyle 0\leqslant M\leqslant 1}$. Когда сложность шифра достаточно близка к 0, шифр является шифром простой замены. При некотором значении ${\displaystyle M}$ распределение символов шифралфавита становится равномерным (около 0,3 для шифртекста из 200 символов), однако, если продолжать увеличивать сложность, можно достигнуть граничного значения, при котором однозначно расшифровать текст уже нельзя. Омофонические замены высших порядков имеют один и тот же шифртекст для различных открытых текстов, поэтому в случаях, когда длина шифртекста меньше расстояния единственности, понять, какой именно вариант открытого текста будет верным, невозможно[8].

Омофоническая замена второго порядка — это омофоническая замена, такая, что шифртекст можно расшифровать двумя вариантами. Например, «${\displaystyle 13}$ ${\displaystyle 9}$ ${\displaystyle 2}$ ${\displaystyle 32}$ ${\displaystyle 2}$ ${\displaystyle 19}$ ${\displaystyle 27}$ ${\displaystyle 10}$ ${\displaystyle 8}$ ${\displaystyle 32}$ ${\displaystyle 13}$ ${\displaystyle 3}$» с помощью одного ключа (ключ 1) можно расшифровать как «МАМА МЫЛА РАМУ», а с помощью второго ключа (ключ 2) как «АМУР УМЫЛ УРАЛ». Оба открытых текста не несут особого смысла, однако хорошо иллюстрируют, что за одним и тем же шифртекстом могут скрываться абсолютно разные сообщения[9].

Криптограммы известного серийного убийцы Зодиака зашифрованы шифром омофонической замены. Одна из двух криптограмм до сих пор не расшифрована[13].

Криптограммы Бейла считаются зашифрованными шифром омофонической замены первого порядка, причем вероятность расшифровать вторую криптограмму (единственную из трех, которую смогли расшифровать) так, чтобы получить другой осмысленный текст, наименьшая[14][15].

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

• Саймон Сингх. Глава 2. Нераскрываемый шифр // Книга шифров. Тайная история шифров и их расшифровки = The Code Book by Simon Singh / перевод с английского А. Галыгина. — М.: АСТ, 2007. — Т. 2. — С. 69—74. — 4000 экз. — ISBN 978-5-17-038477-8.
• Пазизин С. В., Малюк А. А., Пригожин Н. С. Глава 3. Криптографические методы защиты информации // Введение в защиту информации в автоматизированных системах. — М.: Горячая линия - Телеком, 2001. — С. 52. — 148 с. — 3000 экз. — ISBN 5-93517-062-0.
• Долгов В. А., Анисимов В. В. Глава 5. Шифры замены // Криптографические методы защиты информации. — Хабаровск: Издательство ДВГУПС, 2008. — С. 32—33. — 155 с. — 30 экз. (недоступная ссылка)
• Арто Саломаа. Глава 1. Классическая криптография // Криптография с открытым ключом = Public-Key Cryptography / Под редакцией А. Е. Андреева и А. А. Болотова. — М.: Мир, 1995. — С. 35. — 318 с. — ISBN 5-03-001991-X.
• Шнайер Брюс. Глава 1. Основные понятия // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C / перевод с английского А. Галыгина. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4. Архивная копия от 8 октября 2013 на Wayback Machine
• Дэвид Кан. Взломщики кодов / Перевод с английского А. Ключевский. — М.: Центрполиграф, 2000. — ISBN 5-227-00678-4. (недоступная ссылка)
• Carl Hammer. Second order homophonic ciphers (англ.) = Second order homophonic ciphers // Cryptologia : Научный журнал. — Taylor & Francis, 1988. — Vol. 12. — P. 11-20. — ISSN 0161-1194. — doi:10.1080/0161-118891862747.
• John C. King & Dennis R. Bahler. An alhoritmic solution of sequental homophonic ciphers (англ.) = An alhoritmic solution of sequental homophonic ciphers // Cryptologia : Научный журнал. — Taylor & Francis, 1993. — Vol. 17. — P. 148-165. — ISSN 0161-1194. — doi:10.1080/0161-119391867827.
• John C. King & Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems (англ.) = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia : Научный журнал. — Taylor & Francis, 1993. — Vol. 17. — P. 45-54. — ISSN 0161-1194. — doi:10.1080/0161-119391867755.

• Анисимов В. В. Шифры замены (неопр.). Криптографические методы защиты информации. Дата обращения: 4 декабря 2012.