Криптография, или тайнопись, вероятно так же стара, как и письменность в целом. Но лишь в последнее время она стала объектом широкомасштабных научных исследований. Одной из причин этого послужило большое число новых приложений в области защиты информации. Возможно, даже более важной причиной огромного роста научных исследований в криптографии явилась плодотворная идея криптографии с открытым ключом, создавшая новые перспективы и возможности в обмене информацией.
Наука и искусство криптографии имеют две стороны. Существует мир легальных коммуникаций, частью которого являются, к примеру, легальные пользователи банковских и биржевых сообщений. Этот мир можно рассматривать как открытый и залитый солнечным светом. Однако существует и темный мир врага :-), прибегающего ко всевозможным запрещенным приемам. И если люди легального мира хотят, чтобы враг как можно меньше понимал содержание их сообщений, то врагу напротив, нравится иметь дело с посланиями, которые легко расшифровать.
Криптография — это продолжение борьбы между двумя мирами. Необходимость разработки более сильных методов в легальном мире продиктована успехами врагов и означает в свою очередь новый вызов в их адрес. Таким образом, борьба продолжается.
Как представлены два этих мира? Что касается прошлого, то тут никаких трудностей нет. Сначала описывается метод легального мира и затем объясняется, как враг предпринял успешную атаку. Сегодня же ситуация в корне меняется. Всякий раз, когда описывается успешная вражеская атака, мы должны признать, что соответствующие методы легального мира все же не были надежными. Нельзя достигнуть успеха одновременно в обоих мирах.
Можно действовать следующим образом: сначала в деталях дать метод для легального мира, затем в общих чертах набросать некоторые возможные варианты вражеских атак, при этом одновременно пояснить, почему эти атаки скорее всего не будут иметь успеха. Это, конечно, не исключает возможного триумфа некоторых других, может быть очень изобретательных, вражеских атак. Так или иначе, далее в
тексте используется данный подход. Вероятность безопасности методов часто является очень высокой, хотя математически это не всегда можно доказать.
Следующее замечание применимо к обоим мирам. Хотя мы называем их "легальный" и "темный", это не всегда означает, что первые — "хорошие парни", а последние — из Мордора, где живет Саурон. В различных ситуациях роли могут меняться. Например, перехват сообщений может применяться нашей страной во время войны, тогда как посланиями обменивался наш враг. Конечно, справедливость на нашей стороне! Или другой пример: легальные пользователи банка могут быть преступниками, а полиция должна расследовать их действия. Терминология, введенная ниже, будет беспристрастной, т.е. никаких суждений относительно того, какая из противоборствующих сторон права, мы делать не будем.
Теперь мы готовы ввести фундаментальные понятия криптографии. Они будут использоваться на протяжении всего
цикла статей. Подчеркнем, что терминология отнюдь не однозначна и фиксирована для различных описаний секретного письма. При введении терминологии мы часто будем приводить и другие обозначения тех же понятий, используемых некоторыми другими авторами.
Наш всеобщий термин для секретного письма — это криптография. Он действителен для обоих миров. Некоторые используют термин криптология в этом универсальном смысле и резервируют термин криптография для деятельности легального мира.
Основная структура изображена на рис. 1.1. Сообщение посылается по незасекреченному каналу, где оно может быть перехвачено с помощью подслушивания.
Картина будет той же самой, говорим ли мы, допустим, о конном курьере или электронной почте. Мы не можем обеспечить безопасность канала, и, следовательно, возможен перехват. Первоочередные цели врага — нарушить секретность связи и извлечь выгоду из тайной информации. Далеко идущие цели могут состоять в следующем. Во-первых, враг может захотеть изменить сообщение, запутав при этом получателя недостоверным текстом, а во-вторых, враг может обмануть получателя, назвав имя ложного отправителя.
Во всех этих случаях большим преимуществом легальных пользователей было бы то обстоятельство, если бы враг не понимал перехваченного им сообщения. Для этих целей может быть использован некоторый метод шифровки.
Сообщение в его оригинальной форме может быть представлено как исходный текст. Затем отправитель зашифровывает данный текст. Результатом этого будет криптотекст. Теперь криптотекст может быть послан через ненадежный канал. Наконец, получатель расшифровывает криптотекст, после чего он/она имеет исходное сообщение.
Таким образом, действия отправителя:
шифрование исходного текста и получение криптотекста. Действия получателя обратные:
расшифровкае криптотекста и получение исходного текста.
Мы можем получить также более короткие символьные выражения: E(pt)=ct и D(ct)=pt.
В литературе часто вместо терминов "исходный текст" и "крипто-текст" используется "открытый текст" и "шифртекст", или кратко "шифр". Глаголами в этом случае являются "зашифровать" и "расшифровать". До недавнего времени использовали слово "код" и соответствующие глаголы "кодировать" и "декодировать", но теперь перестали. Причина этого заключается в том, что слово "код" имеет много других значений: коды, исправляющие ошибки, автоматные коды и т.д. Слово "код" будет ниже использоваться в некоторых специальных случаях, однако не в общем смысле слова "криптотекст".
Теперь проанализируем шифрование и
расшифровку. Оба этих действия производятся в рамках криптосистемы. Криптосистема состоит из следующих компонентов:
1. Пространство исходных сообщений РТ, которое содержит все
возможные исходные тексты pt.
2. Ключевое пространство К. Каждому ключу k в К соответствует
алгоритм шифрования Е^ и расшифрования D^. Если к сообщению pt применить Ek, а к результату шифрования — Dk, то снова
получим pt.
3. Пространство криптотекстов СТ, т.е. набор всевозможных
криптотекстов ct. Элементами СТ являются результаты приме
нения к элементам pt методов шифрования Е^, где k пробегает
все пространство К.
Теперь дадим некоторые основные теоретико-языковые определения. Начнем с конечного непустого множества X, называемого алфавитом. Элементы алфавита X называются буквами. Конечные цепочки элементов из X называются словами. Одна и та же буква может встречаться в слове несколько раз. Слово, содержащее 0 букв, называется пустым словом А. Длина слова w — число букв в нем, где каждая буква считается столько раз, сколько раз она появляется. Множество всех слов над X обозначим через X*. Подмножества множества X* будем называть (формальными) языками над
X.
Например, если в качестве X выбран английский алфавит {А, В, С, ..., Z}, то ABBA, HORSE и KOKOOKOKOONKOKOKOKKO — слова над X (неважно, имеет ли слово какой-нибудь смысл или нет; действительно, третье слово имеет значение лишь на финском). Мы можем также добавить к X строчные буквы, все знаки препинания и пустой символ (пробел), необходимые в обычном тексте. Теперь собрание сочинений Шекспира представляет собой слово над этим расширенным алфавитом.
Вернемся к понятию криптосистемы, анализируя далее ее компоненты. Пространство исходных текстов РТ обычно состоит из всего множества X* для некоторого алфавита X или из всех осмысленных выражений естественного языка. Подчеркнем, что эти две возможности существенно отличаются друг от друга. Если пространством исходных сообщений является X*, то каждая буква в сообщении будет значащей, поэтому нет никакой свободы в процессе расшифрования. С другой стороны, каждый естественный язык имеет высокую избыточность в том смысле, что даже при наличии большого количества ошибок сообщение обычно понимается правильно. Это является огромным преимуществом для перехватчика: он может безошибочно понять сообщение, хотя анализ неверен в нескольких местах! Проиллюстрируем это на примере.
Вначале потребуем, чтобы пространство исходных сообщений состояло из английского языка. Рассмотрим сообщение WE-MEETTOMORROW (мы игнорируем пробелы между индивидуальными словами; это будет часто делаться и в дальнейшем). Зашифруем его как UBQBBNNFIVPNFOOB (в данный момент мы не говорим, как осуществляется зашифрование). Если анализ перехватчиком крипто-текста даст результат WIMIIDTUMAROV, он будет вполне доволен: результат может быть получен верно.
Потребуем теперь, чтобы пространством исходных текстов было все X*, где X — двоичный алфавит {0,1}. Потребуем также, чтобы отправитель и получатель сделали следующее предварительное соглашение, касающееся сообщений: они имеют длину 12 и дают информацию о флоте из 12 кораблей. Посылаемое утром сообщение указывает, какие корабли будут участвовать в действиях текущего дня. К примеру, согласно сообщению 010011000001, участвуют только второй, пятый, шестой и двенадцатый корабли. Сообщения посылаются в зашифрованном виде. Теперь анализ нашего перехватчика должен быть очень аккуратен. Даже если в одном бите будет неточность, может возникнуть серьезная ошибка.
Часто бывает, что исходный текст на английском сперва кодируется в двоичном алфавите, к примеру, заменой каждой буквы двоичным числом, указывающим позицию этой буквы в английском алфавите. Так как 24 < 26 < 32, то для этой цели подходят слова длины пять:
А = 00001, В = 00010, С = 00011, ..., N = 01110, ..., Z = 11010 .
Для трансляции сообщения без всякой цели маскировки мы будем использовать термины кодирование и декодирование. В кодировании мы нуждаемся, к примеру, при передаче текстового сообщения. Таким образом, сообщение вначале кодируется, а затем шифруется. Конечно,
с помощью кодирования избыточность естественного языка никак не меняется.
(Продолжение следует?)
ЗЫ: Нам очень интересно твое мнение
по поводу этой статьи и предстоящего цикла
в целом :). Пиши в коменнты - стоит ли
продолжать и в каком виде это делать,
например писать более понятно или короче?
