КОДИРОВАНИЕ И ИСТОРИЯ - ПЕРВЫЕ ШАГИ

Коды появились в глубокой древности в виде криптограмм (по-гречески — тайнописи), когда ими пользовались для засекречивания важного сообщения от тех, кому оно не было предназначено. Уже знаменитый греческий историк Геродот (V век до н. э.) приводил примеры писем, понятных лишь для одного адресата. Спартанцы имели специальный механический прибор, при помощи которого важные сообщения можно было писать особым способом, обеспечивающим сохранение тайны. Собственная секретная азбука была у Юлия Цезаря. В средние века и эпоху Возрождения над изобретением тайных шифров трудились многие выдающиеся люди, в их числе философ Фрэнсис Бэкон, крупные математики Франсуа Виет, Джероламо Кардано, Джон Валлис.

С течением времени начали появляться по-настоящему сложные шифры. Один из них, употребляемый и поныне, связан с именем ученого аббата из Вюрцбурга Тритемиуса, которого к занятиям криптографией побуждало, быть может, не только монастырское уединение, но и потребность сохранять от огласки некоторые духовные тайны. Различные хитроумные приемы кодирования применяли шифровальщики при папском дворе и дворах европейских королей. Вместе с искусством шифрования развивалось и искусство дешифровки, или, как говорят, криптоанализа.

Секретные шифры являются неотъемлемой принадлежностью многих детективных романов, в которых действуют изощренные в хитрости шпионы. Писатель-романтик Эдгар По, которого иногда причисляют к создателям детективного жанра, в своем рассказе «Золотой жук» в художественной форме изложил простейшие приемы шифрования и расшифровки сообщений. Эдгар По относился к проблеме расшифровки оптимистически, вложив в уста своего героя следующую фразу: «...едва ли разуму человека дано загадать такую загадку, которую разум другого его собрата, направленный должным образом, не смог бы раскрыть. Прямо скажу, если текст зашифрован без грубых ошибок и документ в приличной сохранности, я больше ни в чем не нуждаюсь; последующие трудности для меня просто не существуют». Столетие спустя это высказывание было опровергнуто ученым, заложившим основы теории информации, Клодом Шенноном. Шеннон показал, как можно построить криптограмму, которая не поддается никакой расшифровке, если конечно, не известен способ ее составления.

2. ШИФРЫ, ШИФРЫ, ШИФРЫ...

Приемов тайнописи — великое множество, и, скорее всего, это та область, где уже нет нужды придумы­вать что-нибудь существенно новое. Наиболее простой тип криптограмм — это так называемые подстановочные крип­тограммы. Составляя их, каждой букве алфавита сопоставляют определенный символ (иногда тоже букву) и при кодировании всякую букву текста заменяют на соответствующий ей символ. В рассказе «Золотой жук» Эдгара По приводится как раз пример подстановочного шифра.

Автор рассказа наглядно демонстрирует, что расшифровка подобных криптограмм не составляет большой проблемы. Все основывается на том, что различные буквы естественного языка — английского, русского или какого-либо другого — встречаются в осмысленных текстах неодинаково часто. Следовательно, то же самое верно для соответствующих им знаков. В еще большей мере это относится к буквосочетаниям из двух или нескольких букв: лишь некоторые из них часты, многие же вообще не употребляются.

Анализируя частоту появления тех или иных знаков и их сочетаний (именно так поступает герой Эдгара По), можно с большой уверенностью восстановить буквы зашифрованного текста. Даже если в каких-то частях текста возникает неоднозначность, она легко устраняется по смыслу, Этот метод (он именуется частотным анализом) основывается, таким образом, на заранее известных частотах зашифрованных знаков. В следующей таблице указаны относительные частоты букв русского языка.

Буквы «е» и «ё», а также «ь», «ъ» кодируются обычно одинаково, поэтому в таблице они не различаются. Как явствует из таблицы, наиболее частая буква русского языка — «о». Ее относительная частота, равная 0,090, означает, что на 1000 букв русского текста приходится в среднее 90 букв «о». В таком же смысле понимаются относительные частоты и остальных букв. В таблице 1 не указан еще один «символ» — промежуток между словами. Его относительная частота наибольшая и равна 0,175.

Таблица 1. Относительная частота букв русского языка

