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

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

14.12.2020

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

История

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

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

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

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

Шифрование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Каждое число мы будем использовать только единожды. В случае, если диграмма повторилась, возьмем для неё новое число, которое будет больше максимального, имеющегося в алфавите. В нашем случае получится шифртекст « 13 {displaystyle 13} 9 {displaystyle 9} 2 {displaystyle 2} 32 {displaystyle 32} 37 {displaystyle 37} 19 {displaystyle 19} 27 {displaystyle 27} 10 {displaystyle 10} 8 {displaystyle 8} 38 {displaystyle 38} 39 {displaystyle 39} 3 {displaystyle 3} »
  • После завершения шифрования удалим из матрицы все неиспользованные элементы
  • Страница шифрблокнота с минимальной избыточностью может быть получена заменой всех чисел различными случайными числами. Очевидно, что в таком случае мы можем получить шифртекст « 1 {displaystyle 1} 2 {displaystyle 2} 3 {displaystyle 3} 4 {displaystyle 4} 5 {displaystyle 5} 6 {displaystyle 6} 7 {displaystyle 7} 8 {displaystyle 8} 9 {displaystyle 9} 10 {displaystyle 10} 11 {displaystyle 11} 12 {displaystyle 12} ». Ключ-таблица диграмм и ключи для каждого из получателей для такого набора сообщений сократятся до минимально возможных.
  • Если прочитать буквы в порядке, указанном соответствующими каждой букве числами, получится открытый текст. Из-за этого использование такого шифра становится невозможным, так как для получения открытого текста злоумышленнику будет достаточно иметь ключ, не имея даже закрытого текста. Это делает бессмысленным уменьшение избыточности текста. С другой стороны, использованная ранее матричная форма омофонической замены второго порядка имеет достаточно хорошую криптостойкость, если использовать полный алфавит. Два текста будут давать 33 ⋅ 33 = 1089 {displaystyle 33cdot 33=1089} ( 26 ⋅ 26 = 676 {displaystyle 26cdot 26=676} ) возможных диграмм, которые будут мало повторяться, если только текст не будет слишком большим. В итоге избыточность зашифрованных сообщений будет невысокой, в то время, как в сообщении будет использоваться большое число различных символов, что является серьезными препятствиями для криптоанализа.

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

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

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

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

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