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

Омофоническая замена (англ. Homophonic substitution cipher) — шифр подстановки, при котором каждый символ открытого текста заменяется на один из нескольких символов шифра алфавита, причём количество заменяющих символов для одной буквы пропорционально частоте этой буквы. Это позволяет скрыть настоящую частоту появления данной буквы в зашифрованном тексте.

История

Шифрование методом омофонической замены известно с XV века.

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

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

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

Шифрование

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

Вероятность появления букв русского алфавита
Буква Вероятность А 0,069 Б 0,013 В 0,038 Г 0,014 Д 0,024 Е,Ё 0,071 Ж 0,007 З 0,016	Буква Вероятность И 0,064 Й 0,010 К 0,029 Л 0,039 М 0,027 Н 0,057 О 0,094 П 0,026	Буква Вероятность Р 0,042 С 0,046 Т 0,054 У 0,023 Ф 0,003 Х 0,008 Ц 0,005 Ч 0,012	Буква Вероятность Ш 0,006 Щ 0,004 Ъ 0,001 Ы 0,015 Ь 0,013 Э 0,002 Ю 0,005 Я 0,017

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

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

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

№	А	Б	В	…	Е	…	О	П	Р	…	Э	Ю	Я
1	012	128	325	…	037	…	064	058	265	…	501	064	106
2	659	556	026	…	700	…	149	073	333	…	248	749	098
…	…	…	…	…	…	…	…	…	…	…		…	…
17	111		061	…	144	…	903	656	476	…			453
…	…		…	…	…	…	…	…	…	…
38	366		804	…	…	…	123		865	…
…	…			…	…	…	…		…	…
69	095				…		010
…					…		…
71					541		268
…							…
94							479

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

Криптоанализ

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

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

Особенности шифра

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

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

Характеристики шифра

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

Омофоническая замена второго порядка

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

Ключ 1 М 13, 2 А 9, 32, 10 Ы 19 Л 27 Р 8 У 3

Ключ 2 М 9, 19 А 13 Ы 27 Л 10 Р 32 У 8,2

Создание ключа и шифрование

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

М	А	М	А	М	Ы	Л	А	Р	А	М	У
А	М	У	Р	У	М	Ы	Л	У	Р	А	Л

Теперь заметим, что, если читать полученную запись не по строкам, а по столбцам, мы получим 9 различных диграмм (пар букв): «МА», «АМ», «МУ», «АР», «ЫМ», «ЛЫ», «АЛ», «РУ», «УЛ». Все диграммы, кроме «МА», «МУ» и «АР» повторяются один раз. Далее случайным образом заполним матрицу $6\cdot 6$ (6 — количество букв в алфавитах открытых текстов, в случае использования в тексте всего алфавита, мы будем иметь матрицу $33\cdot 33$ или $26\cdot 26$ для русского и английского алфавитов соответственно) числами, например, от 1 до 36.

	А	Л	М	Р	У	Ы
А	21	10	9	32	26	34
Л	16	6	7	14	30	27
М	13	18	23	28	2	5
Р	4	15	36	22	8	35
У	25	3	17	29	20	33
Ы	1	31	19	24	12	11

Каждая строка и каждый столбец сопоставлены с одним из символов алфавита первого и второго открытых текстов соответственно. Теперь каждой диграмме соответствует некоторое число (на пересечении соответствующих строк и столбцов), следовательно, заменяя диграмму на соответствующее число, мы можем зашифровать тексты. Матрица с числами, соответствующими диграммам, играет в данном случае роль ключа. Чтобы сохранить полную матрицу в секрете, её разделяют на две матрицы: одна получается сортировкой элементов строк, другая — сортировкой столбцов и транспонированием. На выходе мы будем иметь две матрицы, в каждой из которых элементы в строках упорядочены по возрастанию (убыванию), а одну матрицу можно использовать для получения только одного открытого текста. Для примера взяты тексты с одинаковыми алфавитами, так как предполагается, что в общем случае для создания шифра будет использован весь алфавит и что шифр должен охватывать все возможные диграммы.

Ключ для первого получателя А 9 10 21 26 32 34 Л 6 7 14 16 27 30 М 2 5 13 18 23 28 Р 4 8 15 22 22 36 У 3 17 20 26 29 33 Ы 1 11 12 19 24 31

Ключ для второго получателя А 1 4 13 16 22 25 Л 3 6 10 15 18 31 М 7 9 17 19 23 36 Р 14 22 24 28 29 32 У 2 8 12 20 26 30 Ы 5 11 27 33 34 35

Омофоническая замена с минимальной избыточностью

Для улучшения метода можно добиться минимальной избыточности шифралфавита. Алгоритм

1. Каждое число мы будем использовать только единожды. В случае, если диграмма повторилась, возьмём для неё новое число, которое будет больше максимального, имеющегося в алфавите. В нашем случае получится шифротекст «$13$ $9$ $2$ $32$ $37$ $19$ $27$ $10$ $8$ $38$ $39$ $3$»
2. После завершения шифрования удалим из матрицы все неиспользованные элементы
3. Страница шифроблокнота с минимальной избыточностью может быть получена заменой всех чисел различными случайными числами. Очевидно, что в таком случае мы можем получить шифротекст «$1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$». Ключ-таблица диграмм и ключи для каждого из получателей для такого набора сообщений сократятся до минимально возможных.

А Л М Р У Ы А 8 2 4, 10 Л 7 М 1, 11 3, 5 Р 9 У 12 Ы 6

Ключ 1 А 2, 4, 8, 10 Л 7 М 1, 3, 5, 11 Р 9 У 12 Ы 6

Ключ 2 А 1, 11 Л 8, 12 М 2, 6 Р 4, 10 У 3, 5, 9 Ы 7

Если прочитать буквы в порядке, указанном соответствующими каждой букве числами, получится открытый текст. Из-за этого использование такого шифра становится невозможным, так как для получения открытого текста злоумышленнику будет достаточно иметь ключ, не имея даже закрытого текста. Это делает бессмысленным уменьшение избыточности текста. С другой стороны, использованная ранее матричная форма омофонической замены второго порядка имеет достаточно хорошую криптостойкость, если использовать полный алфавит. Два текста будут давать $33\cdot 33=1089$ ($26\cdot 26=676$) возможных диграмм, которые будут мало повторяться, если только текст не будет слишком большим. В итоге избыточность зашифрованных сообщений будет невысокой, в то время, как в сообщении будет использоваться большое число различных символов, что является серьёзными препятствиями для криптоанализа.

Примеры, получившие известность

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

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

Омофоническая замена в природе

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

Литература

• Саймон Сингх. Глава 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.