Ненадежность подстановочных криптограмм (сравнительная легкость их расшифровки) была замечена уже дав но, и потому в разное время предлагались различные другие методы шифрования. Среди них важное место занимают перестановочные криптограммы. При их составлении весь текст разбивается на группы, состоящие из одинакового числа букв, и внутри каждой группы буквы некоторым образом переставляются. Если группа достаточно длинная (иногда это весь текст целиком), то число возможных пере­становок очень велико, отсюда большое многообразие перестановочных криптограмм. Мы рассмотрим один тип перестановочной криптограммы, которая составляется при помощи так называемого ключевого слова. Буквы текста, ко­торый должен быть передан в зашифрованном виде, первоначально записываются в клетки прямоугольной таблицы, по ее строчкам. Буквы ключевого слова пишутся над столбцами и указывают порядок (нумерацию) этих столбцов способом, объясняемым ниже. Чтобы получить закодированный Текст, надо выписывать буквы по столбцам с учетом их нумерации. Пусть текст таков: «В связи с создавшимся положением отодвигаем сроки возвращения домой. Рамзай». Используем для записи текста, в котором 65 букв, прямоугольную таблицу , в качестве ключевого возьмем слово из 6 букв «запись», столбцы занумеруем в соответствии с положением букв ключевого слова в алфавите. В результате получится следующая кодовая таблица:

Таблица 2

Выписывая буквы из столбцов таблицы 2 (сначала из первого, затем из второго и т. д.), получаем такую шифровку:

Ссшоидмвщомвсвпноеиадаязмомирзноавоилевсоемзздсжоговийииаяетакряр

Ключевое слово известно, конечно, и адресату, который поэтому без труда расшифрует это сообщение. Но для тех, кто этим ключом не владеет, восстановление исходного текста весьма проблематично (хотя в принципе и возможно). Частотный анализ здесь по вполне понятным причинам не решает задачи. В лучшем случае, поскольку частоты букв примерно такие, как в таблице 1, он позволяет предполо­жить, что было применено перестановочное кодирование.

Использование ключевого слова, конечно, не обязательно, можно было указать нумерацию столбцов цифровым ключом, в данном случае числом 214356. Слово удобнее, если ключ надо хранить в памяти (что немаловажно для конспирации).

Имеется ряд шифров, в которых совмещены приемы подстановочного и перестановочного кодирования. Шифр можно еще более усложнить, если дополнительно к этому каждую букву заменять не одним, а двумя или несколькими симво­лами (буквами или числами). Вот пример. Расположим буквы русского алфавита в квадратной таблице 6х6 произ­вольным образом, например, так, как в следующей таблице.

Каждую букву шифруем парой цифр: первая цифра это номер строки, в которой стоит данная буква, вторая — номер столбца. Например, букве «б» соответствует обозна­чение 21, а слову «шифр» — обозначение 51022304.

Еще большие трудности для криптоанализа представ­ляет шифр, связываемый с именем Тритемиуса. Этот шифр является развитием рассматриваемого в дополнении 2 кода Цезаря и состоит в следующем. Буквы алфавита нумеруются по порядку числами 0, 1, ... , 30. При шифровании ключевое слово (или номера его букв) подписы­вается под сообщением с повторениями, как показано ниже:

всвязиссоздавшимсяположениемотодвигаемсрокивозвра

записьзаписьзаписьзаписьзаписьзаписьзаписьзаписьз

щениядомойрамзай

аписьзаписьзапис

Каждая буква сообщения «сдвигается» вдоль алфавита по следующему правилу: буква с номером т, под которой стоит буква ключевого слова с номером k, заменяется на букву с номером l=m+k (если m+k<31) или букву с но­мером l=m+k—31 (если m+k≥31). Например, первая буква «в» сдвигается на 7 букв и заменяется буквой «й», следующая буква «с» остается без изменения и т. д. Таким образом, номер l кодирующей буквы вычисляется по формуле:

l=m+k (mod 31).

В цифровых обозначениях исходное сообщение и повторяемое ключевое слово запишутся в следующем виде:

После суммирования по модулю 31 получаем следующую последовательность чисел:

9.17.17.7.24.4.24.17.29.15.21.27.9.24.23.20.3.26.22.14.26. 22.23.1.20.8.20.20.0.14.21.4.17.16.20.27.12.12.1.24.0.6. 15.2.29.15.19.12.7.25.20.21.25.26.11. 14. 27. 22. 26. 12. 7.

12.22.8.26.

Наконец, заменяя числа на буквы, приходим к закодированному тексту:

йссзшдшсюпхьйшчфгыцоыцчбфиффаохдсрфьммбшажпвю

пумзщфхщылоьцымзмциы

Если ключевое слово известно, то дешифровка произво­дится безо всякого труда на основе равенства:

m=l—k (mod 31).

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

  Мы рассмотрели лишь некоторые способы составления   криптограмм. Заметим, что комбинируя их, можно получать шифры, еще более труднодоступные для расшифровки. Однако вместе с этим возрастают трудности пользования шифром для отправителя секретного сообщения и адресата, поскольку сильно усложняется техника шифровки и дешифровки даже при наличии ключа.

Источник информации: Аршинов Н. М., Садовский Л. Е. Коды и математика. – М.: Наука, 1983