Коды математики

DjVu

      ПРЕДИСЛОВИЕ
      Право же, не будет ошибкой предположить, что у большинства читателей слова «код», «кодирование» вызывают примерно одинаковые представления. Ведь все хорошо знают, что коды или шифры используются для передачи секретной информации. Менее известно, однако, что в наше время коды приобрели и иное значение, быть может, более обыденное, но зато куда более важное и широкое. В этой их новой роли коды и кодирование — прежде всего средство для экономной, удобной и практически безошибочной передачи сообщений. Новые применения кодов сложились в результате бурного развития различных средств связи, неизмеримо возросшего объема передаваемой информации.
      Решать возникшие в связи с этим задачи было бы невозможно без привлечения самых разнообразных математических методов. Неслучайно поэтому теория кодирования считается сейчас одним из наиболее важных разделов прикладной математики. Желание познакомить широкий круг читателей с задачами и методами этой теории и является основной нашей целью. Все же немного места уделили мы также кодам в их изначальном смысле — как средству обеспечения секретности.
      Первая часть книги (§§ 1—10) написана вполне элементарно, и для ее понимания читателю достаточно ознакомиться с приложением 1, содержащим простейшие сведения о сравнениях.
      В дальнейшем изложении, однако, существенно исполь-вуются основные факты линейной алгебры, а также факты, связанные с понятиями поля и группы. Все необходимые определения и теоремы содержатся в приложениях 2—5.
      Не освоившись с материалом этих приложений, читатель не смог бы свободно ориентироваться во второй части книги.
      В заключение отметим, что в конце большинства параграфов имеется раздел «Задачи и дополнения», где рассматриваются некоторые более специальные и, как правило, более трудные вопросы, а также приводятся задачи для самостоятельного решения. Читателю, желающему основательно разобраться в содержании книги, мы рекомендуем не пренебрегать этими задачами.
      М. И. Аршинов, Л. Е. Садовский
     
      1. КОДИРОВАНИЕ - ИСТОРИЯ И ПЕРВЫЕ ШАГИ
      Коды появились в глубокой древности в виде криптограмм (по-гречески — тайнописи), когда ими пользовались для засекречивания важного сообщения от тех, кому оно не было предназначено. Уже знаменитый греческий историк Геродот (V век до и. э.) приводил примеры писем, понятных лишь для одного адресата. Спартанцы имели специальный механический прибор, при помощи которого важные сообщения можно было писать особым способом, обеспечивающим сохранение тайны. Собственная секретная азбука была у Юлия Цезаря. В средние века и эпоху Возрождения над изобретением тайных шифров трудились многие выдающиеся люди, в их числе философ Фрэнсис Бэкон, крупные математики Франсуа Виет, Джероламо Кардано, Джон Валлис.
      С течением времени начали появляться по-настоящему сложные шифры. Один из них, употребляемый и поныне, связан с именем ученого аббата из Вюрцбурга Тритемиуса, которого к занятиям криптографией побуждало, быть может, не только монастырское уединение, но и потребность сохранять от огласки некоторые духовные тайны. Различные хитроумные приемы кодирования применяли шифровальщики при папском дворе и дворах европейских королей. Вместе с искусством шифрования развивалось и искусство дешифровки, или, как говорят, криптоанализа.
      Секретные шифры являются неотъемлемой принадлежностью многих детективных романов, в которых действуют изощренные в хитрости шпионы. Писатель-романтик Эдгар По, которого иногда причисляют к создателям детективного жанра, в своем рассказе «Золотой жук» в художественной форме изложил простейшие приемы шифрования и расшифровки сообщений. Эдгар По относился к проблеме расшиф-
      ровки оптимистически, вложив в уста своего героя следующую фразу: «...едва ли разуму человека дано загадать такую загадку, которую разум другого его собрата, направленный должным образом, не смог бы раскрыть. Прямо скажу, если текст зашифрован без грубых ошибок и документ в приличной сохранности, я больше ни в чем не нуждаюсь; последующие трудности для меня просто не существуют». Столетие спустя это высказывание было опровергнуто ученым, заложившим основы теории информации, Клодом Шенноном. Шеннон показал, как можно построить криптограмму, которая не поддается никакой расшифровке, если, конечно, не известен способ ее составления.
      О некоторых приемах криптографии и криптоанализа мы расскажем в следующем параграфе, в остальных частях книги речь будет идти в основном об ином направлении в кодировании, которое возникло уже в близкую нам эпоху. Связано оно с проблемой передачи сообщений по линиям связи, без которых (т. е. без телеграфа, телефона, радио, телевидения и т. д.) немыслимо наше нынешнее существование. В задачу такого кодирования, как уже говорилось, входит отнюдь не засекречивание сообщений, а иная цель: сделать передачу сообщений быстрой, удобной и надежной. Предназначенное для этой цели кодирующее устройство сопоставляет каждому символу передаваемого текста, а иногда и целым словам или фразам (сообщениям) определенную комбинацию сигналов (приемлемую для передачи по данному каналу связи), называемую кодом или кодовым словом. При этом операцию перевода сообщений в определенные последовательности сигналов называют кодированием, а обратную операцию, восстанавливающую по принятым сигналам (кодовым словам) передаваемые сообщения, декодированием.
      Заметим сразу же, что различные символы или сообщения должны кодироваться различными кодовыми словами, в противном случае по кодовым словам нельзя было бы восстановить передаваемые сообщения.
      Исторически первый код, предназначенный для передачи сообщений, связан с именем изобретателя телеграфного аппарата Сэмюэля Морзе и известен всем как азбука Морзе. В этом коде каждой букве или цифре сопоставляется своя последовательность из кратковременных (называемых точками) и длительных (тире) импульсов тока, разделяемых паузами. Другой код, столь же широко распространенный в телеграфии (код Бодо), использует для кодирования два элементарных сигнала — импульс и паузу, при этом сопоставляемые буквам кодовые слова состоят из пяти таких сигналов.
      Коды, использующие два различных элементарных сигнала, называются двоичными. Удобно бывает, отвлекаясь от их физической природы, обозначать эти два сигнала символами 0 и 1. Тогда кодовые слова можно представлять как последовательности из нулей и единиц.
      Двоичное кодирование тесно связано с принципом дихотомии (деления пополам). Поясним этот принцип на примере.
      Некто задумал число, заключенное между 0 и 7. Угадывающему разрешено задавать вопросы, ответы на которые даются лишь в форме «да» или «нет». Каким образом следует задавать вопросы, чтобы возможно быстрее узнать задуманное число?
      Самый бесхитростный путь — перебирать числа в любом порядке, надеясь на удачу. В этом случае при везении может хватить и одного вопроса, но если не повезет, то может понадобиться и целых семь. Поэтому не будем рассчитывать на везение и постараемся построить такую систему вопросов, чтобы любой из ответов — «да» или «нет» — давал нам одинаковую (пусть сначала и неполную) информацию о задуманном числе. Например, первый вопрос может бытьтаким: «Заключено ли задуманное число в пределах от 0 до 3?» Оба ответа — и «да» и «нет» — одинаково приближают нас к цели: в любом случае остаются четыре возможности для неизвестного числа (а первоначально их было восемь).
      Если на первый вопрос получен утвердительный ответ, то во второй раз можно спросить: «Не является ли задуманное число нулем или единицей?»; если же ответ был отрицательным, спросим: «Не является ли задуманное число четверкой или пятеркой»? В любом случае после ответа на второй вопрос останется выбор из двух возможностей. Для того чтобы его осуществить, достаточно одного вопроса. Итак, для угадывания задуманного числа, каким бы оно ни было, достаточно трех вопросов (каждый из них выясняет, содержится ли задуманное число в «нижней» половине заключающего его промежутка). Можно показать, что меньшего числа вопросов недостаточно.
      Если возможные ответы «да» или «нет» обозначить условно символами 0 и 1, то ответы запишутся в виде последовательности, состоящей из нулей и единиц. Так, например, если задуманное число было нулем, то на каждый из трех вопросов ответом будет «да». Трем «да» соответствует последовательность 000.
      Если было задумано число 8, то ответами будут «да», «нет», «нет», т. е. числу 3 соответствует последовательность 011. По результатам ответов можно составить следующую таблицу:
      (...)
     
      2. ШИФРЫ, ШИФРЫ, ШИФРЫ...
      Приемов тайнописи — великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое. Наиболее простой тип криптограмм — это так называемые подстановочные криптограммы. Составляя их, каждой букве алфавита сопоставляют определенный символ (иногда тоже букву) и при кодировании всякую букву текста заменяют на соответствующий ей символ. В рассказе «Золотой жук» Эдгара По приводится как раз пример подстановочного шифра.
      Автор рассказа наглядно демонстрирует, что расшифровка подобных криптограмм не составляет большой проблемы. Все основывается на том (за подробностями отсылаем читателя к оригиналу), что различные буквы естественного языка — английского, русского или какого-либо другого — встречаются в осмысленных текстах неодинаково часто. Следовательно, то же самое верно для соответствующих им знаков. В еще большей мере это относится к буквосочетаниям из двух или нескольких букв: лишь некоторые из них часты, многие же вообще не употребляются.
      Промежутки с единицами
      Анализируя частоту появления тех или иных знаков и их сочетаний (именно так поступает герой Эдгара По), можно с большой уверенностью восстановить буквы зашифрованного текста. Даже если в каких-то частях текста возникает неоднозначность, она легко устраняется по смыслу. Этот метод (он именуется частотным анализом) основывается, таким образом, на заранее известных частотах зашифрованных знаков. В следующей таблице указаны относительные частоты букв русского языка.
      Буквы «е» и «ё», а также «ь», «ъ» кодируются обычно одинаково, поэтому в таблице они не различаются. Кик явствует из таблицы, наиболее частая буква русского языка — «о». Ее относительная частота, равная 0,090, означает, что на 1000 букв русского текста приходится в среднем 90 букв «о». В таком же смысле понимаются относительные частоты и остальных букв. В таблице 2 не указан еще один «символ» — промежуток между словами. Его относительная частота наибольшая и равна 0,175.
      С помощью таблицы 2 читатель сумеет, по-видимому, расшифровать такую криптограмму (расшифровку и пояснения см. в дополнении 1 на стр. 15):
      Цярснсмщи ямякзж онкдждм мд снкыйн гкю онгрсямнб-нцмщф йпзоснвпялл мн б гптвзф рктцяюф нм ркнемдд.
      Ненадежность подстановочных криптограмм (сравнительная легкость их расшифровки) была замечена уже давно, и потому в разное время предлагались различные другие методы шифрования. Среди них важное место занимают перестановочные криптограммы. При их составлении весь текст разбивается на группы, состоящие из одинакового числа букв, и внутри каждой группы буквы некоторым образом переставляются. Если группа достаточно длинная (иногда это весь текст целиком), то число возможных перестановок очень велико, отсюда большое многообразие перестановочных криптограмм. Мы рассмотрим один тип перестановочной криптограммы, которая составляется при помощи так называемого ключевого слова. Буквы текста, который должен быть передан в зашифрованном виде, первоначально записываются в клетки прямоугольной таблицы, по ее строчкам. Буквы ключевого слова пишутся над столбцами и указывают порядок (нумерацию) этих столбцов способом, объясняемым ниже. Чтобы получить закодированный текст, надо выписывать буквы по столбцам с учетом их нумерации. Пусть текст таков: «В связи с создавшимся положением отодвигаем сроки возвращения домой. Рамзай». Используем для записи текста, в котором 65 букв, прямоугольную таблицу 11x6, в качестве ключевого возьмем слово из 6 букв «запись», столбцы занумеруем в соответствии с положением букв ключевого слова в алфавите. В результате получится следующая кодовая таблица:
     
      Выписывая буквы из столбцов таблицы 3 (сначала из первого, затем из второго и т. д.), получаем такую шифровку:
      Ссшоидмвщомвсвпнееиадаязмомир-
      зноавоилевсоемзздсжоговийииаяетакряр
      Ключевое слово известно, конечно, и адресату, который поэтому без труда расшифрует это сообщение. Но для тех, кто этим ключом не владеет, восстановление исходного текста весьма проблематично (хотя в принципе и возможно). Частотный анализ здесь по вполне понятным причинам не решает задачи. В лучшем случае, поскольку частоты букв примерно такие, как в таблице 2, он позволяет предположить, что было применено перестановочное кодирование.
      Использование ключевого слова, конечно, не обязательно, можно было указать нумерацию столбцов цифровым ключом, в данном случае числом 214356. Слово удобнее, если ключ надо хранить в памяти (что немаловажно для конспирации).
      Имеется ряд шифров, в которых совмещены приемы подстановочного и перестановочного кодирования. Шифр можно еще более усложнить, если дополнительно к этому каждую букву заменять не одним, а двумя или несколькими символами (буквами или числами). Вот Пример. Расположим буквы русского алфавита в квадратной таблице 6x6 произвольным образом, например так, как в следующей таблице.
      Таблица 4
      Каждую букву шифруем парой цифр: первая цифра это номер строци, в которой стоит данная буква, вторая —¦ номер столбца. Например, букве «б» соответствует обозначение 21, а слову «шифр» — обозначение 51022304.
      Еще большие трудности для крйптоанализа представляет шифр, связываемый с именем Тритемцуса. Этот шифр
      является развитием рассматриваемого в дополнении 2 кода Цезаря и состоит в следующем. Буквы алфавита нумеруются по порядку числами 0, 1, , 30 (см. табл. 2). При шифровании ключевое слово (или номера его букв) подписывается под сообщением с повторениями, как показано ниже: всвязиссоздавшимсяположениемотодвигаемсрокивозвра записьзаписьзаписьзаписьзаписьзаписьзаписьзаписьз щени ядомойр амзай аписьзаписьзапис
      (...)
      Чрезвычайно трудно расшифровать подобный текст, если ключ неизвестен, хотя в истории криптографии были случаи, когда такие тексты разгадывались. Дело в том, что повторяемость ключевого слова накладывает некоторый отпечаток на криптограмму, а это может быть обнаружено статистическими методами, которые позволяют судить о длине ключевого слова, после чего расшифровка значительно упрощается.
      Мы рассмотрели лишь некоторые способы составления криптограмм. Заметим, что комбинируя их, можно получать шифры, еще более труднодоступные для расшифровки. Однако вместе с этим возрастают трудности пользования шифром для отправителя секретного сообщения и адресата, поскольку сильно усложняется техника шифровки и дешифровки даже при наличии ключа
      Задачи и дополнения
      1. Для расшифровки криптограммы на стр. 11 подсчитаем, сколько раз встречается в ней каждая буква. Результаты подсчета приведены в следующей таблице:
      Таблица 6
      Число появлений в тексте 11 9 6655433333 3222222221 1 1
      Наиболее часто встречающийся символ «н» скорее Fcero означает букву «о». Сделав такое предположение, рассмотрим следующий по частоте символ «м». В криптограмме имеется двубуквенное сочетание «мн», и так как «н» — это «о», то символ «м» соотпетству. г согласной.
      Среди согласных в русском языке выделяются по частоте буквы «т» и <сн» (см. табл. 2), и потому «м» скорее всего означает одну из этих букв. разберем случай, когда «м» означает «н», предоставляя читателю самостоятельно убедиться, что другая возможность не приводит к осмысленной расшифровке криптограммы.
      Если «м»—это «н», то в сочетании «мд», встречающемся в криптограмме, «д» означает.скорее всего гласную. Из наиболее вероятных длЯ «Д» вариантов «а», «е», «и» выбираем «е», потому что лишь в этом случае имеющееся в криптограмме слово «ркнемдд» допускает осмысленную расшифровку. Итак три знака разгаданы: «и» — это «о», «м» — «н», «д» — «е». Обращаемся к сочетанию «ямякзж». В нем «я» может означать лигиь гласную «а» или «и». Любые другие возможности заведомо не допускают разумного прочтения слова «ямякзж». Испытаем букву «а». ПоДставляя вместо «я» букву «а», вместо «м» — «н», вместо других знаков — точки, получим недописанное слово «ана...». В словаре имеется всего лишь несколько слов из 6 букв с таким началом: «анализ», «аналог*» «ананас», «анатом». Из них годится лишь первое (почему?). Если вместо «я» подставить букву «и», то получится шестибуквенное сочетание с рачалом «ини», но в словаре нет ни одного такого слова. Расшифрованы еще четыре буквы: «я», «к», «з», «ж» означают соответственно «а», «л».
      KOHEЦ ФPAГMEHTA КНИГИ