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

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

История

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

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

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

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

Шифрование

Пусть $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

(*) В таблице представлены результаты на основе анализа художественных и научно-технических текстов общим объёмом более 1000000 символов. При этой же оценке вероятность "пробела" - 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, "А"-906, тогда зашифрованное слово имеет вид числовой последовательности "325700865095".

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

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

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

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

Особенность данного метода состоит в том, что шифрозамены не повторяются, значит, если у буквы "Ф" - 3 шифрозамены, например "100", "477" и "906", то шифрозамены "100", "477" и "906" обозначают только букву "Ф". Для одного и того же открытого текста может быть составлено множество различных открытых текстов при использовании одного и того же ключа, который представляет из себя таблицу^[4].

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

Пример шифра

E	T	R	I	S	H	…	J	Z
001	124	221	302	383	454	…	998	999
…
123	220	301	382	453

Тогда, например, слово «thetree» будет зашифровано как «152 454 001 186 251 101 057»

Примечание

1. ↑ ^{1 2} Сингх, 2007, p. 70
2. ↑ Кан, 2000, p. 7
3. ↑ ^{1 2} Анисимов, ссылка
4. ↑ ^{1 2} Долгов, 2008, p. 33
5. ↑ Сингх, 2007, p. 72

Литература

Саймон Сингх Глава 2. Нераскрываемый шифр // Книга шифров. Тайная история шифров и их расшифровки = The Code Book by Simon Singh / перевод с английского А. Галыгина. — М.: АСТ, 2007. — Т. 2. — С. 69-74. — 4000 экз. — ISBN 978-5-17-038477-8

Пазизин С. В., Малюк А. А., Пригожин Н. С. Глава 3. Криптографические методы защиты информации // Введение в защиту информации в автоматизированных системах. — М.: Горячая линия - Телеком, 2001. — С. 52. — 3000 экз. — ISBN 5-93517-062-0

Долгов В. А., Анисимов В.В. Глава 5. Шифры замены // Криптографические методы защиты информации. — Хабаровск: Издательство ДВГУПС, 2008. — С. 32-33. — 30 экз.

Арто Саломаа Глава 1. Классическая криптография // Криптография с открытым ключом = Public-Key Cryptography / Под редакцией А. Е. Андреева и А. А. Болотова. — М.: "Мир", 1995. — С. 35. — ISBN 5-03-001991-X

Дэвид Кан Взломщики кодов / Перевод с английского А. Ключевский. — М.: Центрполиграф, 2000. — ISBN 5-227-00678-4

Ссылки

Анисимов В. В. Шифры замены (ru — русский). Криптографические методы защиты информации. Проверено 4 декабря 2012.

Для улучшения этой статьи по информационным технологиям желательно?: Проставить интервики в рамках проекта Интервики. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.