Русская Википедия:Омофоническая замена

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

История

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

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

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

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

Шифрование

Пусть <math>i</math> — символ алфавита, который используется в открытом тексте. Для каждого <math>i</math> составим множество символов <math>M_i</math>, таким образом, чтобы для различных символов <math>i</math> и <math>j</math> множества <math>M_i</math> и <math>M_j</math> не пересекались. Обычно элементами множества <math>M_i</math> являются числа. При омофоническом шифровании, число замен для каждого символа берется пропорционально вероятности появления этого символа в открытом тексте. При шифровании замена для символа открытого текста выбирается либо случайным образом (генератор случайных чисел), либо определенным образом (например, по порядку). Чтобы запомнить буквы, которые чаще всего встречаются в текстах, используют комбинации букв «сеновалитр» и «tetrishonda» для русского и английского языков соответственно. Эти комбинации похожи на слова, а потому легко запоминаютсяШаблон:Sfn.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ключ для первого получателя
А 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. Каждое число мы будем использовать только единожды. В случае, если диграмма повторилась, возьмем для неё новое число, которое будет больше максимального, имеющегося в алфавите. В нашем случае получится шифртекст «<math>13</math> <math>9</math> <math>2</math> <math>32</math> <math>37</math> <math>19</math> <math>27</math> <math>10</math> <math>8</math> <math>38</math> <math>39</math> <math>3</math>»
  2. После завершения шифрования удалим из матрицы все неиспользованные элементы
  3. Страница шифрблокнота с минимальной избыточностью может быть получена заменой всех чисел различными случайными числами. Очевидно, что в таком случае мы можем получить шифртекст «<math>1</math> <math>2</math> <math>3</math> <math>4</math> <math>5</math> <math>6</math> <math>7</math> <math>8</math> <math>9</math> <math>10</math> <math>11</math> <math>12</math>». Ключ-таблица диграмм и ключи для каждого из получателей для такого набора сообщений сократятся до минимально возможныхШаблон:Sfn.
А Л М Р У Ы
А 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

Если прочитать буквы в порядке, указанном соответствующими каждой букве числами, получится открытый текст. Из-за этого использование такого шифра становится невозможным, так как для получения открытого текста злоумышленнику будет достаточно иметь ключ, не имея даже закрытого текста. Это делает бессмысленным уменьшение избыточности текста. С другой стороны, использованная ранее матричная форма омофонической замены второго порядка имеет достаточно хорошую криптостойкость, если использовать полный алфавит. Два текста будут давать <math>33\cdot33=1089</math> (<math>26\cdot26=676</math>) возможных диграмм, которые будут мало повторяться, если только текст не будет слишком большим. В итоге избыточность зашифрованных сообщений будет невысокой, в то время, как в сообщении будет использоваться большое число различных символов, что является серьезными препятствиями для криптоанализаШаблон:Sfn.

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

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки


Шаблон:Добротная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Статья
  2. ↑ Шаблон:Статья
  3. ↑ Шаблон:Статья
  4. ↑ Шаблон:Статья
  5. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Омофоническая_замена&oldid=10515965