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

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

История

Шифрование методом омофонической замены известно с XV века^[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].

Вероятность появления букв русского алфавита
Буква Вероятность А 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. В таком случае для самого редкого элемента понадобится ровно один символ^[4].

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

№	А	Б	В	…	Е	…	О	П	Р	…	Э	Ю	Я
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

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

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

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

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

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

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

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

	А	Л	М	Р	У	Ы
А	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

Каждая строка и каждый столбец сопоставлены с одним из символов алфавита первого и второго открытых текстов соответственно. Теперь каждой диграмме соответствует некоторое число (на пересечении соответствующих строк и столбцов), следовательно, заменяя диграмму на соответствующее число, мы можем зашифровать тексты. Матрица с числами, соответствующими диграммам, играет в данном случае роль ключа. Чтобы сохранить полную матрицу в секрете, её разделяют на две матрицы: одна получается сортировкой элементов строк, другая — сортировкой столбцов и транспонированием. На выходе мы будем иметь две матрицы, в каждой из которых элементы в строках упорядочены по возрастанию (убыванию), а одну матрицу можно использовать для получения только одного открытого текста. Для примера взяты тексты с одинаковыми алфавитами, так как предполагается, что в общем случае для создания шифра будет использован весь алфавит и что шифр должен охватывать все возможные диграммы^[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. Каждое число мы будем использовать только единожды. В случае, если диграмма повторилась, возьмём для неё новое число, которое будет больше максимального, имеющегося в алфавите. В нашем случае получится шифротекст «${\displaystyle 13}$ ${\displaystyle 9}$ ${\displaystyle 2}$ ${\displaystyle 32}$ ${\displaystyle 37}$ ${\displaystyle 19}$ ${\displaystyle 27}$ ${\displaystyle 10}$ ${\displaystyle 8}$ ${\displaystyle 38}$ ${\displaystyle 39}$ ${\displaystyle 3}$»
2. После завершения шифрования удалим из матрицы все неиспользованные элементы
3. Страница шифроблокнота с минимальной избыточностью может быть получена заменой всех чисел различными случайными числами. Очевидно, что в таком случае мы можем получить шифротекст «${\displaystyle 1}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle 4}$ ${\displaystyle 5}$ ${\displaystyle 6}$ ${\displaystyle 7}$ ${\displaystyle 8}$ ${\displaystyle 9}$ ${\displaystyle 10}$ ${\displaystyle 11}$ ${\displaystyle 12}$». Ключ-таблица диграмм и ключи для каждого из получателей для такого набора сообщений сократятся до минимально возможных^[11].

А Л М Р У Ы А 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

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

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

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

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

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

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