Дэвид Кан - Взломщики кодов

• Название: Взломщики кодов
• Автор: Дэвид Кан
• Издательство: Центрполиграф
• Жанр: Прочая околокомпьтерная литература
• Год: 2000
• ISBN: 5-227-00678-4

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

---

В тех случаях, когда изобретатели и предприниматели учитывают явления, связанные с частотами встречаемости букв, они могут получить значительную дополнительную прибыль. Наиболее ярким примером является Ф. Морзе. В 1838 г. он решил использовать алфавитную систему сигналов для своего только что изобретенного электромагнитного телеграфа. Морзе сосчитал буквы в наборной кассе типографии одной филадельфийской газеты и присвоил наиболее короткие сочетания из точек и тире самым частым буквам.

За небольшими исключениями Морзе придерживался этого правила и при создании своего знаменитого кода, поставив в соответствие самый короткий знак (точку) самой распространенной букве («е»), другой короткий знак (тире) – следующей часто встречающейся букве («t») и т. д. При использовании современного кода Морзе, слегка отличающегося от его первоначального варианта, на передачу телеграммы из 100 букв на английском языке требуется около 940 знаков. Если бы код Морзе был составлен произвольным образом, то на такую же телеграмму потребовалось бы около 1160 знаков, или примерно на 23% больше. Благодаря проницательности изобретателя, принесшей, кстати, значительные денежные выгоды его потомкам, стало возможно передавать за один сеанс почти на 25% больше телеграмм, чем в случае, если бы Морзе составлял свой код наугад.

Из этих примеров видно, что частоты букв действительно довольно постоянны. Неоднократно проведенные опыты по их подсчету подтверждают этот факт. Например, восемь немецких криптоаналитиков независимо друг от друга подсчитали частоту буквы «е» в различных текстах на родном языке объемом примерно в тысячу букв. Полученные ими результаты колеблются от 16 до 19,2%. Эти цифры можно сравнить с подсчетом частот встречаемости букв, проведенным в лингвистических целях немецким филологом Ф. Кёдингом в 1898 г. Его подсчет можно принять за эталон: Кёдинг обработал 59298274 буквы, извлеченные из 20 миллионов слогов немецкого языка. Среди них он насчитал 10598015 букв «е», или 17,9%. Интересно, что средняя цифра от восьми результатов аналогичных подсчетов на текстах меньшего объема составляет 18%, то есть отклонение от нормы, полученной Кёдингом, составляет лишь одно «е» на тысячу букв. Получается, что любой человеческий язык укладывается в строгие статистические нормы!

В чем причина этого поразительного явления? Ответ можно найти с помощью разработанной после Второй мировой войны теории, которая называется «теория информации». Предметом ее изучения являются математические законы, которым подчиняются системы передачи данных. Созданная для решения проблем телефонии и телеграфии, она оказалась применима практически ко всем устройствам, передающим информацию, включая компьютеры и нервную систему животных. Ее идеи оказались настолько плодотворными, что были взяты на вооружение другими науками – психологией, лингвистикой, молекулярной генетикой, историей, статистикой и нейрофизиологией. Создатель этой теории стал также родоначальником ее применения в криптографии.

Клод Шеннон родился в городе Петоски в штате Мичиган 30 апреля 1916 г. Поступив в Мичиганский университет, Шеннон занялся серьезным изучением электротехники и математики. Именно там у него впервые проявился интерес к теории связи и криптографии.

В Массачусетском технологическом институте Шеннон написал диссертацию, в которой содержалось множество новаторских идей, связанных с разработкой телефонных систем. Получив степень доктора математических наук, Шеннон поступил на службу в лабораторию компании «Белл», которая была заинтересована в реализаций этих идей на практике.

«Во время Второй мировой войны,

– рассказывал Шеннон, -

компания «Белл» работала над засекречиванием информации. Я тогда занимался системами связи и был назначен в несколько комиссий, изучавших криптоаналитические методы. Начиная примерно с 1941 г., исследования в области математической теории связи и теории шифров велись мной одновременно. Я трудился в обеих областях сразу, и кое-какие идеи в одной из них возникали у меня, когда я работал в другой. Я не хочу сказать, что одна из этих областей доминирует над другой. Просто они настолько тесно связаны, что их невозможно разделить».

Хотя разработка обеих теорий была в основном завершена примерно к 1944 г., Шеннон продолжал уточнять полученные результаты до 1948-1949 гг., когда они были опубликованы в виде двух отдельных статей в солидном теоретическом журнале «Белл систем текникал джорнэл».

В обеих статьях Шеннона – «Математическая теория связи» и «Теория связи в секретных системах» – идеи излагаются в краткой, математической форме. Обе они изобилуют выражениями вроде «должно существовать единственное обратное преобразование» и формулами вида «TjRj(TkRl)-1TmRn». Тем не менее точный и выразительный стиль изложения Шеннона вдохнул в них жизнь. В результате его первая статья породила теорию информации, а вторая – теорию шифров.

