Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Рис. 1. нение
Cq rn-t
n-q+1 =W +
-?+1 = W + l'
4. Используя результаты дополнений 2, 3, убедиться в справедливости тождества:
?=0 '
(символ [л/2] означает наибольшее целое число, не превосходящее л/2).
5. При каком q число двоичных слов из дополнения 3 максимально?
6. Показать, что число всех я-буквенных rf-ичных слов, в которых один из символов встречается фиксированное число t раз, равно Cin (d—1)"_( (ср. дополнение 1).
7. Обобщить результаты дополнений 2 и 3 применительно к d-ччїю-му алфавиту.
2. ШИФРЫ, ШИФРЫ, ШИФРЫ...
Приемов тайнописи — великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое. Наиболее простой тип криптограмм — это так называемые подстановочные криптограммы. Составляя их, каждой букве алфавита сопоставляют определенный символ (иногда тоже букву) и при кодировании всякую букву текста заменяют на соответствующий ей символ. В рассказе «Золотой жук» Эдгара По приводится как раз пример подстановочного шифра.
Автор рассказа наглядно демонстрирует, что расшифровка подобных криптограмм не составляет большой проблемы. Все основывается на том (за подробностями отсылаем читателя к оригиналу), что различные буквы естественного языка — английского, русского или какого-либо другого — встречаются в осмысленных текстах неодинаково часто. Следовательно, то же самое верно для соответствующих им знаков. В еще большей мере это относится к буквосочетаниям из двух или нескольких букв: лишь некоторые из них часты, многие же вообще не употребляются.
10 Анализируя частоту появления тех или иных знаков и их сочетаний (именно так поступает герой Эдгара По), можно с большой уверенностью восстановить буквы зашифрованного текста. Даже если в каких-то частях текста возникает неоднозначность, она легко устраняется по смыслу. Этот метод (он именуется частотным анализом) основывается, таким образом, на заранее известных частотах зашифрованных знаков. В следующей таблице указаны относительные частоты букв русского языка.
Буквы «е» и «ё», а также «ь», «ъ» кодируются обычно одинаково, поэтому в таблице они не различаются. Kax явствует из таблицы, наиболее частая буква русского языка — «о». Ее относительная частота, равная 0,090, означает, что на 1000 букв русского текста приходится в среднем 90 букв «о». В таком же смысле понимаются относительные
Таблица 2
№ Буква Относит, частота № Буква Относит, частота № Буква Относит, частота
0 а 0,062 10 К 0,028 20 Ф 0,002
1 б 0,014 11 л 0,035 21 X 0,009
2 в 0,038 12 M 0,026 22 ц 0,004
3 F 0,013 13 H 0,053 23 ч 0,012
4 д 0,025 14 о 0,090 24 ш 0,006
5 е, ё 0,072 15 п 0,023 25 щ 0,003
6 ж 0,007 16 P 0,040 26 ы 0,016
7 3 0,016 17 с 0,045 27 ь, ъ 0,014
8 и 0,062 18 T 0,053 28 э 0,003
9 й 0,010 19 У 0,021 29 ю 0,006
30 я 0,018
частоты и остальных букв. В таблице 2 не указан еще один «символ» — промежуток между словами. Его относительная частота наибольшая и равна 0,175.
С помощью таблицы 2 читатель сумеет, по-видимому, расшифровать такую криптограмму (расшифровку и пояснения см. в дополнении 1 на стр. 15):
Цярснсмщи ямякзж онкдждм мд снкыйн гкю онгрсямнб-
нцмщф йпзоснвпялл мн б гптвзф рктцяюф нм ркнемдд.
Ненадежность подстановочных криптограмм (сравнительная легкость их расшифровки) была замечена уже дав-
Ii но, и потому в разное время предлагались различные другие методы шифрования. Среди них важное место занимают перестановочные криптограммы, При их составлении весь текст разбивается на группы, состоящие из одинакового числа букв, и внутри каждой группы буквы некоторым образом переставляются. Если группа достаточно длинная (иногда это весь текст целиком), то число возможных перестановок очень велико, отсюда большое многообразие перестановочных криптограмм. Мы рассмотрим один тип перестановочной криптограммы, которая составляется при помощи так называемого ключевого слова. Буквы текста, который должен быть передан в зашифрованном виде, первоначально записываются в клетки прямоугольной таблицы, по ее строчкам. Буквы ключевого слова пишутся над столбцами и указывают порядок (нумерацию) этих столбцов способом, объясняемым ниже. Чтобы получить закодированный текст, надо выписывать буквы по столбцам с учетом их нумерации. Пусть текст таков: «В связи с создавшимся положением отодвигаем сроки возвращения домой. Рамзай». Используем для записи текста, в котором 65 букв, прямоугольную таблицу 11x6, в качестве ключевого возьмем слово из 6 букв «запись», столбцы занумеруем в соответствии с положением букв ключевого слова в алфавите. В результате получится следующая кодовая таблица:
Таблица 3
3 а п и с ь
2 1 4 3 5 6
в с в я 3 и
с с о 3 Д а
D UI и M с я
П о л о ж е
H и е M о T
О д в и г а
е M с P о к
и в о 3 п P
а щ е H и я
Д о M о й P
а M 3 а й Выписывая буквы из столбцов таблицы 3 (сначала из первого, затем из второго и т. д.), получаем такую шифровку:
Ссшоидмвщомвевпиоеиадаязмомирзноавоилевсоемзздс-
жоговийииаяетакряр
Ключевое слово известно, конечно, и адресату, который поэтому без труда расшифрует это сообщение. Но для тех, кто этим ключом не владеет, восстановление исходного текста весьма проблематично (хотя в принципе и возможно). Частотный анализ здесь по вполне понятным причинам не [ ешает задачи. В лучшем случае, поскольку частоты букв примерно такие, как в таблице 2, он позволяет предположить, что было применено перестановочное кодирование.
