Исторические основы криптологии (стр. 12 из 15)

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

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

Поступив в 1921 г. на службу в войска связи, У. Фридман успешно применял свои методы для вскрытия машинных шифров. Когда была создана служба радиоразведки, У.Фридман стал ее главой и продолжил свои разработки, самой значимой из которых было вскрытие японской пурпурной шифрмашины. В 1929 г. он стал широко известен как один из ведущих криптографов мира, когда "Британская энциклопедия" поместила его статью "О кодах и шифрах". С основными результатами У. Фридмана можно познакомиться в четырехтомнике "Военная криптография".

Выдающиеся результаты в применении математических методов в криптографии принадлежат Клоду Шеннону. К. Шеннон получил образование по электронике и математике в Мичиганском университете, где и начал проявлять интерес к теории связи и теории шифров. В 1940 г. он получил степень доктора по математике, в течение года обучался в Принстонском институте усовершенствования, после чего был принят на службу в лабораторию компании "BellTelephone".

К 1944 г. К. Шеннон завершил разработку теории секретной связи. В 1945 г. им был подготовлен секретный доклад "Математическая теория криптографии", который был рассекречен в 1949 г. и издан.

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

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

Центральной в работах К. Шеннона является концепция избыточной информации, содержащейся в текстовых сообщениях. Избыточность означает, что в сообщении содержится больше символов, чем в действительности требуется для передачи содержащейся в нем информации. Например, всего лишь десять английских слов — the, of, and, to, a, in, that, it, is, i — составляют более 25% любого (английского) текста. Легко понять, что их можно изъять из текста без потери информации, так как их легко восстановить по смыслу (или по контексту). Фактически К.Шеннон показал, что успех криптоанализа определяется тем, насколько избыточность, имеющаяся в сообщении, "переносится" в шифрованный текст. Если шифрование "стирает" избыточность, то восстановить текст сообщения по криптограмме становится принципиально невозможно.

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

Пусть для зашифрования нормативного английского языка применяется шифр простой замены, в котором каждый из 26! ключей может быть выбран с равной вероятностью. Пусть противник знает об источнике сообщений лишь то, что он создает английский текст. Тогда априорными вероятностями различных сообщений из N букв являются их относительные частоты в нормативном тексте. Если же противник перехватил крипто грамму из N букв, то он может вычислить условные вероятности открытых текстов и ключей, которые могут создать такую криптограмму. Если N достаточно велико, скажем N = 50, то обычно имеется единственное сообщение (и единственный ключ) с условной вероятностью, близкой к единице (это — само сообщение, подвергнутое шифрованию), в то время как все другие сообщения имеют суммарную вероятность, близкую к нулю. Таким образом, имеется, по существу, единственное "решение" такой криптограммы. Для меньших значений N, скажем N = 10, обычно найдется несколько пар сообщений и ключей, вероятности которых сравнимы друг с другом, то есть, нет ни одного сообщения (и ключа) с вероятностью, близкой к единице. В этом случае "решение" криптограммы неоднозначно.

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

Теоретической мерой секретности (или стойкости) по К.Шеннону является энтропийная характеристика — неопределенность шифра по открытому сообщению, которая измеряет (в статистическом смысле), насколько "близка" средняя криптограмма из N букв к единственному "решению". Он выводит формулу для приближенного вычисления минимального N,при котором находится единственное "решение". Такая величина получила название расстояния единственности. Формула для расстояния единственности связывает между собой неопределенность шифра по открытому тексту и избыточность текста. Чем большим оказывается расстояние единственности, тем более шифр приближается к совершенному шифру, для которого формально расстояние единственности равно

.

Наконец, К. Шеннон вводит понятие рабочей характеристики шифра, подходя к практической оценке стойкости. Он формулирует также основные критерии оценки качества секретных систем с позиций практики их использования.

Как видим, К. Шеннону удалось решить фундаментальные проблемы в теоретической криптографии. Его работы стимулировали бурный рост научных исследований по теории информации и криптографии.

В работах К. Шеннона по исследованию свойств языка важную роль играет величина удельной энтропии Н на букву текста, другими словами, среднее количество информации, передаваемой буквой открытого текста. Предложенный им метод экспериментов с угадыванием очередной буквы английского текста по предыдущим буквам оказался неэффективным при получении оценок величины Н для других языков. Метод "отгадывания" развил в своих работах А. Н. Колмогоров. Достаточно точные приближения параметра Н для русского и французского языков получил Б. Б. Пиотровский. Он указал на существенную разницу между значениями Н для текстов различного характера (литературных, деловых, разговорной речи).

Понятие "количества информации", содержащейся в тексте, базировалось, по К. Шеннону, лишь на частотных характеристиках. В своих фундаментальных работах 60-х годов А. Н. Колмогоров подошел к определению количества информации с учетом смыслового содержания текста, что позволило уточнить приближение величины Н для литературных текстов. Необходимо также отметить, что еще задолго до К. Шеннона частотные характеристики языка изучал выдающийся русский ученый А. А. Марков. Сегодня часто используются так называемые марковские модели открытых текстов, учитывающие зависимости букв текста от предыдущих букв.

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

Согласно, идея телефонного шифратора была запатентована Д. Х. Роджерсом еще в 1881 г., спустя пять лет после изобретения Беллом телефона. Идея состояла в передаче телефонного сообщения по нескольким (в простейшем случае — по двум) цепям поочередными импульсами в некоторой быстро изменяющейся последовательности. Предлагалось разнести такие линии на значительное расстояние друг от друга с тем, чтобы устранить возможность подключения сразу ко всем одновременно. Подключение же к одной из них позволяло бы слышать лишь отдельные неразборчивые сигналы.