Главной в работах Шеннона является концепция избыточной информации. В его интерпретации слово «избыточность» сохраняет свое основное значение ненужного избытка, но оно уточняется и расширяется. Избыточность, по Шеннону, означает, что в сообщении содержится больше символов, чем в действительности требуется для передачи информации. В простом примере, который привел сам Шеннон, входящая в сочетание «qu» буква «u» – лишняя, поскольку в английских словах «u» всегда стоит после «q». По его мнению, также не обязателен и определенный артикль, употребляемый перед существительными во множественном числе. Ведь, посылая телеграммы, англичане прекрасно обходятся без него.

Насколько велика избыточность английского языка, наглядно демонстрируют некоторые из военных сообщений, которые спрессовываются в «черную магию» сокращенных слов и выражений вроде: «off pres on AD for an indef per». Человек посвященный без особых затруднений прочтет: «officer present on active duty for an indefinite period»124. Эта избыточность связана с излишком правил, обременяющих все языки.

Одни правила, приводящие к избыточности, можно найти в грамматике («I am», а не «I is»), другие – в фонетике (ни одно из английских слов не может начинаться на «ng»), третьи – в идиомах (после глагола «believe» не может стоять глагол в инфинитиве). Четвертые основаны на различного рода ограничениях, налагаемых на словарь. Пользуясь языком, гораздо более избыточным и ограниченным, чем речь взрослых, подросток говорит «swell»125 для выражения одобрительного отношения, передать которое старший по возрасту может с помощью доброго десятка других слов. Как писал Шеннон: «Две крайности избыточности в английском языке представлены словарным запасом „бэйсик инглиш“126 и книгой Джеймса Джойса127 «Поминки по Финнегану». Словарь первого ограничен 850 словами, его избыточность очень велика. Это отражается в расширении, происходящем при переводе какого-нибудь отрывка из «Поминок по Финнегану» на «бэйсик инглиш». Со своей стороны, Джойс увеличивает словарь и этим самым, как утверждают, достигает сжатости семантического содержания».

Еще два источника избыточности имеют особое значение, учитывая их влияние на таблицу частот встречаемости букв. Один из них берет свое начало от различных связей, к которым так часто обращаются люди и которые, естественно, отражаются в языке. Это связи одного лица или предмета с другим («the son of John»128 или «the book on the table»129) и какого-то предмета с действием («put it down»130). Английский язык выражает такие связи отдельными словарными единицами, называемыми «словами-функциями». Местоимения, предлоги, артикли и союзы – все это слова-функции. Некоторые из них служат для задания чисто грамматических связей, являясь своего рода лингвистической стенографией: говорят «я» вместо того, чтобы все время повторять свое имя. Слова-функции самостоятельного значения не имеют. Но они входят в число наиболее распространенных слов английского языка, так как передаваемые ими связи встречаются чаще других. Всего лишь десяток английских слов («the», «of», «and», «to», «a», «in», «that», «it», «is» и «I») занимает более ? любого текста. Преобладание этих слов неизбежно влияет на таблицу частот встречаемости. Например, своим появлением в ней буква «h» в большинстве случаев бывает обязана только определенному артиклю «the».

Второй источник языковой избыточности проистекает из человеческой лености, которая заставляет людей выбирать легко выговариваемые и узнаваемые звуки. На произнесение глухих согласных «р», «t», «k» тратится меньше энергии, чем на соответствующие звонкие согласные «b», «d», «g». Поэтому частота первых в среднем вдвое превосходит частоту вторых в 16 различных языках. Равным образом и краткие гласные звуки используются заметно чаще, чем долгие гласные или дифтонги131.

Всякий, кто желает овладеть каким-то языком, предварительно должен узнать лингвистические правила, которые, собственно, и порождают присущую вожделенному языку избыточность. Знание этих правил позволяет находить и исправлять ошибки, появляющиеся при передаче сообщений. Если, например, в телеграмме на английском языке будет пропущена одна точка и буква «i» («..») в слове «individual»132 превратится в «е» («.»), получатель телеграммы сообразит, что сделана ошибка, так как в английском языке слова «endividual» нет. Когда в языке нет избыточности, как в случае с телефонными номерами, где одна неправильно набранная цифра приводит к вызову другого абонента, люди сами привносят ее. Они повторяют номер, сообщая его кому-либо, а при передаче фамилий они обычно говорят: «б – Борис, о – Ольга…» Объясняется это просто: чем больше избыточность, тем легче обнаружить ошибки. Если в деловом письме получатель встретится с последовательностью «rhe company», он выделит «rhe» как несуществующее слово, вспомнит, что правила английского языка позволяют поставить перед словом «company»133 определенный артикль, учтет, что на клавиатуре пишущей машинки «г» соседствует с «t», и придет к выводу, что вместо «rhe» должно стоять «the».